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

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

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

3、個圓盤移到C柱，即完成移動。柱，即完成移動。令令h(n)表示表示n個圓盤所需要的轉移盤次。個圓盤所需要的轉移盤次。因此有：因此有：( )(),( ).h nh nh21111從這個遞推關系式可以逐項遞推得到所有的從這個遞推關系式可以逐項遞推得到所有的h(n)。根據(jù)算法先把前面根據(jù)算法先把前面n-1個盤子轉移到個盤子轉移到B上；然后把第上；然后把第n個盤子轉到個盤子轉到C上；最后將上；最后將B的的n-1個盤子轉移到個盤子轉移到C上。上。下面我們利用母函數(shù)來得到下面我們利用母函數(shù)來得到h(n)的通項表達式。的通項表達式。假設序列假設序列h(n)對應的母函數(shù)為對應的母函數(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假設假設 ( ).xABH xxxxx112121下面我們用冪級

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

6、奇數(shù)個5的數(shù)的個數(shù)，則有的數(shù)的個數(shù)，則有若它含有偶數(shù)個若它含有偶數(shù)個5，則，則 pn必須取必須取5以外的九個數(shù)中的以外的九個數(shù)中的一個；一個；若若 p1 p2pn-1含有奇數(shù)個含有奇數(shù)個5，則，則 pn必須取成必須取成5。a1=8，b1=1.設設 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這樣就得到了關于這樣就得到了關于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、位十進制數(shù)共有位十進制數(shù)共有910n-2個，要么含有奇?zhèn)€，要么含有奇數(shù)個數(shù)個5，要么含有偶數(shù)個，要么含有偶數(shù)個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，這相當于從其他，這相當于從其他n-1個元素中取個元素中取r個做個做可重

9、組合；可重組合；這樣的組合可以分為兩種情況：這樣的組合可以分為兩種情況：C n rC n rC nr ( , )( ,1)(1, ).(2) 出現(xiàn)出現(xiàn)a1，這相當于從，這相當于從n個元素中取個元素中取r-1個做可重組個做可重組合再加上合再加上a1。因此有。因此有初始條件為初始條件為C nnC nn ( ,1),(1,1)1,因此還可以令因此還可以令例例2 從從n個不同的元素個不同的元素a1,a2,an中取中取r個做允許重復個做允許重復的組合，求不同的組合數(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遞推關系遞推關系 中有中有2個參個參數(shù)，對于固定的數(shù)，對于固定的n， 的母函數(shù)為的母函數(shù)為Gn(x)，則，則C n rC n rC nr ( , )( ,1)(1, )C n r( , )因此有因此有( )( )( )()nnnGxGxGxxx 1221111因此由二項式展開定理可知因此由二項式展開定理可知()()()( , )(

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

12、的兔子數(shù)目設為On對，則對，則.nnnFNO但是注意到但是注意到 On = Fn-1，Nn = On-1 = Fn-2，因此有，因此有,.nnnFFFFF 12121利用這個遞推關系很容易可以得到：利用這個遞推關系很容易可以得到：, , , FFFFFFFFF 31242353423325下面我們利用母函數(shù)來計算下面我們利用母函數(shù)來計算Fn的通項表達式。的通項表達式。設設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的兩個根設為：的兩個根設為：則有則有( ).xABG xxxxx 2111利用待定系數(shù)法易有利用待定系數(shù)法易有,AB 1515因此有因此有( )()()nnnnG xxx 0015()nnnnx 115即通項表達式為：即通項表達式為：().nnnF 15下面介紹一些關于下面介紹一些關于Fibonacci數(shù)列的結論。數(shù)列的結論。(1) 任意正整數(shù)任意正整數(shù)N可以表示成可以表示成Fibonacci數(shù)列中的數(shù)的數(shù)列中的數(shù)的有限和，即有限和，即=2=niiiNs F,滿足滿足si=0或或1，且，且si si+1=0。(2) 邊長為邊長為Fn的正方形可以分解為若干個邊長為的正方形可以分解為若干

14、個邊長為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下面介紹一個下面

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