Fibonacci
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3562 Accepted Submission(s): 1621
Problem Description
2007年到来了。经过2006年一年的修炼，数学神童zouyu终于把0到100000000的Fibonacci数列
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。
Input
输入若干数字n(0 <= n <= 100000000)，每个数字一行。读到文件尾。
Output
输出f[n]的前4个数字（若不足4个数字，就全部输出）。
Sample Input
0
1
2
3
4
5
35
36
37
38
39
40
Sample Output
0
1
1
2
3
5
9227
1493
2415
3908
6324
1023
Author
daringQQ
Source
Recommend
此图片配合上一篇文章看 口味更加，，这种方法已经熟练掌握了；
变形公式很重要！！！！！！！注意极限很重要！！！！！！(当然用快速幂去解也可以的拉。。)
懂得常系数线性非齐次递推关系也很重要！！熟练用高中log知识也很重要！！！
总结就是 数学很重要！！！
代码要预处理好小于4位数的情况 而且从上面的图片看出 只有n>=20时 误差不会太大
#include<stdio.h>
#include<math.h>
int K[21];
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int n,i;
double t1,t2,t3,ans;
K[1]=1;K[2]=1;
for(i=3;i<=20;i++)
K[i]=K[i-1]+K[i-2];
while(scanf("%d",&n)!=EOF)
{
if(n<=20) {printf("%d\n",K[n]);continue;}
t1=-0.5*log10((5.0));
t2=log10((1+sqrt(5))/2.0);
t3=t1+n*t2;
t3=t3-(int)t3;
ans=pow(10.0,t3);
ans=ans+10e-8;
while(ans<=1000)
ans=ans*10;
printf("%d\n",(int)ans);
}
return 0;
}