当我运行我的程序计算所有偶数斐波那契数之和时，为什么会得到负输出？

Question

背景：

我正在研究 Project Euler 问题 #2，我有一个 class 来解决这个问题。对于那些以前没有这样做过的人来说，这就是问题所在：

斐波那契数列中的每一项都是通过添加前两项生成的。从 1 和 2 开始，前 10 项将是： 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 考虑斐波那契数列中不超过四百万的项，求偶数项之和

问题：

我已经构建了解决给定问题的程序，但是当我运行它时，我得到值 -1833689714。这不应该是返回的值，因为我只对正数求和并且没有执行我所知道的乘法。我该如何解决这个问题？

我的代码

import java.util.ArrayList;

class Main {
  public static void main(String[] args) {

    int answer = resultsSum(fibonacci(4000000));
    System.out.println(answer);

  }

  public static int resultsSum(ArrayList<Integer> resultList){

    int total = 0;
    for(Integer r : resultList){

      total += r.intValue();

    }

    return total;

  }

  public static ArrayList<Integer> fibonacci(int n){

    ArrayList fibEvens = new ArrayList<Integer>();
    int a = 1;
    int b = 2;
    fibEvens.add(b);

    for(int i = 1; i < (n - 1); i++) {

      int tempVar = a;
      a = b;
      b += tempVar;
      if(b % 2 == 0){

        fibEvens.add(b);

      }
    }
    return fibEvens;
  }
}

https://projecteuler.net/problem=2

Answer 1

看起来你的代码试图得到第 4 百万个斐波那契数，这与 斐波那契数列中值不超过四百万的项完全不同 .

Answer 2

您得到否定结果的原因是斐波那契数列第 88 项以上的项超过了 java 中 Long 数据类型的最大正值, 即 9,223,372,036,854,775,80。

当您尝试将 long 数据类型递增到超过其最大值时，它会环绕到最小值 (-9,223,372,036,854,775,80)。在斐波那契项超过最大值时，您已经重复了很多次。

此外，您发布的问题表明，当从序列派生的数字的值大于 400 万时，您应该停止，而不是尝试添加前 400 万个值的偶数（这很大）。

Answer 3

因为

int 数据类型存储从 -2^31 到 2^31 - 1
Integer数据类型存储从-2^63到2^63 - 1

试试 BigInteger

public static BigInteger fibonacci(int n) {
    BigInteger[] f = new BigInteger[n + 1];
    f[0] = BigInteger.ZERO;
    if (n > 0) {
        f[1] = BigInteger.ONE;
    }
    for (int i = 2; i < f.length; i++) {
        f[i] = f[i - 1].add(f[i - 2]);
    }
    return f[n];
}

但是400万斐波那契值很长。查看更多 300th, 500th

当我运行我的程序计算所有偶数斐波那契数之和时，为什么会得到负输出？

Why do I get a negative output when I run my program to compute the sum of all even Fibonacci numbers?

java

algorithm

debugging

fibonacci

当我 运行 我的程序计算所有偶数斐波那契数之和时，为什么会得到负输出？

Why do I get a negative output when I run my program to compute the sum of all even Fibonacci numbers?

java

algorithm

debugging

fibonacci

当我运行我的程序计算所有偶数斐波那契数之和时，为什么会得到负输出？