网上关于斯特拉森矩阵的乘法，代码框架很多
只是没有实现的代码块（有，但是就是不会运行）
老师布置的了相关利用分治法来做的的题目
想了很久，大概三天了（分治法大问题化小问题）是真没有完美的解决方法
找到了个可以运行的java代码：java写的代码思路是真的清晰（粉java）
package sort; /** * @Author liguo * @Description * @Data 2018-04-07 14:44 */ public class Sitelasen { public static void main(String[] args) { int[][] cc = {{1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}}; int[][] e = new Sitelasen().multiMatrix( cc, cc ); for (int i = 0; i < e.length; i++) { for (int j = 0; j < e.length; j++) System.out.print( e[i][j] + " " ); System.out.println(); } } int[][] multiMatrix(int[][] x, int[][] y)//矩阵的乘法 { Sitelasen matr = new Sitelasen(); int a = x.length / 2; if (x.length == 2) { int m1 = (x[0][1] - x[1][1]) * (y[1][0] + y[1][1]), m2 = (x[0][0] + x[1][1]) * (y[0][0] + y[0][1]), m3 = (x[1][0] - x[0][0]) * (y[0][0] + y[0][1]), m4 = (x[0][0] + x[0][1]) * y[1][1], m5 = x[0][0] * (y[0][1] - y[1][1]), m6 = x[1][1] * (y[1][0] - y[0][0]), m7 = (x[1][0] + x[1][1]) * y[0][0]; int[][] c = new int[2][2]; c[0][0] = m1 + m2 + m6 - m4; c[0][1] = m4 + m5; c[1][0] = m6 + m7; c[1][1] = m2 + m3 + m5 - m7; return c; } else { int[][] a11 = new Sitelasen().sepaMatr( x, 0, 0 ); int[][] a12 = new Sitelasen().sepaMatr( x, 0, a ); int[][] a21 = new Sitelasen().sepaMatr( x, a, 0 ); int[][] a22 = new Sitelasen().sepaMatr( x, a, a ); int[][] b11 = new Sitelasen().sepaMatr( y, 0, 0 ); int[][] b12 = new Sitelasen().sepaMatr( y, 0, a ); int[][] b21 = new Sitelasen().sepaMatr( y, a, 0 ); int[][] b22 = new Sitelasen().sepaMatr( y, a, a ); int[][] m1 = matr.multiMatrix( matr.operaMatr( a11, a22, '-' ), matr.operaMatr( b21, b22, '+' ) ), m2 = matr.multiMatrix( matr.operaMatr( a11, a22, '+' ), matr.operaMatr( b11, b22, '+' ) ), m3 = matr.multiMatrix( matr.operaMatr( a21, a11, '-' ), matr.operaMatr( b11, b12, '+' ) ), m4 = matr.multiMatrix( matr.operaMatr( a12, a11, '+' ), b22 ), m5 = matr.multiMatrix( a11, matr.operaMatr( b12, b22, '-' ) ), m6 = matr.multiMatrix( a22, matr.operaMatr( b21, b11, '-' ) ), m7 = matr.multiMatrix( matr.operaMatr( a21, a22, '+' ), b11 ); int[][] c11 = matr.operaMatr( matr.operaMatr( m6, m4, '-' ), matr.operaMatr( m1, m2, '+' ), '+' ); int[][] c12 = matr.operaMatr( m4, m5, '+' ); int[][] c21 = matr.operaMatr( m6, m7, '+' ); int[][] c22 = matr.operaMatr( matr.operaMatr( m2, m3, '+' ), matr.operaMatr( m5, m7, '-' ), '+' ); return matr.mergMatr( c11, c12, c21, c22 ); } } int[][] mergMatr(int[][] x11, int[][] x12, int[][] x21, int[][] x22)//和并矩阵，将c11,c12,c21,c22合并成一个矩阵 { int[][] a = new int[2 * x11.length][2 * x11.length]; for (int i = 0; i < x11.length; i++) for (int j = 0; j < x11.length; j++) { a[i][j] = x11[i][j]; } for (int i = 0; i < x11.length; i++) for (int j = 0; j < x11.length; j++) { a[i][j + x11.length] = x12[i][j]; } for (int i = 0; i < x11.length; i++) for (int j = 0; j < x11.length; j++) { a[i + x11.length][j] = x21[i][j]; } for (int i = 0; i < x11.length; i++) for (int j = 0; j < x11.length; j++) { a[i + x11.length][j + x11.length] = x22[i][j]; } return a; } int[][] sepaMatr(int[][] x, int m, int n)//分解矩阵成矩阵块 { int[][] a = new int[x.length / 2][x.length / 2]; for (int i = 0; i < a.length; i++) for (int j = 0; j < a.length; j++) { a[i][j] = x[m + i][n + j]; } return a; } int[][] operaMatr(int[][] x, int[][] y, char f)//矩阵的加减 { if (f == '+') { int[][] a = new int[x.length][x.length]; for (int i = 0; i < x.length; i++) for (int j = 0; j < x.length; j++) a[i][j] = x[i][j] + y[i][j]; return a; } else if (f == '-') { int[][] a = new int[x.length][x.length]; for (int i = 0; i < x.length; i++) for (int j = 0; j < x.length; j++) a[i][j] = x[i][j] - y[i][j]; return a; } else { System.out.println( "error" ); int[][] a = new int[1][1]; return a; } } }
同时也有了一个可以跑起来的c++实现：
#include<iostream> #include<math.h> #include<fstream> using namespace std; ifstream infile("123.txt",ios::in); void Input(int n,int **A) { //infile>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) infile>>A[i][j]; } void Output(int n,int **A) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) cout<<A[i][j]<<' '; cout<<endl; } cout<<endl; } void Divide(int n,int **A,int **A11,int **A12,int **A21,int **A22) { int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) { A11[i][j]=A[i][j]; A12[i][j]=A[i][j+n]; A21[i][j]=A[i+n][j]; A22[i][j]=A[i+n][j+n]; } } void Unit(int n,int **A,int **A11,int **A12,int **A21,int **A22) { int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) { A[i][j]=A11[i][j]; A[i][j+n]=A12[i][j]; A[i+n][j]=A21[i][j]; A[i+n][j+n]=A22[i][j]; } } void Sub(int n,int **A,int **B,int **C) { int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]-B[i][j]; } void Add(int n,int **A,int **B,int **C) { int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j]; } void Mul(int n,int **A,int **B,int **M) { if(n==1) M[0][0]=A[0][0]*B[0][0]; else { n=n/2; int **A11,**A12,**A21,**A22; int **B11,**B12,**B21,**B22; int **M11,**M12,**M21,**M22; int **M1,**M2,**M3,**M4,**M5,**M6,**M7; int **T1,**T2; A11=new int*[n]; A12=new int*[n]; A21=new int*[n]; A22=new int*[n]; B11=new int*[n]; B12=new int*[n]; B21=new int*[n]; B22=new int*[n]; M11=new int*[n]; M12=new int*[n]; M21=new int*[n]; M22=new int*[n]; M1=new int*[n]; M2=new int*[n]; M3=new int*[n]; M4=new int*[n]; M5=new int*[n]; M6=new int*[n]; M7=new int*[n]; T1=new int*[n]; T2=new int*[n]; int i; for(i=0;i<n;i++) { A11[i]=new int[n]; A12[i]=new int[n]; A21[i]=new int[n]; A22[i]=new int[n]; B11[i]=new int[n]; B12[i]=new int[n]; B21[i]=new int[n]; B22[i]=new int[n]; M11[i]=new int[n]; M12[i]=new int[n]; M21[i]=new int[n]; M22[i]=new int[n]; M1[i]=new int[n]; M2[i]=new int[n]; M3[i]=new int[n]; M4[i]=new int[n]; M5[i]=new int[n]; M6[i]=new int[n]; M7[i]=new int[n]; T1[i]=new int[n]; T2[i]=new int[n]; } Divide(n,A,A11,A12,A21,A22); Divide(n,B,B11,B12,B21,B22); // cout<<"A11,A12,A21,A22"<<endl; // Output(n,A11);Output(n,A12);Output(n,A21);Output(n,A22); Sub(n,B12,B22,T1); // cout<<"B12-B22"<<endl; // Output(n,T1); Mul(n,A11,T1,M1); Add(n,A11,A12,T2); Mul(n,T2,B22,M2); Add(n,A21,A22,T1); Mul(n,T1,B11,M3); Sub(n,B21,B11,T1); Mul(n,A22,T1,M4); Add(n,A11,A22,T1); Add(n,B11,B22,T2); Mul(n,T1,T2,M5); Sub(n,A12,A22,T1); Add(n,B21,B22,T2); Mul(n,T1,T2,M6); Sub(n,A11,A21,T1); Add(n,B11,B12,T2); Mul(n,T1,T2,M7); Add(n,M5,M4,T1); Sub(n,T1,M2,T2); Add(n,T2,M6,M11); Add(n,M1,M2,M12); Add(n,M3,M4,M21); Add(n,M5,M1,T1); Sub(n,T1,M3,T2); Sub(n,T2,M7,M22); Unit(n,M,M11,M12,M21,M22); } } int main() { int n; cout<<"please input number n"<<endl; cin>>n; int **A,**B,**C; A=new int*[n]; B=new int*[n]; C=new int*[n]; for(int i=0;i<n;i++) { A[i]=new int[n]; B[i]=new int[n]; C[i]=new int[n]; } Input(n,A); cout<<"A Matrix is"<<endl; Output(n,A); Input(n,B); cout<<"B Matrix is"<<endl; Output(n,B); Input(n,C); //Output(n,C); Mul(n,A,B,C); cout<<"The Product of A and B is"<<endl; Output(n,C); // cout<<n<<endl; infile.close(); return 0; }
//就编程实来讲，以后我再也不会花费大量时间来训练类似的题目了
实现是一方面，更多的是你在历尽很多bug后，还是没有做出来能够跑起来的程序就很无奈
//本来自己还想做任意阶矩阵乘法的，实现不了，就降低了难度，想着做n*n阶矩阵，到最后只想做出来二的整数次幂阶的斯特拉森矩阵乘法。