2-2-遞推關系與Fibonacci數列課件

2.2遞推關系與Fibonacci數列

遞推關系

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

B

C第三步把B柱的小圓盤移到C柱，即完成移動。當n=2時，第一步把A柱的小圓盤移到B柱；第二步把A柱的大圓3假定n-1個盤子的轉移算法已經確定，對于一般n個圓盤的問題，ABC首先把A柱上面的n-1個圓盤移到B柱；然后把A柱最下面的圓盤移到C柱；最后把B柱的n-1個圓盤移到C柱，即完成移動。假定n-1個盤子的轉移算法已經確定，對于一般n個圓盤的問題，4令h(n)表示n個圓盤所需要的轉移盤次。因此有：從這個遞推關系式可以逐項遞推得到所有的h(n)。根據算法先把前面n-1個盤子轉移到B上；然后把第n個盤子轉到C上；最后將B的n-1個盤子轉移到C上。下面我們利用母函數來得到h(n)的通項表達式。假設序列h(n)對應的母函數為H(x)，即令h(n)表示n個圓盤所需要的轉移盤次。因此有：從這個遞推關5因此有因此有6或者利用x2:x3:x4:+)同樣可以得到：或者利用x2:x3:x4:+)同樣可以得到：7假設下面我們用冪級數展開的方法得到h(n).利用待定系數法容易得到A=1，B=-1，即即假設下面我們用冪級數展開的方法得到h(n).利用待定系數法容8對于一個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.對于一個n位十進制數p1p2…pn-1pn，則p19設{an}的母函數為A(x)，{bn}的母函數為B(x)，則或者利用x2:x3:+)設{an}的母函數為A(x)，{bn}的母函數為B(x)10類似的還有這樣就得到了關于A(x)和B(x)的聯(lián)立方程組：可以解得：類似的還有這樣就得到了關于A(x)和B(x)的聯(lián)立方程組：可11因此有由于另解：n-1位十進制數共有9×10n-2個，要么含有奇數個5，要么含有偶數個5。故有：因此有因此有由于另解：n-1位十進制數共有9×10n-2個，要么12因此有因此有13(1)不出現(xiàn)a1，這相當于從其他n-1個元素中取r個做可重組合；這樣的組合可以分為兩種情況：(2)出現(xiàn)a1，這相當于從n個元素中取r-1個做可重組合再加上a1。因此有初始條件為因此還可以令例2從n個不同的元素a1,a2,…,an中取r個做允許重復的組合，求不同的組合數(1)不出現(xiàn)a1，這相當于從其他n-1個元素中取r個做可重14注意到遞推關系

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

的母函數為Gn(x)，則注意到遞推關系15因此有因此由二項式展開定理可知因此有因此由二項式展開定理可知162.Fibonacci數列Fibonacci數列是遞推關系的又一個典型問題，數列的本身有著許多應用。有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的一對小兔。問過了n個月后共有多少對兔子？設滿n個月時兔子對數為Fn，其中當月新生兔數目設為Nn對，上個月留下的兔子數目設為On對，則但是注意到On=Fn-1，Nn=On-1=Fn-2，因此有2.Fibonacci數列Fibonacci數列是遞推關17利用這個遞推關系很容易可以得到：下面我們利用母函數來計算Fn的通項表達式。設Fn的母函數為G(x)，則x3:x4:+)利用這個遞推關系很容易可以得到：下面我們利用母函數來計算Fn18方程1-x-x2=0的兩個根設為：則有利用待定系數法易有因此有即通項表達式為：方程1-x-x2=0的兩個根設為：則有利用待定系數法易有因此19下面介紹一些關于Fibonacci數列的結論。(1)任意正整數N可以表示成Fibonacci數列中的數的有限和，即滿足si=0或1，且sisi+1=0。(2)邊長為Fn的正方形可以分解為若干個邊長為Fi和Fi+1的長方形。參見課本圖形。下面介紹一些關于Fibonacci數列的結論。(1)任意正202-2-遞推關系與Fibonacci數列課件212-2-遞推關系與Fibonacci數列課件222-2-遞推關系與Fibonacci數列課件23下面介紹一個Fibonacci數列在優(yōu)化中的應用。問題：求單峰函數f(x)在區(qū)間[a,b]上的最大值。三分法：將第k步的區(qū)間[ak,bk]三等分，即優(yōu)點：每次區(qū)間長度縮短1/3。數值方法迭代求解。首先令a1=a，b1=b。若，則取否則取缺點：上一步中點的值在下一步沒有用到。下面介紹一個Fibonacci數列在優(yōu)化中的應用。問題：求單240.618方法：將三分法中的2/3換成0.618。不妨假設區(qū)間為[0,1]，上一步的取值點為x，1-x。為了充分利用上一步取值點的信息，因此要求x2=x(1-x)，解得x約等于0.618。為什么取0.618？假設保留的區(qū)間為[0,x]，則下一步的取值點為x2，x(1-x)。這比三分法節(jié)省了大約一半的運算量。0.618方法：將三分法中的2/3換成0.618。不妨假設區(qū)25Fibonacci方法：在第k步令因此若要求最后區(qū)間長度不超過d，則可由(b-a)/Fn<d解出Fn，即確定n。這樣在n步迭代后，bn-an=(b-a)/Fn。注意到因此當n趨于無窮時，F(xiàn)ibonacci方法與0.618方法的區(qū)間縮短率相同。可以證明Fibonacci方法是一維極值問題的最優(yōu)策略，而0.618是近似最優(yōu)的。Fibonacci方法：在第k步令因此若要求最后區(qū)間長度不超262.2遞推關系與Fibonacci數列

遞推關系

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

B

C第三步把B柱的小圓盤移到C柱，即完成移動。當n=2時，第一步把A柱的小圓盤移到B柱；第二步把A柱的大圓29假定n-1個盤子的轉移算法已經確定，對于一般n個圓盤的問題，ABC首先把A柱上面的n-1個圓盤移到B柱；然后把A柱最下面的圓盤移到C柱；最后把B柱的n-1個圓盤移到C柱，即完成移動。假定n-1個盤子的轉移算法已經確定，對于一般n個圓盤的問題，30令h(n)表示n個圓盤所需要的轉移盤次。因此有：從這個遞推關系式可以逐項遞推得到所有的h(n)。根據算法先把前面n-1個盤子轉移到B上；然后把第n個盤子轉到C上；最后將B的n-1個盤子轉移到C上。下面我們利用母函數來得到h(n)的通項表達式。假設序列h(n)對應的母函數為H(x)，即令h(n)表示n個圓盤所需要的轉移盤次。因此有：從這個遞推關31因此有因此有32或者利用x2:x3:x4:+)同樣可以得到：或者利用x2:x3:x4:+)同樣可以得到：33假設下面我們用冪級數展開的方法得到h(n).利用待定系數法容易得到A=1，B=-1，即即假設下面我們用冪級數展開的方法得到h(n).利用待定系數法容34對于一個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.對于一個n位十進制數p1p2…pn-1pn，則p135設{an}的母函數為A(x)，{bn}的母函數為B(x)，則或者利用x2:x3:+)設{an}的母函數為A(x)，{bn}的母函數為B(x)36類似的還有這樣就得到了關于A(x)和B(x)的聯(lián)立方程組：可以解得：類似的還有這樣就得到了關于A(x)和B(x)的聯(lián)立方程組：可37因此有由于另解：n-1位十進制數共有9×10n-2個，要么含有奇數個5，要么含有偶數個5。故有：因此有因此有由于另解：n-1位十進制數共有9×10n-2個，要么38因此有因此有39(1)不出現(xiàn)a1，這相當于從其他n-1個元素中取r個做可重組合；這樣的組合可以分為兩種情況：(2)出現(xiàn)a1，這相當于從n個元素中取r-1個做可重組合再加上a1。因此有初始條件為因此還可以令例2從n個不同的元素a1,a2,…,an中取r個做允許重復的組合，求不同的組合數(1)不出現(xiàn)a1，這相當于從其他n-1個元素中取r個做可重40注意到遞推關系

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

的母函數為Gn(x)，則注意到遞推關系41因此有因此由二項式展開定理可知因此有因此由二項式展開定理可知422.Fibonacci數列Fibonacci數列是遞推關系的又一個典型問題，數列的本身有著許多應用。有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的一對小兔。問過了n個月后共有多少對兔子？設滿n個月時兔子對數為Fn，其中當月新生兔數目設為Nn對，上個月留下的兔子數目設為On對，則但是注意到On=Fn-1，Nn=On-1=Fn-2，因此有2.Fibonacci數列Fibonacci數列是遞推關43利用這個遞推關系很容易可以得到：下面我們利用母函數來計算Fn的通項表達式。設Fn的母函數為G(x)，則x3:x4:+)利用這個遞推關系很容易可以得到：下面我們利用母函數來計算Fn44方程1-x-x2=0的兩個根設為：則有利用待定系數法易有因此有即通項表達式為：方程1-x-x2=0的兩個根設為：則有利用待定系數法易有因此45下面介紹一些關于Fibonacci數列的結論。(1)任意正整數N可以表示成Fibonacci數列中的數的有限和，即滿足si=0或1，且sisi+1=0。(2)邊長為Fn的正方形可以分解為若干個邊長為Fi和Fi+1的長方形。參見課本圖形。下面介紹一些關于Fibonacci數列的結論。(1)任意正462-2-遞推關系與Fibonacci數列課件472-2-遞推關系與Fibonacci數列課件482-2-遞推關系與Fibonacci數列課件49下面介紹一個Fibonacci數列在優(yōu)化中的應用。