java - 用Java实现的计算斐波那契数列的算法给出了奇怪的结果

Question

当我运行 Countdown.class 时，我得到以下输出：

263845041
-1236909152
-973064111
2084994033
1111929922
-1098043341
13886581
-1084156760
-1070270179
2140540357

发射！

“Blast Off！”之前的数字 应该是前 10 个斐波那契数。我的源代码如下。

    public class Fibonacci {

  public static long fib(int n) {
    if (n <= 1) return 1;
    return fib(n-1) + fib(n-2);
  }

  public static long fastfib(int n) {
    int a = 0;
    int b = 1;
    int c = 0;

    for (int i = 0; i <= n; n++) {
      c = a + b;
      a = b;
      b = c;    
    }

    return c;
  }

}

实现 fastfib 方法的类是：

public class Countdown {

  public static void countdown(int n) {
    if (n == 0) System.out.println("Blast Off!");
    else {
      System.out.println(Fibonacci.fastfib(n));
      countdown(n - 1); 
    }
  }

  public static void main(String[] args) {
    countdown(10);
  }
}

Answer 1

尽管您的fastfib()方法返回long，但计算是在ints 上完成的。

您遇到整数溢出。

确保声明a,b,c为longs 而不是ints。如果您想要更大的数字（也超出longs 的范围） - 您可能想看看BigInteger（并使用它）。

---

编辑：正如@ExtremeCoders在评论中提到的那样，循环中的代码中还有另一个问题for：
for (int i = 0; i <= n; n++)应该是for (int i = 0; i <= n; i++)，你想要增加i- 不是n。

Answer 2

除了其他答案，

for (int i = 0; i <= n; n++) {

应该

for (int i = 0; i <= n; i++) {
//                      ^ that's an i

Answer 3

将 a、b 和 c 的数据类型更改为 long，它将开始正常工作。您的数字超出了 int 的限制。

Answer 4

你应该使用 BigInteger insted of long

导入 java.math.BigInteger；

公共类斐波那契{

public static BigInteger fib(BigInteger n) {
    int result = n.compareTo(BigInteger.valueOf(1)); // returns -1, 0 or 1 as this BigInteger is numerically less than, equal to, or greater than val.
    if (result != 1) return BigInteger.valueOf(1);

    return fib(

            n.subtract(
                    BigInteger.valueOf(1).add
                        (n.subtract
                                (
                                        BigInteger.valueOf(-2)
                                )
                        )
                    )
                );
}

public static BigInteger fastfib(int n) {
    BigInteger a = BigInteger.valueOf(0);
    BigInteger b =  BigInteger.valueOf(1);
    BigInteger c =  BigInteger.valueOf(0);

    for (int i = 1; i < n; i++) {
        c = a.add(b);
        a = b;
        b = c;    
    }

    return c;
}

}