递归斐波那契数列
我正在尝试生成斐波那契系列并提供了以下相同的代码。当我针对较小的值运行此代码时，它会输出正确的结果。然而，当我尝试计算数字“50”的序列时，它会输出直到第 47 个数字的正确结果，而第 48,49 和第 50 项的结果不正确。我也尝试使用 unsigned long int 但它没有纠正结果。有人可以建议我在这里做错了什么吗？ 谢谢。
#include<stdio.h>
unsigned long long int fibr(unsigned long long int);
int main(){
unsigned long long int n;
printf("Enter a number\n");
scanf("%llu",&n);
//res=fibr(n);
while(n>=0){
printf("%llu\n",fibr(n));
n--;
}
}
unsigned long long int fibr(unsigned long long int n){
if((n==0)||(n==1))
return n;
else return fibr(n-1)+fibr(n-2);
}
'根据建议，我合并了 unsigned long long int。已修改上面的代码，但现在它给出了段错误。请任何提示。除了可用的标准库之外，我不允许使用任何其他库。 '
I am trying to generate Fibonacci series and provided the code for the same below. When I run this code for smaller values, it outputs correct results. However, when I try and calculate series for a number say '50', it out puts correct results upto the 47th number and result for 48,49 and 50th term are incorrect. I tried using unsigned long int as well but it did not correct the results. Can some please suggest what am I doing wrong here.
Thanks.
#include<stdio.h>
unsigned long long int fibr(unsigned long long int);
int main(){
unsigned long long int n;
printf("Enter a number\n");
scanf("%llu",&n);
//res=fibr(n);
while(n>=0){
printf("%llu\n",fibr(n));
n--;
}
}
unsigned long long int fibr(unsigned long long int n){
if((n==0)||(n==1))
return n;
else return fibr(n-1)+fibr(n-2);
}
'After the suggestions , I incorporated unsigned long long int. Have modified the code above but now it gives a seg fault. Any hints please. I am not allowed to use any other library except the standards one available. '
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您是否尝试过使用
unsigned long long？Did you try using
unsigned long long?这是你的第二个问题的答案：
我认为你从一开始就遇到了这个问题：
是一个无限循环，因为
n是一个无符号整数。由于递减，n将变为负数。但由于它是无符号的，它会回绕并导致递归中的堆栈溢出。此外，您的算法可能是执行此操作最慢的方法。它以指数时间运行。所以当
n很大时，运行它会花费很长时间。更好的方法是这样的：
该方法将在恒定时间内运行。 :)
Here's the answer to your second question:
I think you had this problem from the beginning:
is an infinite loop since
nis an unsigned integer.nwill go negative due to the decrement. But since it's unsigned, it will wrap around and cause a stack-overflow in your recursion.Also, your algorithm is probably slowest way to do this. It runs in exponential time. So it will take a very long time to run it when
nis big.A better way is just this:
This method will run in constant time. :)
C 数据类型的大小是有限的。因此，如果您使用
int、long或long long，由于斐波那契数列快速增长的性质，在某些时候您的结果将会溢出-数字。要存储如此大的数字，您需要一些
BigInteger实现。请查看C 语言中的“BigInt”？。C data types are limited in size. So if you use
int,longorlong long, at some point, your result will overflow, due to the fast-growing nature of fibonacci-numbers.To store such big numbers, you'll need some
BigIntegerimplementation. Have a look at “BigInt” in C? for this.你会得到整数溢出。对于
unsigned int，最大可能值为 4294967295，但第 48 个斐波那契数为 4807526976。You get integer overflow. For
unsigned intthe largest possible value is 4294967295, but 48th Fibonacci number is 4807526976.将 fibr() 转换为记忆其结果可将 fibr(90) 在我的计算机上的运行时间减少到几毫秒。从递归切换到迭代应该会产生类似的结果。
Converting
fibr()to memoize its results reduces the running time for fibr(90) to a few milliseconds on my machine. Switching from recursion to iteration should have similar results.