斐波那契据数列求解

斐波那契数列求解

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

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

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

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

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

#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();}