1.1 题目描述
输入的第一行中有3个整数n, m,k,表示A矩阵是n行m列,B矩阵是m行k列。接下来的n行，每行m个数字，表示矩阵A中的元素。接下来的m行，每行k个元素，表示矩阵B中的元素。
【样例输入】
3 2 3
1 1
1 1
1 1
1 1 1
1 1 1
【样例输出】
2 2 2
2 2 2
2 2 2
1.1 矩阵乘法 之 迭代算法（三重循环）
- 现有矩阵 A(m×k) B(k×n)
- 将AB相乘，得到C(m×n)
- 具体的过程是这样的：
将 A[i][t] × B[t][j] 的k在其取值范围内进行累积，填到 C[i][j] 的位置。
#include<iostream>
using namespace std;// 这是 “迭代算法 ” int main() {int n, m, k;cin >> n >> m >> k;int mar1[n][m]; // 第一矩阵 n×mint mar2[m][k]; // 第二矩阵 m×kint mar3[n][k]; // 结果矩阵 n×k// 输入 mar1for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> mar1[i][j];}}// 输入 mar2for (int i = 0; i < m; i++) {for (int j = 0; j < k; j++) {cin >> mar2[i][j];}}for (int i = 0; i < n; i++) {for (int j = 0; j < k; j++) {int res = 0;for (int t = 0; t < m; t++) {res += mar1[i][t] * mar2[t][j];}mar3[i][j] = res;}}// 输出结果矩阵for (int i = 0; i < n; i++) {for (int j = 0; j < k; j++) {cout << mar3[i][j] << " ";}cout << endl;}return 0;
}
既然是三重循环，那么时间复杂度就是O(n^3),其实还是蛮高的。所以接下来讲的是分治优化后的算法。
1.2 矩阵乘法 之 递归算法（分而治之）
- 将原A和B矩阵每个都分成四块（左上，左下，右上，右下）
- 将这些子矩阵相乘，最后拼成最终的结果矩阵C。
点击查看代码
具体代码还在生成中,敬请期待......