14天閱讀挑戰賽
努力是為了不平庸~
算法學習有些時候是枯燥的，這一次，讓我們先人一步，趣學算法！歡迎記錄下你的那些努力時刻（算法學習知識點/算法題解/遇到的算法bug/等等），在分享的同時加深對于算法的了解，同時吸收他人的奇思妙想，一起見證技術er的成長~
目錄
神奇的兔子數列
1、問題分析
2、算法設計
3、算法複雜度
4、算法改進
神奇的兔子數列
假設第1個月有1對初生的兔子，第2個月進入成熟期，第3個月開始生育兔子，而1對成熟的兔子每月會生 1對兔子，兔子永不死去..那麼，由1對初生的兔子開始，12個月後會有多少對兔子呢？ 兔子數列即斐波那契數列，它的發明者是意大利數學家菜奧納爾多斐波那契。1202年，萊奧納爾多撰寫了《算盤全書》，該書是一部較全面的初等數學著作。書中系統地介紹了印度一阿拉伯數位及其演算法則，以及中國的盈不足術”：此外還引入了負數，并研究了一些簡單的一次同餘式組。
1、問題分析
不妨拿新出生的1對小兔子分析。
第1個月，小兔子①沒有繁殖能力，是以還是1對。
第2個月，小兔子①進入成熟期，仍然是1對。
第3個月，兔子①生了1對小兔子②，于是這個月共有2(1+1=2)對兔子。
第4個月，兔子①又生了1對小兔子③，是以比共有3(1+2=3)對兔子。
第5個月，兔子①又生了1對小兔子④，而在第3個月出生的兔子②也生下了1對小兔子⑤，是以共有5(2+3=5)對兔子。
第6個月，兔子①②③各生下了1對小兔子，新生的3對兔子加上原有的5對兔子，這個月共有8(3+5=8)對兔子。
......
為了讓表達更清楚，可用圖示分别表示新生兔子、成熟期兔子和生育期兔子，兔子的繁殖過程如圖所示。
由上述分析可得： 當月的兔子數=上月兔子數+上上月的兔子數 斐波那契數列如下： 1,1,2,3,5,8,13,21,34, 遞歸表達式如下：
2、算法設計
下列按照遞歸算法進行：
int Fibl(int n){
if(n==1|n=2)
return 1;
return Fib1(n-1)+Fib1(n-2);
} 3、算法複雜度
遞歸表達式和時間複雜度T()的關系如下：
求出斐波那契數列的通項公式：
由于T(n)≥F(n)，是以這是一個指數階的算法！
4、算法改進
斐波那契數列中的每一項（開頭的兩項除外）是前兩項之和，如果記錄前兩項的值，則隻需要一次加法 運算就可以得到目前項的值，時間複雜度會不會更低一些呢？不妨用數組試試看，見如下算法。
int Fib2(int n){
int*F=new int[n+l];//定義一個長度為n+1的數組，空間尚未使用
F[1]=1
F[2]=1;
for(int i=3;i<=nji++)
F[i]=F[i-1]+F[i-2];
return F[n];
} 該算法時間複雜度降到了多項式，且空間複雜度為O()。 對算法再做進一步的改進采取疊代法進行設計：
int Fib3(int n){
if(n=1||n=2)
return 1;
ints1=1;//用s1和s2記錄前面的兩項
int s2=1;
for(int i=3;i<=nji++){
int tmp=s1+s2;
s1=s2;
s2=tmpj;
}
return s2;
} 該算法使用了幾個輔助變量進行疊代，時間複雜度為0()，但空間複雜度降到了0(1)。