Типовые алгоритмы обработки двумерных массивов
Обработку двумерного массива можно условно разделить на три группы:
· Обработка всего массива;
· Обработка отдельно по строкам и столбцам;
· Обработка относительно диагоналей.
Рассмотрим типовые алгоритмы обработки двумерных массивов каждой группы в отдельности.
Обработка всего массива
| Таблица 5.1. | ||
| Типовой алгоритм | Программная реализация (Паскаль) | |
| Заполнение (порядок обхода элементов двумерного массива - построчно слева направо) | … for i:=1 to n do for j:=1 to m do readln (x[i,j]); … | |
| Вывод | … for i:=1 to n do begin for j:=1 to m do write (x[i,j], ' '); writeln; end; … | |
| Сумма, произведение | … s:=0; p:=1; for i:=1 to n do for j:=1 to m do begin s:=s+x[i,j]; p:=p*x[i,j]; end … | |
| Максимальный (минимальный) элемент | … max:=x[1,1]; min:=x[1,1]; for i:=1 to n do for j:=1 to m do begin if x[i,j]>max then max:=x[i,j]; if x[i,j]<min then min:=x[i,j]; end … | |
| Выбор по условию | … for i:=1 to n do for j:=1 to m do if {условие} then {действие} … |
Типовые алгоритмы обработки двумерного массива отдельно по строкам:
| Таблица 5.2. | ||
| Типовой алгоритм | Программная реализация (Паскаль) | |
| Сумма элементов каждой строки | … for i:=1 to n do s[i]:=0; for i:=1 to n do for j:=1 to m do s[i]:=s[i]+x[i,j]; for i:=1 to n do write (s[i]); … | |
| Произведение элементов каждой строки | … for i:=1 to n do p[i]:=1; for i:=1 to n do for j:=1 to m do p[i]:=p[i]*x[i,j]; for i:=1 to n do write (p[i]); | |
| Максимальный (минимальный) элемент каждой строки | … for i:= 1 to n do begin max[i]:=x[i,1]; min[i]:=x[i,1]; end; for i:=1 to n do for j:=1 to m do begin if x[i,j]>max[i] then max[i]:=x[i,j]; if x[i,j]<min[i] then min[i]:=x[i,j]; end; for i:=1 to n do write (max[i]); writeln; for i:=1 to n do write (min[i]); … | |
| Выбор по условию (в каждой строке) | … for i:= 1 to n do begin rez[i]:=0; end; for i:=1 to n do for j:=1 to m do if {условие} then {rez[i]:=…}; for i:=1 to n do write (rez[i]); … |
Типовые алгоритмы обработки двумерного массива отдельно по столбцам:
| Таблица 5.3. | ||
| Типовой алгоритм | Программная реализация (Паскаль) | |
| Сумма элементов в каждом столбце | … for j:=1 to m do s[j]:=0; for j:=1 to m do for i:=1 to n do s[j]:=s[j]+x[i,j]; for j:=1 to m do write (s[j]); … | |
| Произведение элементов в каждом столбце | … for j:=1 to m do p[j]:=1; for j:=1 to m do for i:=1 to n do p[j]:=p[j]*x[i,j]; for j:=1 to m do write (p[j]); … | |
| Максимальный (минимальный) элемент в каждом столбце | … for j:= 1 to m do begin max[j]:=x[i,1]; min[j]:=x[i,1]; end; for j:=1 to m do for i:=1 to n do begin if x[i,j]>max[j] then max[j]:=x[i,j] if x[i,j]<min[j] then min[j]:=x[i,j] end; for j:=1 to m do write (max[j]); writeln; for j:=1 to m do write (min[j]); … | |
| Выбор по условию (в каждом столбце) | … for j:= 1 to m do rez[j]:=0; for j:=1 to m do for i:=1 to n do if {усл.} then {rez[i]:=…}; for j:=1 to m do write (rez[j]); … |
Типовые алгоритмы обработки двумерного массива относительно диагоналей
Если количество строк и столбцов в двумерном массиве одинаково, то такой массив называется квадратным. Типовые алгоритмы для квадратных массивов позволяют обрабатывать массив относительно его диагональных элементов. Зависимость индексов элементов, расположенных на побочной диагонали легко определяется при после повторения Лекции 1 (номер строки элемента растет, номер столбца убывает).
Рис. 5.1.
Главная диагональ. В таблице приведены типовые алгоритмы обработка элементов двумерного массива, расположенных НА, ВЫШЕ и НИЖЕ главной диагонали.
| Таблица 5.4. | ||
| Типовой алгоритм | Программная реализация (Паскаль) | |
| Сумма элементов, расположенных НА главной диагонали | … s:=0; for i:=1 to n do s:=s+x[i,i]; … | |
| Сумма элементов, расположенных ВЫШЕ главной диагонали | … s:=0; for i:=1 to n do for j:=1 to n do if i<j then s:=s+x[i,j]; … | |
| Сумма элементов, расположенных НИЖЕ главной диагонали | … s:=0; for i:=1 to n do for j:=1 to n do if i>j then s:=s+x[i,j]; … |
Побочная диагональ. В таблице приведены типовые алгоритмы обработка элементов двумерного массива, расположенных НА, ВЫШЕ и НИЖЕ побочной диагонали.
| Таблица 5.5. | ||
| Типовой алгоритм | Программная реализация (Паскаль) | |
| Сумма элементов, расположенных НА побочной диагонали | … s:=0; for i:=1 to n do s:=s+x[i, n-i+1]; … | |
| Сумма элементов, расположенных ВЫШЕ побочной диагонали | … s:=0; for i:=1 to n do for j:=1 to n do if (i<n-j+1) then s:=s+x[i,j]; … | |
| Сумма элементов, расположенных НИЖЕ побочной диагонали | … s:=0; for i:=1 to n do for j:=1 to n do if (i>n-j+1) then s:=s+x[i,j]; … |
Обработка квадратной матрицы относительно диагоналей (рациональный обход)
Предложенные выше типовые алгоритмы обработки квадратного массива относительно диагоналей нерациональны, т.к. перебираются все элементы массива. Более рационально ограничить перебор элементов. Решит проблему введение зависимости начального или конечного значений управляющей переменной внутреннего цикла от значения счетчика внешнего цикла.
Рассмотрим типовые алгоритмы обработки квадратного массива относительно диагоналей рациональным способом на примерах.
Задача: заполнить элементы квадратного массива "1" так, как показано на рисунке:
| Таблица 5.6. | |||
| Ниже и на главной диагонали | Выше и на главной диагонали | Выше и на побочной диагонали | Ниже и на побочной диагонали |
| 100000000 110000000 111000000 111100000 111110000 111111000 111111100 111111110 | 011111111 001111111 000111111 000011111 000001111 000000111 000000011 000000001 | 111111110 111111100 111111000 111110000 111100000 111000000 110000000 100000000 | 000000001 000000011 000000111 000001111 000011111 000111111 001111111 011111111 |
| Программная реализация на Паскале: … for i:=1 to n do for j:=1 to i do x[i,j]:=1; … | Программная реализация на Паскале: … for i:=1 to n do for j:=i to n do x[i,j]:=1; … | Программная реализация на Паскале: … for i:=1 to n do for j:=1 to (n-i+1) do x[i,j]:=1; … | Программная реализация на Паскале: … for i:=1 to n do for j:=(n-i+1) to n do x[i,j]:=1; … |
Ключевые термины
· Двумерный массив -именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу. Массивы с одним индексом называют одномерными, с двумя - двумерными.
· Квадратный массив - двумерный массив, количество строк и столбцов в котором одинаково.
Краткие итоги
Для решения задач с использованием двумерных массивов необходимо воспользоваться типовыми алгоритмами обработки, такими как:
· Обработка всего массива:
o Заполнение, вывод
o Сумма, произведение
o Максимальный (минимальный) элемент
o Выбор по условию
· Обработка отдельно по строкам и столбцам:
o Заполнение, вывод
o Сумма, произведение
o Максимальный (минимальный) элемент
o Выбор по условию
· Обработка относительно диагоналей:
o Заполнение, вывод
o Сумма, произведение
o Максимальный (минимальный) элемент
o Выбор по условию
При обработке квадратного массива относительно его диагоналей необходимо воспользоваться рациональным способом, исключающим обход всех элементов массива.
Набор для практики
Вопросы.
· Что произойдет если поменять местами счетчики внешнего и внутреннего цикла i и j в заголовках циклов (в типовом алгоритме обработки двумерного массива)?
· Какова зависимость индексов элементов, расположенных на главной диагонали квадратного массива? Побочной?
Упражнения.
· Найдите максимальный элемент из минимальных элементов каждой строки двумерного массива и минимальный элемент из максимальных элементов каждого столбца двумерного массива размерностью NxM.
· Заполните квадратные массивы, как предложено на рис. 5.2:
Рис. 5.2.