我开始做分而治之的概念,遇到矩阵乘法。我可以使用for循环执行以下代码,但对于递归实践,我又采取了一步,并尝试自行完成。
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
int bigA[][];
int bigB[][];
public Codechef (int bigA[][],int bigB[][]) {
this.bigA = bigA;
this.bigB = bigB;
}
public int[][] recursiveMatrixMultipy (int A[][],int B[][],int n) {
int c[][] = new int[n][n];
if (n == 1) {
c[0][0] = bigA[ A[0][0] ][ A[1][0] ] * bigB[ B[0][0] ][ B[1][0] ];
} else {
int r_start = A[0][0];
int r_end = A[0][1];
int c_start = A[1][0];
int c_end = A[1][1];
int r_mid = r_start + (r_end - r_start) / 2;
int c_mid = c_start + (c_end - c_start) / 2;
int a11[][] = {{r_start,r_mid},{c_start,c_mid}};
int a12[][] = {{r_start,{c_mid + 1,c_end}};
int a21[][] = {{r_mid + 1,r_end},c_mid}};
int a22[][] = {{r_mid + 1,c_end}};
int b11[][] = {{r_start,c_mid}};
int b12[][] = {{r_start,c_end}};
int b21[][] = {{r_mid + 1,c_mid}};
int b22[][] = {{r_mid + 1,c_end}};
System.out.println ("A " + Arrays.deepToString(A));
System.out.println ("B " + Arrays.deepToString(B));
System.out.println (n);
System.out.println ("a11 " + Arrays.deepToString(a11));
System.out.println ("a12 " + Arrays.deepToString(a12));
System.out.println ("a21 " + Arrays.deepToString(a21));
System.out.println ("a22 " + Arrays.deepToString(a22));
int c11[][] = addMatrix(recursiveMatrixMultipy (a11,b11,n / 2),recursiveMatrixMultipy (a12,b21,n / 2) );
int c12[][] = addMatrix(recursiveMatrixMultipy (a11,b12,b22,n / 2) );
int c21[][] = addMatrix(recursiveMatrixMultipy (a21,recursiveMatrixMultipy (a22,n / 2) );
int c22[][] = addMatrix(recursiveMatrixMultipy (a21,n / 2) );
c = merge (c11,c12,c21,c22);
}
return c;
}
public int[][] addMatrix (int A[][],int B[][]) {
int n = A[0].length;
int c[][] = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = A[i][j] + B[i][j];
}
}
return c;
}
public int[][] merge (int c11[][],int c12[][],int c21[][],int c22[][]) {
int n_C = c11[0].length;
int n = 2 * n_C;
int C[][] = new int[n][n];
for (int i = 0; i < n_C; i++) {
for (int j = 0; j < n_C; j++) {
C[i][j] = c11[i][j];
C[i][j + n_C] = c12[i][j];
C[i + n_C][j] = c21[i][j];
C[i + n_C][j + n_C] = c22[i][j];
}
}
return C;
}
public static void main (String[] args) throws java.lang.Exception
{
int matrix[][] = {{1,2,3,4},{1,4}};
int n = matrix[0].length;
//checks if power of 2
if ((n > 0) && ( ( n & ( n - 1 ) ) == 0 ) ) {
Codechef matrixDivAndConquer = new Codechef (matrix,matrix);
int A[][] = {{0,n - 1},{0,n - 1}};
int B[][] = {{0,n - 1}};
int C[][] = matrixDivAndConquer.recursiveMatrixMultipy (A,B,n);
System.out.println (Arrays.deepToString(C));
}
}
}
A [[0,3],[0,3]]
B [[0,3]]
4
a11 [[0,1],1]]
a12 [[0,[2,3]]
a21 [[2,1]]
a22 [[2,3]]
A [[0,1]]
B [[0,1]]
2
a11 [[0,0],0]]
a12 [[0,[1,1]]
a21 [[1,0]]
a22 [[1,1]]
A [[0,3]]
B [[2,2]]
a12 [[0,[3,3]]
a21 [[1,2]]
a22 [[1,3]]
2
a11 [[0,3]]
A [[2,1]]
2
a11 [[2,2],0]]
a12 [[2,1]]
a21 [[3,0]]
a22 [[3,1]]
A [[2,2]]
a12 [[2,3]]
a21 [[3,2]]
a22 [[3,3]]
2
a11 [[2,3]]
现在,这似乎无法给我正确的答案。我在这里想念什么?
我只是在输出之间粘贴了一些内容,以便更容易理解我在做什么。 我的输出:
[[24,34,24,34],[24,34]]
正确回答上述矩阵:
[[10,20,30,40],[10,40]]