chap遞推關(guān)系舉例、fibonacci數(shù)列

1、chap遞推關(guān)系舉例、fibonacci數(shù)列 例例1 1 Hanoi塔塔問題：問題：這是組合數(shù)學(xué)中的一 個著名問題。n個圓盤依其半徑大小，從 下而上套在A柱上。每次只允許取一個移 到柱B或C上，而且不允許大盤放在小盤 上方。若要求把柱A上的n個盤移到C柱上, 請設(shè)計一種方法并估計要移動幾個盤次。 現(xiàn)在只有A、B、C三根柱子可用。 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 Hanoi問題是個典型的組合問題,第一步要設(shè)計 算法，進(jìn)而估計它的復(fù)雜性，即估計工作量。 A B C 2.6 2.6 遞推關(guān)系遞推關(guān)系 算法：算法：n=2時 第一步先把最上面的一個圓盤套在

2、B上z z第二步把下面的一個圓盤移到C上 最后把B上的圓盤移到C上 到此轉(zhuǎn)移完畢 chap遞推關(guān)系舉例、fibonacci數(shù)列 對于一般n個圓盤的問題， w 假定n-1個盤子的轉(zhuǎn)移算法已經(jīng)確定。 先把上面的n-1個圓盤經(jīng)過C轉(zhuǎn)移到B。 第二步把A下面一個圓盤移到C上 最后再把B上的n-1個圓盤經(jīng)過A轉(zhuǎn)移到C上 A B C 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 上述算法是遞歸的運用。n=2時已給出 算法；n=3時，第一步便利用算法把上面 兩個盤移到B上，第二步再把第三個圓盤 轉(zhuǎn)移到柱C上；最后把柱B上兩個圓盤轉(zhuǎn) 移到柱C上。n=4，5，依此類推。 2.6

3、 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 算法分析：算法分析：令h(n)表示n個圓盤所需要 的轉(zhuǎn)移盤次。根據(jù)算法先把前面n-1個盤 子轉(zhuǎn)移到B上；然后把第n個盤子轉(zhuǎn)到C上； 最后再一次將B上的n-1個盤子轉(zhuǎn)移到C上。 n=2時，算法是對的，因此，n=3是算法 是對的。依此類推。于是有 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 算法復(fù)雜度為： ( )2 (1)1, (1)1 (a)h nh nh ,)3()2() 1 ()( 32 xhxhxhxH H(x)是序列h(1),h(2),h(3) 的母函數(shù)。給定了 序列，對應(yīng)的母函

4、數(shù)也確定了。反過來也一樣， 求得了母函數(shù)，對應(yīng)的序列也就可得而知了。 當(dāng)然，利用遞推關(guān)系(a)式也可以依次求得 h(1),h(2),h(3) ，這樣的連鎖反應(yīng)關(guān)系，叫做遞遞 推關(guān)系推關(guān)系。 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 下面介紹如何從(a)式求得母函數(shù)H(x)的一種形 式算法。所謂形式算法說的是假定這些冪級數(shù) 在作四則運算時，一如有限項的代數(shù)式一樣。 ,)3()2() 1 ()( 32 xhxhxhxH 23 ) 2( ) -2 (1)2 (2),xH xhxhx _ 3 2 )2(2)3( )1 (2)2() 1 ()()21 ( xhh x

5、hhxhxHx 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 根據(jù)(a)， , 1)2(2)3(, 1) 1 (2)2(, 1) 1 ( hhhhh )1/()()21 ( 32 xxxxxxHx 或利用遞推關(guān)系(a)有 1) 1 (2)2(: 2 hhx 1)2(2)3(: 3 hhx ) _ )1/()(2)( 2 xxxxHxxH 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 整理得 2 (12 )( ) 11 xx x H xx xx )21)(1 ( )( xx x xH 這兩種做法得到的結(jié)果是一樣的。即： 2.6

6、2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 令 (1 2 )(1) ( ) 11 2(1)(1 2 ) () (2) (1)(1 2 ) ABAxBx H x xxxx AB -AB x xx xxBABA)2()( 如何從母函數(shù)得到序列 h(1),h(2),h(3) ？ 下面介紹一種化為部分分?jǐn)?shù)的算法。 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 由上式可得： . 1 , 1BA 即： 12BA 0 BA 22332 2233 1 11 ( ) 121 (1222)(1) (21)(21)(21) (21) kk k H x x

7、x xxxxx xxx x 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 因為： 1 )()( k k xkhxH 12)( k kh 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 例例2. 求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的 個數(shù)。 解:先從分析n位十進(jìn)制數(shù)出現(xiàn)偶數(shù)個5的數(shù) 的結(jié)構(gòu)入手,p1p2pn-1 是n-1位十進(jìn)制數(shù)， 若含有偶數(shù)個5，則pn 取5以外的 0,1,2,3,4,6,7,8,9 九個數(shù)中的一個，若 p1p2pn-1只有奇數(shù)個5，則取pn=5，使 p1p2pn-1 pn成為出現(xiàn)偶數(shù)個5的十進(jìn)制數(shù)。 2.6 2

8、.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 解法解法1： 令 an= n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)， bn= n位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個5的數(shù)的個數(shù)。 有： 11 9 nnn baa 11 9 nnn abb 且 11 8, 1 (b) ab 2.6 2.6 遞推關(guān)系遞推關(guān)系 (b)是關(guān)于序列an和bn的聯(lián)立關(guān)系。 chap遞推關(guān)系舉例、fibonacci數(shù)列 設(shè)序列an 的母函數(shù)為A(x)，序列bn 的母函數(shù)為B(x) 。 2 123 2 12 2 12 ( ) 9( )99 ) ( ) A xaa xa x xA xa xa x xB xb xb x 則有

9、_ 8)()()91 (xxBxAx 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 ) 9 : 9 : 9 : 334 3 223 2 112 baax baax baax _ )()(98)(xxBxxAxA 8)()()91 ( xxBxAx 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 又： _ 1)()()91 (xxAxBx 故得關(guān)于母函數(shù)A(x)和B(x)的聯(lián)立方程組： 1)()91 ()( 8)()()91 ( xBxxxA xxBxAx 2 123 2 12 2 12 ( ) 9( )99 ) ( ) B xb

10、b xb x xB xb xb x xA xa xa x 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 x x x x D 91 91 22 (19 )xx 2 80181xx )101)(81 (xx )101)(81 ( 871 91 1 8 80181 1 )( 2 xx x x x xx xA )101)(81 ( 1 1 8 91 )101)(81 ( 1 )( xx x x x xx xB 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 0 )10987( 2 1 ) 101 9 81 7 ( 2 1 )( k kk

11、k x xx xA 11 10 2 9 8 2 7 kk k a 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 解法二：解法二： n-1位的十進(jìn)制數(shù)的全體共 ,從中 去掉含有偶數(shù)個5的數(shù)，余下的便是n-1位 中含有奇數(shù)個5的數(shù)。故有： 2 109 n 1 2 1 11 109 9 n n n nnn ab baa 8 ,1098 1 2 1 aaa n nn 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 令 2 21 2 321 88)(8 ) )( xaxaxxA xaxaaxA _ 2 2312 )8()8(8)()81

12、(xaaxaaxAx 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 x x x x xxxAx 101 718 101 9 8 10998)()81 ( 2 0 )10987( 2 1 ) 101 9 81 7 ( 2 1 )101)(101 ( 718 )( k kkk x xxxx x xA 11 79 810 22 kk k a 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 表示，其結(jié)果可能有以下兩種情況。 n aaa, 21 例例3：從n個元素中取r個進(jìn)行允許重復(fù) ),(rnC的組合。假定允許重復(fù)的組合數(shù)用 1) 1)

13、 不出現(xiàn)某特定元素設(shè)為a1，其組合數(shù)為 ), 1(rnC n aa, 2 ,相當(dāng)于排除a1后從 中取r個做允許重復(fù)的組合。 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 2）至少出現(xiàn)一個 a1 ，取組合數(shù)為 相當(dāng)于從 中取r-1個做允許重復(fù)的組合 然后再加上一個a1得從n個元素中取r個允許重復(fù) 的組合。 ) 1,(rnC n aaa, 21 依據(jù)加法原則可得： (1)( , )( ,1)(1, )C n rC n rC nr 1) 1 , 1(,) 1 ,(nnCnnC 因 1)0 ,(nC 故令 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fib

14、onacci數(shù)列 遞推關(guān)系(1)帶有兩個參數(shù)n和r。 2 2 1 ( )( ,0)( ,1)( ,2) ( ) ( ,0)( ,1) ) ( )(1,0)(1,1) n n n G xC nC nxC nx xG xC nxC nx GxC nC nx _ 1 (1)( )( )0 (2) nn x GxGx 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 (2)式是關(guān)于Gn(x) 的遞推關(guān)系，但系數(shù) (1-x) 不 是常數(shù)。 x xx xCxCCxG 1 1 1 )2 , 1 () 1 , 1 ()0 , 1 ()( 2 2 1 12 2 1 -1 11 (

15、)( )( ) 1(1) 11 ( ) (1- )(1- ) nnn nn G xGxGx xx G x xx 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 由二項式定理 23 (1) (1)(1)(2) 1 2!3! n x n nn nn nxxx 可得 ), 1( )!1( )!1( ! ) 1() 1( ),( rrnC n rn r rnnn rnC 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 Fibonacci數(shù)列是遞推關(guān)系的又一個典型問題， 數(shù)列的本身有著許多應(yīng)用。 問題：問題：有雌雄兔子一對，假定過兩月便可繁

16、殖 雌雄各一的一對小兔。問過了n個月后共有多少 對兔子？ 設(shè)滿n個月時兔子對數(shù)為 Fn其中當(dāng)月新生兔數(shù)目設(shè) 為Nn 對。第n-1個月留下的兔子數(shù)目設(shè)為On 對。 nnn ONF 2.6 2.6 遞推關(guān)系遞推關(guān)系- -FibonacciFibonacci數(shù)列數(shù)列 chap遞推關(guān)系舉例、fibonacci數(shù)列 但 211 , nnnnn FONFO 即第n-2個月所產(chǎn)的兔子到第n個月都有繁殖能力了. 1212 , 1 (1) nnn FFFFF 由遞推關(guān)系(1)式可依次得到 , 523 , 3 , 2 435 324213 FFF FFFFFF 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉

17、例、fibonacci數(shù)列 2 21 )(xFxFxG ) : : 234 4 123 3 FFFx FFFx _ )()()( 22 xGxxxGxxxxG xxGxx)()1 ( 2 設(shè) 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 x B x A xx x xx x xG 2 51 1 2 51 1 ) 2 51 1)( 2 51 1 ( 1 )( 2 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 1)( 2 5 0 BA BA 5 2 0 BA BA 5 1 , 5 1 BA 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap

18、遞推關(guān)系舉例、fibonacci數(shù)列 )()( 5 1 2 51 1 1 2 51 1 1 5 1 )( 222 xx xx xG () 5 nn n F 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 其中 2 51 51 2 , 2 51 51 2 111515 ()()() ) (2) 2255 nnnn n F 618. 1 2 51 1 n n F F 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 w 趣味結(jié)論趣味結(jié)論 =2 1Fibonacci = 0 1 0 1 ( ) , , n in i iii N Ns F ss s 任意正整數(shù) 可以表示為序列的有 限和： 2 1 ( ) n ii FibonacciF FF 方形，即邊長為的正方形 可以分解為若干邊長為和的矩形的和 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 122 1) 1 nn FFFF 證明：證明： 12 11 342 231 ) nnn nnn FFF FFF FFF FFF _ 12222 1 nnn FFFFFF 2.6 2.6 遞推關(guān)系遞推關(guān)系 chap遞推關(guān)系舉例、fibonacci數(shù)列 135212 2) nn FFFFF 證明：證明：