Тема 9. Программирование на языке Паскаль. Массивы
1 Тема 9. Программирование на языке Паскаль. Массивы Массивы Массивы относятся к так называемым структурированным типам данных. Константы и переменные структурированных типов позволяют хранить не одно, а несколько значений, представленных в некоторой структуре. Массивом называется упорядоченная совокупность элементов одного типа данных. Различают одномерные массивы и массивы большей размерности (двумерные, трехмерные и так далее). Одномерные массивы Одномерный массив подобен вектору-строке, в которой содержатся значения одного определенного типа. Для упорядочения элементов массива каждый из них имеет индекс (упрощенно, порядковый номер). В качестве индексов могут быть использованы данные любого типа, имеющего внутренний порядок. На практике в качестве индексного чаще всего используется тип-диапазон, состоящий из целых чисел. Тип-диапазон записывается следующим образом: [<нижний индекс>.. <верхний индекс>] Например, запись [1..10] означает, что индексы элементов массива изменяются от 1 до 10. Нижний индекс не обязательно должен быть равен 1, но практически это наиболее удобно (в этом случае верхний индекс совпадает с размером массива). Одномерный массив представляется в программе собственным идентификатором и должен быть описан как массив-переменная или массив-константа. Для описания одномерного массива-переменной используется следующая запись: <имя массива>: array [<нижний индекс>..<верхний индекс>] of <тип элементов>; Например, для описания одномерного массива-переменной с именем m, состоящего из 10 целых чисел, необходимо сделать следующую запись: m: array [1..10] of integer; Описание одномерного массива-константы производится аналогично, но с добавлением значений всех элементов: <имя массива>: array [<нижний индекс>..<верхний индекс>] of <тип элементов> = (<значение первого элемента>. <значение последнего элемента>); m: array [1..5] of byte = (33, 44, 11, 55, 22); Для доступа к элементам одномерного массива в программе используется следующая запись: <имя массива>[<индекс элемента>] M[5]:=15; a:=m[1]+14; Рассмотрим несколько задач обработки одномерных массивов. Общим условием для всех задач будет следующее: дан одномерный массив целых чисел m (3, 0, -5, 11, 7, 3, -7, 9). Задача 1. Найти сумму всех элементов массива.
2 Общим подходом к решение задач обработки одномерных массивов является последовательный перебор всех элементов с выполнением требуемых действий. Для перебора элементов достаточно последовательно изменять индекс элементов в цикле. В силу того, что границы изменения индексов заранее известны, наиболее подходящим циклом является цикл с параметром. Для создания простых учебных программ, в которых реализуются алгоритмы обработки массивов, можно задавать массив как массив-константу, что дает возможность не вводить элементы массива при каждом запуске программы. Для поиска суммы всех элементов необходимо перебрать все элементы массива и добавить значение каждого из них в какую-либо переменную. Для организации цикла используем переменную i. Блок-схема алгоритма будет выглядеть так (рис. 1). Ввод массива m s=0 i=1..8 s=s+m[i] Вывод s Текст программы будет таким. program p1; M: array [1..8] of integer= (3, 0, -5, 11, 7, 3, -7, 9); s,i: integer; for i:=1 to 8 do s:=s+m[i]; writeln('s=',s); Рис. 1 Задача 2. Найти среднее значение положительных элементов массива. Для решения поставленной задачи необходимо перебрать все элементы массива, найти сумму и количество положительных элементов, затем разделить сумму на количество. Для каждого элемента в цикле проверяется условие положительности. При истинности условия значение элемента добавляется в переменную суммы, кроме того увеличивается на единицу значение специальной переменной-счетчика. Блок-схема алгоритма представлена на рис. 2.
3 Ввод массива m s=0, k=0 i=1..8 m[i]>0 нет да s=s+m[i] k=k+1 a=s/k Вывод a Рис. 2 Текст программы для решения этой задачи будет выглядеть так. program p2; M: array [1..8] of integer= (3, 0, -5, 11, 7, 3, -7, 9); s,k,i: integer; a: real; for i:=1 to 8 do if (m[i]>0) then begin s:=s+m[i]; k:=k+1; end; a:=s/k; writeln('a=',a); Задача 3. Найти значение минимального элемента массива Алгоритм поиска минимального элемента массива сводится к следующему: перед началом перебора считаем минимальным значение первого элемента и присваиваем это значение специальной переменной; начинаем перебор со второго элемента; если значение очередного элемента меньше текущего минимума, производим переприсваивание значения переменнойминимума. Текст программы будет таким:
4 program p3; M: array [1..8] of integer= (3, 0, -5, 11, 7, 3, -7, 9); min,i: integer; min:=m[1]; for i:=2 to 8 do if (M[i]<min) then min:=m[i]; writeln('min=',min); Для поиска максимального элемента достаточно изменить знак в условии (а также имя переменной, в которой ищется максимум, хотя это и не обязательно). Двумерные массивы Двумерный массив подобен матрице, то есть состоит из столбцов и строк. Для обращения к элементам таких массивов используется два индекса индекс строки и индекс столбца. Соответственно при описании двумерных массивов указывается два диапазона изменения индексов. Описание двумерного массива-переменной будет выглядеть следующим образом: <имя массива>: array [<нижний индекс строк>..<верхний индекс строк>,<нижний индекс столбцов>..<верхний индекс столбцов>] of <тип элементов>; M: array [1..5,1..4] of real; Описание двумерного массива-константы выглядит так: <имя массива>: array [<нижний индекс строк>..<верхний индекс строк>,<нижний индекс столбцов>..<верхний индекс столбцов>] of <тип элементов>=((элементы первой строки). (элементы последней строки)); M: array [1..2, 1..3] of integer = ((4, -3, 6), (0, -5, 3)); Для обращения к элементу двумерного массива используется следующая запись: <имя массива>[<индекс строки>,<индекс столбца>] M[1,3] Рассмотрим задачи обработки двумерных массивов, которые будут иметь следующее начальное условие: дан двумерный массив целых чисел M: ((-1, 5, 8, -11), (1, 7, -15, 0), (3, -3, -4, 16)). Задача 1. Найти сумму элементов второй строки.
5 В данном случае необходимо перебрать все элементы второй строки, которую можно считать одномерным массивом. Введем для обозначения индексов переменные i (для строк) и j (для столбцов). Сумму будем искать в переменной s. Блок-схема алгоритма решения этой задачи представлена на рис. 3. Ввод массива m s=0, i=2 j=1..4 s=s+m[i,j] Вывод s Рис. 3 Текст программы будет выглядеть так: program p4; M: array [1..3,1..4] of integer = ((-1, 5, 8, -11), (1, 7, -15, 0), (3, -3, -4, 16)); s,i,j: integer; i:=2; for j:=1 to 4 do s:=s+m[i,j]; writeln('s=',s); Задача 2. Найти сумму всех элементов массива. В отличие от предыдущей задачи здесь необходимо организовать не перебор всех элементов выделенной строки, а перебор всех элементов массива. Это достигается добавлением еще одного (внешнего) цикла, в котором изменяется индекс строк (переменная i). Получаемая в этом случае конструкция называется вложенными циклами. Блок-схема алгоритма показана на рис. 4.
6 Ввод массива m s=0 i=1..3 j=1..4 s=s+m[i,j] Вывод s Рис. 4 Текст программы для решения задачи будет таким. program p5; M: array [1..3,1..4] of integer = ((-1, 5, 8, -11), (1, 7, -15, 0), (3, -3, -4, 16)); s,i,j: integer; for i:=1 to 3 do for j:=1 to 4 do s:=s+m[i,j]; writeln('s=',s); Конструкция из вложенных циклов, в которых изменяются индексы строк и столбцов, позволяет перебрать все элементы двумерного массива (или выделенный фрагмент массива) и применяется во всех задачах обработки двумерных массивов.