0

I know there are a lot of already existing questions about this problem, but I haven't found anything that answers mine. My recursion is working fine for lower numbers (I tried int 10) but when I expand it to 100, it becomes exactly one step lower than it should. Not sure why.

My code:

public BigDecimal distinctLadderPaths(int rungs) {
    if (rungs < 0)
      throw new ArithmeticException("Ladders can't have negative rungs."); // if negative, throw exception
    else if (rungs == 0)
      return BigDecimal.valueOf(0); //if zero, return zero
    else if (rungs <= 2)
      return BigDecimal.valueOf(rungs); //if 1 or 2, return 1 or 2, respectively
    else{
      long[] f = new long[(rungs + 1)]; //create long Array for memory (f for fibonacci)
      f[0] = 0; //1 steps
      f[1] = 1; //2 steps
      for(int i = 2; i <= rungs; i++) { //loop
        f[i] = f[i - 1] + f[i - 2]; //at each step in the loop, add 1 step lower and 2 steps lower from the number of iterations
      }
      return BigDecimal.valueOf(f[rungs]); //return fibonacci value at final step of the rungs as BigDecimal
    }
  }

test code:

@Test
  public void testDistinctLadderPaths100 (){
    int rungs = 100;
    BigDecimal expected = new BigDecimal("573147844013817084101");
    BigDecimal result = lp.distinctLadderPaths(rungs);
    assertEquals(expected, result);
  }

I'm told the output should be 57314784401381708410, but I'm getting 3736710778780434371 (which is the fibonacci number at the 99th step). Any ideas why?

4

2 回答 2

4

You are using long array to store the data. The range of long data type in java is -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807. And the result of 100th fab is out of the range of long data type. That's why java is rounding the extra data and giving you the result as 3736710778780434371. Try using any other data type it will work fine. There is no issue in the logic, it's the issue of data type.

A working example might look like this:

BigInteger[] f = new BigInteger[(rungs + 1)]; //create BigInteger Array for memory (f for fibonacci)
      f[0] = BigInteger.valueOf(1); //1 steps
      f[1] = BigInteger.valueOf(1); //2 steps
      for(int i = 2; i <= rungs; i++) { //loop
        f[i] = f[i - 1].add(f[i - 2]); //at each step in the loop, add 1 step lower and 2 steps lower from the number of iterations
      }
于 2020-08-03T04:53:51.460 回答
2

fibonacci seq starts from 1. Sequence is 1, 1, 2, 3, 5, 8.. so initallize f[0] = f[1] = 1;

于 2020-08-03T04:41:41.173 回答