遞歸——自己定義自己2
- 思考：和的定義
假設(shè)n為0以上的整數(shù)，使用遞歸的方式從0到n的整數(shù)之和。
- n=0時(shí), S(n)=0
- n>1時(shí)，n=S(n-1) (n=1,2,3...)
解析式 S(n)= n x (n+1) / 2 (高斯的斷言)
斐波那契數(shù)列
- 思考：有一種動(dòng)物，TA出生2天后，就開始以每天1只的速度繁殖后代。假設(shè)第1天，有一只這樣的動(dòng)物（該動(dòng)物剛出生，從第3天起繁殖后代）。問，到第11天，共有多少只？
思路，按順序思考，找出規(guī)律。
- 第1天，只有1只動(dòng)物
- 第2天，只有1只動(dòng)物，還沒有繁衍后代
- 第3天，第1天的1只動(dòng)物，繁殖1個(gè)后代，合計(jì)2只
- 第4天，第1天的1只動(dòng)物，又繁殖1個(gè)后代
第3天出生的還沒有開始繁殖，總共3只- 第1天和第3天出生的2只動(dòng)物各繁殖1個(gè)后代。
第4天出生的1只動(dòng)物還沒繁殖后代，合計(jì)5只。
進(jìn)行歸納的時(shí)候，不用想著第n天幾只，可以如下思考：
- 第n-1天出生的動(dòng)物，在第n天還活著
- 第n-2天以前出生的動(dòng)物，在第n天后會(huì)繁殖1個(gè)后代
- 總結(jié)出遞推公式：
若設(shè)第n天的動(dòng)物總數(shù)為F(n)，則
F(n)=F(n-1)+F(n-2)
第n天的動(dòng)物數(shù) = 第n-1天前的動(dòng)物數(shù) + 第n-2天前出生的動(dòng)物數(shù)
在這里，為了讓等式成立（即讓n=2時(shí)，公式成立），定義F(0)=0，F(xiàn)(1)=1，F(xiàn)(n)=F(n-1)+F(n-2)
由此，我們可以推斷出:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
...
F(11) = F(10) + F(9) = 55 + 34 = 89
- 問題中出現(xiàn)的數(shù)列:
0,1,1,2,3,4,5,13,18,21,34,55,89, ...
是在13世紀(jì)由數(shù)學(xué)家斐波那契發(fā)現(xiàn)的，因此稱為斐波那契數(shù)列
斐波那契數(shù)列是非常優(yōu)美的，用它出現(xiàn)的變形非常多，我找了幾個(gè)利用TA作的圖：
斐波那契數(shù)列作圖
斐波那契螺旋
自然界的斐波那契
帕斯卡三角形
這個(gè)用文字描述非常累贅，公式不太好表達(dá)，因?yàn)楹?jiǎn)書不支持LaTex，所以就不寫了。
楊輝三角形: 除每行最左側(cè)與最右側(cè)的數(shù)字以外，每個(gè)數(shù)字等于它的左上方與右上方兩個(gè)數(shù)字之和：
初始
加好之后
楊輝三角形
思考題：
- 遞歸形式畫一棵樹
- 謝爾平斯基三角形
總結(jié)，把握結(jié)構(gòu)是“分解”整個(gè)問題的突破口
