Fibonacci数列F(n)递归地定义为： 1 n<=2F(n)={ F(n-1)+F(n-2) n>2 列出前几项：1，1，2，3，5，8，13，21，34。。。 注意到这些数字没有，很多都是在大自然中出现的，我知道的少，不过你可以在互联网上搜一下，关键词：黄金分割。 没错，这个数列中体现了黄金分割，用数学方法很容易证明。首先它是发散的，但是不妨假设F(n+1)/F(n)是可以收敛的，设e=limF(n+1)/F(n)，由递推方程：F(n)=F(n-1)+F(n-2)，两边同除F(n-1)得（在极限情况下）：e=1+1/e，解出来就得e=1.618...，同时也得知它近似地相当于指数数列1.618^n，至少会以这样的增涨率增涨。 以下总结一下Fibonacci数列的计算方法。 1，直接递归计算。 int fibonacci(int n){ if(n<=2) return 1; return fibonacci(n-1)+fibonacci(n-2);} 它的计算效率同它的数值增涨效率一样是指数型的（O(1.618^n)），因为它会在递归中重复计算子问题，改进的方法就是‘打表’，把已经计算过的F(n)记录下来，在以后的计算中只管用就是了，也叫备忘录方法，也是DP算法的一个组成部分。 2、备忘录方法。 int fibonacci(int n){ if(mem(n)>0) return mem(n); return mem(n)=fibonacci(n-1)+fibonacci(n-1);} 也可以直接用递推法，先开一个表f(n)，然后由f(1)=f(2)=1开始计算。 inf fibonacci(int n){ if(n<=2) return 1; int *f=new int[n+1]; f[1]=f[2]=1; for(int i=3;i<=n;++i) f[i]=f[i-1]+f[i-2]; int result=f[n]; delete[] f; return result;} 前者是自顶向下，后者是自底向上，其效率是一样的，都是O(n)。从指数型复杂度到线性复杂度，是多大的提高啊。然而效率还可以提高。 3、矩阵的方法。 思想来源上上次PKU的acm warmuphttp://acm.pku.edu.cn/JudgeOnline/problem?id=3070 {{F(n+1),F(n)},{F(n),F(n-1)}} = {{1,1} ^n{1,0}} 我当时就想，用加法算都只能是O(n)的，换成n个矩阵的连乘不是更废劲吗？其实不然，乘法方法有比加法更好的性质，用加法只能利用前两个的值，而乘法却不同，因为乘法有结合律，可以大幅度下降算法的耗时。 令A(n)表示一个矩阵序列 A(n)= {{F(n),F(n-1)},{F(n-1),F(n-2)} 那么A(2)={{1,1},{1,0}}，由那个表达式得到： A(n)=A(2)^(n-1)，A(2)是己知的2*2矩阵，现在的问题就是如何求 A(2)^n 因为方阵的乘法有结合律，所以 A(2)^n=A(2)^(n/2)*A(2)^(n/2)，不妨设n是偶数 所以求A(n)就可以化成求A(n/2)并作一次乘法，所以递归方程是： T(n)=T(n/2)+O(1) 它的解是O(lbn)，不可思议吧。 这是我AC的代码：#include <iostream>using namespace std; struct Matrix22{ int a,b,c; void operator*=(const Matrix22 &m); void display();}; void Matrix22::operator *=(const Matrix22 &m){ int p=b*m.b; int aa=a*m.a+p; int bb=a*m.b+b*m.c; int cc=p+c*m.c; a=aa%10000; b=bb%10000; c=cc%10000;} void Matrix22::display(){ printf("{%d,%d,%d},\n",a,b,c);}int main(void){ Matrix22 base[31]={{1,1,0},{2,1,1},{5,3,2},{34,21,13},{1597,987,610},{4578,8309,6269},{7565,7723,9842},{3954,4261,9693},{237,9867,370},{3858,9269,4589},{8525,5243,3282},{4674,4101,573},{4477,7947,6530},{8338,2629,5709},{3885,9563,4322},{4194,3541,653},{8317,3227,5090},{6018,4389,1629},{9645,2683,6962},{4514,6581,7933},{5757,3707,2050},{4898,549,4349},{1805,6603,5202},{7634,7221,413},{797,7387,3410},{2978,7109,5869},{6365,3323,3042},{5554,9461,6093},{7437,2267,5170},{8258,69,8189},{9325,4843,4482} }; int n; while(1) { scanf("%d",&n); if(n==-1) break; if(n<2) printf("%d\n",n); else { Matrix22 x={1,0,1}; --n; for(int i=0;n;++i,n>>=1) { if(n & 0x1) x*=base[i]; } printf("%d\n",x.a); } } return 0;} 最后我们要观察这样的矩阵方法可否推广到一般情形，我们暂且称这样的递推序列为‘c阶线性递推方程’吧，它的意思就是说F(n)由与n相距c远的前面的一些F(m)组成的线性组合，比如Fibonacci数列的最大距离就是2，所以这样的递推式需要确定一个序列至少要知道最初的c个己知初值，我们的目的就是要求这样的递归式的一般算法： F(n)={F(n-1),F(n-2),...F(n-c)}*K{F(1),F(2),,,F(c)}^T=C 其中K={x1,x2,...xc}^T，C={c1,c2,...cc}^T都是非0的常向量。 我们构造A(n)表示一个c*c的矩阵序列，且形式为 A(n)= {{F(n),F(n-1),F(n-2),...F(n-c+1)},{F(n-1),F(n-2),F(n-3),...F(n-c)},......{F(n-c+1),F(n-c),F(n-c-c),...F(n-2c+2)}} 为了使它有意义，n-2c+2>=1，所以n>=2c-1，所以A(n)的初始矩阵是A(2c-1)，可以按递归式直接构造它，然后我们考虑A(n)的生成矩阵会是什么样子，设为G，于是应满足： A(n)=A(n-1)G 观察A(n-1)的第一行，它刚好就是{F(n-1),F(n-2),...F(n-c)}，由递推式，知G的第一列应为K，而第二列设为x，则要满足{F(n-1),F(n-2),...F(n-c)}x=F(n-1)，很简单，x={1,0,0,...}，同样第三列是{0,1,0,0,...}，所以右边应该是一个(c-1)*(c-1)的单位矩阵I再在最下面补上一行0，于是G可以表示为： G={K,{I,0}^T} 于是A(n)的通项就是 A(n)=A(2c-1)*G^(n-2c+1) 比如Fibonacci数列的K={1,1}^T，所以G={K,{I,0}^T}={{1,1}, {1,0}} 再举一个例子，也是以前做过的一个题，母牛生小牛的题，在一个农场上有很多母牛，第1年有一只母牛，而且每过4年，母牛会开始生小母牛，小母牛过4年后也会开始生，此后就每年生一只小母年，问第n年时有多少只母牛？ 简单例出前几个数字：1，1，1，2，3，4，6，。。。会发现一个规律，就是第n年的母牛数F(n)恰等于前一年的母牛数F(n-1)，以及前三年的母牛数F(n-3)之和，其实直接得到这个递推式也不难，因为F(n-3)到F(n)刚好4年（第4年），所以F(n-3)都是一些可以生仔的牛数，它们会添加F(n-3)个小牛，同时F(n-1)是所有的牛妈妈，那当然有F(n)=F(n-1)+F(n-3)。 它的K={1,0,1},c=3，生成矩阵G={{1,1,0}, {0,0,1}, {1,0,0}} 所以有A(n)=A(3)*G^(n-2) A(3)={{1,1,1}, {1,1,0}, {1,0,0}} 从O(2^n)到O(n)，再到O(lbn)，效率提高得也太猛烈了，不过一点要提出来，不管什么样的算法，Fiboacci数列本身数值的递增是指数型的，所以要想算很高阶的结果，也近乎不太可能，所以经常会在一个模数范围内考虑。 rickone 2006/11/06
评论