double arrow

Типовые алгоритмы решения задач с использованием матриц

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

На рис.9.3 приведен алгоритм вычисления суммы элементов матрицы a(m*n). Внешний цикл предназначен для установления текущего адреса i строки матрицы, а внутренний (вложенный) – текущего адреса j ее столбца.

Вычисление произведения Р элементов матрицы осуществляется по аналогичной блок – схеме, в которой следует заменить символ S на P, операцию S = 0 на операцию P = 1, а операцию S = S + ai j - на операцию P =P*ai j.

В некоторых случаях возникает вопрос, какой цикл должен быть внешним, а какой – внутренним. Ответ на него следующий.

Если условием задачи предусматриваются какие-либо операции в строках, то внешний цикл должен определять текущий адрес строки, если же предусматриваются операции в столбцах, то внешний цикл должен определять текущий адрес столбца. Если же операции над элементами матрицы не акцентируются на строках или на столбцах, как в случае вычисления суммы или произведения элементов матрицы, то взаимное расположение циклов может быть любым.

 
 


Рис. 9.3 Блок – схема вычисления суммы элементов матрицы

Пример 1. В заданной матрице a(m*n) определить наибольшие элементы строк.

Алгоритм решения этой задачи представлен на рис.9.4. Здесь внешний цикл определяет текущий адрес строки. Получив адрес строки , первый элемент ее (элемент первого столбца) берется в в качестве начального значения переменной . Вложенный цикл предусматривает определение текущего порядкового номера элемента в данной строке (номер столбца). В дальнейшем используется типовой алгоритм определения наибольшего числа в ряде чисел (в строке матрицы). Следует подчеркнуть, что в задаче требуется определить максимальные элементы в строках, поэтому внешний цикл алгоритма устанавливает текущий адрес строки.

 
 


_

+

Рис.9.4. Блок-схема определения максимального элемента в строке матрицы

Пример 2. В заданной матрице a(m*n) определить наибольший элемент в каждом столбце.

Алгоритм решения этой задачи приведен на рис.9.5. В отличие от предыдущего примера в этом алгоритме внешний цикл определяет текущий адрес столбца.

В случае примера с вычислением суммы всех элементов матрицы (Рис.9.3) внешний цикл может определять как текущий адрес строки, так и текущий адрес столбца, поскольку здесь не акцентируется место операций (строки или столбцы). Областью операций являются все элементы матрицы без уточнения, в каких строках или столбцах они расположены.

Приведенные алгоритмы составляют далеко не полный перечень алгоритмов с операциями над элементами матриц. Однако они могут быть использованы как фрагменты при разработке более сложных алгоритмов.

Следует хорошо понимать логику типовых алгоритмов, хорошо запомнить их и умело применять при решении различных задач. Это позволит экономить время на разработку алгоритмов других задач, в которых используются типовые алгоритмы.

 
 


_

Рис. 9.5 Блок-схема определения максимального элемента

в столбце матрицы


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: