英文:
ladder, 1 or 2 rungs at a time, recursion / fibonacci error
问题
我知道关于这个问题已经有很多现有的问题，但我还没有找到任何可以回答我的问题的东西。我的递归对较小的数字（我尝试了10）有效，但当我扩展到100时，它的结果比应该的结果低了一步。不太确定为什么。
我的代码：
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
public void testDistinctLadderPaths100 (){
int rungs = 100;
BigDecimal expected = new BigDecimal("573147844013817084101");
BigDecimal result = lp.distinctLadderPaths(rungs);
assertEquals(expected, result);
}
我被告知输出应该是 57314784401381708410，但我得到的结果是 3736710778780434371（这是在第99步的斐波那契数）。有什么想法吗？
英文:
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?
答案1
得分: 4
你正在使用long数组来存储数据。在Java中，long数据类型的范围是-9,223,372,036,854,775,808到9,223,372,036,854,775,807。而第100个斐波那契数的结果超出了long数据类型的范围。这就是为什么Java会四舍五入多余的数据并将结果显示为3736710778780434371。尝试使用其他数据类型就可以正常工作。逻辑没有问题，问题出在数据类型上。
一个可行的示例可能如下所示：
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 <= 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
得分: 3
fibonacci序列从1开始。序列是1, 1, 2, 3, 5, 8...
所以初始化f[0] = f[1] = 1;
英文:
fibonacci seq starts from 1. Sequence is 1, 1, 2, 3, 5, 8..
so initallize f[0] = f[1] = 1;
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论