[Solved] Fibonacci Sum Problem Consult Rest Methods Biginteger Api Documentation Needed Solve Follo Q37196204

Fibonacci Sum problem

Consult the rest of the methods of BigInteger from its APIdocumentation as needed to solve the following problem.

public static List fibonacciSum(BigInteger n)

Fibonacci numbers, that dusty and tired example of sillyrecursion in teaching introductory computer science, turn out havemore interesting combinatorial properties that make up goodproblems for us to solve. Relevantly for the current moment, anypositive integer n can be broken down exactly one way as a sum ofdistinct Fibonacci numbers that add up to n, under the additionalconstraint that no two consecutive Fibonacci numbers appear in thissum. (After all, if the sum contains two consecutive Fibonaccinumbers Fi and Fi+1, these two can always be replaced by Fi+2without affecting the total.)

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

Your method must remain efficient even if n contains thousandsof digits. To do so, maintain a list of Fibonacci numbers that youhave generated so far initialized with

private static List fibs = new ArrayList<>();
static { fibs.add(BigInteger.ONE); fibs.add(BigInteger.ONE); }

and then whenever the last Fibonacci number in this list is notbig enough for your present needs, extend the list with the nextFibonacci number that you get by adding the last two knownFibonacci numbers. Keeping all your Fibonacci numbers that you havediscovered so far in one sorted list allows you to do things suchas using Collections.binarySearch to quickly determine if somethingis a Fibonacci number…

*TEST FILE *

import static org.junit.Assert.*;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
import java.util.Random;

import java.io.*;
import java.util.*;
import java.util.zip.CRC32;
import java.math.BigInteger;

public class Test {

private static final int SEED = 12345;
private static final BigInteger TWO = new BigInteger(“2”);
  
@Test public void testFibonacciSum() {
CRC32 check = new CRC32();
Random rng = new Random(SEED);
BigInteger curr = BigInteger.ONE;
for(int i = 0; i < 1000; i++) {
List result = P2J5.fibonacciSum(curr);
for(BigInteger b: result) {
check.update(b.toString().getBytes());
}
curr = curr.add(new BigInteger(“” + (rng.nextInt(5) + 1)));
curr = curr.multiply(TWO);
}
assertEquals(702310714L, check.getValue());
}
}

Expert Answer

---

Answer to Fibonacci Sum problem Consult the rest of the methods of BigInteger from its API documentation as needed to solve the fo… . . .