VJ水題堆-關(guān)于斐波那契數(shù)列的求解過程

2019-11-14 11:36:15

字體：大中小

供稿：網(wǎng)友

做水題的過程中，有很多題一看就知道是與斐波那契數(shù)列相關(guān)知識(shí)求解的過程，即a[x]=a[x-1]+a[x-2]; 例如：

1.超級(jí)樓梯：有一樓梯共M級(jí)，剛開始時(shí)你在第一級(jí)，若每次只能跨上一級(jí)或二級(jí)，要走上第M級(jí)，共有多少種走法？輸入數(shù)據(jù)首先包含一個(gè)整數(shù)N，表示測試實(shí)例的個(gè)數(shù)，然后是N行數(shù)據(jù)，每行包含一個(gè)整數(shù)M（1<=M<=40）,表示樓梯的級(jí)數(shù)。對(duì)于每個(gè)測試實(shí)例，請(qǐng)輸出不同走法的數(shù)量。2.一只小蜜蜂... 有一只經(jīng)過訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行。請(qǐng)編程計(jì)算蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)。其中，蜂房的結(jié)構(gòu)如下所示。

一只小蜜蜂原題

3.骨牌鋪方格在2×n的一個(gè)長方形方格中,用一個(gè)1× 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數(shù). 例如n=3時(shí),為2× 3方格，骨牌的鋪放方案有三種,如下圖

骨牌鋪方格原題

很容易發(fā)現(xiàn)這些題都是利用斐波那契數(shù)列直接求解的題。或者抽象一點(diǎn)，都是通過遞歸方法進(jìn)行求解。談及遞歸很容易想到的是利用函數(shù)的遞歸調(diào)用進(jìn)行求解。比如說：

int fun(int x){ if(x==1||x==0)return 1; return fun(x-1)+(x-2);}

這樣的解法直接明了，但是在提交過程中總發(fā)現(xiàn)會(huì)TE。仔細(xì)分析發(fā)現(xiàn)是對(duì)于每次運(yùn)算的結(jié)果沒有進(jìn)行儲(chǔ)存而造成了重復(fù)運(yùn)算。比如在計(jì)算fun(40)時(shí)遞歸計(jì)算了fun(39)和fun(38),而在計(jì)算fun(39)的過程中又計(jì)算了一遍fun(38)。也就是說，計(jì)算過一遍的結(jié)果不能加以儲(chǔ)存，重復(fù)的計(jì)算造成了時(shí)間上的浪費(fèi)。這時(shí)候很容易想到用數(shù)組來儲(chǔ)存對(duì)應(yīng)的結(jié)果。那么為了實(shí)現(xiàn)遞歸數(shù)列的計(jì)算，應(yīng)該這樣操作

int a[55];a[0]=a[1]=1;for(int i=2;i<55;i++) a[i]=a[i-1]+a[i-2];

此時(shí)數(shù)組中儲(chǔ)存的就應(yīng)該是斐波那契數(shù)列的第n項(xiàng)了，這時(shí)候輸入一個(gè)對(duì)應(yīng)的值x，直接輸出a[x]即為問題的解，時(shí)間復(fù)雜度為O（n）；接下來自然而然的就會(huì)想，函數(shù)遞歸調(diào)用結(jié)合數(shù)組也具有相同的能力儲(chǔ)結(jié)果

#include<stdio.h>#include<iostream>#include<string.h>using namespace std;int a[55];int func(int x){ if(a[x])//如果a[x]不為0，說明a[x]被計(jì)算過了,或是已經(jīng)有了初始值 return a[x]； //如果a[x]沒有被計(jì)算過，說明需要遞歸； a[x]=func(x-1)+func(x-2); return a[x];}int main(){ memset(a,0,sizeof(a));//其實(shí)不需要 a[0]=a[1]=1; func(55);//這是說，從高向低開始遞歸 int no; scanf("%d",&no); 但是，在實(shí)際過程中又出現(xiàn)了一個(gè)不大不小的問題：數(shù)據(jù)溢出了！也就是說，32位的數(shù)字已經(jīng)無法儲(chǔ)存結(jié)果了。因此我們需要64位的整型參與運(yùn)算針對(duì)不同的編譯器，有了兩種解決對(duì)策： VC++：64位整型的數(shù)類型為_int64,那么輸入輸出的時(shí)候就要寫成printf(“%I（大寫的i）64d”,a[50]);這種數(shù)據(jù)類型不支持輸入輸出流的>>和<<操作 GC++：64位整型的數(shù)據(jù)類型位long long (int),輸入輸出的時(shí)候?qū)懗蓀rintf（“%lld”,a[50]);longlong類型同時(shí)支持輸入輸出流的>>和<<；也就是說，一類題讓我知道了兩種解題方法，兩個(gè)避開小陷阱的方法。開心o(￣▽￣)ブ