Лабораторная работа № 4. Обработка массивов
Цель работы – приобретение навыков программирования при решении задач с использованием одномерных и двумерных массивов, а также характерных приемов программирования.
4.1 Массивы и их обработка с помощью циклов
Массив – это структурированный тип данных, состоящий фиксированного числа элементов одного типа.
Массивы характеризуются именем, размерностью (количеством элементов), номерами (индексами) элементов в нем и значениями каждого элемента. Каждый элемент массива определяется своим индексом, по которому к нему осуществляется доступ.
Одномерный массив иначе называется вектором. Элемент одномерного массива имеет один индекс, указывающий на его порядковый номер.
Двумерный массив иначе называется матрицей. Элемент двумерного массива имеет два индекса: первый индекс соответствует номеру строки, второй – номеру столбца, в которых находится элемент.
В таблице 4.1 приводятся характеристики вектора Х(4) и матрицы А(3,3).
Таблица 4.1 - Примеры одномерного и двумерного массивов
Имя |
Размерность |
Номера элементов |
Значения элементов |
Х |
4 (в массиве 4 элемента) |
(х1, х2, х 3, х 4) |
(-3.8, 7.6, 2, 4.3), т.е. х1 = -3.8, х4 = 4.3 |
А |
А(3,3) (в массиве 9 элементов: 3 строки, 3 столбца) |
т.е. а23 = 0; а32 = 4.2 |
Как и любой другой объект программы, массив должен быть объявлен. Существует два способа описания массива:
- явный - в разделе Type описания типов данных (между Const и Var) задается размерность массива и тип его элементов, затем в разделе Var сформированному типу массива присваивается имя. Например,
Type T = array [1..4] of real; Var A: T; |
{Объявлен массив А, состоящий из} {четырех вещественных элементов} |
|
Type Z = array[1..3,1..4] of real; Var В:Z; |
{Объявлен вещественный массив B,} {состоящий из трех строк и четырех столбцов} |
- неявный - минуя раздел Type. Например,
Var A: array [1..4] of real; |
{Объявлен массив A(4)} |
|
Var B: array [1..3, 1..4] of real; |
{Объявлен массив B(3,4)} |
Так в языке Паскаль нет возможности вводить и выводить массивы как единый объект, для обработки массивов используются операторы циклов. Ввод и вывод одномерных массивов возможен только поэлементно с помощью оператора цикла:
-
For i:=1 to 10 do
Read (a[i]);
{ввод вектора А(10) в строку,}
{значения вводятся через пробел}
For i:=1 to 10 do
Readln (a[i]);
{ввод вектора А(10) в столбец, ввод каждого}
{элемента подтверждается клавишей Enter}
For i:=1 to 10 do
Write (a[i]);
{вывод вектора А(10) в одну строку}
For i:=1 to 10 do
Writeln (a[i]);
{вывод вектора А(10) в один столбец}
Работая с матрицей также надо организовать перебор всех ее элементов, причем необходимо открыть два цикла для изменения номера строки (i) и номера столбца (j), т.е. в одном цикле организовать другой. Таким образом, ввод и вывод двумерных массивов возможен только поэлементно с помощью организации вложенного цикла:
{поэлементный ввод массива А(5,5)} |
{поэлементный вывод массива А(5,5)} |
For i:=1 to 5 do For j:=1 to 5 do Read (a[i,j]); |
For i:=1 to 5 do For j:=1 to 5 do Write (a[i,j]); |
При таком способе организации вывода двумерный массив будет выведен на экране в одну строку. Если же в цикле использовать оператор Writeln (а[i,j]), то массив будет выведен в один столбец. Для того чтобы получить на экране матрицу в ее общепринятом виде, используется следующая организация вывода двумерного массива:
For i:=1 to 4 do
Begin
For j:=1 to 5 do
Write (а[i,j]);
Writeln
End;
Пустой оператор Writeln в данном случае используется для перевода курсора на следующую строку.
Циклы, аналогичные рассмотренному выше, называются вложенными. Цикл, в котором создается другой цикл, называется внешним, цикл, создаваемый внутри, - внутренним. Правила организации внешнего и внутреннего цикла те же, что и простого цикла. Вложенных циклов может быть больше двух. Параметры внешнего и внутреннего циклов должны быть разными, причем при фиксированном значении параметра внешнего цикла параметр внутреннего цикла принимает по очереди все свои значения.
Как правило, характерные приемы программирования применяют к определенным элементам массивов, а именно: к элементам между заданными номерами строк и столбцов; при выполнении действий с элементами строк и столбцов; к элементам главной диагонали или параллельных ей; элементам побочной диагонали; элементам, расположенным выше и ниже главной диагонали.
Для того чтобы алгоритм был составлен правильно, необходимо хорошо представлять взаимосвязь индексов элементов матрицы (таблица 4.2).
Таблица 4.2 - Взаимосвязь индексов элементов матрицы
Расположение элементов в массиве |
Взаимосвязь индексов строк (i) и столбцов (j) |
Примеры организации циклов для перебора элементов |
главная диагональ |
i = j |
S:=0; For i:=1 to n do S:=S+a[i i]; |
побочная диагональ (n - порядок матрицы) |
i + j = n + 1 |
P:=1; For i:=1 to n do P:=P*a[i, n+1-i]; |
выше главной диагонали |
i < j |
k:=0; For i:=1 to n do For j:=1 to n do If i<j {или i>j} then k:=k+1; |
ниже главной диагонали |
i > j |
Если обработка массива идет построчно, то внешний цикл организуют по i, а внутренний по j, и, наоборот, при переборе элементов матрицы по столбцам внешний цикл организуют по j, а внутренний по i. Кроме того, если работа производится с элементами строк или столбцов, то между операторами открытия вложенных циклов или операторами их закрытия обычно стоит какой-либо оператор, осуществляющий действие со строкой или столбцом.
4.2 Примеры алгоритмов и программ обработки массивов
4.2.1 Найти наибольшее значение вектора Х(5) и его порядковый номер.
На рисунке 4.1 представлены блок-схема алгоритма, программа и контрольная развертка. Алгоритм нахождения наибольшего элемента в векторе, рассматриваемый в этом примере, состоит в следующем:
- задание некоторой промежуточной переменной значения равного значению одного из элементов массива;
- организация цикла, в котором должен присутствовать условный оператор, сравнивающий значение очередного элемента массива и введенной переменной;
- если элемент оказывается больше переменной, то ей присваивается значение этого элемента и при необходимости запоминается и его номер;
- последнее значение переменной при выходе из цикла и будет наибольшим элементом массива.
|
program primer4_1; type T = array [1..5] of real; var X:T; max:real; i, n: integer; begin for i :=1 to 5 do begin write (’введи x (’, i:2,’)’); readln (x[i]) end; max := x[1]; n := 1; for i :=2 to 5 do if x[i]>max then begin max := x[i]; n := i end; writeln(’Наибольший элемент-’, max); writeln (’его номер-’, n) end. |
Контрольная развертка Пусть введен массив Х(3, 7, -4, 8, 2). Согласно алгоритму max:=3; n:=1. i=2 x(2) > max 7 > 3 да max = x(2) = 7; n = i = 2 i=3 x(3) > max -4 > 7 нет max = x(2) = 7; n = i = 2 i=4 x(4) > max 8 > 7 да max = x(4) = 8; n = i = 4 i=5 x(5) > max 2 > 8 нет max = x(4) = 8; n = i = 4 по окончании цикла вывод полученных значений max = 8 и n = 4 |
|
Рисунок 4.1 - Нахождение наибольшего элемента в одномерном массиве |
4.2.2 Найти среднее арифметическое элементов вектора А(10). Блок-схема и программа решения задачи представлены на рисунке 4.2.
|
Program primer4_2; type T = array [1..5] of real; var A:T; S, SA:real; i, K: integer; begin for i := 1 to 10 do read (a[i]); S:=0; K:=0; for i := 1 to 10 do if a[i] > 0 then begin S:=S + a[i]; K:=K+1 end; SA=S/K; writeln (’SA=’, SA:10:2) end. |
Рисунок 4.2 – Пример обработки одномерного массива |
-
Найти количество положительных элементов матрицы А(4,5) среди элементов, расположенных выше главной диагонали.
Блок-схема и программа решения задачи представлены на рисунке 4.3. При решении данной задачи перед открытием циклов, в которых будет осуществляться накапливание количества, необходимо обнулить начальное значение переменной К. Отбор элементов выполняется с использованием сложного условия, т.е. условие выбора положительных элементов массива и условие отбора элементов, расположенных выше главной диагонали, заключены в круглые скобки и объединены с помощью конъюнкции (аnd).
program primer4_3; type T = array [1..4,1..5]of real; var A:T; i, j, K: integer; begin for i:=1 to 4 do for j:=1 to 5 do read (a[i,j]); K:=0; for i:=1 to 4 do for j:=1 to 5 do if (a[i,j]>0) and (i < j) then K:=K+1; writeln (’K=’, K) end.
|
|
Рисунок 4.3 – Пример обработки двумерного массива |