天天看點

14天閱讀挑戰賽(神奇的兔子數列)神奇的兔子數列

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)對兔子。

......

為了讓表達更清楚,可用圖示分别表示新生兔子、成熟期兔子和生育期兔子,兔子的繁殖過程如圖所示。

14天閱讀挑戰賽(神奇的兔子數列)神奇的兔子數列

 由上述分析可得: 當月的兔子數=上月兔子數+上上月的兔子數 斐波那契數列如下: 1,1,2,3,5,8,13,21,34, 遞歸表達式如下:

14天閱讀挑戰賽(神奇的兔子數列)神奇的兔子數列

2、算法設計

下列按照遞歸算法進行:

 int Fibl(int n){
     if(n==1|n=2)
     return 1;
     return Fib1(n-1)+Fib1(n-2);
 }      

3、算法複雜度

遞歸表達式和時間複雜度T()的關系如下:

14天閱讀挑戰賽(神奇的兔子數列)神奇的兔子數列

 求出斐波那契數列的通項公式:

14天閱讀挑戰賽(神奇的兔子數列)神奇的兔子數列

 由于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)。

繼續閱讀