亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

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

 更新時間:2013年03月19日 12:16:47   作者:  
斐波那契數(shù)列 優(yōu)化矩陣求法實例,需要的朋友可以參考一下

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

  (一)遞歸

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

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

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)

  利用臨時變量來保存中間的計算過程,加快運算。

復(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ù)列的遞推公式為:f(1)=1,f(2)=2,f(n)=f(n-1)+f(n-2)(n>=3)

   用矩陣表示為:

 

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

 

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

為了保證解滿足 Xi={0或1},對上述公式的求解從右向左,即求解順序為Xn,Xn-1,Xn-2,....,X1,X0。

  完整代碼實現(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)   ///對于大于等于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)    ///對于小于32的k(16,8,4,2,1);
    {
        if(k>=(long long)pow(2,i))  ///如果k大于某一個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);
}

相關(guān)文章

  • C++和python實現(xiàn)單鏈表及其原理

    C++和python實現(xiàn)單鏈表及其原理

    這篇文章主要介紹了C++和python實現(xiàn)單鏈表及其原理,單鏈表是鏈表家族中的一員,每個節(jié)點依舊由數(shù)據(jù)域(data)和指針域(next)組成,鏈表的具體概念下面文章將詳細(xì)介紹,需要的小伙伴可以參考一下
    2022-03-03
  • Qt實現(xiàn)文本編輯器(二)

    Qt實現(xiàn)文本編輯器(二)

    這篇文章主要介紹了利用Qt實現(xiàn)的一個文本編輯器。本文將具體講解下是如何實現(xiàn)菜單欄以及工具欄上對應(yīng)的需求,感興趣的可以動手試一試
    2022-01-01
  • linux 匿名管道實例詳解

    linux 匿名管道實例詳解

    這篇文章主要介紹了linux 匿名管道實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • C語言數(shù)據(jù)結(jié)構(gòu)之 折半查找實例詳解

    C語言數(shù)據(jù)結(jié)構(gòu)之 折半查找實例詳解

    這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之 折半查找實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • C語言編程數(shù)據(jù)結(jié)構(gòu)線性表之順序表和鏈表原理分析

    C語言編程數(shù)據(jù)結(jié)構(gòu)線性表之順序表和鏈表原理分析

    本篇文章是C語言編程篇主要為大家介紹了C語言編程中的數(shù)據(jù)結(jié)構(gòu)線性表,文中附含豐富的圖文示例代碼為大家詳解了線性表中的順序表和鏈表,有需要的朋友可以借鑒參考下
    2021-09-09
  • c語言abort函數(shù)實例用法

    c語言abort函數(shù)實例用法

    在本篇文章里小編給大家整理了一篇關(guān)于c語言abort函數(shù)實例用法及相關(guān)知識點,有興趣的朋友們可以學(xué)習(xí)下。
    2021-09-09
  • C++的輸入和輸出流詳解

    C++的輸入和輸出流詳解

    這篇文章主要為大家詳細(xì)介紹了C++的輸入和輸出流,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2022-03-03
  • C語言詳解實現(xiàn)鏈?zhǔn)蕉鏄涞谋闅v與相關(guān)接口

    C語言詳解實現(xiàn)鏈?zhǔn)蕉鏄涞谋闅v與相關(guān)接口

    二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指,用鏈表來表示一棵二叉樹,即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點由三個域組成,數(shù)據(jù)域和左右指針域,左右指針分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址
    2022-04-04
  • COLORREF,COLOR,RGB,CString的轉(zhuǎn)化總結(jié)分析

    COLORREF,COLOR,RGB,CString的轉(zhuǎn)化總結(jié)分析

    實際的軟件開發(fā)過程中,常需要用到非.net平臺的代碼。這時候就可能碰到ColorRef(也就是以int類型代表的顏色值或是以DWORD值表示的顏色)。這跟.net平臺下的顏色的相互轉(zhuǎn)換MS并沒有直接實現(xiàn)
    2013-09-09
  • 構(gòu)造函數(shù)不能聲明為虛函數(shù)的原因及分析

    構(gòu)造函數(shù)不能聲明為虛函數(shù)的原因及分析

    構(gòu)造函數(shù)不需要是虛函數(shù),也不允許是虛函數(shù),因為創(chuàng)建一個對象時我們總是要明確指定對象的類型,盡管我們可能通過實驗室的基類的指針或引用去訪問它但析構(gòu)卻不一定,我們往往通過基類的指針來銷毀對象
    2013-10-10

最新評論