遞歸求和一個二維數組的元素？

我是算法初學者，剛開始閱讀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

遞歸求和一個二維數組的元素？

回答

相關問題