递归求和一个二维数组的元素？

我是算法初学者，刚开始阅读Michael Rich的“Java中的数据结构和算法”。他提出了一个名为“BinarySum（A，i，n）”的基于二元递归的函数。递归求和一个二维数组的元素？

BinarySum(A,i,n) 
Input:An array A and integer i and n 
Output: The sum of n integers in A starting and index i 
if n==1 then 
    return A[i]; 
return BinarySum(A,i,[n/2])+BinarySum(A,i+[n/2],[n/2])

而且我们最初将通过BinarySum（A，0，n）开始呼叫。

在接下来的练习中，有一个问题要求我描述一种使用递归来添加一个n * n二维整数数组的所有元素的方法。他给出的提示是我们可以通过使用两个递归调用来遵循BinarySum（A，i，n）的风格。

我被困在这个，我可以想到像n * n矩阵的每一行循环的解决方案，然后为每一行，我打电话BinarySum（A，我，n），然后相加在一起。但我真的不认为这是这个练习的目的。

想过其他可能的解决方案，但我坚持使用递归实现它。专家可以提供一些提示吗？谢谢。

来源

2014-09-22 Kevin

使用的Java代码，

这是BinarySum二维矩阵，假设你有N1行和n2列，因此，总和将等于N1/2第一行的总和和最后n1/2行。对于每一行，总和将被划分成N2/2个第一列和N 2/2最后一列，

public static void main(String[] args) { 

    int[][] data = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}; 
    System.out.println(sum(data, 0, 3, 0, 4)); 
} 

public static int sum(int[][] data, int x, int n1, int y, int n2) { 

    if (n1 == 1 && n2 == 1) { 
     return data[x][y]; 
    } 
    if (n1 == 1) { 
     return sum(data, x, n1, y, (n2/2)) + sum(data, x, n1, y + (n2/2), n2 - (n2/2)); 
    } else { 
     return sum(data, x, (n1/2), y, n2) + sum(data, x + (n1/2), n1 - (n1/2), y, n2); 
    } 
}

输出：

来源

2014-09-22 09:25:41

我不会给你伪代码。我想你可以在解释后很容易地弄清楚。用类似的递归技术有多种方法可以实现这一点。

对于2-d阵列，您现在递归分支成4家支行，而不是2.你可以认为这是划分网格为4个子网格和递归总结起来。这基本上意味着，现在您的递归函数BinarySum（A，i，j，n）将从单元格（i，j）开始总计n行和n列（确保在n时适当地点处理地板和天花板很奇怪）。
另一种看待这种情况的方法是有两个函数，一个用于递归求和行，另一个用于递归求和列。所以你的BinarySum（A，i，n）将递归地将行号为i的所有行累加到行号为n的行上。当n = 1时，你的问题就会归结为一维数组的所有元素的总和（使用你已经有的函数来计算）。

来源

2014-09-22 08:52:26

public static int deepSum(int[][] data){ 
    //n*n 
    return deepSum(data, data.length, data.length); 
} 
private static int deepSum(int[][] data, int n, int m){ 
    if (n ==1) 
     return deepSumCol(data ,m, 0); 
    else 
     return deepSum(data, n-1,m) + deepSumCol(data, m, n-1); 
} 

private static int deepSumCol(int[][] data, int n ,int m){ 
    if (n ==1) 
     return data[m][0]; 
    else{ 
     return deepSumCol(data, n -1,m) + data[m][n-1]; 
    } 

}

来源

2016-08-04 03:30:48

递归求和一个二维数组的元素？

回答

相关问题