遞推關系與Fibonacci數列

遞推關系與Fibonacci數列1.遞推關系Hanoi塔問題：這是組合數學中的一個著名問題。n個圓盤依其半徑大小，從下而上套在A柱上。每次只允許取一個移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱An個盤移到C柱上，請設計一種方法并估計要移動幾個盤次?，F(xiàn)在只有A、B、C三根柱子可用。首先要設計算法，進而估計它的復雜性，即估計工作量。當n=2時，第一步把A柱的小圓盤移到B柱；第二步把A柱的大圓盤移到C柱；A

B

C第三步把B柱的小圓盤移到C柱，即完成移動。假定n-1個盤子的轉移算法已經確定，對于一般n個圓盤的問題，ABC首先把A柱上面的n-1個圓盤移到B柱；然后把A柱最下面的圓盤移到C柱；最后把B柱的n-1個圓盤移到C柱，即完成移動。令h(n)表示n個圓盤所需要的轉移盤次。因此有：從這個遞推關系式可以逐項遞推得到所有的h(n)。根據算法先把前面n-1個盤子轉移到B上；然后把第n個盤子轉到C上；最后將B的n-1個盤子轉移到C上。下面我們利用母函數來得到h(n)的通項表達式。假設序列h(n)對應的母函數為H(x)，即因此有或者利用x2:x3:x4:+)同樣可以得到：假設下面我們用冪級數展開的方法得到h(n).利用待定系數法容易得到A=1，B=-1，即即對于一個n位十進制數p1p2…pn-1pn，則p1

p2…pn-1

是n-1位十進制數。例1求n位十進制數中出現(xiàn)偶數個5的數的個數。因此若令an表示n位十進制數中出現(xiàn)偶數個5的數的個數，bn表示出現(xiàn)奇數個5的數的個數，則有若它含有偶數個5，則pn必須取5以外的九個數中的一個；若p1p2…pn-1含有奇數個5，則pn必須取成5。a1=8，b1=1.設{an}的母函數為A(x)，{bn}的母函數為B(x)，則或者利用x2:x3:+)類似的還有這樣就得到了關于A(x)和B(x)的聯(lián)立方程組：可以解得：因此有由于另解：n-1位十進制數共有9×10n-2個，要么含有奇數個5，要么含有偶數個5。故有：因此有因此有(1)不出現(xiàn)a1，這相當于從其他n-1個元素中取r個做可重組合；這樣的組合可以分為兩種情況：(2)出現(xiàn)a1，這相當于從n個元素中取r-1個做可重組合再加上a1。因此有初始條件為因此還可以令例2從n個不同的元素a1,a2,…,an中取r個做允許重復的組合，求不同的組合數注意到遞推關系

中有2個參數，對于固定的n，

的母函數為Gn(x)，則因此有因此由二項式展開定理可知2.Fibonacci數列Fibonacci數列是遞推關系的又一個典型問題，數列的本身有著許多應用。有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的一對小兔。問過了n個月后共有多少對兔子？設滿n個月時兔子對數為Fn，其中當月新生兔數目設為Nn

對，上個月留下的兔子數目設為On對，則但是注意到On=Fn-1，Nn=On-1=Fn-2，因此有利用這個遞推關系很容易可以得到：下面我們利用母函數來計算Fn的通項表達式。設Fn的母函數為G(x)，則x3:x4:+)方程1-x-x2=0的兩個根設為：則有利用待定系數法易有因此有即通項表達式為：下面介紹一些關于Fibonacci數列的結論。(1)任意正整數N可以表示成Fibonacci數列中的數的有限和，即滿足si=0或1，且sisi+1=0。(2)邊長為Fn的正方形可以分解為若干個邊長為Fi和Fi+1的長方形。參見課本圖形。方法：將三分法中的2/3換成。不妨假設區(qū)間為[0,1]，上一步的取值點為x，1-x。為了充分利用上一步取值點的信息，因此要求x2=x(1-x)，解得x約等于。為什么??？假設保留的區(qū)間為[0,x]，則下一步的取值點為x2，x(1-x)。這比三分法節(jié)省了大約一半的運算量。Fibonacci方法：在第k步令因此若要求最后區(qū)間長度不超過d，則可由(b-a)/Fn<d解出Fn，即確定n。