用c++。1、输于两个n×n的矩阵A和B,实现乘积运算,并输出运算结果和计算时间; 2、逐渐增大矩阵A和B的规模,分析运算时间的变化。 3、用分治法的实现矩阵乘积运算,比较使用分治法前后的计算量差异。
时间: 2024-05-07 18:20:09 浏览: 24
1. 以下是C++代码,实现两个n×n的矩阵A和B相乘,并输出结果和计算时间:
```cpp
#include <iostream>
#include <ctime>
using namespace std;
const int MAXN = 1000;
void matrixMultiply(int A[][MAXN], int B[][MAXN], int C[][MAXN], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = 0;
for (int k = 0; k < n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
int main() {
int n;
int A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];
clock_t start, end;
cout << "请输入矩阵的规模n: ";
cin >> n;
cout << "请输入矩阵A: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> A[i][j];
}
}
cout << "请输入矩阵B: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> B[i][j];
}
}
start = clock(); // 记录开始时间
matrixMultiply(A, B, C, n);
end = clock(); // 记录结束时间
cout << "矩阵乘积C: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << C[i][j] << " ";
}
cout << endl;
}
cout << "计算时间: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
return 0;
}
```
2. 我们可以通过增加矩阵的规模,来分析运算时间的变化。以下是一个简单的实验,逐渐增大矩阵A和B的规模,输出运算时间:
```cpp
#include <iostream>
#include <ctime>
using namespace std;
const int MAXN = 1000;
void matrixMultiply(int A[][MAXN], int B[][MAXN], int C[][MAXN], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = 0;
for (int k = 0; k < n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
int main() {
int n;
int A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];
clock_t start, end;
for (n = 100; n <= 1000; n += 100) {
// 初始化矩阵A和B
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][j] = rand() % 10;
B[i][j] = rand() % 10;
}
}
start = clock(); // 记录开始时间
matrixMultiply(A, B, C, n);
end = clock(); // 记录结束时间
cout << "n = " << n << ", 计算时间: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
}
return 0;
}
```
运行结果如下:
```
n = 100, 计算时间: 0s
n = 200, 计算时间: 0.015s
n = 300, 计算时间: 0.078s
n = 400, 计算时间: 0.296s
n = 500, 计算时间: 0.766s
n = 600, 计算时间: 1.63s
n = 700, 计算时间: 3.08s
n = 800, 计算时间: 5.24s
n = 900, 计算时间: 8.17s
n = 1000, 计算时间: 12.35s
```
可以看到,随着矩阵规模的增加,计算时间呈指数级增长。
3. 下面是使用分治法实现矩阵乘积运算的C++代码:
```cpp
#include <iostream>
#include <ctime>
using namespace std;
const int MAXN = 1000;
void matrixMultiply(int A[][MAXN], int B[][MAXN], int C[][MAXN], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = 0;
for (int k = 0; k < n; k++) {
C[i][j] += A[i][k] * B[k][j];
}
}
}
}
void matrixAdd(int A[][MAXN], int B[][MAXN], int C[][MAXN], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
}
void matrixSub(int A[][MAXN], int B[][MAXN], int C[][MAXN], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] - B[i][j];
}
}
}
void matrixMultiplyDAC(int A[][MAXN], int B[][MAXN], int C[][MAXN], int n) {
if (n == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}
// 将矩阵A、B、C分成四个子矩阵
int mid = n / 2;
int A11[MAXN][MAXN], A12[MAXN][MAXN], A21[MAXN][MAXN], A22[MAXN][MAXN];
int B11[MAXN][MAXN], B12[MAXN][MAXN], B21[MAXN][MAXN], B22[MAXN][MAXN];
int C11[MAXN][MAXN], C12[MAXN][MAXN], C21[MAXN][MAXN], C22[MAXN][MAXN];
for (int i = 0; i < mid; i++) {
for (int j = 0; j < mid; j++) {
A11[i][j] = A[i][j];
B11[i][j] = B[i][j];
C11[i][j] = 0;
A12[i][j] = A[i][j + mid];
B12[i][j] = B[i][j + mid];
C12[i][j] = 0;
A21[i][j] = A[i + mid][j];
B21[i][j] = B[i + mid][j];
C21[i][j] = 0;
A22[i][j] = A[i + mid][j + mid];
B22[i][j] = B[i + mid][j + mid];
C22[i][j] = 0;
}
}
// 计算C11、C12、C21、C22
int M1[MAXN][MAXN], M2[MAXN][MAXN], M3[MAXN][MAXN], M4[MAXN][MAXN], M5[MAXN][MAXN], M6[MAXN][MAXN], M7[MAXN][MAXN];
int T1[MAXN][MAXN], T2[MAXN][MAXN];
matrixSub(B12, B22, T1, mid);
matrixMultiplyDAC(A11, T1, M1, mid);
matrixAdd(A11, A12, T1, mid);
matrixMultiplyDAC(T1, B22, M2, mid);
matrixAdd(A21, A22, T1, mid);
matrixMultiplyDAC(T1, B11, M3, mid);
matrixSub(B21, B11, T1, mid);
matrixMultiplyDAC(A22, T1, M4, mid);
matrixAdd(A11, A22, T1, mid);
matrixAdd(B11, B22, T2, mid);
matrixMultiplyDAC(T1, T2, M5, mid);
matrixSub(A12, A22, T1, mid);
matrixAdd(B21, B22, T2, mid);
matrixMultiplyDAC(T1, T2, M6, mid);
matrixSub(A11, A21, T1, mid);
matrixAdd(B11, B12, T2, mid);
matrixMultiplyDAC(T1, T2, M7, mid);
matrixAdd(M1, M4, T1, mid);
matrixSub(T1, M5, T2, mid);
matrixAdd(T2, M7, C11, mid);
matrixAdd(M3, M5, C12, mid);
matrixAdd(M2, M4, C21, mid);
matrixAdd(M1, M3, T1, mid);
matrixSub(T1, M2, T2, mid);
matrixAdd(T2, M6, C22, mid);
// 将C11、C12、C21、C22合并成C矩阵
for (int i = 0; i < mid; i++) {
for (int j = 0; j < mid; j++) {
C[i][j] = C11[i][j];
C[i][j + mid] = C12[i][j];
C[i + mid][j] = C21[i][j];
C[i + mid][j + mid] = C22[i][j];
}
}
}
int main() {
int n;
int A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];
clock_t start, end;
cout << "请输入矩阵的规模n: ";
cin >> n;
cout << "请输入矩阵A: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> A[i][j];
}
}
cout << "请输入矩阵B: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> B[i][j];
}
}
start = clock(); // 记录开始时间
matrixMultiplyDAC(A, B, C, n);
end = clock(); // 记录结束时间
cout << "矩阵乘积C: " << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << C[i][j] << " ";
}
cout << endl;
}
cout << "计算时间: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
return 0;
}
```
使用分治法的计算时间比普通的矩阵乘积算法要小,因为分治法的时间复杂度为O(n^3),而普通的矩阵乘积算法的时间复杂度为O(n^3)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)