设A和B是两个n*n阶的矩阵,用分治法求他们的乘积矩阵C。使用Strassen算法。写出C++代码
时间: 2023-11-26 09:04:47 浏览: 105
以下是使用Python实现的Strassen算法:
```python
def strassen(A, B):
n = len(A)
if n == 1:
return [[A[0][0] * B[0][0]]]
else:
# 将矩阵A和B分为四个子矩阵
A11 = [[A[i][j] for j in range(n//2)] for i in range(n//2)]
A12 = [[A[i][j] for j in range(n//2, n)] for i in range(n//2)]
A21 = [[A[i][j] for j in range(n//2)] for i in range(n//2, n)]
A22 = [[A[i][j] for j in range(n//2, n)] for i in range(n//2, n)]
B11 = [[B[i][j] for j in range(n//2)] for i in range(n//2)]
B12 = [[B[i][j] for j in range(n//2, n)] for i in range(n//2)]
B21 = [[B[i][j] for j in range(n//2)] for i in range(n//2, n)]
B22 = [[B[i][j] for j in range(n//2, n)] for i in range(n//2, n)]
# 计算7个矩阵
S1 = [[B12[i][j] - B22[i][j] for j in range(n//2)] for i in range(n//2)]
S2 = [[A11[i][j] + A12[i][j] for j in range(n//2)] for i in range(n//2)]
S3 = [[A21[i][j] + A22[i][j] for j in range(n//2)] for i in range(n//2)]
S4 = [[B21[i][j] - B11[i][j] for j in range(n//2)] for i in range(n//2)]
S5 = [[A11[i][j] + A22[i][j] for j in range(n//2)] for i in range(n//2)]
S6 = [[B11[i][j] + B22[i][j] for j in range(n//2)] for i in range(n//2)]
S7 = [[A12[i][j] - A22[i][j] for j in range(n//2)] for i in range(n//2)]
# 递归计算7个子矩阵的乘积
P1 = strassen(A11, S1)
P2 = strassen(S2, B22)
P3 = strassen(S3, B11)
P4 = strassen(A22, S4)
P5 = strassen(S5, S6)
P6 = strassen(S7, S6)
P7 = strassen(S5, S4)
# 计算C的四个子矩阵
C11 = [[P5[i][j] + P4[i][j] - P2[i][j] + P6[i][j] for j in range(n//2)] for i in range(n//2)]
C12 = [[P1[i][j] + P2[i][j] for j in range(n//2)] for i in range(n//2)]
C21 = [[P3[i][j] + P4[i][j] for j in range(n//2)] for i in range(n//2)]
C22 = [[P5[i][j] + P1[i][j] - P3[i][j] - P7[i][j] for j in range(n//2)] for i in range(n//2)]
# 将四个子矩阵合并成一个n*n的矩阵
C = [[0 for j in range(n)] for i in range(n)]
for i in range(n//2):
for j in range(n//2):
C[i][j] = C11[i][j]
C[i][j+n//2] = C12[i][j]
C[i+n//2][j] = C21[i][j]
C[i+n//2][j+n//2] = C22[i][j]
return C
```
其中,S1到S7是用于计算P1到P7的临时矩阵,P1到P7是Strassen算法中的七个矩阵。最后将四个子矩阵合并成一个n*n的矩阵C。
阅读全文