HDU 1568（非常经典微妙的 斐波纳契计算）
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。
0 1 2 3 4 5 35 36 37 38 39 40
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;
}
评论 (0)