Обработка массивов. Общий вид описания массива

1 Модуль 8 Лекция 8 1 Обработка массивов Традиционно к структурированным типам данных в языке Pascal относят массивы, множества и записи. Иногда структурированным считают строковый тип. На самом деле строки занимают промежуточное положение между простыми и структурированными типами, но т.к. большинство их Массив представляет собой упорядоченное множество однотипных элементов. В системе Турбо Паскаль массив описывается переменной сложной структуры. При описании массива необходимо указать:  способ объединения элементов в структуру (одномерный, двухмерный и т.д. массивы);  число элементов;  тип элементов. Общий вид описания массива <имя>: array [тип-диапазон индексов] of <тип элементов>; Доступ к каждому элементу массива осуществляется с помощью индексов. Тип-диапазон каждого индекса задается левой и правой границами изменения индекса. В записи на языке Турбо Паскаль между границами диапазона ставится символ  (две точки). Число индексов определяет структуру массива: если используется один индекс, то такой массив называется одномерным, если два индекса – двухмерным, и т.д. В общем случае размерность массива может быть произвольной. 1.1. Одномерные массивы В математике одномерному массиву соответствует n-мерный вектор, например: x  {xi }; i  1, n , где xi – компонента (координата) вектора; i – номер компоненты; n – число компонент. Описание одномерного массива На языке Турбо Паскаль описание одномерного массива задается следующим образом: <имя>: array [m1..m2] of <тип элементов>; m1..m2 – диапазон значений индекса. 2 свойств реализуются как свойства сложных данных, то строки рассматриваются как структурированный тип. Индекс одномерного массива определяет порядковый номер элемента в массиве. Тип элементов в массиве может быть любым: простым (real, integer, char), структурным (array), строковым (string). По описанию массива в памяти компьютера выделяется область последовательных ячеек, в которую при выполнении программы заносятся значения элементов массива. Например, по описанию Var X: array [1..5] of real; в памяти будет выделяться область из пяти последовательных ячеек для записи значений элементов вещественного типа. Индексные переменные Выбор отдельного элемента из массива осуществляется с помощью индексной переменной, которая задается следующим образом: x[i] – индексная переменная (элемент массива). Здесь x – имя массива; i – индекс (номер элемента массива). В качестве индекса используются:  целые константы, например x[2]x2;  целые переменные, например x[k]xk;  индексные выражения, например x[2n+1]x2n+1. Замечание. Индексными выражениями являются арифметические выражения целого типа. Индексная переменная, как и простая, может стоять в левой части оператора присваивания, например: x[3]:=2.5; Ввод-вывод одномерных массивов Ввод-вывод массивов осуществляется поэлементно с помощью оператора цикла for…to, в котором в качестве параметра используется индекс. Пример 1. Организовать ввод с клавиатуры массива: A = (1.2, 5, –6.8, 14). В разделе Var необходимо задать описание массива и индекса. 3 Var A: array [1..4] of real; i: integer; В операторной части программы ввод массива рекомендуется организовать в виде диалога, поместив перед вводом оператор вывода (writeln), в котором дается поясняющее сообщение, например: Begin {начало программы} writeln(‘Введите массив А’); for i := 1 to 4 read(a[i]); В момент работы оператора read на клавиатуре через один или несколько пробелов набираются элементы массива (ввод в строке экрана) и нажимается клавиша [Enter]: 1.2 5 –6.8 14 [Enter] Замечание. Элементы массива можно вводить в «столбик», если после ввода каждого элемента нажимать клавишу [Enter]. Пример 2. Организовать вывод массива А на экран таким образом, чтобы все элементы располагались на одной строке экрана. В программе надо записать следующие операторы: for i := 1 to 4 do write(a[i]:5:1); writeln; Вид выводимого массива на экране: 1.2 5.0 –6.8 14.0 Оператор writeln без списка служит для перевода курсора к началу следующей строки. Обработка одномерных массивов При решении задач обработки массивов используют базовые алгоритмы реализации циклических вычислительных процессов: организация счетчика, накопление сумм и произведений, поиск минимального и максимального элементов массива. Задача 1. Организация счетчика Дан целочисленный массив: B  {bi }; i  1, 20 . Определить количество элементов массива, которые делятся на 3 без остатка. Program OM_1; Var B: array [1..20] of integer; 4 i, L: integer; Begin writeln(‘Введите массив В’); for i :=1 to 20 do read(b[i]); L := 0; for i :=1 to 20 do if (b[i] MOD 3) = 0 then L := L+1; writeln(‘L =’, L); End. Задача 2. Накопление суммы и произведения Дано целое число n и массив вещественных чисел: X  {xi }; i  1, n . Вычислить среднее арифметическое и среднее геометрическое чисел массива, используя формулы: 1 S n n n xi ;  i 1 Pn xi  i 1 . Program ОМ_2; Var Х: array [1..100] of real; n, i: integer; S, P: real; Begin writeln(‘Введите размер массива n’); read(n); writeln(‘Введите массив Х’); for i := 1 to n do read(x[i]); S := 0; P := 1; for i := 1 to n do begin S := S + x[i]; 5 P := Px[i]; end; S := S/n; P := exp(1/nln(P)); writeln(‘S =’, S:6:2); writeln(‘P =’, P:10:2); End. Задача 3. Поиск минимального и максимального элементов массива Дан вещественный массив: T  {t i }; i  1, 10 . Поменять местами минимальный и максимальный элементы массива и вывести массив после обмена. Решение В этой задаче для осуществления обмена надо знать не только значения минимального и максимального элементов массива, но и их местоположение. Поэтому во время поиска минимального и максимального элементов необходимо фиксировать их индексы. Введем обозначения: min – минимальный элемент; imin – индекс минимального элемента; max – максимальный элемент; imax – индекс максимального элемента. Program ОМ_3; Var T: array [1..10] of real; i, imin, imax: integer; min, max: real; Begin writeln(‘Введите массив T’); for i := 1 to 10 do read(t[i]); min := +1E6; max := –1E6; for i := 1 to 10 do 6 begin if t[i]max then begin max := t[i]; imax := i; end; end; t[imin]:= max; t[imax]:= min; for i := 1 to 10 do write(t[i]:6:2); writeln; End. 1.2 Двухмерные массивы Двухмерные массивы в математике представляются матрицей:  a11  a A   21   a  m1 a12 a 22  am2  a1n    a 2n      a mn  , A  {a } ij mn или сокращенно можно записать: , где m – число строк; n – число столбцов; i, j – индексы (номера) текущих строки и столбца, на пересечении которых находится элемент aij. Описание двухмерного массива Описание матрицы в разделе Var задается структурным типом вида: <имя>: array [m1..m2, n1..n2] of <тип элементов>; m1..m2 – диапазон значений индекса i, определяющий число строк; n1..n2 – диапазон значений индекса j, определяющий число столбцов. 7 По описанию матрицы во внутренней памяти компьютера выделяется область из mn последовательных ячеек, в которые при работе программы записываются значения элементов матрицы. Например, по описанию: Var A: array [1..3, 1..5] of real; в памяти компьютера для элементов матрицы выделяется область, состоящая из 35=15 последовательных ячеек вещественного типа. Из описания видно, что матрица состоит из трех строк и пяти столбцов. Обращение к отдельным элементам матрицы осуществляется с помощью переменной с двумя индексами, например: a[i, j]aij; a[2, 3]a23; a[2n, k+1]a2n, k+1. Ввод-вывод двухмерного массива Для поэлементного ввода и вывода матрицы используется двойной цикл for…to. Если задать индекс i как параметр внешнего цикла, а индекс j как параметр внутреннего цикла, то ввод-вывод матрицы осуществляется построчно. Пример 1. Организовать ввод целочисленной матрицы M по строкам.  1 2 3  M    4 5 6 . Описание матрицы вместе с текущими индексами имеет вид: Var M: array [1..2, 1..3] of integer; i, j: integer; Ввод в программе реализуется в форме диалога, т.е. сопровождается поясняющим сообщением: writeln(‘Введите матрицу М’); for i := 1 to 2 do for j := 1 to 3 do read(m[i, j]); На клавиатуре желательно для наглядности восприятия набирать элементы матрицы по строкам, отделяя числа друг от друга одним или несколькими пробелами: 1 2 3 [Enter] 8 4 5 6 [Enter] Пример 2. Организовать вывод матрицы M на экран. Вывод матрицы необходимо реализовать в удобном для чтения виде, т.е. чтобы на одной строке экрана располагалась одна строка матрицы. С этой целью в тело внешнего цикла, помимо внутреннего, включается оператор writeln, который переводит курсор к началу следующей строки экрана после вывода текущей строки матрицы. for i := 1 to 2 do begin for j := 1 to 3 do write(m[i, j]:3); writeln; end; Вывод матрицы на экран будет следующим: 1 2 3 4 5 6 Обработка матриц Базовыми алгоритмами обработки матриц являются те же алгоритмы, которые используются при обработке одномерных массивов. Однако реализацию этих алгоритмов можно условно рассматривать для двух типов задач. 1. Алгоритмы реализуются при просмотре всех элементов матрицы (просмотр может быть с условием). Начальная установка алгоритма выполняется перед двойным циклом. В этом случае запись операторов цикла для параметров i и j осуществляется последовательно друг за другом и имеет вид: <начальная установка>; for i := 1 to m do for j := 1 to n do <тело цикла>; 2. Алгоритмы реализуются внутри каждой строки или каждого столбца матрицы. В этом случае начальная установка алгоритма выполняется между операторами цикла, записанными для параметров i и j. Например, если алгоритм реализуется для каждой строки, то запись в программе имеет следующий вид: for i := 1 to m do begin <начальная установка>; for j := 1 to n do <тело цикла>; 9 end; Ниже рассмотрены примеры программирования задач каждого типа. Реализация алгоритмов задач первого типа A  {a } ij 46 Задача 1. Дана матрица вещественных чисел . Вычислить значение Z  P1 / P2 , где P1 и P2 – произведения положительных и отрицательных элементов матрицы соответственно. Program DМ1_1; Var A: array [1..4, 1..6] of real; i, j: integer; P1, P2, Z: real; Begin writeln(‘Введите матрицу А’); for i := 1 to 4 do for j := 1 to 6 do read(a[i,j]); P1 := 1; P2 := 1; for i := 1 to 4 do for j :=1 to 6 do begin if a[i,j]>0 then P1 := P1a[i,j]; if a[i,j]<0 then P2 := P2a[i,j]; end; Z := P1/abs(P2); writeln(‘Z=’, Z:10:2); End. B  {b } ij 55 Задача 2. В квадратной целочисленной матрице вычислить модуль разности между числом нулевых элементов, стоящих ниже главной диагонали, и числом нулевых элементов, стоящих выше главной диагонали. Введем обозначения: 10 L1 – число нулевых элементов ниже главной диагонали; L2 – число нулевых элементов выше главной диагонали; L = |L1 – L2|. Program DМ1_2; Var B: array [1..5, 1..5] of integer; i, j, L1, L2, L: integer; Begin writeln(‘Введите матрицу B’); for i := 1 to 5 do for j := 1 to 5 do read(b[i,j]); L1 := 0; L2 := 0; for i := 1 to 5 do for j := 1 to 5 do if b[i,j]=0 then begin if i>j then L1 := L1+1; if i