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

1、1例例1 1 Hanoi塔塔問題：問題：這是組合數(shù)學中的一個著名問題。n個圓盤依其半徑大小，從下而上套在A柱上。每次只允許取一個移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個盤移到C柱上,請設計一種方法并估計要移動幾個盤次?，F(xiàn)在只有A、B、C三根柱子可用。2.6 2.6 遞推關(guān)系遞推關(guān)系2Hanoi問題是個典型的組合問題,第一步要設計算法，進而估計它的復雜性，即估計工作量。A B C2.6 2.6 遞推關(guān)系遞推關(guān)系算法：算法：n=2時第一步先把最上面的一個圓盤套在B上z z第二步把下面的一個圓盤移到C上 最后把B上的圓盤移到C上 到此轉(zhuǎn)移完畢3 對于一般n個圓盤的問題，w 假

2、定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)系4 上述算法是遞歸的運用。n=2時已給出算法；n=3時，第一步便利用算法把上面兩個盤移到B上，第二步再把第三個圓盤轉(zhuǎn)移到柱C上；最后把柱B上兩個圓盤轉(zhuǎn)移到柱C上。n=4，5，依此類推。 2.6 2.6 遞推關(guān)系遞推關(guān)系5 算法分析：算法分析：令h(n)表示n個圓盤所需要的轉(zhuǎn)移盤次。根據(jù)算法先把前面n-1個盤子轉(zhuǎn)移到B上；然后把第n個盤子轉(zhuǎn)到C上；最后再一次將B上的n-1個盤子轉(zhuǎn)移到C上。 n=2時，算

3、法是對的，因此，n=3是算法是對的。依此類推。于是有 2.6 2.6 遞推關(guān)系遞推關(guān)系6算法復雜度為：( )2 (1)1, (1)1 (a)h nh nh,)3()2() 1 ()(32xhxhxhxH H(x)是序列h(1),h(2),h(3) 的母函數(shù)。給定了序列，對應的母函數(shù)也確定了。反過來也一樣，求得了母函數(shù)，對應的序列也就可得而知了。 當然，利用遞推關(guān)系(a)式也可以依次求得h(1),h(2),h(3) ，這樣的連鎖反應關(guān)系，叫做遞遞推關(guān)系推關(guān)系。2.6 2.6 遞推關(guān)系遞推關(guān)系7 下面介紹如何從(a)式求得母函數(shù)H(x)的一種形式算法。所謂形式算法說的是假定這些冪級數(shù)在作四則運算時

4、，一如有限項的代數(shù)式一樣。,)3()2() 1 ()(32xhxhxhxH23) 2( ) -2 (1)2 (2),xH xhxhx_32)2(2)3( )1 (2)2() 1 ()()21 (xhhxhhxhxHx2.6 2.6 遞推關(guān)系遞推關(guān)系8 根據(jù)(a)，, 1)2(2)3(, 1) 1 (2)2(, 1) 1 ( hhhhh)1/()()21 ( 32xxxxxxHx 或利用遞推關(guān)系(a)有1) 1 (2)2(:2 hhx1)2(2)3(:3 hhx )_)1/()(2)( 2xxxxHxxH2.6 2.6 遞推關(guān)系遞推關(guān)系9 整理得2(12 )( )11xxx H xxxx)21)

5、(1 ()(xxxxH 這兩種做法得到的結(jié)果是一樣的。即： 2.6 2.6 遞推關(guān)系遞推關(guān)系10 令(1 2 )(1)( )11 2(1)(1 2 )() (2) (1)(1 2 )ABAxBxH xxxxxAB -AB xxxxxBABA)2()( 如何從母函數(shù)得到序列 h(1),h(2),h(3) ？下面介紹一種化為部分分數(shù)的算法。2.6 2.6 遞推關(guān)系遞推關(guān)系11 由上式可得：. 1 , 1BA 即：12BA0 BA223322233111( )121 (1222)(1) (21)(21)(21) (21)kkkH xxxxxxxxxxxx2.6 2.6 遞推關(guān)系遞推關(guān)系12因為：1)

6、()(kkxkhxH12)( kkh2.6 2.6 遞推關(guān)系遞推關(guān)系13 例例2. 求n位十進制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。解:先從分析n位十進制數(shù)出現(xiàn)偶數(shù)個5的數(shù)的結(jié)構(gòu)入手,p1p2pn-1 是n-1位十進制數(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的十進制數(shù)。2.6 2.6 遞推關(guān)系遞推關(guān)系14 解法解法1：令 an= n位十進制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)， bn= n位十進制數(shù)中出現(xiàn)奇數(shù)個5的數(shù)的個數(shù)。 有：119nnnbaa119nnnabb且118,

7、 1 (b)ab2.6 2.6 遞推關(guān)系遞推關(guān)系 (b)是關(guān)于序列an和bn的聯(lián)立關(guān)系。15設序列an 的母函數(shù)為A(x)，序列bn的母函數(shù)為B(x) 。2123212212 ( ) 9( )99) ( ) A xaa xa xxA xa xa xxB xb xb x則有_8)()()91 (xxBxAx 2.6 2.6 遞推關(guān)系遞推關(guān)系16 )9 : 9 : 9 : 33432232112baaxbaaxbaax_)()(98)(xxBxxAxA8)()()91 ( xxBxAx 2.6 2.6 遞推關(guān)系遞推關(guān)系17 又：_1)()()91 (xxAxBx故得關(guān)于母函數(shù)A(x)和B(x)的聯(lián)

8、立方程組：1)()91 ()(8)()()91 (xBxxxAxxBxAx2123212212( )9( )99) ( ) B xbb xb xxB xb xb xxA xa xa x 2.6 2.6 遞推關(guān)系遞推關(guān)系18xxxxD91 91 22(19 )xx280181xx)101)(81 (xx)101)(81 (87191 18801811)(2xxxxxxxxA)101)(81 (118 91)101)(81 (1)(xxxxxxxxB 2.6 2.6 遞推關(guān)系遞推關(guān)系190)10987(21)1019817(21)( kkkkxxxxA111029827 kkka 2.6 2.6

9、遞推關(guān)系遞推關(guān)系20 解法二：解法二： n-1位的十進制數(shù)的全體共 ,從中去掉含有偶數(shù)個5的數(shù)，余下的便是n-1位中含有奇數(shù)個5的數(shù)。故有： 2109n121111099nnnnnnabbaa8 ,1098 121aaannn 2.6 2.6 遞推關(guān)系遞推關(guān)系21令221232188)(8 )(xaxaxxAxaxaaxA_22312)8()8(8)()81 (xaaxaaxAx 2.6 2.6 遞推關(guān)系遞推關(guān)系22xxxxxxxAx10171810198 10998)()81 ( 20)10987(21 )1019817(21)101)(101 (718)( kkkkxxxxxxxA1179

10、 81022kkka 2.6 2.6 遞推關(guān)系遞推關(guān)系23表示，其結(jié)果可能有以下兩種情況。 naaa,21例例3：從n個元素中取r個進行允許重復),(rnC的組合。假定允許重復的組合數(shù)用1) 1) 不出現(xiàn)某特定元素設為a1，其組合數(shù)為), 1(rnCnaa,2,相當于排除a1后從中取r個做允許重復的組合。 2.6 2.6 遞推關(guān)系遞推關(guān)系24 2）至少出現(xiàn)一個 a1 ，取組合數(shù)為 相當于從 中取r-1個做允許重復的組合然后再加上一個a1得從n個元素中取r個允許重復的組合。) 1,(rnCnaaa,21依據(jù)加法原則可得： (1)( , )( ,1)(1, )C n rC n rC nr1) 1

11、, 1(,) 1 ,(nnCnnC因1)0 ,(nC故令 2.6 2.6 遞推關(guān)系遞推關(guān)系25 遞推關(guān)系(1)帶有兩個參數(shù)n和r。221( )( ,0)( ,1)( ,2)( ) ( ,0)( ,1) ( )(1,0)(1,1) nnnG xC nC nxC nxxG xC nxC nxGxC nC nx_1(1)( )( )0 (2)nnx GxGx 2.6 2.6 遞推關(guān)系遞推關(guān)系26 (2)式是關(guān)于Gn(x) 的遞推關(guān)系，但系數(shù) (1-x) 不是常數(shù)。xxxxCxCCxG111 )2 , 1 () 1 , 1 ()0 , 1 ()( 2211221-111 ( )( )( )1(1)11

12、 ( )(1- )(1- )nnnnnG xGxGxxxG xxx 2.6 2.6 遞推關(guān)系遞推關(guān)系27由二項式定理23(1)(1)(1)(2)12!3! nxn nn nnnxxx 可得), 1( )!1()!1(!) 1() 1(),(rrnCnrnrrnnnrnC 2.6 2.6 遞推關(guān)系遞推關(guān)系28 Fibonacci數(shù)列是遞推關(guān)系的又一個典型問題，數(shù)列的本身有著許多應用。問題：問題：有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的一對小兔。問過了n個月后共有多少對兔子？設滿n個月時兔子對數(shù)為 Fn其中當月新生兔數(shù)目設為Nn 對。第n-1個月留下的兔子數(shù)目設為On 對。nnnONF 2.6

13、 2.6 遞推關(guān)系遞推關(guān)系- -FibonacciFibonacci數(shù)列數(shù)列29 但211 , nnnnnFONFO即第n-2個月所產(chǎn)的兔子到第n個月都有繁殖能力了.1212 , 1 (1)nnnFFFFF由遞推關(guān)系(1)式可依次得到 , 523 , 3 , 2 435324213FFFFFFFFF 2.6 2.6 遞推關(guān)系遞推關(guān)系30221)(xFxFxG ): : 23441233FFFxFFFx_)()()(22xGxxxGxxxxGxxGxx)()1 ( 2 設 2.6 2.6 遞推關(guān)系遞推關(guān)系31xBxAxxxxxxxG25112511 )2511)(2511 (1)( 2 2.6

14、2.6 遞推關(guān)系遞推關(guān)系321)(250BABA520BABA51 , 51BA 2.6 2.6 遞推關(guān)系遞推關(guān)系33)()(51 251112511151)( 222xxxxxG() 5nnnF 2.6 2.6 遞推關(guān)系遞推關(guān)系34其中251512 ,251512111515()()() ) (2)2255nnnnnF618. 12511nnFF 2.6 2.6 遞推關(guān)系遞推關(guān)系35w 趣味結(jié)論趣味結(jié)論=21Fibonacci = 0 1 01( ) , ,niniiiiNNs Fss s任意正整數(shù) 可以表示為序列的有限和：21( )niiFibonacciFFF方形，即邊長為的正方形可以分

15、解為若干邊長為和的矩形的和 2.6 2.6 遞推關(guān)系遞推關(guān)系361221) 1 nnFFFF 證明：證明：1211342231 )nnnnnnFFFFFFFFFFFF_ 122221nnnFFFFFF 2.6 2.6 遞推關(guān)系遞推關(guān)系371352122) nnFFFFF 證明：證明：2221246524321 )nnnFFFFFFFFFFF_nnFFFFF212531 2.6 2.6 遞推關(guān)系遞推關(guān)系382221213) nnnFFFF F 證明：證明： )( )()(111123243243231232132221221nnnnnnnnFFFFFFFFFFFFFFFFFFFFFFFFFFF_122221 nnnFFFFF 2.6 2.6 遞推關(guān)系遞推關(guān)系39 2.6 2.6 遞推關(guān)系遞推關(guān)系( ) , f xa b求單峰函數(shù)在區(qū)間上的最大值。11,aa bb令,kka b設區(qū)間為，將其三等分，即三分法：三分法：12(),().33kkkkkkkkabaaba1111()(),kkkkkkkkkkffaa babb若，則取否則，取特點：每次區(qū)間長度縮短1/3缺點：上一步點的值下一步?jīng)]有用到40 2.6 2.6 遞推關(guān)系遞推關(guān)系0.618方法：方法：將三