/*
分析:
又是数学。。。又被完虐。。。
要用到斐波那契公式:
F(n)=(1/√5)*[((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)
=(1/√5)*[((1+√5)/2)^n*(1-((1-√5)/(1+√5))^n)](n=1,2,3.....)
用的对数,详细解释看这里吧:
http://hi.baidu.com/aekdycoin/item/a4407c37850e5b9db80c03a6
2012-11-22
*/
#include"stdio.h" #include"string.h" #include"stdlib.h" #include"math.h" #define f (sqrt(5.0)+1.0)/2.0 int fac[21]; int main() { int n; int i,l; double bit; fac[0]=0; fac[1]=1; for(i=2;i<=20;i++) fac[i]=fac[i-1]+fac[i-2]; while(scanf("%d",&n)!=-1) { if(n<=20) {printf("%d\n",fac[n]);continue;} bit=-0.5*log(5.0)/log(10.0)+((double)n)*log(f)/log(10.0); bit=bit-floor(bit); bit=pow(10.0,bit); while(bit<1000) bit*=10; printf("%d\n",(int)bit); } return 0; }