Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А1,...Аn, заданных своими размерами n(i)*m(i). При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера. Замечание: Рассмотрим М = M1 * M2 * … * Mn, где Mi – матрица размера ri-1 * ri. Составим алгоритм нахождения наименьшего количества элементарных операций умножений матриц с задаными размерами r0, r1, … rn. // матрица размера n*m умножается на матрицу размера m*k #include <conio.h> #include <stdlib.h> #define MIN (x,y) ((x<y) ? x : y) // макрос для нахождения минимума из двух чисел int main() { // заполнения матриц случайными числами randomize(); for (i = 0; i <= n; i++) { for (j = 0; j <= m; j++) { random (m[i][j]); } } for (i = 0; i <= m; i++) { for (j = 0; j <= k; j++) { random (r[i][j]); } } // вывод матриц на экран for (i = 0; i <= n; i++) { for (j = 0; j <= m; j++) { printf ("%d ", m[i][j]); } printf ("\n"); } for (i = 0; i <= m; i++) { for (j = 0; j <= k; j++) { printf ("%d ", r[i][j]); } printf ("\n"); } int i(0), l(0); // вспомогательная переменные for (i = 1; i <= n; i++) m[i][i] = 0; // обнуляем элементы по диагонали for (l = 1; l <= n-1; l++) { for (i =1; i <= n-l; i++) { j = i + l; // вычисляем j-й индекс m[i][j] = MIN (m[i][k] + m[k+1][j] + r[i-1] * r[k] * r[j]); //перемножение } } for (i = 0; i <= n; i++) { for (j = 0; j <= m; j++) { printf ("%d ", m[i][j]); } printf ("\n"); } return 0; }
Ключевые слова:
перемножения матриц, сложность алгоритма
|
|||||||