遞歸題目之斐波那契數列

作者: cnyao 來源: 博客園發布時間: 2009-11-26 21:46 閱讀: 2434 次推薦: 0 原文鏈接 [收藏]

原題：用遞歸求第10個數，它等于前2數之和，如{1，1，2，3，5}

得到遞歸式為f(n)=f(n-1)+f(n-2)，終止條件為f(0)=1, f(1)=1。求的數為f(9)。

1 #include <iostream>
2 using namespace std;
3
4 int f(int n)
5 {
6     if (n==1 || n==0)
7     {
8         return 1;
9     }
10     else
11     {
12         return f(n-2)+f(n-1);
13     }
14 }
15
16 int main()
17 {
18     cout<<f(9)<<endl;
19
20     return 0;
21 }
22

由于遞歸式比較簡單，所以這個程序也就沒有什么好說的。

但是關于斐波那契，還是有不少內容來探討。

斐波那契數列最初出現是計算兔子的數目，所以又被稱為“兔子數列”，所以看到農夫養牛等問題，還是可以聯系上的。

關于斐波那契的討論，主要集中在對其的優化，以及其擴展題目上，遞歸已經由只有一項在變，變成兩項在變了。其擴展的題目，如何得到遞歸式，如何透過現象來將遞歸式寫出來，才是真正的要點。

包括農夫養牛問題，爬樓梯問題，打靶問題等等，應該算起來都算是斐波那契問題的一些擴展。

【擴展】

1. 一個農夫養了一頭牛，三年后，這頭牛每年會生出1頭牛，生出來的牛三年后，又可以每年生出一頭牛……問農夫10年后有多少頭牛?n年呢

老外喜歡養牛，在很多題目中都可以看到奶牛還是什么牛的身影。這道題目的網址為：

http://topic.csdn.net/u/20091001/15/40bf4993-8ed7-45cc-968f-97c524dae3c4.html?80749

而前段時間園子中有兄弟已經詳細探討了這個問題。

http://www.cnblogs.com/chinese-zmm/archive/2009/10/31/1593586.html

關于這個問題，其實一開始遇到是使用模擬的思路去想的，而且想得比較的糊涂，因為牛生下來之后，并不是馬上就可以生小牛，是在三年后，每年生一頭牛，那假設某一年，就有能生小牛的，還有一年生小牛的，還有兩年生小牛的，然后就自己把自己繞住了。

但是，其實沒有這么復雜，就是將其分為能生小牛的和不能生小牛的。

從而得到：

今年的牛的數目=去年的牛的數目+三年前牛的數目

也就是f(n)=f(n-1)+f(n-3)

這里

f(n-2) 第一年

f(n-1) 第二年

f(n) 第三年

看了一下題目，應該是三年后，那就應該是n-3。

代碼如下：

1 #include <iostream>
2 using namespace std;
3
4 int Fibonacci(int n)
5 {
6     if (n==1 || n==2 || n==3)
7     {
8         return 1;
9     }
10     return Fibonacci(n-1)+Fibonacci(n-3);
11 }
12
13 int main()
14 {
15     cout<<Fibonacci(10+1)<<endl;
16 }

這里輸入參數為n+1，是因為是n年后的數目，所以需要加1。

這道題目，也可以使用數組將運算的結果保存下來，然后直接進行計算，這就是常說的動態規劃。

代碼如下：

1 int Fibonacci2(int n)
2 {
3     int *num=new int[n];
4     num[0]=num[1]=num[2]=1;
5     for (int i=3;i<n;i++)
6     {
7         num[i]=num[i-1]+num[i-3];
8     }
9     int ret=num[n-1];
10     delete []num;
11     return ret;
12 }
13
14 int main()
15 {
16     cout<<Fibonacci2(10+1)<<endl;
17 }

上面的程序使用了n個的數組來存，但是其實并不需要，只需要3個數參與運算即可。

而園子中的兄弟在這個基礎上又做了兩個擴展，一個是將特殊一般化，也就是不單單是3年，如果是m年呢？

如果m年則得到

f(n)=f(n-1)+f(n-m)

同時這里的牛只有生沒有死，那加上到了一定的時間牛就會死呢？

假設牛到了第8年就掛了。

那就可以得到

f(n)=f(n-1)+f(n-3)-f(n-8)

2. 打靶問題：一個人打靶，成績為0～10之間的任意一個整數。包括0和10。一共打了10次總共得分89分。問得分的可能性。

可以得到比較明顯的一個遞歸式，f(n)=x+f(n-1)，而x的取值為0-10之間的任意一個整數。

所以我們需要去做一個變化的x，其實也就是一個循環來得到。

因為要求的結果為得分的可能性，所以我們要將結果保存起來，然后每遇到結果為89的，則將保存的結果打印出來，然后統計+1，所以我們需要一個10個數的數組來做這件事情。

遞歸終止條件是當n為0時終止，此時來判斷分值并進行相應的操作。

1 #include <iostream>
2 using namespace std;
3
4 int countresult;
5 int store[10];
6
7
8 void getscore(int sum, int n)
9 {
10     if(sum<0 || sum+(n+1)*10<89 || sum>89)
11         return;
12     if(n==0)
13     {
14         //check the number
15         if(sum==89)
16         {
17             for(int i=0;i<10;i++)
18                 cout<<store[i]<<" ";
19             cout<<endl;
20             countresult++;
21         }
22         return;
23     }
24     for(int i=0;i<=10;i++)
25     {
26         store[10-n]=i;
27         getscore(sum+i,n-1);
28     }
29 }
30
31 int main()
32 {
33     getscore(0,10);
34     cout<<"總數"<<countresult<<endl;
35     return 0;
36 }

注意上面的代碼，其實上面還是應用了遞歸中常使用的一種做法--剪枝。

上面的代碼并不太好，比較好的是下面的代碼，但是兩種方法作出的值是一樣的。

1 #include <iostream>
2 using namespace std;
3
4 int sum;
5 int store[10];
6
7 void Output()
8 {
9     for(int i = 9; i>=0; --i)
10     {
11        cout<<store[i]<<" ";
12     }
13    cout<<endl;
14     ++sum;
15 }
16
17 void Cumput(int score, int num)
18 {
19    if(score < 0 || score > (num+1)*10 ) //次數num為0～9
20       return;
21    if(num == 0)
22    {
23        store[num] = score;
24        Output();
25        return;
26    }
27    for(int i = 0; i <= 10; ++i)
28    {
29        store[num] = i;
30        Cumput(score - i, num - 1);
31    }
32 }
33
34 int main(int argc, char* argv[])
35 {
36     Cumput(89, 9);
37     cout<<"總數:"<<sum<<endl;
38     return 0;
39 }

上面代碼參考：http://www.cnblogs.com/lds85930/archive/2007/07/05/807198.html

其實這里的話題很廣，涉及到具體的各種優化，如何提高執行的時間（當然，前提是要保證結果的正確性），不過對于算法這個還是了解不深啊，大家可以看看這些，給些意見。

3. 爬樓梯問題：

一個N級的樓梯，一個人每次可以爬一級，也可以爬兩級，問如果給定一個N要求輸出所有的爬樓方法，并統計出方法數。

可以思考，在第n級的時候，可以通過f(n-1)爬1級得到，也可以通過f(n-2)爬兩級得到，如果f(n-2)爬1級，也就是又到f(n-1)，其實是涵蓋在前面一種情況下的。所以得到遞歸公式： f(n)=f(n-1)+f(n-2)，很明顯，得到遞歸公式后，就是斐波那契數列。

再擴展，如果每次可以爬一級，也可以爬兩級，也可以爬三級。那此時遞歸公式怎么推？

此時就要加上f(n-3)的情況，而f(n-3)上面爬2級，爬1級，又回到f(n-2)或者f(n-1)，所以得到遞歸式為

f(n)=f(n-1)+f(n-2)+f(n-3)

關于斐波那契的類似問題很多，但是如何思考得到遞歸式是重點，當得到正確的遞歸式后，就明白是斐波那契，那就能夠直接使用斐波那契相關的方法來做該問題了。

最后有一道思考題，是概率題：

一副52張的牌（去掉大小鬼），4張A排在一起的概率是多少？

為了避免誤解題意，將原題也放在這里 (A deck of 52 cards is shuffled thoroughly. What is the probability that the 4 aces are all next to each other?)