方阵乘法递归与传统方式

Question

我实现了两种方阵乘法算法。 multiply_normal 是传统方式，使用 3 个嵌套 for 循环，multiply 是递归方式。

然而，即使 multiply_normal 算法给出了正确的输出，其他算法似乎无法输出正确的结果。

完整代码如下：

public class App {
    public static void main(String[] args) throws Exception {
        int a[][] = { { 1, 1, 1 }, { 2, 2, 2 }, { 3, 3, 3 } };
        int b[][] = { { 1, 1, 1 }, { 2, 2, 2 }, { 3, 3, 3 } };

        print(multiply_normal(a, b));

        System.out.println();

        print(multiply(a, b));

    }

    public static int[][] multiply(int[][] A, int[][] B) {

        int n = A.length;

        int[][] R = new int[n][n];

        if (n == 1)

            R[0][0] = A[0][0] * B[0][0];

        else {

            int[][] A11 = new int[n / 2][n / 2];
            int[][] A12 = new int[n / 2][n / 2];
            int[][] A21 = new int[n / 2][n / 2];
            int[][] A22 = new int[n / 2][n / 2];
            int[][] B11 = new int[n / 2][n / 2];
            int[][] B12 = new int[n / 2][n / 2];
            int[][] B21 = new int[n / 2][n / 2];
            int[][] B22 = new int[n / 2][n / 2];

            split(A, A11, 0, 0);
            split(A, A12, 0, n / 2);
            split(A, A21, n / 2, 0);
            split(A, A22, n / 2, n / 2);

            split(B, B11, 0, 0);
            split(B, B12, 0, n / 2);
            split(B, B21, n / 2, 0);
            split(B, B22, n / 2, n / 2);

            // P:=M2+M3−M6−M7
            int[][] C11 = add(multiply(A11, B11), multiply(A12, B21));

            // Q:=M4+M6
            int[][] C12 = add(multiply(A11, B12), multiply(A12, B22));

            // R:=M5+M7
            int[][] C21 = add(multiply(A21, B11), multiply(A22, B21));

            // S:=M1−M3−M4−M5
            int[][] C22 = add(multiply(A21, B12), multiply(A22, B22));

            // Step 3: Join 4 halves into one result matrix
            join(C11, R, 0, 0);
            join(C12, R, 0, n / 2);
            join(C21, R, n / 2, 0);
            join(C22, R, n / 2, n / 2);
        }

        // Step 4: Return result
        return R;
    }

    // Method 2
    // Function to subtract two matrices
    public int[][] sub(int[][] A, int[][] B) {
        //
        int n = A.length;

        //
        int[][] C = new int[n][n];

        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i = 0; i < n; i++)

            // Inner loop for columns
            for (int j = 0; j < n; j++)

                // Subtracting corresponding elements
                // from matrices
                C[i][j] = A[i][j] - B[i][j];

        // Returning the resultant matrix
        return C;
    }

    // Method 3
    // Function to add two matrices
    public static int[][] add(int[][] A, int[][] B) {

        //
        int n = A.length;

        // Creating a 2D square matrix
        int[][] C = new int[n][n];

        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i = 0; i < n; i++)

            // Inner loop for columns
            for (int j = 0; j < n; j++)

                // Adding corresponding elements
                // of matrices
                C[i][j] = A[i][j] + B[i][j];

        // Returning the resultant matrix
        return C;
    }

    // Method 4
    // Function to split parent matrix
    // into child matrices
    public static void split(int[][] P, int[][] C, int iB, int jB) {
        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)

            // Inner loop for columns
            for (int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)

                C[i1][j1] = P[i2][j2];
    }

    // Method 5
    // Function to join child matrices
    // into (to) parent matrix
    public static void join(int[][] C, int[][] P, int iB, int jB)

    {
        // Iterating over elements of 2D matrix
        // using nested for loops

        // Outer loop for rows
        for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++)

            // Inner loop for columns
            for (int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++)

                P[i2][j2] = C[i1][j1];
    }

    public static int[][] multiply_normal(int[][] A, int[][] B) {
        int n = A.length;

        int C[][] = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                C[i][j] = 0;
                for (int k = 0; k < n; k++) {
                    C[i][j] = C[i][j] + A[i][k] * B[k][j];
                }
            }
        }

        return C;
    }

    public static void print(int[][] a) {
        for (int i = 0; i < a.length; i++) {
            for (int k = 0; k < a.length; k++) {
                System.out.print(a[i][k] + " ");
            }
            System.out.println();
        }
    }
}

multiply_normal的输出（输入在main方法中）：

6 6 6 
12 12 12 
18 18 18

multiply的输出：

3 3 0 
6 6 0 
0 0 0

所以，我错在哪里了？我应该怎么做才能解决这个问题？如果你能帮助我，我将不胜感激。

Answer 1

简要回顾代码后：在给定的示例中，n/2 等于 1，这可能不是您想要的。
我希望这两种方法都能为均匀大小（比如 4x4）的矩阵产生相同的结果。

方阵乘法递归与传统方式

Square Matrix Multiply Recursive vs. Traditional Way

java

algorithm

recursion

matrix-multiplication