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