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

#includeiostream#includealgorithm#includemath.husingnamespacestd;intmultiply(intn,intA[64][64],intB[64][64],intC[64][64]);intsub(intA[64][64],intB[64][64],intC[64][64],intn);intadd(intA[64][64],intB[64][64],intC[64][64],intn);intmain(){intn;cinn;inti,j;intC[64][64];intA[64][64];for(inti=0;in;i++){for(j=0;jn;j++){cinA[i][j];//输入A}}intB[64][64];for(inti=0;in;i++){for(j=0;jn;j++){cinB[i][j];//输入B}}multiply(n,A,B,C);//调用递归函数for(inti=0;in;i++){for(j=0;jn;j++){coutC[i][j];if(jn-1)cout;//输出C}coutendl;}multiply(n,B,A,C);//调用递归函数for(inti=0;in;i++){for(j=0;jn;j++){coutC[i][j];if(jn-1)cout;//输出C}coutendl;}}intmultiply(intn,intA[64][64],intB[64][64],intC[64][64]){if(n==2)//进行常规矩阵乘法运算(也可将范围缩小到1){C[0][0]=A[0][0]*B[0][0]+A[0][1]*B[1][0];C[0][1]=A[0][0]*B[0][1]+A[0][1]*B[1][1];C[1][0]=A[1][0]*B[0][0]+A[1][1]*B[1][0];C[1][1]=A[1][0]*B[0][1]+A[1][1]*B[1][1];}else{intA11[64][64];//A11for(inti=0;in/2;i++){for(intj=0;jn/2;j++){A11[i][j]=A[i][j];}}intA21[64][64];//A21for(inti=0;in/2;i++){for(intj=0;jn/2;j++){A21[i][j]=A[i+n/2][j];}}intA12[64][64];//A12for(inti=0;in/2;i++){for(intj=0;jn/2;j++){A12[i][j]=A[i][j+n/2];}}intA22[64][64];//A22for(inti=0;in/2;i++){for(intj=0;jn/2;j++){A22[i][j]=A[i+n/2][j+n/2];}}intB11[64][64];//B11for(inti=0;in/2;i++){for(intj=0;jn/2;j++){B11[i][j]=B[i][j];}}intB21[64][64];//B21for(inti=0;in/2;i++){for(intj=0;jn/2;j++){B21[i][j]=B[i+n/2][j];}}intB12[64][64];//B12for(inti=0;in/2;i++){for(intj=0;jn/2;j++){B12[i][j]=B[i][j+n/2];}}intB22[64][64];//B22for(inti=0;in/2;i++){for(intj=0;jn/2;j++){B22[i][j]=B[i+n/2][j+n/2];}}intS1[64][64];//S1sub(B12,B22,S1,n/2);intS2[64][64];//S2add(A11,A12,S2,n/2);intS3[64][64];//S3add(A21,A22,S3,n/2);intS4[64][64];//S4sub(B21,B11,S4,n/2);intS5[64][64];//S5add(A11,A22,S5,n/2);intS6[64][64];//S6add(B11,B22,S6,n/2);intS7[64][64];//S7sub(A12,A22,S7,n/2);intS8[64][64];//S8add(B21,B22,S8,n/2);intS9[64][64];//S9sub(A11,A21,S9,n/2);intS10[64][64];//S10add(B11,B12,S10,n/2);intP1[64][64];//P1multiply(n/2,A11,S1,P1);intP2[64][64];//P2multiply(n/2,S2,B22,P2);intP3[64][64];//P3multiply(n/2,S3,B11,P3);intP4[64][64];//P4multiply(n/2,A22,S4,P4);intP5[64][64];//P5multiply(n/2,S5,S6,P5);intP6[64][64];//P6multiply(n/2,S7,S8,P6);intP7[64][64];//P7multiply(n/2,S9,S10,P7);intR[64][64];for(inti=0;in;i++){for(intj=0;jn;j++){R[i][j]=0;}}//初始化第一次add(P5,P4,R,n/2);sub(R,P2,R,n/2);add(R,P6,R,n/2);//加出c11for(inti=0;in/2;i++){for(intj=0;jn/2;j++){C[i][j]=R[i][j];}}//赋值for(inti=0;in;i++){for(intj=0;jn;j++){R[i][j]=0;}}add(P1,P2,R,n/2);for(inti=0;in/2;i++){for(intj=0;jn/2;j++){C[i][j+n/2]=R[i][j];}}for(inti=0;in;i++){for(intj=0;jn;j++){R[i][j]=0;}}add(P3,P4,R,n/2);for(inti=0;in/2;i++){for(intj=0;jn/2;j++){C[i+n/2][j]=R[i][j];}}for(inti=0;in;i++){for(intj=0;jn;j++){R[i][j]=0;}}add(P5,P1,R,n/2);sub(R,P3,R,n/2);sub(R,P7,R,n/2);for(inti=0;in/2;i++){for(intj=0;jn/2;j++){C[i+n/2][j+n/2]=R[i][j];}}}}intsub(intA[64][64],intB[64][64],intC[64][64],intn){for(inti=0;in;i++){for(intj=0;jn;j++){C[i][j]=A[i][j]-B[i][j];}}}intadd(intA[64][64],intB[64][64],intC[64][64],intn){for(inti=0;in;i++){for(intj=0;jn;j++){C[i][j]=A[i][j]+B[i][j];}}}