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

Алгоритмы обработки матриц. Матрица – это двумерный массив, каждый элемент которого имеет два индекса: номер строки – i, номер столбца – j. Поэтому для работы с матрицами необходимо использовать два цикла. Если значениями параметрами первого цикла будут номера строк матрицы, то значениями параметра второго цикла – будут столбцы или наоборот.

Алгоритм ввода-вывода матриц

Матрицы, как и массивы, нужно вводить (выводить) поэлементно. Блок-схема вывода элементов матриц изображена на рис.9.21. Вывод элементов матриц аналогичен вводу.

N,M

I<j

I=j

i>j

i=j

i>j

i+j-1<N

i+j-1=N

i+j-1>N

i+j-1=

i+j-1=N

i+j-1>N

I=1,N

J=1,M

Ввод

Рис. 9.21. Ввод элементов массива

Матрицы имеют следующие свойства:

- если номер строки элемента совпадает с номером столбца (i=j), значит элемент лежит на главной диагонали матрицы;

- если номер строки превышает номер столбца (i>j), то элемент находится ниже главной диагонали матрицы;

- если номер столбца больше номера строки (i<j), то элемент находится выше главной диагонали матрицы;

- элемент лежит на побочной диагонали, если его индексы удовлетворяют неравенству (i+j-1)=N;

- неравенство (i+j-1) <N характерно для элемента, находящегося выше побочной диагонали;

- неравенство (i+j-1) >N характерно для элемента, находящегося ниже побочной диагонали.

Пример 5.6. Найти сумму элементов матрицы, лежащих выше главной диагонали (рис. 9.22.).

Рис. 9.22. Элементы матрицы, лежащие выше главной диагонали матрицы.

Алгоритм решения построен следующим образом. Обнуляется ячейка для накапливания суммы (переменная S). Затем с помощью двух циклов (первый по строкам, второй по столбцам) просматривается каждый элемент матрицы, но суммирование происходит только в том случае, если этот элемент находится выше главной диагонали, т.е. выполняется условие i<j. На рис. 9.23. приведен алгоритм решения задачи.

S =0

S=0

i=1,N

1,N

S

j=1,M

J=I+1,M

S=S+

i<j

S

S=S+

Рис. 9.23. Два варианта алгоритмов нахождения элементов матриц,

лежащих выше главной диагонали.

Алгоритм решения задачи заключается в следующем. Обнуляется ячейка для накапливания суммы (переменная S). Затем с помощью двух циклов (первый по строкам, второй по столбцам) просматривается каждый элемент матрицы, но суммирование происходит только в том случае, если этот элемент находится выше главной диагонали, то есть выполняется решение i<j.

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

1. Дано: Квадратная матрица из положительных элементов.

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

N - нечетное N - четное

Рис. 9.24. К условию задачи по нахождению количества элементов

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

На рис. 5.24. видно, что для решения задачи необходимо выбрать только те элементы, которые отмечены темным цветом. Более темным цветом отмечены те элементы, к которым необходимо обращаться дважды. Первый элемент с номером (1,1) принадлежит как к первой строке, так и к первому столбцу, а элемент с номером (N,N) находится в последней строке и в последнем столбце.

Если матрица нечетная, то существует элемент с номером (N/2+1, N/2+1), который находится на пересечении главной и побочной диагоналей. При четном значении N, диагонали не пересекаются.

Параметр I изменяется от 1 до N, - элемент главной диагонали. Для элементов побочной диагоналиi+j-1=n>j=n-i+1. Для i=1,2,3,…n элемент - элемент побочной диагонали. Элементы, находящиеся по периметру матрицы записываются следующим образом:- первая строка,- последняя строка.- первый столбец.- последний столбец.

Разработать самостоятельно алгоритм нахождения количества элементов по периметру и на диагоналях.

15