Алгоритмы обработки матриц
Матрица- это двумерный массив, каждый элемент которого имеет два индекса: номер строки — i; номер столбца — j. Поэтому для работы с элементами матрицы необходимо использовать два цикла. Если значениями параметра первого цикла будут номера строк матрицы, то значениями параметра второго — столбцы (или наоборот). Обработка матрицы заключается в том, что вначале поочередно рассматриваются элементы первой строки (столбца), затем второй и т.д. до последней. Рассмотрим основные операции, выполняемые над матрицами при решении задач.
Алгоритм ввода-вывода матриц
Матрицы, как и массивы, нужно вводить (выводить) поэлементно. Блок-схема ввода элементов матрицы изображена на рис. 4.1. Вывод матрицы организуется аналогично вводу.
 |  |
| Рис. 4.1. Ввод элементов матрицы | Рис. 4.2. Свойства элементов матрицы |
Рассмотрим несколько задач обработки матриц. Для их решения напомним читателю некоторые свойства матриц (рис. 4.2):
- если номер строки элемента совпадает с номером столбца (i = j), это означает что элемент лежит на главной диагонали матрицы;
- если номер строки превышает номер столбца (i j), то элемент находится ниже главной диагонали;
- если номер столбца больше номера строки (i
- элемент лежит на побочной диагонали, если его индексы удовлетворяют равенству i+j-1 = n;
- неравенство i+j-1 n характерно для элемента находящегося выше побочной диагонали;
- соответственно, элементу лежащему ниже побочной диагонали соответствует выражение i+j-1 n.
Примеры алгоритмов обработки матрицами
ПРИМЕР 4.1. Найти сумму элементов матрицы, лежащих выше главной диагонали (рис 4.3).
 |
| Рис. 4.3. Рисунок к условию задачи из примера 4.1 |
Алгоритм решения данной задачи (рис. 4.4) построен следующим образом: обнуляется ячейка для накапливания суммы (переменная S). Затем с помощью двух циклов (первый по строкам, второй по столбцам) просматривается каждый элемент матрицы, но суммирование происходит только в том случае если, этот элемент находится выше главной диагонали, то есть выполняется свойство i j.
На рисунке 4.5 изображен еще один вариант решения данной задачи. В нем проверка условия i
 |  |
| Рис. 4.4. Блок-схема примера 4.1 (алгоритм 1) | Рис. 4.5. Блок-схема примера 4.1 (алгоритм 2) |
ПРИМЕР 4.2. Вычислить количество положительных элементов квадратной матрицы, расположенных по ее периметру и на диагоналях. Напомним, что в квадратной матрице число строк равно числу столбцов.
Прежде чем преступить к решению задачи рассмотрим рисунок 4.6, на котором изображена схема квадратных матриц различной размерности. Из условия задачи понятно, что не нужно рассматривать все элементы заданной матрицы. Достаточно просмотреть первую и последнюю строки, первый и последний столбцы, а так же диагонали. Все эти элементы отмечены на схеме, причем черным цветом выделены элементы, обращение к которым может произойти дважды. Например, элемент с номером (1,1) принадлежит как к первой строке, так и к первому столбцу, а элемент с номером (N,N) находится в последней строке и последнем столбце одновременно. Кроме того, если N — число нечетное (на рисунке 4.6 эта матрица расположена слева), то существует элемент с номером (N/2+1, N/2+1), который находится на пересечении главной и побочной диагоналей. При нечетном значении N (матрица справа на рис. 4.6) диагонали не пересекаются.
 |
| Рис. 4.6. Рисунок к условию задачи из примера 4.2 |
Итак, разобрав подробно постановку задачи, рассмотрим алгоритм ее решения. Для обращения к элементам главной диагонали вспомним, что номера строк этих элементов всегда равны номерам столбцов. Поэтому, если параметр i изменяется циклически от 1 до N, то Ai,i — элемент главной диагонали. Воспользовавшись свойством, характерным для элементов побочной диагонали получим: i+j-1 = n j = n-i+1, следовательно, для i=1,2,…,n элемент Аi,n-i+1 — элемент побочной диагонали. Элементы, находящиеся по периметру матрицы записываются следующим образом: А1,i — первая строка, АN,i — последняя строка и соответственно Аi,1 — первый столбец, Аi,N — последний столбец.
Блок-схема описанного алгоритма изображена на рис. 4.7. В блоке 1 организуется цикл для обращения к диагональным элементам матрицы. Причем в блоках 2-3 подсчитывается количество положительных элементов на главной диагонали, а в блоках 5-6 на побочной. Цикл в блоке 6 задает изменение параметра i от 2 до N-1. Это необходимо для того, чтобы не обращать к элементам, которые уже были рассмотрены: A11, A1N, AN,1 и AN,N. Блоки 7-8 подсчитывают положительные элементы в первой строке, 9 и 10 — в последней строке, 11 и 12 — в первом столбце, а 13 и 14 в последнем. Блок 15 проверяет, не был ли элемент, находящийся на пересечении диагоналей, подсчитан дважды. Напомним, что это могло произойти только в том случае, если N — нечетное число и этот элемент был положительным. Эти условия и проверяются в блоке 16, который уменьшает вычисленное количество положительных элементов на единицу.
 |
| Рис. 4.7. Блок-схема к примеру 4.2 |
ПРИМЕР 4.3. Проверить, является ли заданная квадратная матрица единичной. Единичной называют матрицу, у которой элементы главной диагонали — единицы, а все остальные — нули.
 |
Решать задачу будем так. Предположим, что матрица единичная (FL=ИСТИНА) и попытаемся доказать обратное. Если окажется, что хотя бы один диагональный элемент не равен единице или любой из элементов вне диагонали не равен нулю, то матрица единичной не является (FL=ЛОЖЬ). Воспользовавшись логическими операциями все эти условия можно соединить в одно и составить блок-схему (рис. 4.8).
 |
| Рис. 4.8. Блок-схема к примеру 4.3 |
ПРИМЕР 4.4. Преобразовать исходную матрицу так, чтобы первый элемент каждой строки был заменен средним арифметическим элементов этой строки.
Для решения данной задачи необходимо найти в каждой строке сумму элементов, которую разделить на их количество. Полученный результат записать в первый элемент соответствующей строки. Блок-схема алгоритма решения приведена на рис. 4.9.
ПРИМЕР 4.5. Задана матрица An, m. Сформировать вектор Pm, в который записать номера строк максимальных элементов каждого столбца.
Алгоритм решения этой задачи следующий: для каждого столбца матрицы находим максимальный элемент и его номер, номер максимального элемента j-го столбца матрицы записываем в j-й элемент массива P. Блок-схема алгоритма приведена на рис. 4.10.
 |  |
| Рис. 4.9. Блок-схема алгоритма примера 4.4 | Рис. 4.10. Блок-схема алгоритма примера 4.5 |
ПРИМЕР 4.6. Написать программу умножения двух матриц An,m и Bm,l.
Например, необходимо перемножить две матрицы
| |
Воспользовавшись правилом строка на столбец, получим матрицу:
 |
В общем виде формула для нахождения элемента Ci,j матрицы имеет вид:
 | где i = 1,Nи j = 1,L. |
Обратите внимание, что проводить операцию умножения можно только в том случае, если количество строк левой матрицы совпадает с количеством столбцов правой. Кроме того, A A.
Блок-схема, изображенная на рис. 4.11, реализует расчет каждого элемента матрицы C в виде суммы по вышеприведенной формуле.
ПРИМЕР 4.7. Поменять местами n-й и l-й столбцы матрицы A(k,m). Блок-схема приведена на рис. 4.12.
 |  |
| Рис. 4.11. Алгоритм умножения двух матриц | Рис. 4.12. Блок-схема алгоритма примера 4.7 |
ПРИМЕР 4.8. Преобразовать матрицу A(m,n) таким образом, чтобы каждый столбец был упорядочен по убыванию. Алгоритм решения этой задачи сводится к тому, что уже известный нам по предыдущей главе алгоритм упорядочивания элементов в массиве выполняется для каждого столбца матрицы. Блок-схема приведена на рис. 4.13.
ПРИМЕР 4.9. Преобразовать матрицу A(m,n) так, чтобы строки с нечетными индексами были упорядочены по убыванию, c четными — по возрастанию. Блок-схема приведена на рис. 4.14.
 |  |
| Рис 4.13. Блок-схема алгоритма примера 4.8 | Рис. 4.14. Блок-схема алгоритма примера 4.9 |
