【类似N^N做法的斐波那契数列】【HDU1568】 Fibonacci

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说的是否正确。

 

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

Happy 2007

 

Recommend

8600   |   We have carefully selected several similar problems for you:  1788 1787 1047 1573 3641 

 

此图片配合上一篇文章看 口味更加，，这种方法已经熟练掌握了；

变形公式很重要！！！！！！！注意极限很重要！！！！！！(当然用快速幂去解也可以的拉。。)

懂得常系数线性非齐次递推关系也很重要！！熟练用高中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
",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
",(int)ans);
	}
	return 0;
}