Калькулятор Фибоначчи с 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, но затем я начал нужны значения, которые были waaay больше, поэтому я был вынужден в BigInteger. Кто-нибудь может понять, что с ним не так? Я думаю, что проблема заключается в возврате метода fibonacci2.

Answer 1

Значение return - это то, что должно быть 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 будет значительно быстрее, чем исходная рекурсивная версия ,