代碼的工作非常緩慢，不打印輸出

Question

我的工作Project Euler problem #2：

在Fibonacci序列中的每個新名詞是通過將前兩個方面產生 。通過 開始1和2中，第一10項將是：

1，2，3，5，8，13，21，34，55，89，...

查找的總和所有序列中的偶數項不超過四百萬。

我的代碼：

public class Two { 
    public static void main(String[] args) { 
     Two obj = new Two(); 
     int sum = 0, i = 1; 

     while (obj.fibonacci(i) < 4000001) {  
      if (obj.fibonacci(i) % 2 == 0) { 
       sum += obj.fibonacci(i); 
       i++; 
      } 
     } 
     System.out.println(sum); 
    } 

    public int fibonacci(int n) { 
     if (n == 0) { 
      return -1; 
     } 
     if (n == 1) { 
      return 1; 
     } 
     if (n == 2) { 
      return 3; 
     } else { 
      return fibonacci(n - 1) + fibonacci(n - 2); 
     } 
    } 
} 

請幫助我，什麼是錯的代碼，當我運行它。它不顯示在控制檯上的輸出和總時間將超過5分鐘

感謝

Answer 1

你被困在一個無限循環那裏你只能增加我時其mod 2等於0.您需要將您的i ++降低。

while (obj.fibonacci(i) <= 4000000) { 
    if (obj.fibonacci(i) % 2 == 0) { 
     sum += obj.fibonacci(i); 
    } 
    i++; 
} 

正如其他意見所述，這不是解決斐波納契問題的最佳方法，但它解決了您的錯誤/問題。如果你不明白爲什麼，並且你會注意到你使用了很多已經解決的遞歸調用，你應該通過一個調試器。既然你在代碼中多次調用它（在while語句和if語句中），你已經增加了處理時間。

這是您的通話斐波納契的樣本，請注意您如何調用該方法斐波納契數相同上多次：

1 
2 
3 
2 
1 
4 
3 
2 
1 
2 
5 

Answer 2

我認爲這個問題在已經明確。 所有偶數總和應該低於400萬，還是最大偶數總數應該低於400萬？

Answer 3

你的問題之一是你過度使用遞歸。您應該嘗試存儲結果以避免每次重新計算所有內容。

Answer 4

雖然您的解決方案可能會起作用，但它會重新計算已經獲得的結果，因此費用相當高。

在這種情況下使用遞歸，爲了得到值fibonacci(4)，您遞歸地添加您以前已經計算過的fibonacci(3)和fibonacci(2)的值。

在列表中存儲你的價值觀，而不是重新計算所有的時間嘗試：

List<Long> fibonacci = new ArrayList<Long>(); 

// First terms 
fibonacci.add(-1L); // 0 is dummy, sequence starts at 1 
fibonacci.add(1L); 
fibonacci.add(2L); 

for (int i = 3; fibonacci.get(i - 1) + fibonacci.get(i - 2) < 4000001; i++) { 
    long u = fibonacci.get(i - 1) + fibonacci.get(i - 2); 
    fibonacci.add(i, u); 
} 

使用這種技術，你可以計算斐波那契序列高達400萬，在不到2秒（因爲我想在我的電腦）。

然後，只需添加一些代碼來計算循環內的總和:-)

Answer 5

如前所述，++需要我的支票外均勻度被移動或者你會停留在循環。

但是你有一個稍大的問題。該fibonacci sequence開始與

... 1，2，3，...

地方，而不是你有... 1，3，...這意味着你會得到不正確的結果。你應該有：

// ... 
if (n == 2) { 
    return 2; 
// ... 

Answer 6

我覺得你可以改善Fibonacci會的方式：

def fib(x) 
     if(x==0 or x==1) then 
       return x; 
     end 
     a,b = 0,1 
     (x-1).times{ a,b = b,a+b; } 
     return b; 
end 

換句話說轉換遞歸迭代。

Answer 7

在這種情況下沒有理由存儲整個斐波那契數列。您可以簡單地沿着序列「走」一些局部變量，並按照總結進行總結。

int fib2 = 0, fib1 = 1, fib0 = fib1 + fib2; 
int sum = 0; 

while (fib0 <= N) 
{ 
    if (fib0 % 2 == 0) sum += fib0; 
    fib2 = fib1; 
    fib1 = fib0; 
    fib0 = fib1 + fib2; 
} 

Answer 8

對@ Blastfurnace解決方案的改進是指出每個第三個值都是偶數。

public static void main(String[] args) { 
    long sum = 0; 
    int runs = 30000; 
    for (int i=0;i< runs;i++) { 
     sum = sumEvenFib(); 
    } 
    long start = System.nanoTime(); 
    for (int i=0;i< runs;i++) { 
     sum = sumEvenFib(); 
    } 
    long time = System.nanoTime() - start; 
    System.out.println(sum+" took "+time/runs+" ns avg"); 
} 

private static long sumEvenFib() { 
    int sum = 0; 
    for(int f1 = 1, f2 = 2;f2 < 4000001;) { 
     sum += f2; 
     int f3 = f1 + f2; 
     f1 = f3 + f2; 
     f2 = f1 + f3; 
    } 
    return sum; 
} 

在我的舊labtop上，這需要約40納秒。或0.000000040秒。