遞推關(guān)系與Fibonacci數(shù)列

1、2.2 遞推關(guān)系與遞推關(guān)系與Fibonacci數(shù)列數(shù)列 遞推關(guān)系遞推關(guān)系 Fibonacci數(shù)列數(shù)列1. 遞推關(guān)系遞推關(guān)系Hanoi塔問題：這是組合數(shù)學(xué)中的一個(gè)著名問題。塔問題：這是組合數(shù)學(xué)中的一個(gè)著名問題。n個(gè)圓盤依其半徑大小，從下而上套在個(gè)圓盤依其半徑大小，從下而上套在A柱上。每柱上。每次只允許取一個(gè)移到柱次只允許取一個(gè)移到柱B或或C上，而且不允許大盤上，而且不允許大盤放在小盤上方。若要求把柱放在小盤上方。若要求把柱A上的上的n個(gè)盤移到個(gè)盤移到C柱上柱上，請?jiān)O(shè)計(jì)一種方法并估計(jì)要移動(dòng)幾個(gè)盤次?，F(xiàn)在只，請?jiān)O(shè)計(jì)一種方法并估計(jì)要移動(dòng)幾個(gè)盤次?，F(xiàn)在只有有A、B、C三根柱子可用。三根柱子可用。首先要設(shè)

2、計(jì)算法，進(jìn)而估計(jì)它的復(fù)雜性，即估計(jì)工首先要設(shè)計(jì)算法，進(jìn)而估計(jì)它的復(fù)雜性，即估計(jì)工作量。作量。當(dāng)當(dāng)n=2時(shí)，時(shí)，第一步把第一步把A柱的小圓盤移到柱的小圓盤移到B柱；柱；第二步把第二步把A柱的大圓盤移到柱的大圓盤移到C柱；柱；A B C第三步把第三步把B柱的小圓盤移到柱的小圓盤移到C柱，即完成移動(dòng)。柱，即完成移動(dòng)。假定假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定，對于一般個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定，對于一般n個(gè)個(gè)圓盤的問題，圓盤的問題，A B C 首先把首先把A柱上面的柱上面的n-1個(gè)圓盤移到個(gè)圓盤移到B柱；柱；然后把然后把A柱最下面的圓盤移到柱最下面的圓盤移到C柱；柱；最后把最后把B柱的柱的n-1個(gè)圓盤移到

3、個(gè)圓盤移到C柱，即完成移動(dòng)。柱，即完成移動(dòng)。令令h(n)表示表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。個(gè)圓盤所需要的轉(zhuǎn)移盤次。因此有：因此有：( )(),( ).h nh nh21111從這個(gè)遞推關(guān)系式可以逐項(xiàng)遞推得到所有的從這個(gè)遞推關(guān)系式可以逐項(xiàng)遞推得到所有的h(n)。根據(jù)算法先把前面根據(jù)算法先把前面n-1個(gè)盤子轉(zhuǎn)移到個(gè)盤子轉(zhuǎn)移到B上；然后把第上；然后把第n個(gè)盤子轉(zhuǎn)到個(gè)盤子轉(zhuǎn)到C上；最后將上；最后將B的的n-1個(gè)盤子轉(zhuǎn)移到個(gè)盤子轉(zhuǎn)移到C上。上。下面我們利用母函數(shù)來得到下面我們利用母函數(shù)來得到h(n)的通項(xiàng)表達(dá)式。的通項(xiàng)表達(dá)式。假設(shè)序列假設(shè)序列h(n)對應(yīng)的母函數(shù)為對應(yīng)的母函數(shù)為H(x)，即，即( )(

4、)( )( )H xhxhxhx 23123( )( )( )( )H xhxhxhx 23123) ( ) -( )( ),xH xhxhx 2322122,xxxxx 231_()( )( ) ( )( ) ( )( )x H xhxhhxhhx23121221322因此有因此有 ( ).xH xxx 112或者利用或者利用( )( )hh2211( )( )hh 3221( )( )hh 4231x2:x3:x4:_ ( )( )/()H xxxH xxx 221+)同樣可以得到：同樣可以得到： ( ).xH xxx 112假設(shè)假設(shè) ( ).xABH xxxxx112121下面我們用冪級

5、數(shù)展開的方法得到下面我們用冪級數(shù)展開的方法得到h(n).( )H xxx 11121()nnnnxx002利用待定系數(shù)法容易得到利用待定系數(shù)法容易得到A=1，B=-1，即，即(),nnnx 121即即( ).nh n 21對于一個(gè)對于一個(gè)n位十進(jìn)制數(shù)位十進(jìn)制數(shù) p1 p2pn-1 pn，則，則 p1 p2pn-1 是是n-1位十進(jìn)制數(shù)。位十進(jìn)制數(shù)。例例1 求求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù)。的數(shù)的個(gè)數(shù)。,nnnnnnaabbba 111199因此若令因此若令an表示表示n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的的數(shù)的個(gè)數(shù)，個(gè)數(shù)，bn表示出現(xiàn)奇數(shù)個(gè)表示出現(xiàn)

6、奇數(shù)個(gè)5的數(shù)的個(gè)數(shù)，則有的數(shù)的個(gè)數(shù)，則有若它含有偶數(shù)個(gè)若它含有偶數(shù)個(gè)5，則，則 pn必須取必須取5以外的九個(gè)數(shù)中的以外的九個(gè)數(shù)中的一個(gè)；一個(gè)；若若 p1 p2pn-1含有奇數(shù)個(gè)含有奇數(shù)個(gè)5，則，則 pn必須取成必須取成5。a1=8，b1=1.設(shè)設(shè) an 的母函數(shù)為的母函數(shù)為A(x)，bn的母函數(shù)為的母函數(shù)為B(x)，則，則( )A xaa xa x 2123( )xA xa xa x 212999) ( )xB xb xb x 212_() ( )( )x A xxB x 198或者利用或者利用aab 2119aab 3229x2:x3:_( )( )( )A xxA xxB x 89+)()

7、 ( )( )x A xxB x 198類似的還有類似的還有( )B xbb xb x 2123( )xB xb xb x 212999) ( )xA xa xa x 212_() ( )( )x B xxA x 191這樣就得到了關(guān)于這樣就得到了關(guān)于A(x)和和B(x)的聯(lián)立方程組：的聯(lián)立方程組：() ( )( ),( )() ( ),x A xxB xxA xx B x 198191( ),()()xA xxx 71818110可以解得：可以解得：( )A xxx1792 18110因此有因此有由于由于(),nnnnx 017 89 102.nnna 117981022另解：另解： n-1

8、位十進(jìn)制數(shù)共有位十進(jìn)制數(shù)共有910n-2個(gè)，要么含有奇?zhèn)€，要么含有奇數(shù)個(gè)數(shù)個(gè)5，要么含有偶數(shù)個(gè)，要么含有偶數(shù)個(gè)5。故有：。故有： ,.nnnnnnaabba 1121199 10因此有因此有, .nnnaaa 21189 108( )A xaa xa x 2123( )xA xa xa x 212888_() ( )()()x A xaaxaax 2213218888xx 2899 10 xxxx 98718110110因此有因此有(),nnnnx 017 89 102.nnna 117981022(1) 不出現(xiàn)不出現(xiàn)a1，這相當(dāng)于從其他，這相當(dāng)于從其他n-1個(gè)元素中取個(gè)元素中取r個(gè)做個(gè)做可重

9、組合；可重組合；這樣的組合可以分為兩種情況：這樣的組合可以分為兩種情況：C n rC n rC nr ( , )( ,1)(1, ).(2) 出現(xiàn)出現(xiàn)a1，這相當(dāng)于從，這相當(dāng)于從n個(gè)元素中取個(gè)元素中取r-1個(gè)做可重組個(gè)做可重組合再加上合再加上a1。因此有。因此有初始條件為初始條件為C nnC nn ( ,1),(1,1)1,因此還可以令因此還可以令例例2 從從n個(gè)不同的元素個(gè)不同的元素a1,a2,an中取中取r個(gè)做允許重復(fù)個(gè)做允許重復(fù)的組合，求不同的組合數(shù)的組合，求不同的組合數(shù)C n r( , )C n ( ,0)1.( )( , )( , )( , )nGxC nC nxC nx 2012(

10、 ) ( , )( , )nxGxC nxC nx 201) ( )(, )(, )nGxC nC nx 11 01 1_()( )( )nnx GxGx 110注意到注意到( )( , )( , )( , )G xCCxCx 211 01 11 2,xxx 2111遞推關(guān)系遞推關(guān)系 中有中有2個(gè)參個(gè)參數(shù)，對于固定的數(shù)，對于固定的n， 的母函數(shù)為的母函數(shù)為Gn(x)，則，則C n rC n rC nr ( , )( ,1)(1, )C n r( , )因此有因此有( )( )( )()nnnGxGxGxxx 1221111因此由二項(xiàng)式展開定理可知因此由二項(xiàng)式展開定理可知()()()( , )(

11、)!rnnnrC n rr 111-( ),()()nnG xxx111111()()!n nnrr 11(, ).C nrr 12. Fibonacci數(shù)列數(shù)列Fibonacci數(shù)列是遞推關(guān)系的又一個(gè)典型問題，數(shù)數(shù)列是遞推關(guān)系的又一個(gè)典型問題，數(shù)列的本身有著許多應(yīng)用。列的本身有著許多應(yīng)用。有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的一對小兔。問過了一對小兔。問過了n個(gè)月后共有多少對兔子？個(gè)月后共有多少對兔子？設(shè)滿設(shè)滿n個(gè)月時(shí)兔子對數(shù)為個(gè)月時(shí)兔子對數(shù)為Fn，其中當(dāng)月新生兔數(shù)目，其中當(dāng)月新生兔數(shù)目設(shè)為設(shè)為Nn 對，上個(gè)月留下的兔子數(shù)目設(shè)為對，上個(gè)月留下

12、的兔子數(shù)目設(shè)為On對，則對，則.nnnFNO但是注意到但是注意到 On = Fn-1，Nn = On-1 = Fn-2，因此有，因此有,.nnnFFFFF 12121利用這個(gè)遞推關(guān)系很容易可以得到：利用這個(gè)遞推關(guān)系很容易可以得到：, , , FFFFFFFFF 31242353423325下面我們利用母函數(shù)來計(jì)算下面我們利用母函數(shù)來計(jì)算Fn的通項(xiàng)表達(dá)式。的通項(xiàng)表達(dá)式。設(shè)設(shè)Fn的母函數(shù)為的母函數(shù)為G(x)，則，則FFF321FFF432x3:x4:_( )( ( )( )G xxxx G xxx G x22+)() ( )xxG xx 21( ).xG xxx 21, 151522方程方程1-x

13、-x2=0的兩個(gè)根設(shè)為：的兩個(gè)根設(shè)為：則有則有( ).xABG xxxxx 2111利用待定系數(shù)法易有利用待定系數(shù)法易有,AB 1515因此有因此有( )()()nnnnG xxx 0015()nnnnx 115即通項(xiàng)表達(dá)式為：即通項(xiàng)表達(dá)式為：().nnnF 15下面介紹一些關(guān)于下面介紹一些關(guān)于Fibonacci數(shù)列的結(jié)論。數(shù)列的結(jié)論。(1) 任意正整數(shù)任意正整數(shù)N可以表示成可以表示成Fibonacci數(shù)列中的數(shù)的數(shù)列中的數(shù)的有限和，即有限和，即=2=niiiNs F,滿足滿足si=0或或1，且，且si si+1=0。(2) 邊長為邊長為Fn的正方形可以分解為若干個(gè)邊長為的正方形可以分解為若干

14、個(gè)邊長為Fi和和Fi+1的長方形。的長方形。參見課本圖形。參見課本圖形。( );nnFFFF 12231FFF132FFF243) nnnFFF 21_nnnFFF 11nnFFFFF 1222.nF 21( );nnFFFFF 1352124FF 12FFF342) nnnFFF21222_FFF564.nnFFFFF 135212( ) .nnnFFFF F 2221215FF F 2121()FF FFF FF F 222312321) () nnnnnnnnFF FFF FFF 21111_()FF FFF FF F 233423423.nnnFFFF F 222121下面介紹一個(gè)下面

15、介紹一個(gè)Fibonacci數(shù)列在優(yōu)化中的應(yīng)用。數(shù)列在優(yōu)化中的應(yīng)用。問題：求單峰函數(shù)問題：求單峰函數(shù)f(x)在區(qū)間在區(qū)間a,b上的最大值。上的最大值。(),().kkkkkkkkabaaba1233三分法：三分法：將第將第k步的區(qū)間步的區(qū)間ak,bk三等分，即三等分，即優(yōu)點(diǎn)：優(yōu)點(diǎn)：每次區(qū)間長度縮短每次區(qū)間長度縮短1/3。數(shù)值方法迭代求解。首先令數(shù)值方法迭代求解。首先令a1=a，b1=b。若若 ，則取，則取()()kkff ,kkkkaab 11否則取否則取,.kkkkabb 11缺點(diǎn)：缺點(diǎn)：上一步中點(diǎn)的值在下一步?jīng)]有用到。上一步中點(diǎn)的值在下一步?jīng)]有用到。0.618方法：方法：將三分法中的將三分法中的2/3換成換成0.618。不妨假設(shè)區(qū)間為不妨假設(shè)區(qū)間為0,1，上一步的取值點(diǎn)為，上一步的取值點(diǎn)為x，1-x。為了充分利用上一步取值點(diǎn)的信息，因此要求為了充分利用上一步取值點(diǎn)的信息，因此要求x2=x(1-x)，解得，解得x約等于約等于0.618。為什么取為什么取0.618？假設(shè)保留的區(qū)間為假設(shè)保留的區(qū)間為0,x，則下一步的取值點(diǎn)為，則下一步的取值點(diǎn)為x2，x(1-x)。這比三分法節(jié)省了大約這比三分法節(jié)省了大約一半一半的運(yùn)算量。的運(yùn)算量。Fibonacci方法：方法：在第在第k步令步令因此若要求最后區(qū)間長度不超過因此若要求最后區(qū)間長度不超過d d，則可由，則可由 (b-