方形矩阵乘法递归在Java中使用分而治之？ [英] Square Matrix Multiply Recursive in Java using Divide and Conquer?

问题描述

我有一个学校项目，以创建2个版本一个java code是将两个方阵。为了更方便，他们只需要2×2，4×4的工作，8×8等我们有一个伪code，看起来像这样（从同一本书在这里从另一个问题采取最有可能的）：

I have a school project to create 2 versions of a javacode that multiplies two square matrices. To make it easier, they only have to work for 2x2, 4x4, 8x8 etc. We have a pseudo code that looks like this (taken from another question in here from the same book, most likely):

我们是要去变成code本（我只知道的Java），我们必须实现分区的一部分。我们可以选择，如果我们想要一个正常的数组或多维数组。在code的两个版本是这样的：一个是要创建分区子矩阵（阵列），第二个是要使用数组索引，并通过他们失望

We are gonna turn this into code (i only know Java), and we have to implement the partition part. We can choose if we want a normal array or a multidimensional array. The two versions of the code goes like this: One is gonna create sub matrices (arrays) in the partition, and the second is gonna use array indexes and pass them down.

什么即时通讯最困惑的就是在底部随机使用阵列+阵列和INT + INT的。我得到的code的想法，但我不知道如何正确地实现这一点。

What Im most confused about is the random use of array + array and int + int in the bottom. I get the idea of the code, but I have no idea how to implement this correctly.

任何人都可以点我在正确的方向？

Can anyone point me in the right direction??

推荐答案

这里是没有应对矩阵的Java实现。这仅适用于n×n的矩阵，使N = 2 ^ x的。

here is a Java implementation without coping the matrices. This works only for nxn matrices so that n= 2^x.

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

    return  matrixMultiplication(
            A, B, 0, 0, 
            0,0, A.length);

}


public static int[][] matrixMultiplication(
        int[][] A, int[][] B, int rowA, int colA, 
        int rowB, int colB, int size){

    int[][] C= new int[size][size];

    if(size==1)
        C[0][0]= A[rowA][colA]*B[rowB][colB];

    else{

        int newSize= size/2;
        //C11
         sumMatrix(C, 

            matrixMultiplication(A, B, rowA, colA, rowB, colB, newSize),
            matrixMultiplication(A, B, rowA, colA+newSize, rowB+ newSize, colB, newSize),
        0, 0);

         sumMatrix(C, 

            matrixMultiplication(A, B, rowA, colA, rowB, colB + newSize, newSize),
            matrixMultiplication(A, B, rowA, colA+newSize, rowB+ newSize, colB+newSize, newSize),
        0, newSize);

         sumMatrix(C, 

            matrixMultiplication(A, B, rowA+ newSize, colA, rowB, colB, newSize),
            matrixMultiplication(A, B, rowA+ newSize, colA+newSize, rowB+ newSize, colB, newSize),
        newSize, 0);

         sumMatrix(C, 

            matrixMultiplication(A, B, rowA+ newSize, colA, rowB, colB+newSize, newSize),
            matrixMultiplication(A, B, rowA+ newSize, colA+newSize, rowB+ newSize, colB+newSize, newSize),
        newSize, newSize);
    }

    return C;

}


private static void sumMatrix(int[][] C, int[][]A, int[][]B,int rowC, int colC){
    int n=A.length;
    for(int i =0; i<n; i++){
        for(int j=0; j<n; j++)  
            C[i+rowC][j+colC]=A[i][j]+B[i][j];
    }

}

这篇关于方形矩阵乘法递归在Java中使用分而治之？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！