Алгоритмы обработки двумерных массивов

 

Двумерный массив - это структура однотипных элементов, расположенных в виде таблицы значений. Такое представление значений соответствует математическому понятию двумерный массив. Каждый элемент в двумерном массиве идентифицируется номером строки и номером столбца, на пересечении которых он расположен. Например, в двумерном массиве А, изображенном на рис. 34, элемент со значением 5 расположен на пересечении третьей строки и второго столбца. Этот элемент будет обозначаться как А(3,2). А элемент А(1,4) имеет значение, равное нулю. Такое представление набора значений позволяет выполнять обработку как отдельных значений в двумерном массиве, так и последовательности значений, расположенных в строках или столбцах.

В дальнейшем будем считать, что для двумерного массива A(N,М) в обозначении элемента А(i,j) первое значение i соответствует номеру строки и изменяется от1 до N, а j - номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один номер для определения местоположения элемента и требовался только один цикл для ввода элементов, в двумерном массиве для обработки элеменов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний, - для изменеия номера столбца j в текущей строке i.

На рис. 35 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов.

 

Рис. 35. Алгоритм ввода элементов двумерного массива

 

При рассмотрении в дальнейшем алгоритмов обработки элементов двумерного массива в целях сокращения их размера фрагмент ввода элементов будем заменять отдельным блоком ввода.

 

Пример 13. Составить алгоритм поиска максимального значения в двумерном массиве А(N,M).

Решение. Поиск максимального элемента в двумерном массиве осуществляется аналогично поиску в одномерном массиве. Отличие состоит в том, что для обработки двумерного массива используем влож Обозначим максимальный элемент переменной МАХ. Значение этой переменной будет меняться на каждой итерации цикла, если очередной значение элемента массива окажется больше МАХ (см. рис.36).

 

Рис.36. Алгоритм поиска максимального значения в двумерном массиве

Пример 14. Составить алгоритм вычисления количества нечетных элементов в каждой строке двумерного массива А(1.. N, 1..М).

Решение. Для определения нечетных элементов будем использовать проверку на нечетность A[ I,J] mod 2 ≠ 0, для подсчета количества нечетных значений - формулу К=К+1и вывод значения К столько раз, сколько строк в массиве. Алгоритм решения представлен на рис. 37.

 

 

Рис.37.Алгоритм вычисления в каждой строке двумерного массива количества нечетных элементов

Пример 15. Составить алгоритм вычисления суммы элементов двумерного массива А(1.. N, 1..М), расположенных выше главной диагонали.

Решение. Для определения условия расположения элементов выше главной диагонали рассмотрим двумерный массив в обобщенном виде на рис. 38. Обратим внимание на диагональные элементы: номер строки и номер столбца совпадают. Значит для определения элементов на главной диагонали достаточно использовать условие I=J, где I- номер строки, J -номер столбца.

 

Для для определения элементов выше главной диагонали достаточно использовать условие I<J, ниже главной диагонали I>J. По условию задачи нам требуется найти сумму элементов двумерного массива А(1.. N, 1..М), расположенных выше главной диагонали, значит применим условие I<J, связывающее такие параметры элемента массива как номер строки I и номер столбца J.

Алгоритмическое решение задачи вычисления суммы элементов двумерного массива, расположенных выше главной диагонали приведено на рисунке 39.

Данный алгоритм содержит два вложенных цикла, каждый из которых относится к циклу с постусловием.

 

 

Рис.39. Алгоритм вычисления суммы элементов двумерного массива, расположенных выше главной диагонали