Fibonnacci 之 矩陣快速幂

斐波那契數列 習題

1.矩陣快速幂 推導 fibonnacci

{1        1}                                 { A     B}
   {1        0}  的n-1次方的結果設為              {C      D}
           

利用矩陣乘法， 可以得到 F【n】=A* F[1 ] + B* F[ 0 ]

接下來 考慮 矩陣的n-1 次方 計算，使用矩陣快速幂`

/*===================================*/
|| 快速幂（（（quickpow）））模闆 ）模闆 
|| P 為等比，，，I 為機關矩陣
|| MAX 要要要初始化！！！！
||
/*===================================*/
/*****************************************************/

const int MAX = 2; 
typedef struct{ 
 int m[MAX][MAX]; 
} Matrix; 
Matrix P = {1, 1,              //  p為     數列的    推導矩陣
           1, 0,
}; 
Matrix I = {1,0,                   //          I為 對應  P 的 機關矩陣
            0,1,
 }; 
 
Matrix matrixmul(Matrix a,Matrix b) //矩陣乘法
{ 
 int i,j,k; 
 Matrix c; 
 for (i = 0 ; i < MAX; i++) 
 for (j = 0; j < MAX;j++)
   { 
       c.m[i][j] = 0; 
      for (k = 0; k < MAX; k++) 
 c.m[i][j] += (a.m[i][k] * b.m[k][j])%mod; 
 c.m[i][j] %=mod；                //由于  當 n 太大時  ，  利用取模  可以求出  數列 的 後幾位數    
 } 
 return c; 
} 
 
Matrix quickpow(long long n) 
{ 
 Matrix m = P, b = I; 
 while (n) 
 { 
     if (n & 1) 
          b = matrixmul(b,m); 
         n = n >> 1;   //    n=n/2；
         m = matrixmul(m,m); 
 } 
 return b; 
} 
使用：：：在：在在在 main()裡直接調用 quickpow()就可以了。。。

           

1. 斐波那契數列 求前幾位數 ，以 求前四位數 為例

在這裡插入代碼片 
      
123456.32=1234.56*10^2 
s=d.xxx*10^(len-4)             //  len 為  位數  =（int）log10（s）+1

log10(s)=log10(d.xxxxx)+log10(10^(len-4))=log10(d.xxxx)+len-4; 
log10(s)+4-len=log10(d.xxxx) 
d.xxxx=10^(log10(s)+4-len) 

s=(1/sqrt(5))*[(1+sqrt(5))/2.0]^n;      //  此處為   斐波那契數列  的數學公式 ， n 為 f【n】中的n

len=(int)log10(s)+1; 
d.xxxx=10^(log10(s)+4-((int)log10(s)+1))=10^(log10(s)-(int)log10(s)+3); 



核心代碼：：：：        
           m =((1+sqrt(5))/2.0);
           k= (-0.5)*log10(5)+n*log10(m);          //k=log10(s);
          
           x=k-(int)k+3;

           ans=pow(10,x);
           printf("%lld\n",ans);              //   ans  必須用 整形 ，    .0lf 的double型 錯

           

Fibonnacci Hdu3117

求前四位數 與後四位數

在這裡插入代碼片#include <iostream>
#include  <bits/stdc++.h>
using namespace std;
const int N=2;
typedef struct
{
    long long  m[N][N];
}matrix;//矩陣;

matrix P={0,1,
         1,1};       //  遞推公式的 推導矩陣

matrix I={1,0,        //   機關矩陣
           0,1};

matrix   chengfa(matrix a,matrix b)
{
    int i,j,k;
    matrix c;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
    {
        c.m[i][j]=0;
        for(int k=0;k<N;k++)
        {
            c.m[i][j]+=(a.m[i][k]*b.m[k][j]);
        }
        c.m[i][j]=c.m[i][j]%mod;                      // 若求  後4位數  則  mod=10000；

    }
    return c;
}
matrix quickpow(long long n)   // 矩陣快速幂，  p^n %mod   p 為推導矩陣
{
    matrix b=I,a=P;

    while(n)
    {
        if(n&1)
            b=chengfa(b,a);
        n=n/2;

        a=chengfa(a,a);
    }
    return b;

}


int main()
{  int f[100];
  long long ansqi,anshou,n;
  double k,a,x;
  matrix b;
  f[0]=0;
  f[1]=1;
  for(int i=2;i<=50;i++)
    f[i]=f[i-2]+f[i-1];

    /*for(int i=2;i<39;i++)
  printf("%d ",f[i]);*/


     while(cin>>n)
     {

         if(n>39)                   //由打表知道， 39 為 最後一個八位數；
        {

        a=(1+sqrt(5))/2.0;

        k=(-0.5)*log10(5)+n*log10(a);    //  k=log10(s);

        x=k-int(k)+3;

        ansqi=pow(10,x);



        b=quickpow(n);      // 所求為  f【n】的矩陣

        anshou=b.m[0][1]*f[1];

        printf("%lld...%04lld\n",ansqi,anshou);


        }
        else
            printf("%d\n",f[n]);


     }
    return 0;
}