使用递归对二维数组中的整数求和？

Question

我需要一些帮助来解决这个问题。我必须使用递归对二维数组中的所有整数求和。以下是我自己设法做的事情，但我被困住了。此代码生成总和 14，应该是 18。

public class tablerecursion {
    public static void main(String[] args) {
        int[][] tabell = new int[][] { { 1, 2, 3 }, { 3, 2, 1 }, { 1, 2, 3 } };
        int sum = rec(tabell, 2, 2);
        System.out.println(sum);
    }

    static int rec(int[][] table, int n, int m) {
        if (m == 0)
            return table[n][0];
        if (n == 0)
            return table[0][m];
        System.out.println("n:" + n + "  m:" + m);

        return rec(table, n - 1, m) + rec(table, n, m - 1);
    }
}

有什么建议吗？基本情况是错误的吗？还是递归方法错误？

Answer 1

我会使用两个函数来解决这个问题。首先创建一个可以递归求和单个（1d）数组的函数。编写一个函数，对外部数组上的前一个函数进行递归求和。

请记住 table[N] 本身就是一个数组。您不必一次性访问所有内容。

Answer 2

你的递归逻辑是错误的。

你得到 14 因为你调用

f(2,2)=f(2,1) + f(1,2)= (f(2,0)+f(1,1)) + (f(1,1) +f(0,2))

f(0,2) 是你的基本情况，3
f(0,2) 是您的基本情况，1
f(1,1) = f(0,1)+f(1,0)=2+3=5

所以总和是 3+1+5+5=14

递归的正确逻辑是 单个递归函数：

以坐标 (x,y) 开始并以 (z,w) 结束的 2x2 数组的总和是 3 个元素的总和：

  xxxxxxxxxx
  xxxxxxxxxx
  xxxxxxxxxx
  yyyyyyyyyN

• 由所有元素组成的数组的总和除最后一行之外的行（上例中的 xxxx-s）
  因此 (x,y) 到 (z,2-1)。

• 由最后一行组成的数组的总和（示例中的右下角 - yyyyy-s 除外）
  因此， (x,w) 到 (z-1,w)

• 坐标 (z,w) 处的数字

• 基本情况是，如果 y>w（零线），则总和为零；
  if x

理想情况下，这实际上是一个双重递归。一种是使用辅助“添加行”函数递归计算所有行的总和 - 当然这也是递归实现的。

Answer 3

其他几个答案建议使用 1D 例程对 2D 数组角上的元素相邻的列和行求和

，但是

将 2D 数组切成四个更小也是有效的二维数组，并以这种方式递归。当然，停止条件是当输入是 1x1 2D 数组时，此时答案很简单。

后续

除非数组尺寸为 2^mx 2^m ，否则这会遇到麻烦；任何其他东西，迟早你都会遇到 Nx1 或 1xN 输入，并且你根本无法将其切成四个子数组。所以无论如何你最终都必须处理一维输入。

Answer 4

看这里是我要提交的内容，并指出递归解决方案不适用：

public static void Main()
{
        var a = new int[][] {  new int[] {1,2,3},
                               new int[] {3,2,1},
                               new int[] {1,2,3}  }; 
        int result = a.Sum(row => row.Sum());
        Console.WriteLine(result);
}

正确比简单地认为正确更好。

Answer 5

这是一个可能的解决方案的示例。如果 java 编译器可以优化尾递归，那么它将与迭代解决方案一样高效。现在它非常积极地吃堆栈。

public static long countSum (int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    return countSum (matrix, 0, 0, 0, matrix.length, matrix[0].length);
}

private static long countSum (int[][] matrix, long acc, int curI, int curJ, int maxI, int maxJ) {
    if (curI >= maxI) {
        return acc;
    }
    if (curJ >= maxJ) {
        return countSum(matrix, acc, curI + 1, 0, maxI, maxJ);
    }
    return countSum(matrix, acc + matrix[curI][curJ], curI, curJ + 1, maxI, maxJ);

}

Answer 6

public int sumarmatriz(int matriz[][],int i,int j)
{
    if(i==0 && j==0){
        return matriz[i][j];
    }
    else if(j==0){
        return sumarmatriz(matriz,i-1,matriz.length-1)+matriz[i][j];
    }
    else{
        return sumarmatriz(matriz,i,j-1)+matriz[i][j];
    }
}

Answer 7

如果您想一次性访问所有内容，我认为您需要这种方法：

public class Array {
  public static void main(String[] args){
    int[][] A = {{1,2,3,4},{1,2,3,4},{1,2,3,4},{1,2,3,4}};
    System.out.print(TwoDSum(A,4,4));
  }
  public static int TwoDSum(int A[][], int n,int m) {
    if(n==1 && m==1) return A[0][0];
    if(m==0){
      n--;
      m=A[n].length;
    }
    return TwoDSum(A,n,m-1)+A[n-1][m-1];
  }
}