注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

斐波那契(Fibonacci)数列  

2009-04-23 15:19:40|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

以下取自《编程之美-微软技术面试心得》

斐波那契数列由如下递推关系式定义:

F(0)=0 F(1)=1

F(n)=F(n-1)+F(n-2) if n>1

求解斐波那契数列的方法有以下几种:


1.根据递推公式可以很容易想到用递归的方法求解第n+1项的值,代码如下:

int Fibonacci(int n){
    if(n<=0)return 0;
    else
        if(n==1)return 1;
    else
        return Fibonacci(n-1)+Fibonacci(n-2);
}

这种方法在计算F[n]时,需要计算从F[2]到F[n-1]每一项的值,这样简单的递归式存在着很多的重复计算,如求F[5]=F[4]+F[3],在求F[4]的时候也需要求一次F[3]的大小,等等。


2.为了减少上述的重复运算,可以用一个数组存储所有已经计算过的项。这样便可以达到用空间换时间的目的。在这种情况下,时间复杂度为O(N),而空间复杂度也为O(N)。


3.如果我们知道一个数列的通项公式,利用公式来计算会更加容易。能不能把这个函数的递推公式计算出来呢?

由递推公式F(n)=F(n-1)+F(n-2),知道F(n)的特性方程为:x^2=x+1(见补充)

有根:x1=(1+sqrt(5.0))/2,x2=(1-sqrt(5.0))/2

所以存在A,B使得:

F(n)=A*x1^n+B*x2^n

代入F(0)=0,F(1)=1,解得A=1/sqrt(5.0),B=-1/sqrt(5.0),即

F(n)=(x1^n-x2^n)/sqrt(5.0)

通过公式,我们可以在O(1)的时间内得到F(n)。但公式引入了无理数,所以不能保证结果的精度。


4.注意到Fibonacci数列是二阶递推数列,所以存在一个2*2的矩阵A,使得:

(F[n] F[n-1])=(F[n-1] F[n-2])*A,结合F[n]=F[n-1]+F[n-2]求解,可得:

A=1 1,1 0(上面是1 1,下面为1 0),由上面的矩阵递推公式有:

(F[n] F[n-1])=(F[n-1] F[n-2])*A=(F[n-2] F[n-3])*A^2=...=(F[1] F[0])*A[n-1],或

斐波那契(Fibonacci)数列 - chhaj5236 - chhaj5236的博客

剩下的问题就是求解矩阵A的方幂。A^n=A*A*...*A,最直接的解法就是通过n-1次乘法得到结果。但是当n很大时,比如1 000 000或1 000 000 000,这个算法的效率就不能接受了。当然,在这个情况下,F[n]在int所表示的整数里早就溢出了,但如果要求解的是F[n]对某个素数的余数时,这个算法会是非常有用和高效的。

注意到:

A^(x+y)=A^x*A^y

A^(x*2)=A^(x+x)=(A^x)^2

用二进制方法表示n:

n=ak*2^k+a(k-1)*2^(k-1)+...+a1*2+a0(其中ai=0或1,i=0,1,...,k)

A^n=A^(ak*2^k+a(k-1)*2^(k-1)+...+a1*2+a0)=(A^(2^k))^ak*...*A^a0

如果能够得到A^(2^i)的值,就可以再经过logn次乘法得到A^n.

而这容易通过递推得到:

A^(2^i)=(A^(2^(i-1)))^2。根据上面的思想,具体代码如下:

Class Matrix;                                               //假设我们已经有了实现乘法操作的矩阵类
Matrix MatrixPow(const Matrix &m,int n){    //求解m的n次方
    Matrix result=Matrix::Identity;                 //赋初值为单位矩阵
    Matrix tmp=m;
    for(;n;n>>=1){
        if(n&1)result*=tmp;
        tmp*=tmp;
    }
}
int Fibonacci(int n){
    Matrix an=MatrixPow(A,n-1);                    //A的值就是上面求解出来的
    return F1*an(0,0)+F0*an(1,0);
}

整个算法的时间复杂度为O(logn)

  评论这张
 
阅读(1560)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017