- •Лекция 15 Базовые алгоритмы работы с массивами
- •Обработка матриц
- •Построчная обработка
- •Обработка по столбцам
- •Обработка всей матрицы
- •Обход по «спирали» квадратной матрицы порядка n
- •Обработка части матрицы Обработка элементов главной или побочной диагоналей квадратной матрицы
- •Обработка элементов над(под) главной или побочной диагоналями квадратной матрицы
- •Вставка строки
- •Построение матриц
- •Примеры «Зеркальное отображение» матрицы относительно вертикальной оси, проходящей через ее середину
- •Нахождение минимального элемента матрицы и вычеркивание строки и столбца, на пересечении которых он находится
- •Нахождение сумм элементов квадратной матрицы на главной диагонали и на диагоналях, параллельных главной
- •Умножение матриц
Умножение матриц
Матрица – математический объект, эквивалентный двумерному массиву. Числа располагаются в матрице по строкам и столбцам. Две матрицы одинакового размера можно поэлементно сложить или вычесть друг из друга.
Если число столбцов в первой матрице совпадает с числом строк во второй, то эти две матрицы можно перемножить. У произведения будет столько же строк, сколько в первой матрице, и столько же столбцов, сколько во второй. При умножении матрицы размером 3х4 на матрицу размером 4x7 мы получаем матрицу размером 3x7. Умножение матриц некоммутативно: оба произведения АВ и ВА двух квадратных матриц одинакового размера можно вычислить, однако результаты, вообще говоря, будут отличаться друг от друга. (Отметим, что умножение чисел коммутативно, и произведения АВ и ВА двух чисел A и В равны.)
Для вычисления произведения двух матриц каждая строка первой почленно умножается на каждый столбец второй. Затем подсчитывается сумма таких произведений и записывается в соответствующую клетку результата. Ниже приведен пример умножения двух матриц, которое в этом случае требует 24-х умножений и 16-и сложений. Вообще, стандартный алгоритм умножения матрицы размером ахb на матрицу размером bхс выполняет abc умножений и а(b-1)с сложений.
Рассмотрим стандартный алгоритм умножения матрицы G размером ахb на матрицу Н размером bxс. Результат записывается в матрицу R размером ахс. Алгоритм вычисления элементов матрицы R содержит три вложенных цикла.
Обратите внимание, что первые два цикла имеют в качестве верхних значений параметров цикла значения а и с (как значения размеров новой матрицы). Третий цикл имеет в качестве верхнего значения параметра цикла значение b (количество элементов в строке первой матрицы и столбце второй матрицы):
for (int i=1; i< a ; i++) for (int j=1; i< c ; j++) { R[i][j]=0; for (int k=1; k< b ; k++) R[i][j]=R[i][j]+G[i][k]*H[k][j]; } // for j
