2-2-遞推關(guān)系與Fibonacci數(shù)列課件

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

遞推關(guān)系

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

B

C第三步把B柱的小圓盤移到C柱，即完成移動(dòng)。當(dāng)n=2時(shí)，第一步把A柱的小圓盤移到B柱；第二步把A柱的大圓3假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定，對(duì)于一般n個(gè)圓盤的問(wèn)題，ABC首先把A柱上面的n-1個(gè)圓盤移到B柱；然后把A柱最下面的圓盤移到C柱；最后把B柱的n-1個(gè)圓盤移到C柱，即完成移動(dòng)。假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定，對(duì)于一般n個(gè)圓盤的問(wèn)題，4令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。因此有：從這個(gè)遞推關(guān)系式可以逐項(xiàng)遞推得到所有的h(n)。根據(jù)算法先把前面n-1個(gè)盤子轉(zhuǎn)移到B上；然后把第n個(gè)盤子轉(zhuǎn)到C上；最后將B的n-1個(gè)盤子轉(zhuǎn)移到C上。下面我們利用母函數(shù)來(lái)得到h(n)的通項(xiàng)表達(dá)式。假設(shè)序列h(n)對(duì)應(yīng)的母函數(shù)為H(x)，即令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。因此有：從這個(gè)遞推關(guān)5因此有因此有6或者利用x2:x3:x4:+)同樣可以得到：或者利用x2:x3:x4:+)同樣可以得到：7假設(shè)下面我們用冪級(jí)數(shù)展開的方法得到h(n).利用待定系數(shù)法容易得到A=1，B=-1，即即假設(shè)下面我們用冪級(jí)數(shù)展開的方法得到h(n).利用待定系數(shù)法容8對(duì)于一個(gè)n位十進(jìn)制數(shù)p1p2…pn-1pn，則p1

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

中有2個(gè)參數(shù)，對(duì)于固定的n，

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

遞推關(guān)系

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

B

C第三步把B柱的小圓盤移到C柱，即完成移動(dòng)。當(dāng)n=2時(shí)，第一步把A柱的小圓盤移到B柱；第二步把A柱的大圓29假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定，對(duì)于一般n個(gè)圓盤的問(wèn)題，ABC首先把A柱上面的n-1個(gè)圓盤移到B柱；然后把A柱最下面的圓盤移到C柱；最后把B柱的n-1個(gè)圓盤移到C柱，即完成移動(dòng)。假定n-1個(gè)盤子的轉(zhuǎn)移算法已經(jīng)確定，對(duì)于一般n個(gè)圓盤的問(wèn)題，30令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。因此有：從這個(gè)遞推關(guān)系式可以逐項(xiàng)遞推得到所有的h(n)。根據(jù)算法先把前面n-1個(gè)盤子轉(zhuǎn)移到B上；然后把第n個(gè)盤子轉(zhuǎn)到C上；最后將B的n-1個(gè)盤子轉(zhuǎn)移到C上。下面我們利用母函數(shù)來(lái)得到h(n)的通項(xiàng)表達(dá)式。假設(shè)序列h(n)對(duì)應(yīng)的母函數(shù)為H(x)，即令h(n)表示n個(gè)圓盤所需要的轉(zhuǎn)移盤次。因此有：從這個(gè)遞推關(guān)31因此有因此有32或者利用x2:x3:x4:+)同樣可以得到：或者利用x2:x3:x4:+)同樣可以得到：33假設(shè)下面我們用冪級(jí)數(shù)展開的方法得到h(n).利用待定系數(shù)法容易得到A=1，B=-1，即即假設(shè)下面我們用冪級(jí)數(shù)展開的方法得到h(n).利用待定系數(shù)法容34對(duì)于一個(gè)n位十進(jìn)制數(shù)p1p2…pn-1pn，則p1

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

中有2個(gè)參數(shù)，對(duì)于固定的n，

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