做水題的過程中，有很多題一看就知道是與斐波那契數列相關知識求解的過程，即a[x]=a[x-1]+a[x-2]; 例如：
1.超級樓梯：有一樓梯共M級，剛開始時你在第一級，若每次只能跨上一級或二級，要走上第M級，共有多少種走法？ 輸入數據首先包含一個整數N，表示測試實例的個數，然后是N行數據，每行包含一個整數M（1<=M<=40）,表示樓梯的級數。對于每個測試實例，請輸出不同走法的數量。2.一只小蜜蜂... 有一只經過訓練的蜜蜂只能爬向右側相鄰的蜂房，不能反向爬行。請編程計算蜜蜂從蜂房a爬到蜂房b的可能路線數。 其中，蜂房的結構如下所示。一只小蜜蜂原題
3.骨牌鋪方格 在2×n的一個長方形方格中,用一個1× 2的骨牌鋪滿方格,輸入n ,輸出鋪放方案的總數. 例如n=3時,為2× 3方格，骨牌的鋪放方案有三種,如下圖骨牌鋪方格原題
很容易發現這些題都是利用斐波那契數列直接求解的題?；蛘叱橄笠稽c，都是通過遞歸方法進行求解。談及遞歸很容易想到的是利用函數的遞歸調用進行求解。比如說：
int fun(int x){ if(x==1||x==0)return 1; return fun(x-1)+(x-2);}這樣的解法直接明了，但是在提交過程中總發現會TE。仔細分析發現是對于每次運算的結果沒有進行儲存而造成了重復運算。比如在計算fun(40)時遞歸計算了fun(39)和fun(38),而在計算fun(39)的過程中又計算了一遍fun(38)。也就是說，計算過一遍的結果不能加以儲存，重復的計算造成了時間上的浪費。 這時候很容易想到用數組來儲存對應的結果。那么為了實現遞歸數列的計算，應該這樣操作
int a[55];a[0]=a[1]=1;for(int i=2;i<55;i++) a[i]=a[i-1]+a[i-2];此時數組中儲存的就應該是斐波那契數列的第n項了，這時候輸入一個對應的值x，直接輸出a[x]即為問題的解，時間復雜度為O（n）； 接下來自然而然的就會想，函數遞歸調用結合數組也具有相同的能力儲結果
#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]被計算過了,或是已經有了初始值 return a[x]； //如果a[x]沒有被計算過，說明需要遞歸； a[x]=func(x-1)+func(x-2); return a[x];}int main(){ memset(a,0,sizeof(a));//其實不需要 a[0]=a[1]=1; func(55);//這是說，從高向低開始遞歸 int no; scanf("%d",&no); 但是，在實際過程中又出現了一個不大不小的問題：數據溢出了！也就是說，32位的數字已經無法儲存結果了。因此我們需要64位的整型參與運算 針對不同的編譯器，有了兩種解決對策： VC++：64位整型的數類型為_int64,那么輸入輸出的時候就要寫成printf(“%I（大寫的i）64d”,a[50]);這種數據類型不支持輸入輸出流的>>和<<操作 GC++：64位整型的數據類型位long long (int),輸入輸出的時候寫成printf（“%lld”,a[50]);longlong類型同時支持輸入輸出流的>>和<<； 也就是說，一類題讓我知道了兩種解題方法，兩個避開小陷阱的方法。 開心o(￣▽￣)ブ新聞熱點
疑難解答
