母函數(shù)與遞推關(guān)系

1、母函數(shù)與遞推關(guān)系第1頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2內(nèi)容回顧組合的生成和組合意義模型轉(zhuǎn)換一一對(duì)應(yīng)定義：對(duì)于序列a0,a1,a2,構(gòu)造一函數(shù)：G(x)=a0+a1x+a2x2+,稱函數(shù)G(x)是序列a0,a1,a2,的母函數(shù)(生成函數(shù) generating function)。(1+x)n是序列C(n,0),C(n,1),C(n,n)的母函數(shù)g(x)=1+x+x2+x3+x4+.=1/(1-x)是f(n)=1的母函數(shù)設(shè)級(jí)數(shù)收斂， -1x1生成函數(shù)的x沒有實(shí)際意義第2頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四二項(xiàng)式定理第3頁，共53頁，2022年，5月20日

2、，7點(diǎn)11分，星期四42.2 遞推關(guān)系 利用遞推關(guān)系進(jìn)行計(jì)數(shù)這個(gè)方法在算法分析中經(jīng)常用到 例一.Hanoi問題：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ì)它的復(fù)雜性，即估計(jì)工作量.第4頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四52.2 遞推關(guān)系算法：N=2時(shí)第一步先把最上面的一個(gè)圓盤套在B上第二步把下面的一個(gè)圓盤移到C上 最后把B上的圓盤移到C上 到此轉(zhuǎn)移完畢A B C第5頁，共53頁，2022年，5月2

3、0日，7點(diǎn)11分，星期四62.2 遞推關(guān)系 假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定。對(duì)于一般n個(gè)圓盤的問題,先把上面的n-1個(gè)圓盤經(jīng)過C轉(zhuǎn)移到B;第二步把A下面一個(gè)圓盤移到C上最后再把B上的n-1個(gè)圓盤經(jīng)過A轉(zhuǎn)移到C上n=2時(shí)，算法是對(duì)的，因此，n=3是算法是對(duì)的。以此類推。A B C第6頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四72.2 遞推關(guān)系令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。對(duì)于一般n個(gè)圓盤的問題,先把上面的n-1個(gè)圓盤經(jīng)過C轉(zhuǎn)移到B: h(n-1)次第二步把A下面一個(gè)圓盤移到C上: 1次最后再把B上的n-1個(gè)圓盤經(jīng)過A轉(zhuǎn)移到C上： h(n-1)次算法復(fù)雜度為：構(gòu)造母函數(shù)

4、為：求得了母函數(shù)，對(duì)應(yīng)的序列也就求得h(n)A B C第7頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四82.2 遞推關(guān)系所謂形式算法說的是假定這些冪級(jí)數(shù)在作四則運(yùn)算時(shí)，一如有限項(xiàng)的代數(shù)式一樣。第8頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四9如何從母函數(shù)得到序列 ？化為部分分?jǐn)?shù)的算法。 由上式可得：g(x)=1+x+x2+x3+x4+. = 即：第9頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四102.2 遞推關(guān)系 或利用遞推關(guān)系(2-2-1)有 上式左端為： 右端第一項(xiàng)為： 右端第二項(xiàng)為：第10頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四112.

5、2 遞推關(guān)系例2. 求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù)。 先從分析n位十進(jìn)制數(shù)出現(xiàn)偶數(shù)個(gè)5的數(shù)的結(jié)構(gòu)入手 設(shè)p1p2pn-1是n-1位十進(jìn)制數(shù)，若含有偶數(shù)個(gè)5，則pn取5以外的0，1，2，3，4，6，7，8，9九個(gè)數(shù)中的一個(gè)，若p1p2pn-1 只有奇數(shù)個(gè)5，則pn取5，使p1p2pn-1pn 成為出現(xiàn)偶數(shù)個(gè)5的十進(jìn)制數(shù)。解法1：令an為n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù)， bn為n位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個(gè)5的數(shù)的個(gè)數(shù)。設(shè)序列an的母函數(shù)為A(x)，序列bn的母函數(shù)為B(x)。 第11頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四12a1=8, b1=1第12頁，共53頁，202

6、2年，5月20日，7點(diǎn)11分，星期四132.2 遞推關(guān)系故得關(guān)于母函數(shù)A(x)和B(x)得連立方程組：第13頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四142.2 遞推關(guān)系解法二：n-1位的十進(jìn)制數(shù)的全體共910n-1個(gè)(最高位不為0)，設(shè)所求數(shù)為an,設(shè)A(x)= a1x+a2x2+,按照尾數(shù)是否為5分類：尾數(shù)不是為5的：9an-1尾數(shù)為5的，前n-1位有奇數(shù)個(gè)5：第14頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四152.2 遞推關(guān)系驗(yàn)證：a1=8,a2=73第15頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四16 1）不出現(xiàn)某特定元素設(shè)為a1，其組合數(shù)為

7、，相當(dāng)于排除a1后從a2,.an 中取r個(gè)做允許重復(fù)的組合。2.2 遞推關(guān)系例三：從n個(gè)元素a1,a2,.an中取r個(gè)進(jìn)行允許重復(fù)的組合。假定允許重復(fù)的組合數(shù)用 表示，其結(jié)果可能有以下兩種情況。 2）至少出現(xiàn)一個(gè)a1，取組合數(shù)為 相當(dāng)于從a1,a2,.an中取r-1個(gè)做允許重復(fù)的組合，然后再加上一個(gè)a1得從n個(gè)元素中取r個(gè)允許重復(fù)的組合。第16頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四172.2 遞推關(guān)系 因 ，故令系數(shù)(1-x)不是常數(shù)。但第17頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四18 由二項(xiàng)式定理 可得第18頁，共53頁，2022年，5月20日，7點(diǎn)11分

8、，星期四第19頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四母函數(shù)遞推關(guān)系遞推運(yùn)算初始值代數(shù)運(yùn)算：化為部分分?jǐn)?shù)的算法第20頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.3 母函數(shù)的性質(zhì) 一個(gè)序列和它的母函數(shù)一一對(duì)應(yīng)。給了序列便得知它的母函數(shù)；反之，求得母函數(shù)序列也隨之而定。 為了求滿足某種遞推關(guān)系的序列，可把它轉(zhuǎn)換為求對(duì)應(yīng)的母函數(shù)G(x)，G(x)可能滿足一代數(shù)方程，或代數(shù)方程組，甚至于是微分方程。 最后求逆變換，即從已求得的母函數(shù) G(x)得到序列an。關(guān)鍵在于要搭起從序列到母函數(shù)，從母函數(shù)到序列這兩座橋。21第21頁，共53頁，2022年，5月20日，7點(diǎn)11分，星

9、期四2.3 母函數(shù)的性質(zhì)對(duì)應(yīng)的母函數(shù)分別為、不特別說明,下面假設(shè)、兩個(gè)序列22第22頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四性質(zhì)1：若則 例. 已知?jiǎng)t23 例. 已知?jiǎng)tmmm-1第23頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 性質(zhì)2：則若證： 例.24第24頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 性質(zhì)3：證：若則 ): : : :1 2102102210100LLLLLLLLLLLLLLLL+=+=+=nnaaaabnxaaabxaabxab25第25頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 例. 已知 類似可得：若則26第26

10、頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四性質(zhì)4則證27第27頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 A(x)=a0+a1x+a2x2+, A(x)=a1+2a2x+3a3x2+. 例. 則性質(zhì)5若則性質(zhì)6若則求導(dǎo)積分28第28頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四性質(zhì)7若則證29第29頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.3母函數(shù)的性質(zhì) 例. 已知 30第30頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4 Fibonacci數(shù)列 Fibonacci數(shù)列是遞推關(guān)系的又一個(gè)典型問題。Fibonacci數(shù)列是以

11、遞歸的方法來定義：F0 = 0， F1 = 1 ， Fn = Fn - 1 + Fn - 2 （1）斐波那契數(shù)列由0和1開始，之后的斐波那契數(shù)就由之前的兩數(shù)相加。0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，0不是第一項(xiàng)，而是第0項(xiàng)。31第31頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四1150年印度數(shù)學(xué)家研究箱子包裝物件長寬剛好 為1和2的可行方法數(shù)目時(shí)，首先描述這個(gè)數(shù)列。在西方，1202年，意大利數(shù)學(xué)家斐波那契出版了他的算盤全書。他在

12、書中提出了一個(gè)關(guān)于兔子繁殖的問題：第一個(gè)月有一對(duì)剛誕生的兔子；如果一對(duì)兔子每月能生一對(duì)小兔（一雄一雌）；而每對(duì)小兔在它出生后的第三個(gè)月里，又能開始生一對(duì)小兔，兔子永不死去；由一對(duì)出生的小兔開始，50個(gè)月后會(huì)有多少對(duì)兔子？第n個(gè)月相比n-1個(gè)月多出的兔子數(shù)是n-2個(gè)月的兔子生出來的，即Fn=Fn-1+Fn-2 32Leonardo of PisaSon of Bonaccio 第32頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 設(shè)2.4.1遞推關(guān)系第33頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.1遞推關(guān)系34第34頁，共53頁，2022年，5月20日，7點(diǎn)11分

13、，星期四 1） 證明：2.4.1遞推關(guān)系Fn=Fn-1+Fn-235第35頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 2） 證明：2.4.1遞推關(guān)系Fn=Fn-1+Fn-236第36頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 3） 證明：2.4.1遞推關(guān)系37第37頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四一位魔術(shù)師拿著一塊邊長為8英尺的正方形地毯，對(duì)他的地毯匠朋友說：“請(qǐng)您把這塊地毯分成四小塊，再把它們縫成一塊長13英尺，寬5英尺的長方 ” 魔術(shù)881350, 1, 1, 2, 3, 5, 8, 13, 21,.35F(n)*F(n) F(n-1)F

14、(n+1) = (-1)nn=0,1,2第38頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四斐波那契螺旋 39第39頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 設(shè)函數(shù) 在 點(diǎn)取得極大值。要求用若干次試驗(yàn)找到 點(diǎn)準(zhǔn)確到一定的程度。最簡單的方法，把 三等分，令：如下圖：40第40頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 設(shè)函數(shù)y=f(x)在區(qū)間(a,b)上有一單峰極值點(diǎn)，假定為極大點(diǎn)。 所謂單峰極值，即只有一個(gè)極值點(diǎn)，而且當(dāng)x與偏離越大，偏差|f(x)-f() | 也越大。如下圖：41第41頁，共53頁，2

15、022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 依據(jù) 的大小分別討論如下： 當(dāng) ，則極大點(diǎn) 必在 區(qū)間上，區(qū)間 可以舍去。42第42頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 當(dāng) ，則極大點(diǎn) 必在 區(qū)間上，區(qū)間 可以舍去。43第43頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 當(dāng) ，則極大點(diǎn) 必在 區(qū)間上，區(qū)間 和 均可以舍去。44第44頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 可見做兩次試驗(yàn)，至少可把區(qū)間縮至原來區(qū)間的2/3，比如 ，進(jìn)一步在 區(qū)間上找極值點(diǎn)。若繼續(xù)用三等分法，將

16、面對(duì)著這一實(shí)事，即其中 點(diǎn)的試驗(yàn)沒發(fā)揮其作用。為此設(shè)想在 區(qū)間的兩個(gè)對(duì)稱點(diǎn) 分別做試驗(yàn)。45第45頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四 設(shè)保留 區(qū)間，繼續(xù)在 區(qū)間的下面兩個(gè)點(diǎn)x2,(1-x)x 處做試驗(yàn)，若則前一次 的點(diǎn)的試驗(yàn)，這一次可繼續(xù)使用可節(jié)省一次試驗(yàn)。由(2-3-6)式有0.382，0.6180.236，0.3820.146，0.23646第46頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 這就是所謂的0.618優(yōu)選法。即若在 區(qū)間上找單峰極大值時(shí)，可在 點(diǎn)做試驗(yàn)。比如保留區(qū)間 ，由于 ，故只要在 點(diǎn)作一次試驗(yàn)。47第47頁，共

17、53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 優(yōu)選法中可利用Fibonacci數(shù)列，和0.618法不同之點(diǎn)在于它預(yù)先確定試驗(yàn)次數(shù)，分兩種情況介紹其方法。 (a) 所有可能試驗(yàn)數(shù)正好是某個(gè)Fn。這時(shí)兩個(gè)試驗(yàn)點(diǎn)放在Fn-1和Fn-2兩個(gè)分點(diǎn)上，如果Fn-1分點(diǎn)比較好，則舍去小于Fn-2的部分；留下的部分共Fn-Fn-2 = Fn-1個(gè)分點(diǎn)，其中第Fn-2和第Fn-3二試驗(yàn)點(diǎn)，對(duì)應(yīng)的原標(biāo)號(hào)是Fn-2+Fn-2=2Fn-2以及Fn-3+Fn-2=Fn-1,恰好Fn-1點(diǎn)是剛才留下來的試驗(yàn)可以利用。如果Fn-2點(diǎn)更好，則舍去大于Fn-1的部分。在留下的部分共Fn-1個(gè)分點(diǎn)

18、，下一步Fn-2和Fn-3二試驗(yàn)點(diǎn)中，恰好Fn-2是剛才留下來的試驗(yàn)可以利用?？梢娫贔n個(gè)可能試驗(yàn)中，最多用n-1次試驗(yàn)便可得到所求的極值點(diǎn)。48第48頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 (b)利用Fibonacci數(shù)列進(jìn)行優(yōu)選不同于 0.618法之點(diǎn),還在于它適合于參數(shù)只能取整數(shù)數(shù)值的情況.如若可能試驗(yàn)的數(shù)目比 小,但比 大時(shí),可以虛加幾個(gè)點(diǎn)湊成 個(gè)點(diǎn)，但新增加的點(diǎn)的試驗(yàn)不必真做，可認(rèn)定比其他點(diǎn)都差的點(diǎn)來處理。49第49頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 定理：測(cè)試n次可將包含單峰極值點(diǎn)的區(qū)間縮小到原區(qū)間的 ，其中 是任意小的正整數(shù)， 證：對(duì)n用數(shù)學(xué)歸納法。 n=2時(shí)，將區(qū)間(a.b)平分成F(2+1）=2 段。在分點(diǎn)（包括端點(diǎn)a，b）分別標(biāo)上0，1，2。在1點(diǎn)的兩側(cè)取 ，在（1- ）與(1+ )兩點(diǎn)上測(cè)試，無論哪一點(diǎn)較優(yōu)，保留下來的區(qū)間長度均為(1+ )，命題成立。50ab0121- 1+第50頁，共53頁，2022年，5月20日，7點(diǎn)11分，星期四2.4.4在選優(yōu)法上的應(yīng)用 假設(shè)對(duì)于n-1，命題成立 對(duì)于n，將(a,b)平分成Fn+1段，對(duì)分點(diǎn)