Программная обработка массивов кратко

Обновлено: 05.07.2024

Перечень вопросов, рассматриваемых в теме: массивы, описание массивов, заполнение массивов, типовые задачи обработки массивов.

Глоссарий по теме: массив, элемент массива, размерность массива, индекс элемента массива, сортировка.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

- И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова. Информатика и ИКТ. Профильный уровень: учебник для 11 класса. — М.: БИНОМ. Лаборатория знаний, 2012

- К. Ю. Поляков, Е. А. Еремин. Информатика. Углубленный уровень: учебник для 10 класса. В 2 ч. Ч. 2 — М.: БИНОМ. Лаборатория знаний, 2013

- Андреева Е. В. Программирование — это так просто, программирование — это так сложно. Современный учебник программирования. — М.: МЦНМО, 2015

Теоретический материал для самостоятельного изучения

Рассмотрим следующую задачу: ввести с клавиатуры 20 действительных чисел и вычислить их сумму, при этом каждое из чисел сохранить в памяти для последующей обработки.

Для решения этой достаточно простой задачи мы будем вынуждены ввести 20 имен переменных, что, естественно, очень неудобно. Но ведь чисел может быть гораздо больше, чем 20!

Основное предназначение современных компьютеров — обработка большого количества данных. Очень сложно каждой переменной при этом давать собственное имя и не запутаться. Выходом их этой ситуации является использование более сложных по своей конструкции типов данных — составных (или структурированных). Одним из таких типов являются массивы.

Массив — это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющим положение элемента в массиве.

Элемент массива — отдельная переменная, входящая в массив.

Индекс элемента массива — номер элемента в этом массиве.

Размерность массива — количество элементов, которое содержит массив.

Массивы бывают одномерными и многомерными. Мы будем рассматривать только одномерные массивы. Их условно можно представлять в виде таблицы, которая состоит из множества ячеек, расположенных в одну строку или в один столбец.

Описание массивов

В языке Паскаль массивы описываются в блоке описания переменных следующим образом:

var : array [ ] of

- — описание индексации (нумерации) элементов массива. В качестве типа индекса можно использовать любые порядковые типы;

- — тип величин, непосредственно составляющих массив.

Приведем несколько примеров описаний:

varday: array [1..365] of integer; — массив, состоящий из 365 целых чисел, которые пронумерованы от 1 до 365;
vartem: array [0..11] of real; — массив, состоящий из 12 вещественных, пронумерованных от 0 до 11;
var ocenka: array [–2..2] of char; — массив, состоящий из 5 символьных переменных с номерами от -2 до 2:
const n=10; var slovo: array [1..n] of string; — n строковых величин, пронумерованных от 1 до n;

Для того, чтобы обратиться к элементу массива, нужно записать имя массива и в квадратных скобках индекс нужного элемента, например, day[100].

Рассмотрим основные приемы работы с массивами.

Заполнение одномерного массива значениями

Задать элементам массива значения мы можем:

— вводя значения с клавиатуры;

— случайным образом из некоторого диапазона;

Но какой бы способ мы ни выбрали, нам обязательно нужно организовать цикл.

Для начала договоримся, что мы имеем дело с массивом из 10 натуральных чисел (хотя тип элементов в данном случае значения не имеет).

Вывод элементов массива на экран

Вывод элементов также нужно организовывать с помощью цикла. При этом можно объединять процессы формирования массива и вывода его элементов на экран в один цикл, и выводить элементы массива либо в столбик, либо в строчку.

Воспользуемся вторым и третьим способами, рассмотренными выше:

Теперь перейдем к задачам обработки массивов.

Вычисление суммы элементов массива

Алгоритм решения практически полностью совпадает с алгоритмом нахождения суммы некоторого количества чисел, который мы уже рассматривали на третьем уроке в этой теме.

Следующая группа задач очень часто встречается нам в реальной жизни. Это задача поиска в массиве. Например, поиск нужного слова в словаре, поиск времени отправления нужного поезда в расписании и т. д.

В программировании поиск — одна из наиболее часто встречающихся задач вычислительного характера.

В алгоритмах поиска существуют два возможных варианта окончания их работы: поиск может оказаться удачным — заданный элемент найден в массиве и определено его месторасположение, либо поиск может оказаться неудачным – необходимого элемента в данном объеме информации нет. Кроме того, искомый элемент может встретиться в массиве неоднократно.

Рассмотрим несколько типовых задач, которые уже знакомы вам из курса основной школы.

Поиск в массиве элемента, удовлетворяющего некоторому условию

Например, требуется найти в массиве элемент, значение которого равно значению переменной p, или сообщить, что такого элемента в массиве нет.

Мы построим алгоритм, идея которого следующая:

Можно заметить, что наш алгоритм решает еще одну часто встречающуюся задачу обработки массивов — подсчет количества элементов, удовлетворяющих некоторому условию.

Поиск максимального (минимального) элемента массива

Подумаем, какие операции нужно выполнить, если требуется найти максимальный элемент. Естественно, как и в предыдущей задаче, операцию сравнения. Но с чем нам сравнивать очередной элемент массива?

Введем дополнительную переменную max, которой присвоим значение, равное значению элемента массива a[1]. Теперь будем сравнивать все элементы, начиная со 2-го, с max, и если найдем больший элемент, то присвоим его значение переменной max. Конечное значение этой переменной и будет значением наибольшего элемента массива.

Поиск максимального (минимального) среди всех элементов массива, удовлетворяющих некоторому условию

Допустим, нужно найти наибольшее среди всех четных чисел, входящих в массив произвольных натуральных чисел.

Прием, которым мы воспользовались в задаче 5, здесь может привести к ошибке. Например, на первом месте в массиве будет стоять НЕЧЕТНОЕ число, которое окажется больше всех четных. Здесь переменной max лучше присвоить начальное значение, заведомо меньшее всех элементов массива. Например, если наш массив составлен из натуральных чисел, то присвоить max значение -2. Если после окончания программы значение max останется таким же, это будет означать, что в массиве нет четных чисел. Если же они будут, max изменит значение.

Сдвиг элементов массива

Сдвиг элементов массива необходимо выполнять при удалении или вставке элементов. Если происходит удаление, то элементы, расположенные после удаленного, сдвигаются на одну ячейку влево. Если же происходит добавление, то элементы, расположенные после места вставки, сдвигаются вправо. При этом нужно учитывать, что размерность массива уже указана при его описании и измениться не может.

Таким образом при удалении элемента из массива мы можем получить, например, такую ситуацию. Допустим, имеется массив:

Удалим из него элемент с индексом i=4, т. е. a[1]=a[1], a[2]=a[2], a[3]=a[3], a[4]=a[5], a[5]=a[6], a[6]=a[7]. А вот для последнего элемента a[7] новое значение взять неоткуда. Он сохранит свое значение. Получим:

Чтобы избежать такого дублирования последнего элемента обычно на его место ставят число 0.

Программа удаления элемента из массива на языке Паскаль может выглядеть следующим образом:

Сложнее обстоит дело со вставкой элемента внутрь массива. Как мы сказали, при вставке все элементы, расположенные справа от места вставки, сдвигаются вправо. Последнему же элементу сдвигаться некуда, и он пропадет. Чтобы этого не произошло, нужно увеличить размерность массива на 1. Но учесть это надо при описании массива. Второй важный момент заключается в том, что сдвиг значений мы будем производить справа налево до заявленной позиции вставки:

Реверс массива

Реверс массива — это перестановка его элементов в обратном порядке: первый элемент становится последним, а последний — первым.

Из примера видно, что местами меняются 1-й элемент с N-м, второй — с (N–1)-м и т. д. Замечаем, что сумма индексов элементов, участвующих в обмене, равна N+1, поэтому элемент с номером i должен меняться местами с (N+1–i)-м элементом.

Теперь разберемся с организацией цикла. Если мы организуем цикл по всем элементам, то получим:

Все вернулось в исходное состояние, потому что реверс выполнился дважды. Чтобы этого не произошло, нужно остановить процесс обмена на середине массива, т.е. на элементе с индексом (N div 2).

Сортировка массива

Сортировка — один из наиболее распространенных процессов обработки данных.

Под сортировкой массива понимают расстановку элементов массива в заданном порядке.

Порядок сортировки может быть любым, для чисел обычно рассматривают сортировку по возрастанию или убыванию значений.

Цель сортировки — ускорить последующий поиск элементов, т. к. нужный элемент легче искать в упорядоченном массиве.

Существует много различных алгоритмов сортировки. Мы рассмотрим некоторые из них на примере сортировки массива целых чисел в порядке неубывания (a[i] 2 , где n — число элементов в массиве.

Программирование алгоритмов формирования и обработки одномерных массивов — это программирование алгоритмов, предназначенных для обработки множества однотипных компонентов, которые обладают одним общим именем и располагаются в заданной области памяти компьютера.

Массивы: сущность, алгоритмы их обработки

Основным преимуществом сегодняшнего компьютерного оборудования считается высокий уровень производительности и существенный размер памяти. Для записи алгоритмов, использующих большие объёмы информации, в языках программирования, предназначенных для реализации таких алгоритмов, имеются табличные библиотеки. Работа многих алгоритмов была бы сильно усложнена, если бы применяемые в алгоритмах объекты не видоизменялись и не реорганизовывались. Необходимо отметить, организация информационных данных в формате таблиц, то есть массивов, считается основным методом представления данных одного типа, и она используется фактически во всех программах. Табличная методика лежит, также, в основе архитектурной организации нынешнего компьютерного оборудования, а его память, по существу, представляет собой громадный байтовый массив, имеющий адресацию, располагающуюся с последовательным возрастанием. Таким образом, без понимания принципов организации табличных массивов и основных алгоритмических правил их обработки, невозможно понять основы функционирования и уровень возможностей электронной вычислительной машины.

Массивы являются наиболее широко используемой методикой структурной организации данных, позволяющей выполнять их удобное размещение и обработку в компьютерах.

Под массивом понимается набор данных одного типа, имеющий единое имя. В массиве хранятся некоторые значения, которые называются компонентами массива. Все компоненты массива обязательно имеют одинаковый тип. Каждый компонент массива обладает своим индексом, определяющим его местоположение в общей структуре массива. Под размерностью массива понимается количество измерений массива, то есть число индексов одного элемента.

Одномерные массивы

Под одномерным массивом понимается набор однотипных элементов, к которым можно обратиться только по одному индексу. Все элементы массива сохраняются в памяти в определённой последовательности, задаваемой индексной нумерацией. Причём первый элемент имеет нулевой индекс, а следующие элементы получают индексы с номерами один, два и так далее. То есть, фактически, индекс является порядковым номером элемента в массиве. Прежде чем применять массив в программном приложении, его, аналогично переменным, требуется вначале объявить. Объявить массив можно следующим образом:

Готовые работы на аналогичную тему

Рассмотрим примеры объявления одномерных массивов различных типов:

Следует заметить, что не рекомендуется использовать безымянные константы для объявления массива. Массивы одного типа могут быть объявлены при посредстве списка через запятую. В список могут быть включены и переменные одного типа. К примеру, так:

Необходимо также помнить, что при объявлении массива отсчёт индексации ведётся от нуля. Таким образом, первый элемент массива имеет индекс равный нулю. Это означает, что величина допустимого диапазона значений индексов располагается, начиная от нуля и до значения размерности массива минус единица. То есть, если объявлен массив:

Инициализация одномерного массива

Инициализация одномерного массива состоит в присвоении начальных значений его элементам, заявленным при его объявлении. Данная операция осуществляется указанием внутри фигурных скобок начальных значений:

При выполнении инициализации массива с заданием меньшего, чес объём массива, числа начальных величин, остальным элементам выполняется присваивание нулевых значений. К примеру, при объявлении:

осуществляется формирование массива, включающего в свой состав одиннадцать целочисленных элементов. Но, вместе с тем, четырём первым компонентам будут присвоены величины, стоящие в скобках, а остальные элементы будут приравнены к нулю. Данную особенность можно использовать, когда инициализируется массив со всеми нулевыми элементами:

Когда инициализируется массив, количество элементов массива не является обязательным параметром. Возможна запись такого типа:

Размер массива в этом варианте определяется количеством значений в списке элементов, подлежащих инициализации.

Алгоритм вычисления суммы

Приведём пример формирования алгоритма, который позволяет определить суммарное значение всех элементов некоего одномерного информационного массива. Пусть задан массив А, состоящий из набора n элементов $a_1, a_2, a_3, …, a_n$. Необходимо определить суммарное величину этих элементов, а именно:

$S = a_1 + a_2 + a_3 + … + an$.

Вычисление суммы может быть представлено в виде поочерёдного определения набора сумм, согласно формулам:

$S = 0 S = S + a_2 … S = S + a_i S = S + a_n$

$S = S + a_1 S = S + a_3 …$

Чтобы сформировать алгоритм нахождения суммы, можно применить циклические вычисления, где одним из параметров цикла является величина переменной i, меняющаяся от одного до n с шагом, равным единице. Блок-схема алгоритма приведена на рисунке один.

Рисунок 1. Блок-схема алгоритма. Автор24 — интернет-биржа студенческих работ

Массив — структура, стоявшая у истоков программирования. Но, несмотря на то, что массивам уделяется внимание в каждом курсе уроков по любому языку программирования, от новичков все равно ускользает много важной информации, связанной с логикой взаимодействия с этой структурой.

Цель этого поста — собрать некоторую информацию о массивах, которой когда-то не хватало мне. Пост для новичков.

Что такое массив?

Массив - это структура однотипных данных, расположенная в памяти одним неразрывным блоком.

Расположение одномерного массива в памяти

Многомерные массивы хранятся точно также.

Расположение двухмерного массива в памяти

Знание этого позволяет нам по-другому обращаться к элементам массива. Например, у нас есть двухмерный массив из 9 элементов 3х3. Так что есть, как минимум два способа вывести его правильно:

1-й вариант (Самый простой):

2-й вариант (Посложнее):

Формула для обращения к элементу 2-размерного массива, где width - ширина массива, col - нужный нам столбец, а row - нужная нам строчка:

Зная второй вариант, необязательно пользоваться им постоянно, но все же знать стоит. Например, он может быть полезен, когда нужно избавиться ~~от лишних звездочек~~ от указателей на указатели на указатели.

А вот так можно работать с трехмерным массивом

Этим способом можно обходить трехмерные объекты, например.

Формула доступа к элементам в трехмерном массиве, где height - высота массива, width - ширина массива, depth - глубина элемента(наше новое пространство), col - столбец элемента, а row - строка элемента:

Для получения доступа к элементам массива большей размерности по аналогии в формулу добавляем новые пространства.

Алгоритмы обработки массивов

Я не буду здесь писать про алгоритмы сортировки и алгоритмы поиска, так как найти код для почти любого из этих алгоритмов не составит труда.

Изображения - это целый комплекс из разных заголовков и информации о изображении, и самого изображения хранящемся в виде двухмерного массива.

Обработка изображений хорошо научит работать с двумерными массивами. Вот некоторые алгоритмы, которые пригодились мне для обработки изображений:

1) Зеркальное отражение.

Для того чтобы перевернуть изображение по горизонтали нужно всего лишь читать массив, в котором оно содержится сверху вниз и справа налево.

По такому же принципу выполняется переворот изображения по вертикали.

2) Поворот изображения на 90 градусов.

Для поворота изображения нужно повернуть сам двухмерный массив, а чтобы повернуть массив нужно транспонировать двухмерный массив, а затем зеркально отразить по горизонтали.

Пошаговое выполнение алгоритма

Такой алгоритм появился, когда я нарисовал график координат c точками.

График, приведший к решению

Хочу обратить ваше внимание, что здесь я применяю другой способ переворота изображения. Вместо выделения памяти под новый массив, здесь просто меняем местами первые и последние элементы.

Примечание: создать массив размерностью высоты и ширины реального изображения на стеке не выйдет. Только на куче с помощью оператора new.

Заключение

Этот небольшой пост не претендует на невероятные открытия мира информатики, но надеюсь успешно поможет немного вникнуть в устройство массивов падаванам мира IT.

Как я сказал в начале, здесь я собрал частичку того, чего не хватало мне при изучении программирования. Как бы эти вещи не казались бесполезными, все студенты университетов, изучающие информационные технологии проходят через это, и не напрасно — это помогает развивать логику и решать более сложные задачи, которые ждут далее. Приведенные выше примеры показывают некоторые важные способы взаимодействия с массивами.

Я надеюсь этот пост будет полезен, и если это будет так, то я напишу продолжение этой темы.

Аннотация: Используя типовые алгоритмы можно решить любую задачу. В лекции очерчен круг НЕОБХОДИМЫХ ТИПОВЫХ АЛГОРИТМОВ (для обработки одномерных массивов и обработки строк), рассмотрены некоторые олимпиадные задачи, которые решаются с использованием этих алгоритмов. Цель лекции: научиться применять изученные типовые алгоритмы при решении классических задач.

Типовые алгоритмы обработки одномерных массивов

В данной теме будут рассматриваться такие типовые алгоритмы обработки одномерных массивов:

Заполнение, вывод элементов массива
Сумма, произведение элементов
Выбор по условию
Максимальный (минимальный) элемент
Вставка, удаление элементов
Инвертирование (изменения порядка следования элементов заданного массива на обратный)

Программные реализации типовых алгоритмов обработки одномерных массивов приведены в таблице 2.1:

Ключевые моменты в типовых алгоритмах:

Выбор по условию. В качестве условия может проверяться значение элемента массива на четность, кратность элемента какому-либо числу, положительность, отрицательность, равенство нулю. Может проверяться также и значение индекса элемента массива (например, элементы, стоящие на четных местах и др.).

Максимальный (минимальный) элемент. Кроме максимального элемента часто требуется найти и индекс максимального элемента:

Задачи использованием типовых алгоритмов обработки одномерных массивов

Задача: На плоскости изображено N прямоугольников (рис. 2.1). Каждый прямоугольник задан координатами левой нижней и правой верхней вершин. Определить, имеют ли прямоугольники общую площадь .

Идея решения:

максимальная координата по оси Х левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин и …
…максимальная координата по оси У левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин, то …
…общая площадь есть.

В задаче необходимо использовать типовой алгоритм нахождения МАКСИМАЛЬНОГО (МИНИМАЛЬНОГО) ЭЛЕМЕНТА МАССИВА.

Для вычисления общей площади необходимо найти произведение разности:

максимальной координаты по оси Х левых нижних вершин прямоугольников и минимальной координаты правых верхних вершин и …
…максимальной координаты по оси У левых нижних вершин прямоугольников и минимальной координаты правых верхних вершин.

Программа на Бейсике:

Программа на Паскале:

Задача: Латинским квадратом называется массив, в строках и столбцах которого нет одинаковых элементов. Вывести на экран латинский квадрат размером NxN .

Идея решения: Заполнить 1 строку квадратного массива ( NxN ) числами от 1 до N . Вторая строка массива получается путем циклического сдвига элементов первой строки и т. д. (табл. 2.2). Циклический сдвиг можно реализовать, используя типовой алгоритм ВСТАВКИ-УДАЛЕНИЯ (в зависимости от направления циклического сдвига).

Читайте также: