Question

Complete the following methods in java:

Consult the rest of the methods of BigInteger from its API documentation as needed to solve the following problems.

public static List<BigInteger> fibonacciSum(BigInteger n)

The unique breakdown into Fibonacci numbers can be constructed with a greedy algorithm that simply finds the largest Fibonacci number f that is less than or equal to n. Add this f to the result list, and break down the rest of the number given by the expression n-f the same way. This method should create and return some kind of List that contains the selected Fibonacci numbers in descending order. For example, when called with n = 1000000, this method would return a list that prints as [832040, 121393, 46368, 144, 55].

Your method must remain efficient even if n contains thousands of digits. To achieve this, maintain a list of Fibonacci numbers that you have generated so far initialized with

private static List<BigInteger> fibs = new ArrayList<>();

static { fibs.add(BigInteger.ONE); fibs.add(BigInteger.ONE); }

and then whenever the last Fibonacci number in this list is not big enough for your present needs, extend the list with the next Fibonacci number that you get by adding the last two known Fibonacci numbers. Keeping all your Fibonacci numbers that you have discovered so far in one sorted list would also allow you to do things such as using Collections.binarySearch to quickly determine if something is a Fibonacci number.

Answer 1

Code

import java.math.BigInteger;

import java.util.ArrayList;

import java.util.List;

public class Temp {

    

    public static List<BigInteger> fibonacciSum(BigInteger n, ArrayList<BigInteger>fibList){

        if(n.compareTo(new BigInteger("0"))<=0)

            return new ArrayList<>();

        for(int i=fibList.size()-1;i>=0;i--){

            if(n.compareTo(fibList.get(i))>=0){

                List<BigInteger> prev = fibonacciSum(n.subtract(fibList.get(i)), fibList);

                prev.add(fibList.get(i));

                return prev;

            }

        }

        return new ArrayList<>();

    }

    public static void main(String[] args) {

        BigInteger n = new BigInteger("1000000");

        BigInteger a = new BigInteger("0");

        BigInteger b = new BigInteger("1");

        BigInteger c = new BigInteger("1");

        ArrayList<BigInteger>fibList = new ArrayList<>();

        while(c.compareTo(n)<=0){

            c = a.add(b);

            fibList.add(c);

            a = b;

            b = c;

        }

        List<BigInteger>fs = fibonacciSum(n,fibList);

        for(BigInteger bx:fs){

            System.out.println(bx.toString());

        }

    }

}