梯子，每次1或2个横杆，递归/斐波那契错误

go评论30阅读模式

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

问题

``````public BigDecimal distinctLadderPaths(int rungs) {
if (rungs < 0)
throw new ArithmeticException("梯子不能有负数的横档。"); // 如果是负数，抛出异常
else if (rungs == 0)
return BigDecimal.valueOf(0); // 如果是零，返回零
else if (rungs <= 2)
return BigDecimal.valueOf(rungs); // 如果是1或2，分别返回1或2
else{
long[] f = new long[(rungs + 1)]; // 为内存创建long数组（f表示斐波那契数列）
f[0] = 0; // 1 步
f[1] = 1; // 2 步
for(int i = 2; i <= rungs; i++) { // 循环
f[i] = f[i - 1] + f[i - 2]; // 在循环的每一步中，将1步低和2步低的步数相加
}
return BigDecimal.valueOf(f[rungs]); // 返回横档最后一步的斐波那契值，作为BigDecimal
}
}
``````

``````@Test
int rungs = 100;
BigDecimal expected = new BigDecimal("573147844013817084101");
assertEquals(expected, result);
}
``````

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 &lt; 0)
throw new ArithmeticException(&quot;Ladders can&#39;t have negative rungs.&quot;); // if negative, throw exception
else if (rungs == 0)
return BigDecimal.valueOf(0); //if zero, return zero
else if (rungs &lt;= 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 &lt;= 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
int rungs = 100;
BigDecimal expected = new BigDecimal(&quot;573147844013817084101&quot;);
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?

答案1

``````BigInteger[] f = new BigInteger[(rungs + 1)]; // 为内存创建BigInteger数组（f表示斐波那契数列）
f[0] = BigInteger.valueOf(1); // 1步
f[1] = BigInteger.valueOf(1); // 2步
for (int i = 2; i <= rungs; i++) { // 循环
f[i] = f[i - 1].add(f[i - 2]); // 在循环的每一步中，将前一步和前两步的值相加
}
``````

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 &lt;= 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
}
``````

答案2

fibonacci序列从1开始。序列是1, 1, 2, 3, 5, 8...

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

• 本文由 发表于 2020年8月3日 12:34:22
• 转载请务必保留本文链接：https://go.coder-hub.com/63223789.html
• fibonacci
• java
• recursion

go 25

go 26

go 24

go 29