HDU 1568(非常经典微妙的 斐波纳契计算)

spoiler posted @ 2011年4月18日 03:42 in 未分类 , 1592 阅读
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

题目分析:这个题目非常精美!首先题目要求求第N个斐波纳契数的前四位,前提是他不止四位哦!

然后引用到的知识点,斐波纳契的计算公式:(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)

还有对数log()的作用,先让我们回忆一下log 的运算性质吧~

1)log(a*b)=log(a)+log(b); 2)log(a/b)=log(a)-log(b);

其实在数学里面,log可以求一个大数的科学计数法的数值部分,比如说123456

首先log10(1234567)=log(1.234567*10^6)=log(1.234567)+6; 然后log10(1.234567)就是log10(1234567)的小数位

然后10^log10(1.234567)=1.234567,所以通过这样的转换 我们可以很巧妙的得到了一个很大的数的科学计数法的表示值!

然后您要取4位就拿4位!要多少位就拿多少位!

既然这样可以我们就干下去吧!

斐波纳契的计算公式:(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)

log10((1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n])

化简一下得到:

-0.5*log10(5.0)+((double)n)*log(f)/log(10.0)+log10(1-((1-√5)/(1+√5))^n)其中f=(sqrt(5.0)+1.0)/2.0;

在这里  log10(1-((1-√5)/(1+√5))^n)无穷小可以忽略不计!

最后得到 log10(an)=-0.5*log10(5.0)+((double)n)*log(f)/log(10.0)   !

然后就是直接贴代码了

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int s[21]={0,1,1,2};
const double f=((double)sqrt(5)+1)/2.0;
void get_Fibonacci(int x){
	if(x<=20)
		printf("%d\n",s[x]);
	else{
		double ans=(-0.5)*log(5.0)/log(10.0)+(double(x))*log(f)/log(10.0);
		ans=ans-floor(ans);
		double k=pow(10.0,ans);
		//cout<<"k= "<<k<<endl;
		while(k<1000.0)
			k*=10.0;
		printf("%d\n",(int)k);
	}
	
}
int main(){
	int x,i;
	for(i=3;i<=20;i++)
		s[i]=s[i-1]+s[i-2];
      //在这里为了区别其他多于4位的答案我先把4位以内的
     //都计算好存起来!
	while(~scanf("%d",&x)){
		if(x==0){
			printf("0\n");
			continue;	
		}
		get_Fibonacci(x);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter