2d數組遞歸方法（java）

Question

我必須編寫一個方法， 該方法接收二維整數數組的參數。該方法返回具有最高和的總和的行數。 我只能使用遞歸！沒有循環允許！ - 當然我需要做一個私人的方法，將一行作爲一個單一的數組求和，然後我必須做另一個比較行的私有方法，但它並沒有真正的工作，因爲我寫的方法只適用於一維數組，我需要從一個二維數組比較行..

感謝所有樣的幫助..

我的一些代碼：

private int rowSum(int[] array, int index) {//the sum of an array(1d array) 
     if (index == array.length) 
      return 0; 
     else 
      return array[index] + rowSum(array, index + 1); 
    } 

**public int maxRow(int[][] a){------!!!---the problem... 

    }** 

Answer 1

代碼：

public class MainClass { 
    static int contents[][] = { {1, 2 , 3, 4} , { 4, 5, 8, 7}, { 4, 2, 8, 7}, { 4, 5, 0, 7} }; 
    public static void main(String[] args) 
    { 
     System.out.println(getIndexOfRowWithHighestSum(contents, 0, 0)); 
    } 
    public static int getIndexOfRowWithHighestSum(int[][] twoDAray, int currentIndex,int indexWithHighestSum){ 
     if(currentIndex>=twoDAray.length){ 
      return indexWithHighestSum; 
     } 
     int sum1 = getSumOfArray(twoDAray[currentIndex], 0) ; 
     int sum2 = getSumOfArray(twoDAray[indexWithHighestSum], 0); 

     indexWithHighestSum = (sum1 > sum2)?currentIndex:indexWithHighestSum; 

     return getIndexOfRowWithHighestSum(twoDAray, currentIndex+1,indexWithHighestSum); 
    } 
    public static int getSumOfArray(int[] array, int currentIndex){ 
     if(currentIndex>=array.length){ 
      return 0; 
     } 
     return array[currentIndex]+getSumOfArray(array,currentIndex+1); 
    } 
} 

Answer 2

我會嘗試調用一個遞歸方法從主要參數：

• 陣列[] []
• 當前列索引
• 當前行的索引
• 當前行總和
• 最高行索引
• 最高行和

我得到它的工作在這裏，所以這絕對有可能。這是約15行代碼。 祝你好運！

Answer 3

擔任首發的運動，試圖改變自己的rowSum功能的簽名改成這樣：

int rowSum(int[] array, int index, int sumSoFar) 

你應該能夠編寫功能使得遞歸部分的回報表現僅僅是一個遞歸調用：

if (...) // exit case 
    return sumSoFar; 
else 
    return rowSum(...); 

（現在這是一個尾遞歸執行。）

武裝與心態，想想你會怎麼寫：

int indexOfMaxValue(int[] array, int index, int maxValueSoFar, int maxIndexSoFar) 

一旦你得到這些，你應該能夠將這兩個概念結合在一起。

Answer 4

下面的代碼準備運行和測試：

public class RecursionSum { 
    /* Sum a row until <code>index</code>. */ 
    private static int rowSum(int[] a, int index) { 
     if (index == 0) { return a[0]; } 
     // add the current element to the recursive sum 
     return a[index] + rowSum(a, index - 1); 
    } 

    /* Sum a whole row. */ 
    private static int rowSum(int[] a) { 
     return (a.length == 0) ? 0 : rowSum(a, a.length - 1); 
    } 

    /* Find the index of the array having the max sum until <code>index</code>. */ 
    private static int maxRow(int[][] a, int index){ 
     if (index == 0) { return 0; } 
     // compare the current row's sum with the recursive max row's sum, 
     // update index when it's a new winner 
     int maxIndex = maxRow(a, index - 1); 
     return (rowSum(a[maxIndex]) < rowSum(a[index])) ? index : maxIndex; 
    } 

    /* Find the index of the array having the max sum. */ 
    public static int maxRow(int[][] a){ 
     return a.length == 0 ? 0 : maxRow(a, a.length - 1); 
    } 

    /* very simple test */ 
    public static void main(String[] args) { 
     int a1[][] = {}; 
     int a2[][] = {{1, 2, 3, 4}}; 
     int a3[][] = {{ 1, 2, 3, 4}, {8, 90}, {5, 6, 7}, {300, 4, 9}, {4, 6, 12}}; 
     System.out.println(maxRow(a1)); 
     System.out.println(maxRow(a2)); 
     System.out.println(maxRow(a3)); 
    } 
}