二分法求解硕大无比项的斐波那契数列数值

二分法求解超大项的斐波那契数列数值

我们将数列写成：

Fibonacci[0] = 0，Fibonacci[1] = 1

Fibonacci[n] = Fibonacci[n-1] + Fibonacci[n-2] (n >= 2)

可以将它写成矩阵乘法形式：

将右边连续的展开就得到：

下面就是要用O(log(n))的算法计算：

代码如下：

/*求解任一项斐波那契数列值，输入要计算的某一项n，输出该项对应的斐波那契数列值由于值超大，结果对1000000007取余*/#include<iostream>#include<cstdio>using namespace std;struct Matrix{__int64 a[2][2];};Matrix E;void InitE(int size)       //初始化单位矩阵{for(int i=0;i<size;i++){for(int j=0;j<size;j++)E.a[i][j]=(i==j);}}Matrix MatrixMul(Matrix a,Matrix b)     //两矩阵相乘   {Matrix c;int i,j,k;for(i=0;i<2;i++){for(j=0;j<2;j++){c.a[i][j]=0;for(k=0;k<2;k++){c.a[i][j] += ((a.a[i][k]%1000000007)*(b.a[k][j]%1000000007));c.a[i][j]%=1000000007;}}}return c;}Matrix MatrixPow(Matrix a,__int64 n)         //矩阵快速二分求n次幂{Matrix t=E;while(n>0){if(1&n)     //n是奇数t=MatrixMul(t,a);a=MatrixMul(a,a);n >>= 1;}return t;}int main(void){__int64 n;Matrix matrix,m;InitE(2);while(scanf("%I64d",&n)!=EOF){if(n==1||n==2)printf("1\n");else{matrix.a[0][0]=1;     //构造初始矩阵matrix.a[0][1]=1;matrix.a[1][0]=1;matrix.a[1][1]=0;m=MatrixPow(matrix,n-1);printf("%d\n",(m.a[0][0])%1000000007);}}return 0;}

截图如下：