Массивы. Основные алгоритмы обработки массивов на примере языка программирования Pascal (стр. 2 из 3)
Writeln(‘Массив’);
For i:=1 to 3 do
 |
Рисунок 1. Блок-схема поиска требуемого элемента в массиве
Например,
Дан одномерный массив из 7 ячеек. Определить, сколько в нем чисел кратных 7.
Var
mas:array[1..7] of integer;
i:integer; {необходима для перебора массива}
kol:integer; {количество подходящих элементов}
begin
for i:=1 to 7 do
begin
write(‘Введите’ ,i, ‘ элемент’);
readln(mas[i]); {заполняем массив}
if (mas[i] mod 7 =0) and (mas[i]<>0) then kol:=kol+1
{если элемент делится на 7 и в остатке ноль и при этом сам элемент не равен нулю, то увеличиваем счетчик kol}
end;
writeln(“Количество чисел кратных 7 -”, kol) {вывод результата}
end.
Ход выполнения:
| 9 | -7 | 0 | 14 | 5 | 21 | -5 | Элементы |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | Индексы |
Введенный массив
| i = | Readln(mas[i]) | Проверка (mas[i] mod 7 =0) and (mas[i]<>0) | Действие | |
| Шаг 1 | 1 | Mas[1]=9 | ложь | Kol=0 |
| Шаг 2 | 2 | Mas[2]=-7 | истина | Kol=0+1 |
| Шаг 3 | 3 | Mas[3]=0 | ложь | Kol=1 |
| Шаг 4 | 4 | Mas[4]=14 | истина | Kol=1+1 |
| Шаг 5 | 5 | Mas[5]=5 | ложь | Kol=2 |
| Шаг 6 | 6 | Mas[6]=21 | истина | Kol=2+1 |
| Шаг 7 | 7 | Mas[7]= -5 | ложь | Kol=3 |
| Вывод результата на экран | ||||
2.4 Поиск максимального и минимального элементов массива
Общий алгоритм работы можно представить в следующем виде:
· определяются переменные (max и min), в которых в результате выполнения алгоритма разместятся соответственно максимальное и минимальное значения;
· начинается перебор массива с одновременной проверкой «является ли просматриваемый элемент больше максимального или меньше минимального»; в случае, если условие истинно – значение элемента массива присваивается соответствующей переменной;
Основной алгоритм выглядит следующим образом:
Max:= - 32000;
Min:= 32000;
For i:=1 to n do
begin
If mas[i]>max then max:=mas[i];
If mas[i]<min then min:=mas[i];
End;
Ход выполнения:
| 9 | -7 | 0 | -10 | Элементы |
| 1 | 2 | 3 | 4 | Индексы |
Введенный массив
| i = | Данные | Условие | Ответ | Действие | |
| Шаг 1 | 1 | Max=-32000 Min=32000 Mas[1] = 9 | 9 > -32000 9 < 32000 | истина истина | Max=9 Min=9 |
| Шаг 2 | 2 | Max=9 Min=9 Mas[2]= - 7 | -7 > 9 -7 < 0 | ложь истина | Max=9 Min= - 7 |
| Шаг 3 | 3 | Max=9 Min= - 7 Mas[3]=0 | 0 > 9 0 < -7 | ложь ложь | Max=9 Min= - 7 |
| Шаг 4 | 4 | Max=9 Min= - 7 Mas[4] = - 10 | -10 > 9 - 10 < -7 | ложь истина | Max=9 Min= - 10 |
2.5 Сортировка элементов массива
Существует много алгоритмов сортировки массива, но наиболее простым и понятным является сортировка методом «пузырька», при которой самый «легкий» элемент «всплывает», а самый тяжелый «тонет».
Например,
| 9 | -7 | 0 | -8 | Элементы |
| 1 | 2 | 3 | 7 | Индексы |
Дан массив
Необходимо расположить эти элементы в порядке возрастания, т.е. в результате работы программы необходимо получить массив
| -8 | -7 | 0 | 9 | Элементы |
| 1 | 2 | 3 | 7 | Индексы |
При сортировке методом «пузырька» сравниваются два соседних элемента (mas[i] и mas[i+1]). Если mas[i] > mas[i+1], то происходит перестановка элементов. Визуально процесс сортировки можно представить в виде:
Рисунок 2. Сортировка методом «пузырька»
Таким образом, для организации сортировки потребуется два цикла, которые выстраиваются в следующем порядке:
(n-размерность массива)
For j:=1 to n do {количество просмотров массива}
For i:=1 to n-1 do {перебор элементов массива}
If mas[i] > mas[i+1] then begint:=mas[i];
mas[i]:=mas[i+1];
mas[i+1]:=t;
end;
Как видно из примера для перестановки элементов массива требуется дополнительная переменная, которая служит временным хранилищем значения ячейки массива. | 9 | -7 | 0 | -8 |
Шаг 1.
| 9 | -7 | 0 | -8 |
| 9 | -7 | 0 | -8 |
| -7 | -7 | 0 | -8 |
Шаг 2.
| -7 | -7 | 0 | -8 |
| -7 | 9 | 0 | -8 |
Шаг 3.
3. Особенности обработки двумерных массивов
Двумерный массив – структура данных, хранящая в себе прямоугольную матрицу. В матрице каждый элемент определяется номером строки и номером столбца, на пересечении которых он расположен.
Для описания двумерных массивов используются те же способы, что и для одномерных массивов, но в качестве размерности массива задается двойное значение (Например, [1..10,1..10]).
Таким образом, для создания двумерного целочисленного массива размерностью 5×7 (5 строк, 7 столбцов) необходимо записать:
Способ 1
Type mas=array[1..5,1..7] of integer;
Способ 2
Var mas:array[1..5,1..7] of integer;
Для последовательного перебора всех элементов двумерного массива необходимо использовать т.н. вложенный цикл:
For i:=1 to 5 do {перебор строк матрицы}
For j:=1 to 7 do {перебор столбцов (ячеек) в строке}
Т.е. значение индекса строки (i) увеличится только в том случае, если индекс столбца (j) дойдет до своего конечного значения (в примере j = 7).
При такой организации перебора элементов массива процесс перебора будет проходить по следующей схеме: | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 31 | 32 | 33 | 34 | 35 | 36 | 37 |
| 41 | 42 | 43 | 44 | 45 | 46 | 47 |
| 51 | 52 | 53 | 54 | 55 | 56 | 57 |
Рисунок 3. Процесс перебора элементов двумерного массива
Ход выполнения:
| i = | j= | Условие перехода на следующую строку j=7 | Обрабатываемый элемент | |
| Шаг 1 | 1 | 1 | нет | Mas[1,1] |
| Шаг 2 | 1 | 2 | нет | Mas[1,2] |
| Шаг 3 | 1 | 3 | нет | Mas[1,3] |
| Шаг 4 | 1 | 4 | нет | Mas[1,4] |
| Шаг 5 | 1 | 5 | нет | Mas[1,5] |
| Шаг 6 | 1 | 6 | нет | Mas[1,6] |
| Шаг 7 | 1 | 7 | да | Mas[1,7] |
| Шаг 8 | 2 | 1 | нет | Mas[2,1] |
| Шаг 9 | 2 | 2 | нет | Mas[2,2] |
| Шаг 10 | 2 | 3 | нет | Mas[2,3] |
| … | … | … | … | … |
Для того чтобы вывести двумерный массив на экран в виде таблицы необходимо после вывода содержимого каждой строки предусмотреть переход на строку ниже: