hdoj1568

这题碉堡了,第一感觉是大数,但是感觉写起来很烦,而且只要求前几位,这就意味着求出整个fib(n)是不必要的,于是这个想法枪毙掉。接下来想到的是数论,由于本菜鸟数论方面涉猎甚浅,只会解解不定方程的水平,于是各种yy之后,无果。。其实一直在想会不会和科学记数法有关,因为以前遇到过求n!的第一位的题目,但是始终想不到如何联系到科学记数法。。
无奈只能上网查,原来要用到fib的通项公式。。看来自己还是不够敏感阿~
这题以后再写思路,不然满脑子网上的解题思路,就没意思了
记下知识点:1.科学记数法。2.fib通项公式
注意精度问题~

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
const double A=log10(1.0/sqrt(5.0));
const double B=log10((1+sqrt(5.0))/2.0);
const double C=(1-sqrt(5.0))/(1+sqrt(5.0));
int fib[40];
int main()
{
	int n;
	int i,j;
	fib[0]=0;
	fib[1]=1;
	for(i=2;i<=35;i++)
		fib[i]=fib[i-1]+fib[i-2];
	while(scanf("%d",&n)!=EOF)
	{
		if(n<=16)
			printf("%d\n",fib[n]);
		else
		{
			double ans=A+n*B+log10(1-pow(C,n));
			ans=ans-(double)(int)ans;
			double result=pow(10.0,ans);
			while(result<10000)
				result*=10;
			int tmp=result/10;
			printf("%d\n",tmp);
		}
	}

//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>