遞歸列表<Integer>的總和

Question

各位程序員你好。

我有一個非常愚蠢的問題..我應該總結列表中的所有整數，遞歸。我知道有一個更簡單的方法可以做到這一點，而且我也實現了該方法（請參見下面的課程）。但是這個任務的意義在於我必須將列表分成兩半，然後在兩半上遞歸計算總和，最後我只返回half1 + half2。

問題是高級方法不返回所有值的總和。誰能幫幫我嗎？

方法和是簡單的方法。夏季（丹麥語彙總）是更先進的方法。

package opgave1; 

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 
import java.util.Random; 

public class BinærSøgning { 
    public static void main(String[] args) { 
     Random random = new Random(); 
     int tal = 3; 

     List<Integer> liste = new ArrayList<Integer>(); 
     for (int i = 0; i < 10; i++) 
      liste.add(random.nextInt(10)); 
     Collections.sort(liste); 

     System.out.println(liste); 
     //  System.out.println(binærSøgning(liste, 0, tal)); 
     System.out.println(summer(liste, 0)); 
    } 

    public static int binærSøgning(List<Integer> liste, int start, int find) { 
     if (liste.size() > 0) { 
      int midt = liste.size()/2; 
      if (liste.get(midt) == find) 
       return start + midt; 
      else if (liste.size() > 1) { 
       if (find < liste.get(midt)) 
        return binærSøgning(liste.subList(0, midt), start, find); 
       else 
        return binærSøgning(liste.subList(midt + 1, liste.size()), start + midt + 1, find); 
      } 
     } 
     return -1; 
    } 

    public static int sum (List<Integer> list, int i) 
    { 
     if (i == list.size()) 
      return 0; 
     else 
      return list.get(i) + sum(list, i+1); 
    } 


    public static int summer(List<Integer> list, int start){ 
     int right = 0; 
     int left = 0; 

     if(start == list.size()){ 
      return 0; 
     } else { 

      int mid = list.size()/2; 
      if(start < mid){ 
       left += list.get(start) + summer(list.subList(0, mid), start+1); 
      } else if(mid < list.size()){ 
       right += list.get(mid) + summer(list.subList(mid+1, list.size()), mid+1); 
      } 
     } 
     return right + left; 
    } 


} 

Answer 1

對於兩個基本情況，Ii更容易，如果使用子列表，則不需要額外的「開始」參數。 （因爲它是作業，我不會填寫細節。）

public static int summer(List<Integer> list) { 
    //base 1 
    if (list.size() == 0) { 

    } 
    //base 2 
    else if (list.size() == 1) { 

    } 
    else 
    { 
     //no need for if statements now! 
     int left = summer(list.sublist(/* */)) 
     int right = summer(list.sublist(/* */)) 
     return left + right; 
    } 
} 

Answer 2

首先，如果您所需要做的只是使用遞歸，則不需要將列表減半。列表元素的總和是它的第一個元素+列表其餘元素的總和。

二，您的方法太複雜。如果列表爲空，則列表的元素總數爲0，唯一元素包含1個元素，如果方法的結果包含多於1，則該方法的結果總和應用於兩個子列表。您不需要任何啓動參數。

這應該讓你開始。

編輯：自奧斯卡·洛佩茲給你答案，但我覺得它太複雜了，這裏是我的：

public static int sum(List<Integer> list) { 
    if (list.isEmpty()) { 
     return 0; 
    } 
    else if (list.size() == 1) { 
     return list.get(0); 
    } 
    else { 
     int half = list.size()/2; 
     return sum(list.subList(0, half)) + sum(list.subList(half, list.size())); 
    } 
} 

Answer 3

你確定你要分割清單？通常，當你得到這個任務的功課，意思是一樣的東西：

public static int sum(List<Integer> l,int start) { 
if (start==l.size()) return 0; 
return l.get(start)+sum(l,start+1); 
} 

Answer 4

你錯過了列表的元素，當你發送的遞歸啓動+ 1。

 left += list.get(start) + summer(list.subList(0, mid), start+1); 

你還是送

 left += list.get(0) + summer(list.subList(1, mid), 0); 

和

 right += list.get(mid) + summer(list.subList(mid+1, list.size()), 0); 

我不認爲有必要發送任何初始值。每次遞歸都應該取0代替開始。

Answer 5

我認爲它可以以更簡單的方式來解決，通過使兩個區域的第一個和最後一個索引的軌道，就像這樣：

public static int sum(List<Integer> list, int i, int j) { 
    if (i == j) 
     return list.get(i); 
    int half = (i + j)/2; 
    return sum(list, i, half) + sum(list, half + 1, j); 
} 

它被稱爲是這樣的：

List<Integer> list = Arrays.asList(1, 2, 3); 
System.out.println(sum(list, 0, list.size()-1)); 

對於非空列表，它將正常工作。如果列表爲空，則在致電sum之前，您需要檢查它。

Answer 6

我想知道獲取列表「一半」的原因。
對於這個問題的解決方案是獨一無二的：

public int sum_list(List<Integer> list) { 
    if (list == null || list.isEmpty()) { 
     return 0; 
    } 
    return list.remove(0) + sum_list(list); 
}