时间限制：1000 ms | 内存限制：65535 KB
难度：4
- 描述
-
数学神童小明终于把0到100000000的Fibonacci数列（f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2)）的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位（高4位）就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验小明说的是否正确。
- 输入
- 输入若干数字n(0 <= n <= 100000000)，每个数字一行。读到文件尾结束。
- 输出
- 输出f[n]的前4个数字（若不足4个数字，就全部输出）。
- 样例输入
-
0 1 2 3 4 5 35 36 37 38 39 40
- 样例输出
-
0 1 1 2 3 5 9227 1493 2415 3908 6324 1023
-
如果做这个题没有思路的话先想想这个题：
-
求二的n次方的前四位（2^n）其中0<n<100000000;(提示，用到对数log());
-
View Code
1 #include<stdio.h>
2 #include<math.h>
3 int f[]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765};
4 int main()
5 {
6 int n,num;
7 double ans,a=-0.5*log(5)/log(10),b=log( ( 1+sqrt(5.0) )/2 )/log(10);//c=( 1-sqrt(5.0) )/( 1+sqrt(5.0) );
8 while(scanf("%d",&n)!=EOF)
9 {
10 if(n>=21){
11 ans=a+n*b;//+log(1-pow(c,n));
12 ans=ans-(int)ans;
13 num=pow(10,ans)*1000;
14 }
15 else num=f[n];
16 printf("%d\n",num);
17 }
18 return 0;
19 }
