论坛 › 算法及编程语言 › [转贴]Fibonacci数列的计算

风花雪月 发表于 2007-4-28 06:35

[转贴]Fibonacci数列的计算

Fibonacci数列F(n)递归地定义为：
      1                n<=2
F(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;
            f=f=1;
            for(int i=3;i<=n;++i)
                        f=f+f;
            int result=f;
            delete[] f;
            return result;
}
前者是自顶向下，后者是自底向上，其效率是一样的，都是O(n)。从指数型复杂度到线性复杂度，是多大的提高啊。然而效率还可以提高。
3、矩阵的方法。
思想来源上上次PKU的acm warmup
http://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={
{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;
   }
   printf("%d\n",x.a);
}
}
return 0;
}转自算法驿站：http://blog.programfan.com/

[ 本帖最后由 风花雪月 于 2007-4-28 06:39 编辑 ]

风花雪月 发表于 2007-4-28 06:36

最后我们要观察这样的矩阵方法可否推广到一般情形，我们暂且称这样的递推序列为‘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

hao1982 发表于 2007-4-28 08:53

在一个农场上有很多母牛，第1年有一只母牛，而且每过4年，母牛会开始生小母牛，小母牛过4年后也会开始生，此后就每年生一只小母年，问第n年时有多少只母牛？

呵呵,这个题目我也刚编过,有不少方法

风花雪月 发表于 2007-5-5 20:57

原帖由 hao1982 于 2007-4-28 08:53 发表 http://forum.vibunion.com/forum/images/common/back.gif
在一个农场上有很多母牛，第1年有一只母牛，而且每过4年，母牛会开始生小母牛，小母牛过4年后也会开始生，此后就每年生一只小母年，问第n年时有多少只母牛？

呵呵,这个题目我也刚编过,有不少方法

把你写的那出来分享一下，呵呵

查看完整版本: [转贴]Fibonacci数列的计算