Примеры алгоритмов обработки матрицами

ПРИМЕР 4.1. Найти сумму элементов матрицы, лежащих выше главной диагонали (рис 4.3).

Рис. 4.3. Рисунок к условию задачи из примера 4.1

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

На рисунке 4.5 изображен еще один вариант решения данной задачи. В нем проверка условия i<j не выполняется, но, тем не менее, в нем так же суммируются элементы матрицы, находящиеся выше главной диагонали. Для того чтобы понять, как работает этот алгоритм, вернемся к рисунку 4.3. В первой строке заданной матрицы необходимо сложить все элементы, начиная со второго. Во второй - все, начиная с третьего, в i -й строке процесс начнется с (i+1) -го элемента и так далее. Таким образом, первый цикл работает от 1 до N, а второй от i+1 до M. Предлагаем читателю самостоятельно составить программу, соответствующую описанному алгоритму.

Рис. 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. Это необходимо для того, чтобы не обращать к элементам, которые уже были рассмотрены: A₁₁, A_1N, A_N,1 и A_N,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. Сформировать вектор P_m, в который записать номера строк максимальных элементов каждого столбца.

Алгоритм решения этой задачи следующий: для каждого столбца матрицы находим максимальный элемент и его номер, номер максимального элемента 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 >< B ≠ B >< 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

Поиск по сайту: