斐波那契数列求解

斐波那契数列的定义如下：

当n=0时，F[n]=0;

当n=1时，F[n]=1;

当n>1时，F[n]=F[n-1]+F[n-2];

解法一（动态规划思想）：

int Fib(int n)  
{  
    int pre1=1;  
    int pre2=0;  
    if(n==0)  
        return 0;  
    if(n==1)  
        return 1;  
    for(int i=2;i<=n;i++)  
   {  
        result=pre1+pre2;  
        pre2=pre1;  
        pre1=result;  
   }  
   return result;  
}

时间复杂度为O(n);

解法二：分治策略

(F(n),F(n-1))=(F(n-1),F(n-2))*A=...=(F(1),F(0))*A^(n-1);

A={{1,1},{1,0}};

转化为求矩阵A的幂。

代码如下：

#include<iostream>  
using namespace std;  
class Matrix2  
{  
public:  
    Matrix2(int a1,int a2,int b1,int b2)  
    {  
        m11=a1;  
        m12=a2;  
        m21=b1;  
        m22=b2;  
    }  
    int getm11()const  
    {  
        return m11;  
    }  
    int getm12()const  
    {  
        return m12;  
    }  
    int getm21()const  
    {  
        return m21;  
    }  
    int getm22()const  
    {  
        return m22;  
    }  
private:  
    int m11;  
    int m12;  
    int m21;  
    int m22;  
};  
Matrix2 MatrixPow(const Matrix2& m,int n);  
int Fib(int n);  
int main()  
{  
    int n;  
    cin>>n;  
    cout<<Fib(n)<<endl;  
    return 0;  
}  
Matrix2 matmultiply(const Matrix2& mat1,const Matrix2& mat2)  
{  
    int m11=mat1.getm11()*mat2.getm11()+mat1.getm12()*mat2.getm21();  
    int m12=mat1.getm11()*mat2.getm12()+mat1.getm12()*mat2.getm22();  
    int m21=mat1.getm21()*mat2.getm11()+mat1.getm22()*mat2.getm21();  
    int m22=mat1.getm21()*mat2.getm12()+mat1.getm22()*mat2.getm22();  
    return Matrix2(m11,m12,m21,m22);  
}  
Matrix2 MatrixPow(const Matrix2& mat,int n)  
{  
    Matrix2 result(1,0,1,0);  
    Matrix2 tmp=mat;  
    for(; n; n>>=1)  
    {  
        if(n&1)  
            result=matmultiply(result,tmp);  
        tmp=matmultiply(tmp,tmp);  
    }  
    return result;  
}  
int Fib(int n)  
{  
    if(n==0)  
        return 0;  
    else if(n==1)  
        return 1;  
    Matrix2 mat(1,1,1,0);  
    Matrix2 an=MatrixPow(mat,n-1);  
    return an.getm11();  
}

时间复杂度为O(nlogn);

补充：软件开发 , C++ ,