遞推關(guān)系與Fibonacci數(shù)列課件

1、2.2 遞推關(guān)系與Fibonacci數(shù)列 遞推關(guān)系 Fibonacci數(shù)列第1頁，共26頁。1. 遞推關(guān)系Hanoi塔問題：這是組合數(shù)學(xué)中的一個(gè)著名問題。n個(gè)圓盤依其半徑大小，從下而上套在A柱上。每次只允許取一個(gè)移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個(gè)盤移到C柱上，請(qǐng)?jiān)O(shè)計(jì)一種方法并估計(jì)要移動(dòng)幾個(gè)盤次?，F(xiàn)在只有A、B、C三根柱子可用。首先要設(shè)計(jì)算法，進(jìn)而估計(jì)它的復(fù)雜性，即估計(jì)工作量。第2頁，共26頁。當(dāng)n=2時(shí)，第一步把A柱的小圓盤移到B柱；第二步把A柱的大圓盤移到C柱；A B C第三步把B柱的小圓盤移到C柱，即完成移動(dòng)。第3頁，共26頁。假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確

2、定，對(duì)于一般n個(gè)圓盤的問題，A B C首先把A柱上面的n-1個(gè)圓盤移到B柱；然后把A柱最下面的圓盤移到C柱；最后把B柱的n-1個(gè)圓盤移到C柱，即完成移動(dòng)。第4頁，共26頁。令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。因此有：從這個(gè)遞推關(guān)系式可以逐項(xiàng)遞推得到所有的h(n)。根據(jù)算法先把前面n-1個(gè)盤子轉(zhuǎn)移到B上；然后把第n個(gè)盤子轉(zhuǎn)到C上；最后將B的n-1個(gè)盤子轉(zhuǎn)移到C上。下面我們利用母函數(shù)來得到h(n)的通項(xiàng)表達(dá)式。假設(shè)序列h(n)對(duì)應(yīng)的母函數(shù)為H(x)，即第5頁，共26頁。因此有第6頁，共26頁?；蛘呃脁2:x3:x4:+)同樣可以得到：第7頁，共26頁。假設(shè)下面我們用冪級(jí)數(shù)展開的方法得到h(n

3、).利用待定系數(shù)法容易得到A=1，B=-1，即即第8頁，共26頁。對(duì)于一個(gè)n位十進(jìn)制數(shù) p1 p2pn-1 pn，則 p1 p2pn-1 是n-1位十進(jìn)制數(shù)。例1 求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù)。因此若令an表示n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù)，bn表示出現(xiàn)奇數(shù)個(gè)5的數(shù)的個(gè)數(shù)，則有若它含有偶數(shù)個(gè)5，則 pn必須取5以外的九個(gè)數(shù)中的一個(gè)；若 p1 p2pn-1含有奇數(shù)個(gè)5，則 pn必須取成5。a1=8，b1=1.第9頁，共26頁。設(shè) an 的母函數(shù)為A(x)，bn的母函數(shù)為B(x)，則或者利用x2:x3:+)第10頁，共26頁。類似的還有這樣就得到了關(guān)于A(x)和B(x)的聯(lián)立方程組

4、：可以解得：第11頁，共26頁。因此有由于另解： n-1位十進(jìn)制數(shù)共有910n-2個(gè)，要么含有奇數(shù)個(gè)5，要么含有偶數(shù)個(gè)5。故有： 因此有第12頁，共26頁。因此有第13頁，共26頁。(1) 不出現(xiàn)a1，這相當(dāng)于從其他n-1個(gè)元素中取r個(gè)做可重組合；這樣的組合可以分為兩種情況：(2) 出現(xiàn)a1，這相當(dāng)于從n個(gè)元素中取r-1個(gè)做可重組合再加上a1。因此有初始條件為因此還可以令例2 從n個(gè)不同的元素a1,a2,an中取r個(gè)做允許重復(fù)的組合，求不同的組合數(shù)第14頁，共26頁。注意到遞推關(guān)系 中有2個(gè)參數(shù)，對(duì)于固定的n， 的母函數(shù)為Gn(x)，則第15頁，共26頁。因此有因此由二項(xiàng)式展開定理可知第16頁

5、，共26頁。2. Fibonacci數(shù)列Fibonacci數(shù)列是遞推關(guān)系的又一個(gè)典型問題，數(shù)列的本身有著許多應(yīng)用。有雌雄兔子一對(duì)，假定過兩月便可繁殖雌雄各一的一對(duì)小兔。問過了n個(gè)月后共有多少對(duì)兔子？設(shè)滿n個(gè)月時(shí)兔子對(duì)數(shù)為Fn，其中當(dāng)月新生兔數(shù)目設(shè)為Nn 對(duì)，上個(gè)月留下的兔子數(shù)目設(shè)為On對(duì)，則但是注意到 On = Fn-1，Nn = On-1 = Fn-2，因此有第17頁，共26頁。利用這個(gè)遞推關(guān)系很容易可以得到：下面我們利用母函數(shù)來計(jì)算Fn的通項(xiàng)表達(dá)式。設(shè)Fn的母函數(shù)為G(x)，則x3:x4:+)第18頁，共26頁。方程1-x-x2=0的兩個(gè)根設(shè)為：則有利用待定系數(shù)法易有因此有即通項(xiàng)表達(dá)式為：

6、第19頁，共26頁。下面介紹一些關(guān)于Fibonacci數(shù)列的結(jié)論。(1) 任意正整數(shù)N可以表示成Fibonacci數(shù)列中的數(shù)的有限和，即滿足si=0或1，且si si+1=0。(2) 邊長為Fn的正方形可以分解為若干個(gè)邊長為Fi和Fi+1的長方形。參見課本圖形。第20頁，共26頁。第21頁，共26頁。第22頁，共26頁。第23頁，共26頁。下面介紹一個(gè)Fibonacci數(shù)列在優(yōu)化中的應(yīng)用。問題：求單峰函數(shù)f(x)在區(qū)間a,b上的最大值。三分法：將第k步的區(qū)間ak,bk三等分，即優(yōu)點(diǎn)：每次區(qū)間長度縮短1/3。數(shù)值方法迭代求解。首先令a1=a，b1=b。若 ，則取否則取缺點(diǎn)：上一步中點(diǎn)的值在下一步?jīng)]有用到。第24頁，共26頁。0.618方法：將三分法中的2/3換成0.618。不妨假設(shè)區(qū)間為0,1，上一步的取值點(diǎn)為x，1-x。為了充分利用上一步取值點(diǎn)的信息，因此要求x2=x(1-x)，解得x約等于0.618。為什么取0.618？假設(shè)保留的區(qū)間為0,x，則下一步的取值點(diǎn)為x2，x(1-x)。這比三分法節(jié)省了大約一半的運(yùn)算量。第25頁，共26頁。Fibonacci方法：在第k步令因此若要求最后區(qū)間長度不超過d，則可由 (b-a)/Fn d 解出Fn，即確定n。這樣在n步迭代后，