/**

  * 矩阵乘法求解

  * @author Administrator

  *

  */

 public class Strassen {

     public static final int NUMBER = 4;

     private static int[][] A;

     private static int[][] B;

     public Strassen() {

         A = new int[NUMBER][NUMBER];

         B = new int[NUMBER][NUMBER];

     }

     public int[][] starssen(int[][] A, int[][] B) {

         int divide_length = A.length / 2;

         // 定义一些中间变量

         int[][] result = new int[A.length][A.length];

         int[][] M1 = new int[divide_length][divide_length];

         int[][] M2 = new int[divide_length][divide_length];

         int[][] M3 = new int[divide_length][divide_length];

         int[][] M4 = new int[divide_length][divide_length];

         int[][] M5 = new int[divide_length][divide_length];

         int[][] M6 = new int[divide_length][divide_length];

         int[][] M7 = new int[divide_length][divide_length];

         int[][] C11 = new int[divide_length][divide_length];

         int[][] C12 = new int[divide_length][divide_length];

         int[][] C21 = new int[divide_length][divide_length];

         int[][] C22 = new int[divide_length][divide_length];

         int[][] A11 = new int[divide_length][divide_length];

         int[][] A12 = new int[divide_length][divide_length];

         int[][] A21 = new int[divide_length][divide_length];

         int[][] A22 = new int[divide_length][divide_length];

         int[][] B11 = new int[divide_length][divide_length];

         int[][] B12 = new int[divide_length][divide_length];

         int[][] B21 = new int[divide_length][divide_length];

         int[][] B22 = new int[divide_length][divide_length];

         if (A.length == 2) {

             result = multi(A, B, A.length);

         } else {

             // 首先将矩阵A,B分为4块

             for (int i = 0; i < divide_length; ++i) {

                 for (int j = 0; j < divide_length; ++j) {

                     A11[i][j] = A[i][j];

                     A12[i][j] = A[i][j + divide_length];

                     A21[i][j] = A[i + divide_length][j];

                     A22[i][j] = A[i + divide_length][j + divide_length];

                     B11[i][j] = B[i][j];

                     B12[i][j] = B[i][j + divide_length];

                     B21[i][j] = B[i + divide_length][j];

                     B22[i][j] = B[i + divide_length][j + divide_length];

                 }

             }

             // 计算M1

             M1 = starssen(A11, sub(B12, B22, divide_length));

             // 计算M2

             M2 = starssen(add(A11, A12, divide_length), B22);

             // 计算M3

             M3 = starssen(add(A21, A22, divide_length), B11);

             // 计算M4

             M4 = starssen(A22, sub(B21, B11, divide_length));

             // 计算M5

             M5 = starssen(add(A11, A22, divide_length), add(B11, B22, divide_length));

             // 计算M6

             M6 = starssen(sub(A12, A22, divide_length), add(B21, B22, divide_length));

             // 计算M7

             M7 = starssen(sub(A11, A21, divide_length), add(B11, B12, divide_length));

             // 计算C11,C12,C21,C22

             C11 = add(sub(add(M5, M4, divide_length), M2, divide_length), M6, divide_length);

             C12 = add(M1, M2, divide_length);

             C21 = add(M3, M4, divide_length);

             C22 = sub(sub(add(M5, M1, divide_length), M3, divide_length), M7, divide_length);

             // 合并C11,C12,C21,C22到C

             for (int i = 0; i < divide_length; ++i) {

                 for (int j = 0; j < divide_length; ++j) {

                     result[i][j] = C11[i][j];

                     result[i][j + divide_length] = C12[i][j];

                     result[i + divide_length][j] = C21[i][j];

                     result[i + divide_length][j + divide_length] = C22[i][j];

                 }

             }

         }

         return result;

     }

     public static int[][] initial() {

         int [][] result = new int[NUMBER][NUMBER];

         for (int i = 0; i < NUMBER; ++i) {

             for (int j = 0; j < NUMBER; ++j) {

                 // 采用Math生成1~10之间的随机数

                 result[i][j] = (int)(Math.random()*10);

             }

         }

         return result;

     }

     public void output(int[][] result) {

         for (int b[] :result) {

             for (int temp : b) {

                 System.out.print(temp + " ");

             }

             System.out.println();

         }

     }

     /**

      * 蛮力求解矩阵乘法

      * @param a：矩阵a  n*n

      * @param b：矩阵b  n*n

      * @param n： 矩阵大小

      */

     public int[][] multi(int a[][], int b[][], int n) {

         int result[][] = new int[n][n];

         for (int i = 0; i < n; ++i) {

             for (int j = 0; j < n; ++j) {

                 result[i][j] = 0;

                 for (int k = 0; k < n; ++k) {

                     result[i][j] += a[i][k] * b[k][j];

                 }

             }

         }

         return result;

     }

     /**

      * 矩阵加法

      * @param a

      * @param b

      * @param n

      * @return

      */

     public int[][] add(int a[][], int b[][], int n) {

         int result[][] = new int[n][n];

         for (int i = 0; i < n; ++i) {

             for (int j = 0; j < n; ++j) {

                 result[i][j] = a[i][j] + b[i][j];

             }

         }

         return result;

     }

     /**

      * 矩阵减法

      * @param a

      * @param b

      * @param n

      * @return

      */

     public int[][] sub(int a[][], int b[][], int n) {

         int result[][] = new int[n][n];

         for (int i = 0; i < n; ++i) {

             for (int j = 0; j < n; ++j) {

                 result[i][j] = a[i][j] - b[i][j];

             }

         }

         return result;

     }

     public static void main(String[] args) {

         Strassen s = new Strassen();

         A = initial();

         B = initial();

         s.output(A);

         System.out.println("----------------------");

         s.output(B);

         System.out.println("----------------------");

         s.output(s.multi(A, B, NUMBER));

         System.out.println("----------------------");

         int K[][] = new int[2][2];

         K = s.starssen(A, B);

         s.output(K);

     }

 }