有一個(gè)經(jīng)典的算法問(wèn)題轧飞，題目是這樣的：
有一對(duì)小兔子，當(dāng)小兔子成長(zhǎng)到第三個(gè)月的時(shí)候按厘，每個(gè)月都會(huì)生一對(duì)小兔子纲菌，新生的小兔子同他們的父母具有一樣的生殖性質(zhì)（成長(zhǎng)到第三個(gè)月之后每個(gè)月都生一對(duì)），兔子不會(huì)死亡宝磨，求n個(gè)月后有多少對(duì)兔子弧关。
這個(gè)問(wèn)題很容易，有很多種方法可以解決懊烤，比較經(jīng)典的方法有兩種梯醒，遞歸和動(dòng)態(tài)規(guī)劃。
動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃的思路是從最終態(tài)（第n月兔子的數(shù)量）開(kāi)始思考腌紧，嘗試找到第n個(gè)月兔子數(shù)量茸习，和第n-1個(gè)月兔子數(shù)量間的遞推關(guān)系。找到遞推關(guān)系之后壁肋，我們不需要在關(guān)注中間過(guò)程号胚，只需要從最初態(tài)開(kāi)始遞推籽慢，保存每次遞推的結(jié)果（每個(gè)月兔子的數(shù)量），自然就能得出第n個(gè)月兔子的數(shù)量猫胁。
從這道題來(lái)看箱亿，因?yàn)橥米邮且栽逻@個(gè)時(shí)間單位，一代一代生出來(lái)的弃秆，所以每個(gè)月的兔子數(shù)量届惋，應(yīng)該是存在遞推關(guān)系的。那么第n個(gè)月兔子數(shù)量應(yīng)該怎么和n-1個(gè)月兔子數(shù)量聯(lián)系起來(lái)呢菠赚？很顯然脑豹，因?yàn)橥米硬粫?huì)死亡，所以第n個(gè)月兔子的組成應(yīng)該是：n-1個(gè)月時(shí)全部的兔子衡查，和第n個(gè)月新生的兔子數(shù)量之和瘩欺。設(shè)第n個(gè)月的兔子數(shù)量為F(n)，也就是：
F(n)=F(n-1)+第n月新生的兔子
為了完成這個(gè)狀態(tài)轉(zhuǎn)移方程拌牲，我們需要搞清第n月新生兔子和兔子數(shù)量之間的聯(lián)系俱饿。
我們不妨從第k月開(kāi)始跟蹤，因?yàn)橥米拥谌齻€(gè)月可以繁殖塌忽，也就是兔子其實(shí)可以劃分成三種不同的狀態(tài)拍埠，所以我們不妨用mature(k)表示第k月成熟的（可繁殖的）兔子數(shù)量，grow(k)表示第k月正在成長(zhǎng)的（在生命歷程第二個(gè)月的）兔子數(shù)量砚婆，最后用born(k)表示第k月新生的兔子數(shù)量：
k月時(shí)兔子的數(shù)量 ? ? ? ? ?? k+1月時(shí)兔子的數(shù)量 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? k+2月時(shí)兔子的數(shù)量
mature(k) ? ? ? ? ? ? ? ? ? ? ? mature(k+1)=mature(k)+grow(k) ? ? ? ? ?? mature(k+2)=mature(k+1)+grow(k+1)=mature(k)+grow(k)+born(k)
grow(k) ? ? ? ? ? ? ? ? ? ? ? ? ? grow(k+1)=born(k) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? grow(k+2)=born(k+1)=mature(k)+grow(k)
born(k)=mature(k) ? ? ? ?? born(k+1)=mature(k+1) ? ? ? ? ? ? ? ? ? ? ? ?? born(k+2)=mature(k+2)=mature(k)+grow(k)+born(k)
通過(guò)觀察這個(gè)遞推關(guān)系械拍，不難發(fā)現(xiàn)其實(shí)k+2個(gè)月時(shí)新生兔子的數(shù)量就等于第k月時(shí)兔子的總數(shù)。所以我們可以得到狀態(tài)轉(zhuǎn)移方程：
F(n)=F(n-1)+F(n-2)
其實(shí)也可以直觀的去想装盯，第n個(gè)月，所有兔子繁殖之前甲馋，總數(shù)就是n-1月兔子的總數(shù)F(n-1)埂奈，那么這F(n-1)對(duì)兔子中，又有多少是可繁殖的呢定躏，那想必需要減去其中不成熟的账磺，那實(shí)際上，兔子只會(huì)在自己新生的那個(gè)月和其下一個(gè)月不成熟痊远，也就是只需減去F(n-1)中新生的兔子數(shù)量垮抗，也就是：
第n月可以繁殖的兔子數(shù)量=F(n-1)-(n-1月新生的兔子)
結(jié)合我們已知的狀態(tài)轉(zhuǎn)移方程：F(n)=F(n-1)+第n月新生的兔子，將n-1帶入到方程的n中碧聪，顯然答案就是F(n-2)冒版，也就是第n月，可以繁殖的兔子數(shù)量就是F(n-2)逞姿，可以得到一樣的狀態(tài)轉(zhuǎn)移方程辞嗡。
C語(yǔ)言代碼實(shí)現(xiàn)：
#include <stdio.h>
int main(){
? ? unsigned long count[100]={0};? //初始化數(shù)組保存兔子數(shù)量
????int n=0;
????printf("Please input month number(1~99):");
????scanf("%d",&n); //獲取用戶輸入的月份數(shù)
????for(int i=0;i<n;i++){
????????????????if(i==0||i==1){
????????????????????????????count[i]=1;
????????????????}
????????????????else{
????????????????????????????count[i]=count[i-1]+count[i-2];
? ? ? ? ? ? ?? }
????}
????printf("The number of rabbit is:%lu",count[n-1]);
}
這段代碼簡(jiǎn)單的實(shí)現(xiàn)了算法捆等，但是仍然需要升級(jí)，因?yàn)殡m然用戶可輸入的范圍是1~99续室，但實(shí)際測(cè)試下栋烤，即使已經(jīng)使用了unsigned long，因?yàn)閡nsigned long的取值范圍為0至4,294,967,295挺狰，當(dāng)輸入月份在47以上的時(shí)候明郭，值會(huì)溢出》岵矗考慮下一步升級(jí)通過(guò)字符串?dāng)?shù)組保存兔子數(shù)量达址，實(shí)現(xiàn)大整數(shù)的保存。
遞歸
遞歸算法設(shè)計(jì)的思路上相對(duì)比較直接趁耗，明確終止條件沉唠，調(diào)用自身進(jìn)行運(yùn)算就可以了。
所以我們的終止條件是：
當(dāng)月份數(shù)減為1的時(shí)候 ?? return兔子數(shù)=1
當(dāng)月份數(shù)減為2的時(shí)候 ?? return兔子數(shù)=1
運(yùn)算過(guò)程：
F(n)=F(n-1)+F(n-2)
#include <stdio.h>
unsigned long recur(int n);
int main(){
????????int n=0;
????????scanf("%d",&n);
????????printf("%lu",recur(n));
????????return 0;
}
unsigned long recur(int n){
????????if(n==1||n==2){
????????????????return 1;
????????}
????????else{
????????????????return recur(n-1)+recur(n-2);
????????}
}
總結(jié)
兩種方法都可以完成這道題的計(jì)算苛败，但是實(shí)際運(yùn)行下來(lái)满葛，使用動(dòng)態(tài)規(guī)劃基本都是妙出結(jié)果（時(shí)間復(fù)雜度為O(n)），而遞歸則相對(duì)慢很多（時(shí)間復(fù)雜度O(2的n次方)）罢屈，但從空間復(fù)雜度上來(lái)講嘀韧，遞歸更勝一籌。
