斐波那契数列

http://blog.csdn.net/lvshubao1314/article/details/38013897 一：递推 二：矩阵 //斐波那契数列第N项后MOD位，矩阵快速幂求法； #include<iostream> #include<cstdio> #include<string.h> #define LL long long using namespace std; const int MOD=10000; struct Matrix { LL m[3][3]; }; Matrix A={0,0,0, 0,1,1, 0,1,0,}; Matrix E={0,0,0, 0,1,0, 0,0,1,}; Matrix multi(Matrix a,Matrix b) { Matrix ans; for(int i=1;i<=2;i++) { for(int j=1;j<=2;j++) { ans.m[i][j]=0; for(int k=1;k<=2;k++) ans.m[i][j]+=a.m[i][k]*b.m[k][j]%MOD; ans.m[i][j]%=MOD; } } return ans; } Matrix power(Matrix a,int p) { Matrix ans=E,B=a; while(p) { if(p%2==1) ans=multi(ans,B); p=p/2; B=multi(B,B); } return ans; } int main() { int n; while(scanf("%d",&n)!=EOF) { Matrix ans=power(A,n-1); if(n==0) printf("0\n"); else printf("%d\n",ans.m[1][1]); } return 0; }

三：利用数学对数计算求前几位数字

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int main() { int f[25]; f[0]=0,f[1]=1; for(int i=2;i<=20;i++) { f[i]=f[i-1]+f[i-2]; } int n; while(scanf("%d",&n)!=EOF) { if(n<=20) printf("%d\n",f[n]); else { double f=(1.0+sqrt(5.0))/2.0; double p=-0.5*log10(5.0)+n*1.0*log(f)/log(10.0); p=p-floor(p); double ans=pow(10.0,p); while(ans<1000) ans=ans*10; printf("%d\n",(int)ans); } } return 0; }