Операции с массивами: анализ программ - Программирование

Конспект

Массив

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

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

Одномерный массив представляет собой пронумерованную последовательность переменных одного и того же типа, имеющих общее имя. Обращение к конкретной переменной (элементумассива) производится по имени массива и порядковому номеру (индексу) нужного элемента в нём.

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

Аналогично, трёхмерный массив может быть рассмотрен как куб данных, состоящий из элементарных кубиков (элементов массива), каждый из которых имеет три индекса (т.е. трёхмерный массив рассматривается как одномерный массив “слоёв” — матриц).

По тому же принципу могут быть определены массивы большей размерности.

Массивы в языке Паскаль

Объявление п-мерного массива:

где <диапазон индекса> — записанные через две точки начальное и конечное значения индексов элементов по соответствующей размерности (целые числа или символы); <базовый тип> — тип элементов массива.

Примеры:

1) объявление одномерного массива из 10 целых чисел (базовый тип — integer), индексы которых меняются от 0 до 9:

2) объявление одномерного массива из 15 символов (базовый тип — char), индексы которых меняются от -7 до 7:

3) объявление одномерного массива из вещественных чисел (базовый тип — real), в качестве индексов которых используются латинские буквы:

4) объявление двумерного массива размером 10 х 15 из целых чисел (базовый тип — integer), индексы которых отсчитываются с единицы:

или

Обращение к элементу:

1) одномерного массива: Mas [i]

2) двумерного массива: Mas [i, j]

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

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

Здесь вначале описан “шаблон” одномерного массива из 10 целочисленных элементов, а затем по нему, как по образцу, определены два таких массива с именами M1 и М2. В результате с точки зрения программы оба эти массива полностью идентичны и для них допустима операция присваивания одного массива другому целиком: M1 : = М2 (все элементы массива М2 копируются в соответствующие им элементы M1).

Заполнение массива

Производится в цикле (для многомерного массива — во вложенных циклах) поэлементно путём ввода каждого элемента с клавиатуры (оператором read) либо присваивания каждому элементу некоторого значения — константы (например, при обнулении массива) или вычисленного значения выражения.

Другой возможный вариант — указание значений элементов массива при его объявлении.

Примеры:

1) обнуление одномерного массива:

2) присваивание начальных значений элементам двумерного массива:

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

Производится в цикле (для многомерного массива — во вложенных циклах) поэлементно путём вывода каждого элемента с клавиатуры (оператором write).

Для одномерного массива обычно используется оператор write, в котором, кроме обращения к i-му элементу массива, предусмотрен разделяющий пробел (пример: write (Mas [i] .' ') ;), тогда элементы массива выводятся в строку.

Возможен альтернативный вариант, когда используется оператор writeln, в котором указывается значение индекса и значение элемента с этим индексом (пример: writeln (i, ' -й элемент равен ', Mas[i]);), тогда каждый элемент выводится в отдельной строке.

Для двумерного массива вывод строк обычно производится в одну строку (оператор write), а по завершении вывода очередной строки отдельно добавляется пустой оператор writeln для перехода на следующую строку.

Обмен местами элементов массива

Производится аналогично обмену значений двух обычных переменных (обычно при помощи дополнительной “буферной” переменной).

Обработка элементов массива (определение максимума/минимума, вычисление суммы, произведения, среднего и пр.)

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

• При поиске максимума/минимума за предполагаемый максимум/минимум берётся первый элемент массива либо константа, заведомо меньшая/большая любого элемента. Далее каждый очередной элемент массива сравнивается с предполагаемым максимумом/минимумом, и если этот элемент больше/меньше предполагаемого максимума/минимума, то значение этого элемента запоминается в качестве нового предполагаемого максимума/минимума. Дополнительно при этом в отдельной переменной (переменных) может перезапоминаться индекс (индексы) очередного предполагаемого максимума/минимума.

• При вычислении суммы/произведения вначале переменной, выделенной для накопления суммы/произведения, присваивается инициализационное значение (нуль — для суммы, единица — для произведения). Затем в цикле (либо вложенных циклах) выполняется перебор элементов массива и текущее значение суммы/произведения складывается/умножается на текущий элемент массива.

• При вычислении среднего значения выполняется суммирование элементов массива, а затем полученная сумма делится на количество элементов в массиве.

• При определении максимума/минимума, суммы, произведения, среднего значения элементов, удовлетворяющих заданному условию (например, только положительных) дополнительно добавляется условный оператор с соответствующим условием, и требуемое действие (проверка и переприсваивание предполагаемого максимума/минимума, сложение, умножение) выполняется только при истинности этого условия. При вычислении среднего значения также предусматривается отдельная переменная-счётчик, которая увеличивается на 1 каждый раз, когда к сумме добавляется очередной удовлетворяющий условию элемент массива, и после вычисления суммы она делится на значение этого счётчика (количество вошедших в сумму элементов).

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

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

Существует несколько методов сортировки массивов, различающихся сложностью их алгоритма и скоростью работы: сортировка перемешиванием, сортировка выбором, сортировка вставками, быстрая сортировка, пирамидальная, “гномья”, слиянием, деревом, сортировка Шелла, но наиболее понятной и наглядной является пузырьковая сортировка (она же — сортировка простыми обменами).

Метод пузырьковой сортировки можно рассмотреть на примере числового массива из 5 элементов: (5, 3, 8, 1, 4), — который надо отсортировать по возрастанию. Для наглядности элементы располагаются по вертикали, друг над другом, и обводятся кружками разного размера.

Если бы в условии было всего два элемента (например, числа 5 и 3, с которых начинается наш массив), то достаточно было бы сравнить их друг с другом и, если первое из этих чисел больше второго, то поменять их местами.

То же самое можно сделать и для нашего массива — поочерёдно выбрать пары элементов (начиная с первого), сравнить их и поменять местами, если первый из взятой пары элементов окажется больше второго (так как требуется сортировка по возрастанию). Поскольку необходимо разработать алгоритм для исполнения компьютером, используется конструкция “цикл” (конечное значение цикловой переменной i определяется в ходе разбора алгоритма).

№ цикла	№ шага	№№ выбранных элементов ( i и i+1 )	До обмена элементов	После обмена элементов
1	1	1 и 2
1	2	2 и 3
1	3	3 и 4
1	4	4 и 5

Следует помнить, что в цикле значение цикловой переменной i должно меняться от 1 до 4, или, для массива произвольной длины n, — от 1 до (n-1).

Кроме того, хотя массив ещё не отсортирован, самое больше число 8 уже “опустилось” в самый низ на соответствующую ему правильную позицию.

Остаётся повторить цикл ещё раз!

Зная, что последнее число уже стоит на своём месте и его можно исключить из сравнений, меняется значение цикловой переменной от 1 до 3 (т.е. для произвольного массива — от 1 до (n-2)).

№ цикла	№ шага	№№ выбранных элементов (i и i+1)	До обмена элементов	После обмена элементов
2	1	1 и 2
2	2	2 и 3
2	3	3 и 4

Теперь и предпоследняя позиция в массиве тоже занята “правильным” элементом.

Для окончания сортировки в данном случае достаточно поменять местами два первых элемента. Помня, что компьютер является формальным исполнителем, и массив может быть каким угодно, тогда как алгоритм должен обладать свойством универсальности (быть пригодным для сортировки любого массива), требуется выполнить ещё два цикла, в первом из которых переменная iменяется от 1 до 2, а во втором — равна числу 1, даже если один из шагов этого цикла окажется “лишним”.

№ цикла	№ шага	№№ выбранных элементов (i и 1+1 )	До обмена элементов	После обмена элементов
3	1	1 и 2
3	2	2 и 3
4	1	1 и 2

В ходе сортировки меньшие числа, подобно воздушным пузырькам в воде, постепенно “всплывают” наверх, а большие, словно камешки, опускаются вниз (“тонут”). Именно поэтому данный метод сортировки и получил своё название.

Обобщив только что разобранные действия на случай произвольного массива из га элементов получается, что:

1) потребуется (n-1) раз выполнять циклы просмотра элементов массива;

2) в каждом из этих циклов конечное значение цикловой переменной должно становиться меньше на 1, а в самом первом из этих циклов оно должно быть равно (n-1);

3) на каждом шаге выполняется сравнение пары элементов и (для сортировки по возрастанию) если первый из них больше второго, то они меняются местами.

Очевидно, что реализовать все это можно при помощи конструкции из двух вложенных циклов:

Соответствующая программа (например, на Паскале) имеет вид:

Разбор типовых задач

Задача 1. В программе используется одномерный целочисленный массив А с индексами от 0 до 9. Ниже представлен фрагмент программы, записанный на разных языках программирования, в котором значения элементов сначала задаются, а затем меняются.

Бейсик	Паскаль
Си	Алгоритмический язык

Чему будут равны элементы этого массива после выполнения фрагмента программы?

1) 9876543210

2) 0123456789

3) 9876556789

4) 0123443210

Решение

1. Модель массива А:

2. Массив при заполнении обрабатывается весь (диапазон изменения цикловой переменной совпадает с размером массива), а при изменении обрабатывается только часть массива (для i от 0 до 4).

3. Заполнение массива: каждому элементу присваивается значение, равное разности константы 9 и индекса этого элемента:

4. Изменение массива выполняется стоящей в теле второго цикла парой операторов:

Эта алгоритмическая конструкция — обмен местами двух элементов (i-гo и (9-i)-гo) через буферную переменную k.

Эта операция выполняется последовательно для всех значений i:

• i = 0:

• i = 1:

• i = 2:

• i = 3:

• i = 4:

To есть элементы массива меняются местами первый — с последним, второй — с предпоследним и т.д. В результате получается массив 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Ответ: массив 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (вариант ответа № 2).

При определении обрабатываемой части массива следует быть внимательными! Если бы данный массив был обработан целиком, то, начиная со значения i = 5, происходил бы обратный обмен значений элементов. В результате вновь получился бы исходный массив.

Задача 2. В программе используется одномерный целочисленный массив А с индексами от 0 до 10. Ниже представлен фрагмент программы, записанный на разных языках программирования, в котором значения элементов сначала задаются, а затем меняются.

Бейсик	Паскаль
Си	Алгоритмический язык

Чему будут равны элементы этого массива после выполнения фрагмента программы?

Решение

1. Модель массива А:

2. Массив обрабатывается весь (диапазон изменения цикловой переменной совпадает с размером массива).

3. Заполнение массива: каждому элементу присваивается значение, равное его индексу:

4. Изменение массива выполняется стоящей в теле второго цикла парой операторов:

Эта алгоритмическая конструкция похожа на обмен местами двух элементов (i-го и (10-i)-го), но не является обменом, поскольку здесь не используется буферная переменная! Сначала в (10-i)-й элемент заносится значение i-то элемента (а прежнее значение теряется), а затем выполняется обратное присваивание, которое, очевидно, уже ничего не меняет.

Эта операция выполняется последовательно для всех значений i:

• i = 0:

• i = 1:

• i = 2:

• i = 3:

• i = 4:

• i = 5:

(При обмене элемента самого с собой никаких изменений не происходит.)

• i = 6:

При дальнейших операциях массив не изменяется.

• i = 7:

• i = 8:

• i = 9:

• i = 10:

Таким образом, в результате получается массив из элементов: 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0.

Ответ: массив 0, 1, 2, 3, 4, 5, 4, 3, 2, 1, 0 (вариант ответа №4).

Задача 3. Имеется одномерный целочисленный массив М с индексами от 0 до 9. Значения его элементов изначально равны 16, 17, 13, 18, 15, 11, 12, 10, 19, 14 (М[0] = 16, М[1] = 17 и т.д.).

Требуется определить значение переменной х после выполнения фрагмента программы:

Решение

1. Анализируем алгоритм.

В цикле выполняется перебор элементов массива с 1-го по 9-й, при этом нулевой элемент циклом не затрагивается.

На каждом шаге цикла, если очередной (i-й) элемент меньше нулевого, то эти элементы меняются местами.

Переменная х — это счётчик, который подсчитывает количество таких обменов.

2. Выполняем “прогонку” программы:

Ответ: 3.

Задача 4. В программе описан одномерный целочисленный массив. Ниже представлен фрагмент программы, обрабатывающей этот массив:

До выполнения этого фрагмента в массиве находились четырёхзначные нечётные натуральные числа. Какое наименьшее значение может иметь переменная s после выполнения данной программы?

Решение

1) Расписываем вычисление суммы в виде одной строки, помня, что значение i меняется в цикле от 0 до 6 (т.е. до 10 - 4):

2) Теперь сокращаем одинаковые переменные (элементы массива), записанные со знаками “плюс” и “минус”:

Получаем: s = А[0] + А[1] + А[2] - А[7] - А[8] - А[9].

3) Получаемая сумма (разность) должна, по условию, иметь наименьшее значение. А сами элементы массива — это четырёхзначные нечётные натуральные числа, т.е. числа в диапазоне от 1001 до 9999. Следовательно, те элементы массива, которые записаны в выражении со знаком “плюс”, должны быть наименьшими из возможных, а элементы массива со знаком “минус” должны быть наибольшими из возможных. Значит, нужно выбрать их следующими: А[0] = А[1] = А[2] = 1001, а А[7] = А[8] = А[9] = 9999.

4) Вычисляем значение s при этих значениях элементов массива:

Ответ: -26994.