裴波那契數列的遞歸和動態規劃算法

一、??? 概論

通過對裴波那契數列的例子，分析了遞歸和動態規劃算法的本質。并且說明了兩種算法的區別。

裴波那契數列：800年前，意大利的數學家斐波納契出版了驚世之作《算盤書》。在《算盤書》里，他提出了著名的“兔子問題”：假定一對兔子每個月可以生一對兔子，而這對新兔子在出生后第二個月就開始生另外一對兔子，這些兔子不會死去，那么一對兔子一年內能繁殖多少對兔子？

答案是一組非常特殊的數字：1，1，2，3，5，8，13，21，34，55，89……不難發現，從第三個數起，每個數都是前兩數之和，這個數列則稱為“斐波納契數列”，其中每個數字都是“斐波納契數”。

斐波納契數列還暗含著許多有趣的數字規律，如從第3個數開始每隔兩個必是2的倍數，從第4個數開始每隔3個必是3的倍數，從第5個數開始每隔4個必是5的倍數……另外，這個數列最具有和諧之美的地方是，越往后，相鄰兩項的比值會無限趨向于黃金比0.61803……即[5^(1/2)-1]/2。

但這個偉大的發現在當時一直不受數學們的青睞與認可，直到19世紀，斐波納契數列才在該領域占有一席之地并引發出了許多重要的應用。像斐波納契方塊，斐波納契螺旋以及斐波納契數，在生活中都可以見到類似的圖案，譬如說海螺和蝸牛殼等等。

----------------------------以上來自360百科

這個數列感覺還是非常有意思的。感興趣的同學可以多多研究一下。另外本文只是本人一個簡單的分享感悟，有很多不正確的地方，請大家指正。

二、??? 裴波那契數列的遞歸分析

由上面的介紹可以得出裴波那契數列的遞歸算式：

也很容易寫出下面的遞歸算法：

#include <iostream>

using namespace std;

//采用遞歸的方式求解裴波納契數列

int f(int n)

{

if(n==0)return 1;

if(n==1)return 1;

return f(n-1)+f(n-2);

}

int main()

{

//輸出數列的前20項

for(int i=0;i<20;i++)

{

cout<<"第i項："<<f(i)<<endl;

}

return 0;

}

輸出結果如圖：

遞歸算法時間復雜度分析：

由上面的遞歸樹可以分析，最右邊是每次減少2，因此右邊的層次數是最低的，因此可以通過右邊的層次來計算最少的時間復雜度。

每次個節點都產生兩個子節點，因此子節點的個數，就是要計算的復雜度，即總共需要計算：

c是一個常數，即兩個數相加需要的時間。

根據上述等比數列，可以知道時間復雜度為指數級別（具體多少讀者可以根據上面的算式計算）。

因此采用遞歸會導致大量的重復計算，例如在圖中的f(n-3)就會被計算兩次。同時，由于計算機本身的性質，遞歸次數不能過多，否則會導致棧溢出，導致程序崩潰。因此這里采用遞歸算法不僅造成時間復雜度很大，同時還造成棧溢出的可能。

本例中，當采用遞歸求解第40項的時，速度已經很慢，求解第50項的時，已經沒有響應了。

三、??? 裴波那契數列的動態規劃分析

動態規劃的主要兩個步驟：

a)???????? 最優解的結構

f(i)=f(i-1)+f(i-2)，這就是最優解的結構，只不過不像一般的問題，這里的子結構都是固定的

b)???????? 遞歸定義最優解

這里的遞歸定義和遞歸算法中的公式是一樣的。

c)???????? 自底向上

從底向上的求解，這里是最大的區別。遞歸算法是從上到下的計算，即將大問題分別分解成若干個小問題，然后遞歸求解小問題，直到達到原子問題，然后開始逐步返回，計算每個大的問題。即存在某些問題會反復計算多次。

而從底向上的解法，則是從小問題開始，計算完成后就記錄下小問題的解，然后通過小問題的解，構造出大問題的解，如此重復。即每個問題只需要計算一次即可。

d)???????? 由結果構造最優解

動態規劃算法：

#include <iostream>

using namespace std;

//采用遞歸的方式求解裴波納契數列

int f(int n)

{

if(n==0)return 1;

if(n==1)return 1;

return f(n-1)+f(n-2);

}

//采用動態規劃思想求解裴波納契數列

static int record[40]={0};

void count(int n)

{

record[0]=1;

record[1]=1;

for(int i=2;i<n;i++)

{

record[i]=record[i-1]+record[i-2];

}

}

int main()

{

//輸出前20項

count(20);

for(int i=0;i<20;i++)

{

cout<<record[i]<<endl;

}

return 0;

}

輸出結果：

時間復雜度分析：

比較容易知道，上面的算法只是到n的一個簡單循環，因此時間復雜度是o(n)，即n的線性時間復雜度。

本例中，當采用遞歸求解第40和第50項項的時，速度很快。

四、??? 結合了動態規劃和遞歸兩種方法的思想求解裴波納契數列

結合兩種方法的優點，即采用遞歸容易理解的結構，同時加入動態規劃中的記錄表，防止遞歸中的重復計算。即記錄遞歸過程中產生的每一個值，如果遇到已經曾經計算過的小問題的值，則不再重復遞歸，直接返回即可。

算法如下：

#include <iostream>

using namespace std;

//采用遞歸的方式求解裴波納契數列

int f(int n)

{

if(n==0)return 1;

if(n==1)return 1;

return f(n-1)+f(n-2);

}

//采用動態規劃思想求解裴波納契數列

static int record[40]={0};

void count(int n)

{

record[0]=1;

record[1]=1;

for(int i=2;i<n;i++)

{

record[i]=record[i-1]+record[i-2];

}

}

//結合了動態規劃和遞歸兩種方法的思想求解裴波納契數列

static int c[40]={1,1,0};

int f_count(int n)

{

if(n==0)return c[0];

if(n==1)return c[1];

//如果兩個子問題已經存在解 則直接返回這個解，并且記錄當前問題的解

if(c[n-1]!=0 && c[n-2]!=0)

{

c[n]=c[n-1]+c[n-2];

return c[n];

}

//如果不存在，則遞歸求解

else

{

return f_count(n-1)+f_count(n-2);

}

}

int main()

{

//輸出前20項

f_count(20);

for(int i=0;i<20;i++)

{

cout<<c[i]<<endl;

}

return 0;

}

算法輸出：

時間復雜度分析：

由于記錄了曾經計算過的值，因此導致很多點不再被重復計算，僅僅是一個簡單的一重遞歸，即時間復雜度為o(n)，即為n的線性時間。

本例中，當采用遞歸求解第40和第50項項的時，速度同樣很快。

五、??? 總結

個人感覺，其實在某種程度上來說，動態規劃和分治法是有著相同的思想。分治法的思想是將大問題分解為小問題。而動態規劃思想是取最優子結構。但是從計算方法上來說，分治法是自頂向下的分解問題，然后自底向上返回問題的解。而動態規劃一開始就直接從底向上的將小問題的解綜合成大問題的解。動態規劃相對分治法中的遞歸算法時間上是采用了以空間換時間的方式。即在計算小問題的過程中記錄下小問題的值。而遞歸是不會記錄小問題的值，每次都是重復計算。

而采用兩種方法相結合的方式也同樣可以提高運行速度。其內在原因就是是否重復計算的問題。

文檔下載地址：http://pan.baidu.com/share/link?shareid=531539743&uk=2903070410

源代碼下載地址：http://pan.baidu.com/share/link?shareid=535428463&uk=2903070410

文章來自IT部落格(www.itbuluoge.com)

總結

以上是生活随笔為你收集整理的裴波那契数列的递归和动态规划算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。