阶梯，一次 1 或 2 个梯级，递归/斐波那契错误

Question

我知道关于这个问题已经存在很多问题，但我还没有找到任何可以回答我的问题。我的递归对于较低的数字工作正常（我试过 int 10）但是当我将它扩展到 100 时，它变得比它应该的低了一步。不知道为什么。

我的代码：

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
  public void testDistinctLadderPaths100 (){
    int rungs = 100;
    BigDecimal expected = new BigDecimal("573147844013817084101");
    BigDecimal result = lp.distinctLadderPaths(rungs);
    assertEquals(expected, result);
  }

我被告知输出应该是 57314784401381708410，但我得到的是 3736710778780434371（这是第 99 步的斐波那契数）。有什么想法吗？

Answer 1

斐波那契数列从1开始，数列为1, 1, 2, 3, 5, 8.. 所以初始化 f[0] = f[1] = 1;

Answer 2

您正在使用 long 数组来存储数据。 java中long数据类型的范围是-9,223,372,036,854,775,808 to 9,223,372,036,854,775,807。而第 100 个 fab 的结果超出了 long 数据类型的范围。这就是 java 舍入额外数据并为您提供结果 3736710778780434371 的原因。尝试使用它会正常工作的任何其他数据类型。逻辑上没有问题，是数据类型的问题。

一个工作示例可能如下所示：

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
      }

阶梯，一次 1 或 2 个梯级，递归/斐波那契错误

ladder, 1 or 2 rungs at a time, recursion / fibonacci error

java

recursion

fibonacci

ladder-logic