java - 带 BigIntegers 的斐波那契计算器

Question

我正在做一个家庭作业项目，我必须让用户输入一个数字，然后计算机输出最多到该数字的斐波那契数字。我通常可以使用 int 值来做到这一点，但对于这个程序，我需要使用 BigInteger 类型，因为 int、long、double 等类型太小，无法容纳我需要的值。所以，这就是我得到的代码。问题是它没有打印出它应该打印的数字。我的进口:

import java.math.*;
import java.util.Scanner;

其余代码:

    public static void main(String args[]) {

       //input to print Fibonacci series up to how many numbers
        System.out.println("Enter number up to which Fibonacci series to print: ");
        BigInteger i = BigInteger.valueOf(new Scanner(System.in).nextLong());

        System.out.println("First " + i + " Fibonacci numbers: ");
        //printing Fibonacci series upto number
        for(int j=1; i.compareTo(BigInteger.valueOf(j))<0; j++){
            System.out.print(fibonacci2(BigInteger.valueOf(j)) +" ");
        }


    } 







    public static BigInteger fibonacci2(BigInteger number){
        if(number.compareTo(BigInteger.valueOf(1)) == 0 || number.compareTo(BigInteger.valueOf(2)) == 0){
            return BigInteger.valueOf(1);
        }
        BigInteger fibo1=BigInteger.valueOf(1), fibo2=BigInteger.valueOf(1), fibonacci=BigInteger.valueOf(1);
        for(int i=3; number.compareTo(BigInteger.valueOf(i))<=0; i++){

          //Fibonacci number is sum of previous two Fibonacci number
          fibonacci = fibonacci.add(fibo1.add(fibo2));             
          fibo1 = fibo2;
          fibo2 = fibonacci;

        }
        return fibonacci; //The current Fibonacci number

    }   
}

我知道它应该可以工作，因为我能够将它与 int 类型一起使用，但后来我开始需要更大的值，所以我被迫使用 BigInteger。有人能看出它出了什么问题吗？我认为问题出在 fibonacci2 方法的返回上。

Answer 1

返回值必须是BigInteger，而不是您的参数number。您的初始测试是 1 和 2(不是 0 和 1 - 这是开发人员的计数方式)。基本上，快速而肮脏的解决方案类似于

public static BigInteger fibonacci2(int n) {
    if (n == 0 || n == 1) {
        return BigInteger.ONE;
    }
    return fibonacci2(n - 2).add(fibonacci2(n - 1));
}

public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        System.out.println(fibonacci2(i));
    }
}

如果您需要计算较大的值，那么我建议使用 memoization喜欢

private static Map<Integer, BigInteger> memo = new HashMap<>();

public static BigInteger fibonacci3(int n) {
    if (n == 0 || n == 1) {
        return BigInteger.ONE;
    }
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    BigInteger v = fibonacci3(n - 2).add(fibonacci3(n - 1));
    memo.put(n, v);
    return v;
}

请注意，fibonacci3 将比初始递归版本快得多。