学步园

  很久没见到这么神的处理方法了，纪念一下！

n比较小时n<=30，用f(n)=f(n-1)+f(n-2),n>=2求解

n比较大时使用进似计算的通式f(n)=x^n  ,x=(1+sqrt(5))/2  ,  (n<10^10)

巧妙之处在于计算x^n   

#include<iostream><br /> #include<cmath><br /> using namespace std;</p> <p>int main()<br /> {<br /> int f[31]= {0,1};<br /> for(int i=2; i<=30; i++)f[i]=f[i-1]+f[i-2];<br /> for(int i=2; i<=30; i++)while(f[i]>=10000)f[i]/=10;<br /> double num1=log10(sqrt(5)),num2=log10(0.5+sqrt(5)/2);<br /> int n;<br /> while(cin>>n)<br /> {<br /> if(n<=30)<br /> {<br /> cout<<f[n]<<endl;<br /> continue;<br /> }<br /> double t=n*num2-num1;<br /> double d=t-int(t);<br /> d=int(pow(10.0,d)*1000);<br /> cout<<d<<endl;<br /> }<br /> }

参考：http://hi.baidu.com/racebug/blog/item/54ad34ed3c3dfc3426979191.html