代码的工作非常缓慢，不打印输出

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秒。