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

Sample Output

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\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;

}

巴特西

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

Fibonacci

最新文章

热门文章