第二章(2.7-2.8).ppt

1、2.7 遞推關系,利用遞推關系進行計數(shù)這個方法在算法分析中經(jīng)常用到，舉例說明如下：,例一.Hanoi問題：這是個組合數(shù)學中的著名問題。N個圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個盤移到C柱上請設計一種方法來，并估計要移動幾個盤次。現(xiàn)在只有A、B、C三根柱子可用。,2.7 遞推關系,Hanoi問題是個典型的問題，第一步要設計算法，進而估計它的復雜性，即估計工作量。,算法：,N=2時,第一步先把最上面的一個圓盤套在B上, ,第二步把下面的一個圓盤移到C上, ,最后把B上的圓盤移到C上,到此轉移完畢,2.7 遞推

2、關系,對于一般n個圓盤的問題，,假定n-1個盤子的轉移算法已經(jīng)確定。,先把上面的n-1個圓盤經(jīng)過C轉移到B。,第二步把A下面一個圓盤移到C上,最后再把B上的n-1個圓盤經(jīng)過A轉移到C上,2.7 遞推關系,上述算法是遞歸的運用。n=2時已給出算法；n=3時，第一步便利用算法把上面兩個盤移到B上，第二步再把第三個圓盤轉移到柱C上；最后把柱B上兩個圓盤轉移到柱C上。N=4，5，以此類推。,2.7 遞推關系,算法分析：令h(n)表示n個圓盤所需要的轉移盤次。根據(jù)算法先把前面n-1個盤子轉移到B上；然后把第n個盤子轉到C上；最后再一次將B上的n-1個盤子轉移到C上。 n=2時，算法是對的，因此，n=3是

3、算法是對的。以此類推。于是有,2.7 遞推關系,算法復雜度為：,H(x)是序列 的母函數(shù)。給定了序列，對應的母函數(shù)也確定了。反過來也一樣，求得了母函數(shù)，對應的序列也就可得而知了。當然，利用遞推關系(2-2-1)式也可以依次求得 ，這樣的連鎖反應關系，叫做遞推關系。,2.7 遞推關系,下面介紹如何從(2-2-1)式求得母函數(shù)H(x)的一種形式算法。所謂形式算法說的是假定這些冪級數(shù)在作四則運算時，一如有限項的代數(shù)式一樣。,2.7 遞推關系,根據(jù)(2-2-1)，,或利用遞推關系(2-2-1)有,2.7 遞推關系,上式左端為：,右端第一項為：,右端第二項為：,2.7 遞推關系,整理得,這兩種做法得到的

4、結果是一樣的。即：,2.7 遞推關系,令,如何從母函數(shù)得到序列 ？下面介紹一種化為部分分數(shù)的算法。,2.7 遞推關系,由上式可得：,即：,2.7 遞推關系,因為：,2.7 遞推關系,例2.28 求n位十進制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。,先從分析n位十進制數(shù)出現(xiàn)偶數(shù)個5的數(shù)的結構入手 是n-1位十進制數(shù)，若含有偶數(shù)個5，則 取5以外的0，1，2，3，4，6，7，8，9九個數(shù)中的一個，若 只有奇數(shù)個5，則取 ，使 成為出現(xiàn)偶數(shù)個5的十進制數(shù)。,2.7 遞推關系,解法1：,令 =n位十進制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)， =n位十進制數(shù)中出現(xiàn)奇數(shù)個5的數(shù) 的個數(shù)。,故有：,n位數(shù)中不包括0,也有類似解釋

5、。,2.7 遞推關系,(2-2-2)式中的 表達了含有偶數(shù)個5的n位十進制數(shù)的兩個組成部分。 表達由含有偶數(shù)個5的n-1位十進制數(shù) ，令 取5以外的0，1，2，3，4，6，7，8，9九個數(shù)中的一個數(shù)構成的。 項表示當 是含有奇數(shù)個5的n-1位十進制數(shù)，則令 而得 是含偶數(shù)個5的n位十進制數(shù)。,(2-2-2)是關于序列 和 的連立關系。,2.7 遞推關系,設序列 的母函數(shù)為 ，序列 的母函數(shù)為 。,即：,L,L,L,-,-,-,=,-,+,-,-,-,=,-,+,+,+,=,2,2,1,2,2,1,2,3,2,1,),(,),9,9,),(,9,),(,x,b,x,b,x,xB,x,a,x,a,

6、x,xA,x,a,x,a,a,x,A,2.7 遞推關系,承前頁：,2.7 遞推關系,又：,故得關于母函數(shù) 和 得連立方程組：,2.7 遞推關系,2.7 遞推關系,2.7 遞推關系,解法2： n-1位的十進制數(shù)的全體共 從中去掉含有偶數(shù)個5的數(shù)，余下的便是n-1位中含有奇數(shù)個5的數(shù)。故有：,第1位數(shù)中不包括0，故第1位有9種可取值，其它位有10種。,2.7 遞推關系,令,2.7 遞推關系,=,+,=,-,+,-,=,-,-,-,=,0,),10,9,8,7,(,2,1,),10,1,9,8,1,7,(,2,1,),10,1,)(,8,1,(,71,8,),(,k,k,k,k,x,x,x,x,x,

7、x,x,A,a）不出現(xiàn)某特定元素設為 ，其組合數(shù)為 ，相當于排除 后從 中取r個做允許重復的組合。,2.7 遞推關系,例2.30：從n個元素 中取r個進行允許重復的組合。假定允許重復的組合數(shù)用 表示，其結果可能有以下兩種情況。,2.7 遞推關系,b）至少出現(xiàn)一個 ，取組合數(shù)為 相當于從 中取r-1個做允許重復的組合，然后再加上一個 得從n個元素中取r個允許重復的組合。,依據(jù)加法原則可得：,因 ，故令,2.7 遞推關系,遞推關系(2-2-3)帶有兩個參數(shù)n和r。,2.7 遞推關系,(2-2-3)式是關于 的遞推關系，但系數(shù) 不是常數(shù)。但,2.7 遞推關系,承上頁，由二項式定理得,可得,2.8 F

8、ibonacci數(shù)列,2.8.1遞推關系,Fibonacci數(shù)列是遞推關系的又一個典型問題，數(shù)列的本身有著許多應用。,問題：有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的一對小兔。問過了n個月后共有多少對兔子？,設滿n個月時兔子對數(shù)為 其中當月新生兔數(shù)目設為 對。第n-1個月留下的兔子數(shù)目設為 對。當月新生的兔子數(shù)即為n-2個月的兔子數(shù)， n-2個月的兔子到n個月時，都已經(jīng)變成大兔子，能下小兔子了。,2.8.1遞推關系,但,即第n-2個月的所偶兔子到第n個月都有繁殖能力了。,由遞推關系(2-3-1)式可依次得到,2.8.2問題的求解,設,2.8.2問題的求解,承前頁,2.8.2問題的求解,承前頁

9、,2.8.2問題的求解,承前頁,2.8.2問題的求解,其中,2.8.3若干等式,1）,證明：,2.8.3若干等式,2）,證明：,2.8.3若干等式,3）,證明：,2.8.4在選優(yōu)法上的應用,設函數(shù) 在區(qū)間 上有一單峰極值點，假定為極大點。,所謂單峰極值，即只有一個極值點 ，而且當x與 偏離越大，偏差 也越大。如下圖：,2.8.4在選優(yōu)法上的應用,設函數(shù) 在 點取得極大值。要求用若干次試驗找到 點準確到一定的程度。最簡單的方法，把 三等分，令：,如下圖：,2.8.4在選優(yōu)法上的應用,依據(jù) 的大小分別討論如下：,(1) 當 ，則極大點 必在 區(qū)間上，區(qū)間 可以舍去。,2.8.4在選優(yōu)法上的應用,(

10、2)當 ，則極大點 必在 區(qū)間上，區(qū)間 可以舍去。,2.8.4在選優(yōu)法上的應用,(3)當 ，則極大點 必在 區(qū)間上，區(qū)間 和 均可以舍去。,2.8.4在選優(yōu)法上的應用,可見做兩次試驗，至少可把區(qū)間縮至原來區(qū)間的2/3，比如 ，進一步在 區(qū)間上找極值點。若繼續(xù)用三等分法，將面對著這一實事，即其中 點的試驗沒發(fā)揮其作用。為此設想在 區(qū)間的兩個對稱點 分別做試驗。,2.8.4在選優(yōu)法上的應用,設保留 區(qū)間，繼續(xù)在 區(qū)間的下面兩個點 處做試驗，若,則前一次 的點的試驗，這一次可繼續(xù)使用可節(jié)省一次試驗。由(2-3-6)式有,2.8.4在選優(yōu)法上的應用,這就是所謂的0.618優(yōu)選法。即若在 區(qū)間上找單峰極

11、大值時，可在,點做試驗。比如保留區(qū)間 ，由于 ，故只要在,點作一次試驗。,0.236,0.328,0.618,2.8.4在選優(yōu)法上的應用,優(yōu)選法中可利用Fibonacci數(shù)列，和0.618法不同之點在于它預先確定試驗次數(shù)，分兩種情況介紹其方法。,(a) 所有可能試驗數(shù)正好是某個 。,2.8.4在選優(yōu)法上的應用,這時兩個試驗點放在 和 兩個分點上，如果 分點比較好，則舍去小于 的部分；如果 點更好，則舍去大于 的部分。在留下的部分共 個分點，其中第 和第 二試驗點，恰好有一個是剛才留下來的試驗可以利用。,可見在 個可能試驗中，最多用n-1次試驗便可得到所求的極值點,2.8.4在選優(yōu)法上的應用,(

12、b)利用Fibonacci數(shù)列進行優(yōu)選不同于 0.618法之點,還在于它適合于參數(shù)只能取整數(shù)數(shù)值的情況.如若可能試驗的數(shù)目比 小,但比 大時,可以虛加幾個點湊成 個點，但新增加的點的試驗不必真做，可認定比其他點都差的點來處理。,2.8.4在選優(yōu)法上的應用,下面給出兩個定理作為這一節(jié)的結束。,定理：測試n次可將包含單峰極值點的區(qū)間縮小到原區(qū)間的 ，其中 是任意小的正整數(shù)，,2.8.4在選優(yōu)法上的應用,證：對n用數(shù)學歸納法。,n=2時，將區(qū)間 平分成 段。在分點（包括端點a，b）分別標上 。在1點的兩側取 ，在 與 兩點上測試，無論哪一點較優(yōu)，保留下來的區(qū)間長度均為 ，命題成立。,2.8.4在選優(yōu)法上的應用,假設對于n-1，命題成立,對于n，將 平分成 段，對分點（包括端點a，b）依次標上 。先在 點與 點測試，無論哪一點較優(yōu)，保留下來的區(qū)間均為 段。根據(jù)歸納假設，再做n-1次測試（內(nèi)含前兩次測試之一）可將含極