遞推關(guān)系定義

1、第七講遞推關(guān)系定義第七講遞推關(guān)系定義7.1 遞推關(guān)系的定義及建立遞推關(guān)系是組合數(shù)學(xué)的一個(gè)重要課題,它不僅在幾乎所有的數(shù)學(xué)分支中占有重要的地位,而且在計(jì)算機(jī)科學(xué),特別是在算法分析中有著廣泛的應(yīng)用.定義 設(shè) ,10raaa是一個(gè)序列，把該序列中的 ra和 它前面的幾個(gè) )0(riai 關(guān)聯(lián)起來的方程稱為一個(gè)遞推關(guān)系。 如： 錯(cuò)排數(shù) , 4 , 3121 nDDnDnnn7.1 遞推關(guān)系的定義及建立如何建立遞推關(guān)系？舉例說明如下： 例. Hanoi問題：這是個(gè)組合數(shù)學(xué)中的著名問題。N個(gè)圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個(gè)移到柱B或C上，而且不允許大盤放在小盤上方。若要求把

2、柱A上的n個(gè)盤移到C柱上請(qǐng)?jiān)O(shè)計(jì)一種方法來，并估計(jì)要移動(dòng)幾個(gè)盤次?，F(xiàn)在只有A、B、C三根柱子可用。7.1 遞推關(guān)系的定義及建立 Hanoi問題是個(gè)典型的問題，第一步要設(shè)計(jì)算法，進(jìn)而估計(jì)它的復(fù)雜性，集估計(jì)工作量。算法：算法：N=2時(shí)，第一步先把最上面的一個(gè)圓盤套在B上z z第二步把下面的一個(gè)圓盤移到C上 到此轉(zhuǎn)移完畢A B C 最后把B上的圓盤移到C上7.1 遞推關(guān)系的定義及建立n=2時(shí)已給出算法；n=3時(shí)，第一步便利用算法把上面兩個(gè)盤移到B上，第二步再把第三個(gè)圓盤轉(zhuǎn)移到柱C上；最后把柱B上兩個(gè)圓盤轉(zhuǎn)移到柱C上。N=4，5，以此類推。7.1 遞推關(guān)系的定義及建立z 對(duì)于一般n個(gè)圓盤的問題，l 假定

3、n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定。z 先把上面的n-1個(gè)圓盤經(jīng)過C轉(zhuǎn)移到B。z 第二步把A下面一個(gè)圓盤移到C上 z 最后再把B上的n-1個(gè)圓盤經(jīng)過A轉(zhuǎn)移到C上 A B C 7.1 遞推關(guān)系的定義及建立算法分析：算法分析：令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。根據(jù)算法先把前面n-1個(gè)盤子轉(zhuǎn)移到B上；然后把第n個(gè)盤子轉(zhuǎn)到C上；最后再一次將B上的n-1個(gè)盤子轉(zhuǎn)移到C上。 n=2時(shí)，算法是對(duì)的，因此，n=3是算法是對(duì)的。以此類推。于是有 1) 1 ( , 1) 1(2)(hnhnh當(dāng)然，利用遞推關(guān)系上式也可以依次求得 ，這樣的連鎖反應(yīng)關(guān)系，叫做遞推關(guān)系。),3(),2(),1 (hhh7.1 遞推關(guān)系

4、的定義及建立例 在一個(gè)平面上有一個(gè)圓和 n條直線,這些直線中條在圓內(nèi)都同其他的直線相交.如果沒有多 于三條的直線相交于一點(diǎn),試問這 n條直線將圓的每一分成多少個(gè)區(qū)域? 7.1 遞推關(guān)系的定義及建立設(shè)這 n條直線將圓分成的區(qū)域數(shù)為 na，如果有 1 n條直線在圓內(nèi)分成 1 na個(gè)區(qū)域，那 么，再加入第 n條直線 與在圓內(nèi)的其他 1 n條直線相交。顯然，1 n條直線在圓內(nèi)分成 n條線段，而每n條 直線在圓內(nèi)經(jīng)過的區(qū)域分成兩個(gè)區(qū)域。第 n條直線后，圓內(nèi)就增加了 n個(gè)區(qū)域這條直線被 線段又將第 這樣，加入 而對(duì)于 , 0 n顯然有 10 a。 可建立如下的遞推關(guān)系： 1,101 annaann7.1

5、遞推關(guān)系的定義及建立例在一個(gè)平面中,有 n個(gè)圓兩兩相交,但任兩個(gè)圓任三個(gè)圓無公交點(diǎn).求這 n個(gè)圓把平面分成4, 221 aa由圖易見 不相切,多少個(gè)區(qū)域?7.1 遞推關(guān)系的定義及建立設(shè) n個(gè)圓將平面分成 na個(gè)區(qū)域 現(xiàn)假設(shè)前 1 n個(gè)圓1 na個(gè)區(qū)域，當(dāng)加入第 n個(gè)圓時(shí)，由題1 n個(gè)圓相交于 12 n個(gè)點(diǎn)，這 12 n個(gè)點(diǎn)把第 n個(gè)圓分成 12 n個(gè)弧，而每條弧1 n個(gè)圓分成的區(qū)域分成兩個(gè)區(qū)域，n個(gè)圓使成的 區(qū)域數(shù)增加了 12 n個(gè)。 將平面分成 設(shè)這個(gè)圓與前一個(gè) 正好將前面的 故新加入的第 因此可以建立如下的遞推關(guān)系： 2),2(1211 annaann7.1 遞推關(guān)系的定義及建立Fibon

6、acci數(shù)列是遞推關(guān)系的又一個(gè)典型問題，數(shù)列的本身有著許多應(yīng)用。 問題：?jiǎn)栴}：有雌雄兔子一對(duì)，雌兔每月產(chǎn)雌雄各一的一對(duì)新兔，從第二月開始每對(duì)新兔也是每月產(chǎn)一對(duì)新兔問第n個(gè)月后共有多少對(duì)兔子？ 設(shè)第n個(gè)月開始時(shí)兔子對(duì)數(shù)為 其中上月新生兔數(shù)目設(shè)為 對(duì)。第n-個(gè)月留下的兔子數(shù)目設(shè)為 對(duì)。nFnNnOnnnONF 7.2 Fibonacci數(shù)列及性質(zhì) 但211 , nnnnnFONFO 1 , 2121FFFFFnnn7.2 Fibonacci數(shù)列及性質(zhì)例 考慮 n 1棋盤。假設(shè)用紅和藍(lán)兩種顏色之一為棋盤的每一個(gè)方格著色。令 nh是使得沒有兩個(gè)被涂成紅色的方格相鄰的著色方法數(shù)。求出 nh所滿足的遞推關(guān)

7、系，然后得出 nh的公式。 2, 1,1012 hhhhhnnn7.2 Fibonacci數(shù)列及性質(zhì)例 某人上有 n個(gè)臺(tái)階的山路（每步只允許上一臺(tái)階或兩臺(tái)階）。問他有多少種不同的方法數(shù)？ 我們假設(shè)為 ng，則顯然 22, 11 gg且 21 ngngng7.2 Fibonacci數(shù)列及性質(zhì)定義：由初始條件 11, 10 FF及遞推關(guān)系 221 nnFnFnF所確定的數(shù)列 0 nnF叫做 Fibonacci數(shù)列， nF叫做 Fibonacci數(shù)。 7.2 Fibonacci數(shù)列及性質(zhì)性質(zhì) 1） 20, 2 , 1 , 0nknkknnF我們用組合的意義證明： 在上 n級(jí)臺(tái)階的 ng方法中， 恰好

8、有 20nkk步上2級(jí)臺(tái)階（此時(shí)有 kn2 步上1級(jí)臺(tái)階）的方法數(shù)為 !2!2knkkkn kkn7.2 Fibonacci數(shù)列及性質(zhì)所以 20nkkknng從而 20, 2 , 1 , 0nknkknnF7.2 Fibonacci數(shù)列及性質(zhì)性質(zhì) 2） 12210 nnFFFFF 證明：證明：1211342231120 ) nnnnnnFFFFFFFFFFFFFFF_1 22221 nnnFFFFFF7.2 Fibonacci數(shù)列及性質(zhì) 性質(zhì)3） 1-212531nnFFFFF 證明：證明：22212465243021 ) nnnFFFFFFFFFFFF_1 212531 nnFFFFF7.2

9、 Fibonacci數(shù)列及性質(zhì) 性質(zhì)4）122420 nnFFFFF 證明：證明：3212235413210 ) nnnFFFFFFFFFFF_ 122420 nnFFFFF7.2 Fibonacci數(shù)列及性質(zhì) 性質(zhì)5） 12222120 nnnFFFFFF 證明：證明： )( )()(11112324324323123213222102102121100nnnnnnnnFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF _122120 nnnFFFFF7.2 Fibonacci數(shù)列及性質(zhì) 性質(zhì)6） 1, 111 nmmFnFmFnFmnF證明：上有 mn 級(jí)臺(tái)階的臺(tái)階（每步只允許1級(jí)臺(tái)階2階臺(tái)階）的不同方法共有 mnF 種，在第 n級(jí)臺(tái)階的上臺(tái)階方法有 mFnF種，一步 踏在第 n級(jí)臺(tái)階（此時(shí)必有一步是從 1 n級(jí)臺(tái)階跨到第 1 n級(jí)臺(tái)階）的上臺(tái)階方法 有 11 mFnF種。 其中有一步踏沒有或上由加法原則，有 1, 111 nmmFnFmFnFmnF7.2 Fibonacci數(shù)列及性質(zhì)例 求 Fibonacci數(shù) .20F解：因?yàn)?85, 54, 33 FFF 101020 FF 991010FFFF 44555510FFFFFF 895588 3445459FFFFFF 553558 1094655558