整理一下經(jīng)典算法用C/C++實現(xiàn)，并思考總結(jié)
題目：有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數(shù)為多少？
常規(guī)解法
讀題之后，我直接著手進(jìn)行解題：
思路：設(shè)置2個變量分別保存成年兔子數(shù)，幼年兔子數(shù)量，設(shè)置一個計數(shù)器分組分別計算每對小兔子還有幾個月成年，成年后加入成年兔子。成年兔子每月產(chǎn)下幼年兔子加入幼年兔子。
void rabitNormal(int month){
const int MAX_SHALL_RABIT = 1000;//最大小兔子數(shù)量(這個算法用數(shù)組做有局限性，最大只能MAX_SMALL_RABIT個兔子)
int big_rabits = 0;//大兔子數(shù)量(初始都是小兔子)
int small_r = 1;//小兔子數(shù)量
short small_rabits[MAX_SHALL_RABIT];
small_rabits[0]=2;//初始化第一對小兔子計數(shù)器
int idx = 1;
for (int i=0; i<month; i++) {//每個月更新
for (int j=0; j<idx; j++) {
if(small_rabits[j]>0){
small_rabits[j]--;
if(small_rabits[j]==0){//第三個月
big_rabits ++;//大兔子增加
small_r--;//小兔子減少
}
}
}
for(int j=0;j<big_rabits;j++){
small_rabits[idx++] = 2;//每對大兔子生一對小兔子
small_r++;//小兔子數(shù)量增加
}
}
cout<<big_rabits+small_r<<endl;//打印大兔子小兔子總和
}
這個方法直接從實現(xiàn)角度來解決這個問題，就事論事，不太優(yōu)雅。
遞歸算法
因為每對兔子從出生到生產(chǎn)的過程是一致的，所以我考慮是不是封裝一個方法來表示兔子的這一過程，然后用遞歸實現(xiàn)
//遞歸實現(xiàn) 返回第一對兔子和之后所有小兔子生下的總兔子對數(shù)
int rabits(int month){
int r = 0;
for(int i=2;i<=month;i++){
r+=rabits(month-i);//從第3個月起每個月生一堆兔子
}
return 1 + r;//這只兔子升的小兔子的總對數(shù)
}
這個方法我認(rèn)為從解決問題的角度不失為一個好方法。但對規(guī)律問題考慮不深入，也屬于就事論事。
斐波那契數(shù)列
網(wǎng)上看了正規(guī)解法后發(fā)現(xiàn)，這道題表現(xiàn)的本質(zhì)就是斐波那契數(shù)列 f(0)=0,f(1)=1...f(n)=f(n-1)+f(n-2) (當(dāng)前項等于前兩項之和)。這一數(shù)列強(qiáng)大之處我還無法深入體會，我就整理下如何讓兔子生產(chǎn)和斐波那契數(shù)列聯(lián)系起來：
思考過程
1.第一個月1對幼年兔子，0對成年兔子
2.第二個月把幼年兔子加入成年兔子(因為第3個月生產(chǎn)出的幼年兔子等于當(dāng)月的成年兔子)，0對幼年，1對成年
3.第三個月幼年兔子對數(shù) = 前月成年兔子對數(shù)1，成年兔對數(shù) = 前月幼兔對數(shù)+前月成年對數(shù)=0+1=1
總結(jié)公式：
兔子總對數(shù) = 成年兔子對數(shù)+幼年兔子對數(shù)
成年兔子對數(shù) = 前月成年兔子對數(shù)+前月幼年兔子對數(shù) = 前月總對數(shù)
幼年兔子對數(shù) = 前月成年兔子對數(shù) = 大前月兔子總對數(shù)（由上條公式得到）
最終推導(dǎo)公式：兔子總對數(shù) = 前月兔子總對數(shù)+大前月兔子總對數(shù)！ 這個公式正好符合Fibonacci數(shù)列
void rabitFibonacci(){
long f1,f2;
int i;
f1=f2=1;
for(i=1;i<=20;i++)
{
printf("%12ld %12ld",f1,f2);
if(i%2==0) printf("\n");/*控制輸出，每行四個*/
f1=f1+f2;/*前兩個月加起來賦值給第三個月*/
f2=f1+f2;/*前兩個月加起來賦值給第三個月*/
}
}
整個推導(dǎo)過程為了讓幼年兔子對數(shù)更純凈(保證都是上月生產(chǎn)的兔子)，次月我們就把前一個月的幼年兔子并入成年了，這是由于從客觀上來說
- 當(dāng)月成年對數(shù)決定次月幼年對數(shù)同時和當(dāng)月幼年對數(shù)一起決定當(dāng)月總對數(shù)
- 當(dāng)月幼年對數(shù)和當(dāng)月成年對數(shù)決定次月成年對數(shù)
所以以上對幼年對數(shù)當(dāng)月的“純凈”處理有利于對幼年對數(shù)的直接使用(試想一下如果幼年對數(shù)中混有新生的和上個月生的，你該如何處理它)。
從這推導(dǎo)過程的構(gòu)架和實際推導(dǎo)過程中，我認(rèn)為變量定義功能的明確性和純凈性非常重要。我要的不是這個數(shù)列和公式的直接應(yīng)用，而是這個推導(dǎo)過程。想想當(dāng)三個月變成四個月，變成五個月該怎么來推導(dǎo)？
小結(jié)：3個算法前2個算法是我自己寫，第3個方法是參考網(wǎng)上的，推導(dǎo)過程是自己模擬的，雖然花了不少時間做推導(dǎo)，但我覺得還是值得的，因為我現(xiàn)在最缺的就是一顆萬事靜心思考本質(zhì)的心，推導(dǎo)的方式固然重要，但這顆探究本質(zhì)的心更重要
