Strassen矩阵相乘算法的c+代码实现

1、#include#include#includeusing namespace std;int multiply(int n,int A6464,int B6464,int C6464);int sub(int A6464,int B6464,int C6464,int n);int add(int A6464,int B6464,int C6464,int n);int main()int n;cinn;int i,j;int C6464;int A6464;for(int i=0;in;i+)for(j=0;jAij; /输入A int B6464;for(int i=0;in;i+)fo

2、r(j=0;jBij; /输入B multiply(n,A,B,C); /调用递归函数 for(int i=0;in;i+)for(j=0;jn;j+)coutCij;if(jn-1) cout ; /输出C coutendl;multiply(n,B,A,C); /调用递归函数 for(int i=0;in;i+)for(j=0;jn;j+)coutCij;if(jn-1) cout ; /输出C coutendl;int multiply(int n,int A6464,int B6464,int C6464)if(n=2) /进行常规矩阵乘法运算 (也可将范围缩小到1)C00=A00*B

3、00+A01*B10;C01=A00*B01+A01*B11;C10=A10*B00+A11*B10;C11=A10*B01+A11*B11;else int A116464;/A11for(int i=0;in/2;i+) for(int j=0;jn/2;j+)A11ij=Aij;int A216464;/A21for(int i=0;in/2;i+)for(int j=0;jn/2;j+)A21ij=Ai+n/2j;int A126464;/A12for(int i=0;in/2;i+)for(int j=0;jn/2;j+)A12ij=Aij+n/2;int A226464;/A22f

4、or(int i=0;in/2;i+)for(int j=0;jn/2;j+)A22ij=Ai+n/2j+n/2;int B116464;/B11for(int i=0;in/2;i+)for(int j=0;jn/2;j+)B11ij=Bij;int B216464;/B21for(int i=0;in/2;i+)for(int j=0;jn/2;j+)B21ij=Bi+n/2j;int B126464;/B12for(int i=0;in/2;i+)for(int j=0;jn/2;j+)B12ij=Bij+n/2;int B226464;/B22for(int i=0;in/2;i+)f

5、or(int j=0;jn/2;j+)B22ij=Bi+n/2j+n/2;int S16464;/S1sub(B12,B22,S1,n/2);int S26464;/S2add(A11,A12,S2,n/2);int S36464;/S3add(A21,A22,S3,n/2);int S46464;/S4sub(B21,B11,S4,n/2);int S56464;/S5add(A11,A22,S5,n/2);int S66464;/S6add(B11,B22,S6,n/2);int S76464;/S7sub(A12,A22,S7,n/2);int S86464;/S8add(B21,B22

6、,S8,n/2);int S96464;/S9sub(A11,A21,S9,n/2);int S106464;/S10add(B11,B12,S10,n/2);int P16464;/P1multiply(n/2,A11,S1,P1);int P26464;/P2multiply(n/2,S2,B22,P2);int P36464;/P3multiply(n/2,S3,B11,P3);int P46464;/P4multiply(n/2,A22,S4,P4);int P56464;/P5multiply(n/2,S5,S6,P5);int P66464;/P6multiply(n/2,S7,S

7、8,P6);int P76464;/P7multiply(n/2,S9,S10,P7);int R6464;for(int i=0;in;i+)for(int j=0;jn;j+)Rij=0; /初始化第一次 add(P5,P4,R,n/2);sub(R,P2,R,n/2);add(R,P6,R,n/2); /加出c11 for(int i=0;in/2;i+)for(int j=0;jn/2;j+)Cij=Rij; /赋值for(int i=0;in;i+)for(int j=0;jn;j+)Rij=0;add(P1,P2,R,n/2);for(int i=0;in/2;i+)for(int

8、 j=0;jn/2;j+)Cij+n/2=Rij;for(int i=0;in;i+)for(int j=0;jn;j+)Rij=0;add(P3,P4,R,n/2);for(int i=0;in/2;i+)for(int j=0;jn/2;j+)Ci+n/2j=Rij;for(int i=0;in;i+)for(int j=0;jn;j+)Rij=0;add(P5,P1,R,n/2);sub(R,P3,R,n/2);sub(R,P7,R,n/2);for(int i=0;in/2;i+)for(int j=0;jn/2;j+)Ci+n/2j+n/2=Rij; int sub(int A6464,int B6464,int C6464,int n)for(int i=0;