Your objective for this question is to develop a program which will generate a fibbonacci number. The fibbonacci function is defined as such:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
Your program should be able to handle values of n in the range 0 to 50.
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
Your program should be able to handle values of n in the range 0 to 50.
Input
Each test case consists of one integer n in a single line where 0≤n≤50. The input is terminated by -1.
Output
Print out the answer in a single line for each test case.
Sample Input
3
4
5
-1
Sample Output
2
3
5
Hint
you can use 64bit integer: __int64 // 递归
#include<stdio.h> long fibbonacci(int n)
{
if(n==) return ;
else if(n==) return ;
else return fibbonacci(n-) + fibbonacci(n-);
} int main()
{
int n;
while(scanf("%d", &n), n!=-)
printf("%d\n", fibbonacci(n));
return ;
}
Time Limit Exceeded
//
int/long | __int64 |
signed: -2^31 ~ 2^31-1 ~ 2.1*10^9 unsigned: 0 ~ 2^32-1 ~ 4.29*10^9 |
signed:-2^63 ~ 2^63-1 ~ 9.2*10^18 unsigned: 0 ~ 2^64-1 ~ 1.8*10^19 |
// signed: scanf("%I64d",&a); printf("%I64d",a);
unsigned: scanf("%I64u",&a); printf("%I64u",a);
// 说明:
1、int64不能用作为循环变量
2、int64的操作速度较慢
#include<stdio.h> __int64 fibbonacci(int n)
{
__int64 x1=, x2=, x3=;
int i;
for(i=;i<=n;i++)
{
x3=x1+x2;
x1=x2; x2=x3;
}
if(x3) return x3;
else
{
if(n) return x2;
else return x1;
}
} int main()
{
int n; __int64 i;
while(scanf("%d", &n), n!=-)
{
i=fibbonacci(n);
printf("%I64d\n", i); /* __intxx io格式 */
}
return ;
}
AC
// 从第47个斐波那契数开始,其大小超过int范围;
// 从第48个斐波那契数开始,其大小超过unsigned int范围;
// 从第93个斐波那契数开始,其大小超过__int64范围;
// 从第94个斐波那契数开始,其大小超过unsigned __int64范围