快捷導(dǎo)航

斐波那契數(shù)列優(yōu)化矩陣求法實(shí)例

更新時(shí)間：2013年03月19日 12:16:47 作者：

斐波那契數(shù)列優(yōu)化矩陣求法實(shí)例，需要的朋友可以參考一下

　　在做編程題目的時(shí)候經(jīng)常會(huì)遇到“斐波那契數(shù)列”相關(guān)的題目，尤其在做OJ中。下面說(shuō)一些方法：

　　(一)遞歸

　　遞歸是最慢的會(huì)發(fā)生重復(fù)計(jì)算，時(shí)間復(fù)雜度成指數(shù)級(jí)。

long long fac(int n)
{
　　if(n==1) 　　return 1;
　　else if(n==2)  　return 2;
　　else   　return fac(n-1)+fac(n-2);
}

　(二)循環(huán)

　　利用臨時(shí)變量來(lái)保存中間的計(jì)算過(guò)程，加快運(yùn)算。

復(fù)制代碼代碼如下:

long long fac(int n)
{
    long long a=1,b=2,c;
    if(n==1)    return 1;
    else if(n==2)   return 2;
    else
    {
        for(int i=3;i<=n;i++)
        {
            c=a+b; 　　a=b; 　　b=c;
        }
    }
    return b;
}

　　(三)矩陣乘法+空間換時(shí)間(減少乘法，取模運(yùn)算)

　　數(shù)列的遞推公式為：f(1)=1，f(2)=2，f(n)=f(n-1)+f(n-2)(n>=3)

　　用矩陣表示為：

進(jìn)一步，可以得出直接推導(dǎo)公式：

　　由于矩陣乘法滿(mǎn)足結(jié)合律，在程序中可以事先給定矩陣的64，32，16，8，4，2，1次方，加快程序的執(zhí)行時(shí)間。（有些題目需要取模運(yùn)算，也可以事先進(jìn)行一下）。給定的矩陣次冪，與二進(jìn)制有關(guān)是因?yàn)?，如下的公式存在解，滿(mǎn)足Xi={0或1}：

為了保證解滿(mǎn)足 Xi={0或1}，對(duì)上述公式的求解從右向左，即求解順序?yàn)閄n，Xn-1,Xn-2,....,X1,X0。

　　完整代碼實(shí)現(xiàn)如下：

復(fù)制代碼代碼如下:

///求解fac(n)%100000，其中n為大于等于3的正整數(shù)
#include<stdio.h>
#include<math.h>
long long fac_tmp[6][4]={   ///存放矩陣次冪
                    ///位置：00 01 10 11
                   {24578,78309,78309,46269},   ///32次冪%100000
                   {1597,987,987,610}, ///16次冪%100000
                   {34,21,21,13},   ///8次冪%100000
                   {5,3,3,2},   ///4次冪%100000
                   {2,1,1,1},   ///2次冪%100000
                   {1,1,1,0},   ///1次冪%100000
                   };
void fac(int);

int main()
{
    int n;
    scanf("%d",&n);
    fac(n);
    return 1;
}

void fac(int k) ///k>=3
{
    int i;
    long long t00=1,t01=1,t10=1,t11=0; ///表示矩陣的1次冪
    long long a,b,c,d;
    k=k-3; ///公式中是n-2次冪，(t00,t01,t10,t11)表示1次冪。所以一共減3次
    for(i=k;i>=32;i=i-32)   ///對(duì)于大于等于32的k;
    {
        a=(t00*fac_tmp[0][0]+t01*fac_tmp[0][2])%100000;
        b=(t00*fac_tmp[0][1]+t01*fac_tmp[0][3])%100000;
        c=(t10*fac_tmp[0][0]+t11*fac_tmp[0][2])%100000;
        d=(t10*fac_tmp[0][1]+t11*fac_tmp[0][3])%100000;
        t00=a; t01=b; t10=c;t11=d;
    }

    i=4;
    while(i>=0)    ///對(duì)于小于32的k(16,8,4,2,1);
    {
        if(k>=(long long)pow(2,i)) ///如果k大于某一個(gè)2的次冪
        {

            a=(t00*fac_tmp[5-i][0]+t01*fac_tmp[5-i][2])%100000; ///(5-i)：矩陣的2的i次冪在數(shù)組fac_tmp中的位置為fac_tmp[5-i]
            b=(t00*fac_tmp[5-i][1]+t01*fac_tmp[5-i][3])%100000;
            c=(t10*fac_tmp[5-i][0]+t11*fac_tmp[5-i][2])%100000;
            d=(t10*fac_tmp[5-i][1]+t11*fac_tmp[5-i][3])%100000;
            t00=a; t01=b; t10=c;t11=d;
            k=k-(int)pow(2,i);
        }
        i--;
    }

a=(t00*2+t01*1)%100000;
printf("%lld\n",a);
}

您可能感興趣的文章: