母函數(shù)與遞推關(guān)系ppt課件

1、Project I 全陳列生成算法的研討和實(shí)現(xiàn) 5分 選作 C/C+ or Java 11月20日前網(wǎng)絡(luò)學(xué)堂提交 目的 Research and Novelty非命題作文，以下內(nèi)容任選 在實(shí)現(xiàn)和研討4種全陳列生成算法根底上進(jìn)展創(chuàng)新 算法效率和復(fù)雜度分析 新的算法 任何相關(guān)內(nèi)容的創(chuàng)新點(diǎn) 3-6頁(yè) 評(píng)分規(guī)范 Paper (80%) 代碼以及可執(zhí)行文件 (20%)選題分析完善2內(nèi)容回想 組合的生成和組合意義 模型轉(zhuǎn)換 一一對(duì)應(yīng) 定義：對(duì)于序列a0,a1,a2,構(gòu)造一函數(shù)： G(x)=a0+a1x+a2x2+, 稱(chēng)函數(shù)G(x)是序列a0,a1,a2,的母函數(shù)(生成函數(shù) generating funct

2、ion)。 (1+x)n是序列C(n,0),C(n,1),C(n,n)的母函數(shù) g(x)=1+x+x2+x3+x4+.=1/(1-x)是f(n)=1的母函數(shù) 設(shè)級(jí)數(shù)收斂， -1x1生成函數(shù)的x沒(méi)有實(shí)踐意義二項(xiàng)式定理12(1)1( 1)kkxxxx 2(1)(1)(1)(1)12!nkn nn nnkxnxxxk 200(1)(1)(1)(1)12!( )(1)(1)!kkknkkkxxxxkkxxRkk 000000( )!()!()!()!()!()!()!()!()!()!nnnnn kkknknn kk llklnklnn kk ll mmklmaanababknknabcabcl kl

3、nknabcdabcdm lmklnk.1)1 (21xxx42.2 2.2 遞推關(guān)系遞推關(guān)系 利用遞推關(guān)系進(jìn)展計(jì)數(shù)這個(gè)方法在算法分析中經(jīng)常用到 例一.Hanoi問(wèn)題：N個(gè)圓盤(pán)依其半徑大小，從下而上套在A(yíng)柱上。每次只允許取一個(gè)移到柱B或C上，而且不允許大盤(pán)放在小盤(pán)上方。假設(shè)要求把柱A上的n個(gè)盤(pán)移到C柱上請(qǐng)?jiān)O(shè)計(jì)一種方法來(lái)，并估計(jì)要挪動(dòng)幾個(gè)盤(pán)次。如今只需A、B、C三根柱子可用。設(shè)計(jì)算法;估計(jì)它的復(fù)雜性，即估計(jì)任務(wù)量.52.2 2.2 遞推關(guān)系遞推關(guān)系算法：算法：N=2時(shí)第一步先把最上面的一個(gè)圓盤(pán)套在B上第二步把下面的一個(gè)圓盤(pán)移到C上 最后把B上的圓盤(pán)移到C上 到此轉(zhuǎn)移終了A B C62.2 2.2

4、 遞推關(guān)系遞推關(guān)系 假定n-1個(gè)盤(pán)子的轉(zhuǎn)移算法曾經(jīng)確定。 對(duì)于普通n個(gè)圓盤(pán)的問(wèn)題,先把上面的n-1個(gè)圓盤(pán)經(jīng)過(guò)C轉(zhuǎn)移到B; 第二步把A下面一個(gè)圓盤(pán)移到C上 最后再把B上的n-1個(gè)圓盤(pán)經(jīng)過(guò)A轉(zhuǎn)移到C上 n=2時(shí)，算法是對(duì)的，因此，n=3是算法是對(duì)的。以此類(lèi)推。A B C 72.2 2.2 遞推關(guān)系遞推關(guān)系令h(n)表示n個(gè)圓盤(pán)所需求的轉(zhuǎn)移盤(pán)次。對(duì)于普通n個(gè)圓盤(pán)的問(wèn)題,先把上面的n-1個(gè)圓盤(pán)經(jīng)過(guò)C轉(zhuǎn)移到B: h(n-1)次第二步把A下面一個(gè)圓盤(pán)移到C上: 1次最后再把B上的n-1個(gè)圓盤(pán)經(jīng)過(guò)A轉(zhuǎn)移到C上： h(n-1)次算法復(fù)雜度為：構(gòu)造母函數(shù)為：求得了母函數(shù)，對(duì)應(yīng)的序列也就求得h(n)1)-2-(2

5、 1) 1 ( , 1) 1(2)(hnhnh,)3()2()1()(32xhxhxhxHA B C 82.2 2.2 遞推關(guān)系遞推關(guān)系所謂方式算法說(shuō)的是假定這些冪級(jí)數(shù)在作四那么運(yùn)算時(shí)，一如有限項(xiàng)的代數(shù)式一樣。,)3()2()1()(32xhxhxhxH,)2(2) 1 (2- )(2 )32xhxhxxH_32)2(2)3( )1(2)2()1()()21(xhhxhhxhxHx1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh,1)2(2)3(,1)1(2)2(,1)1( hhhhh)1/()()21( 32xxxxxxHx)1)(21()( xxxxH.1)1 (21xxx91

6、12()ABHxxx xxBABA)2()( 如何從母函數(shù)得到序列 ？化為部分分?jǐn)?shù)的算法。),2(),1 (hh 由上式可得：12BA0 BAg(x)=1+x+x2+x3+x4+. = x11. 1 , 1BA 即：11121()Hxxx )21)(1()()(1xxxxkhxHkk12)( kkh121112()()()()AxBxxx 2112()()(AB) - (AB)xxx 2233212221()()xxxxx 22331 2 12121 21()()()()kkkxxxx 102.2 2.2 遞推關(guān)系遞推關(guān)系 或利用遞推關(guān)系(2-2-1)有1)1(2)2(:2hhx1)2(2)3

7、(:3hhx )_)1/()(2)( 2xxxxHxxH 上式左端為：xxHxhxHxhxh)()1 ()()3()2(32 右端第一項(xiàng)為：)(2x )2()1(2)2(2)1(2232xHxhxhxxhxh 右端第二項(xiàng)為：)1/(232xxxx1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh)21)(1()(xxxxH112.2 2.2 遞推關(guān)系遞推關(guān)系例例2. 2. 求求n n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5 5的數(shù)的個(gè)數(shù)。的數(shù)的個(gè)數(shù)。 先從分析n位十進(jìn)制數(shù)出現(xiàn)偶數(shù)個(gè)5的數(shù)的構(gòu)造入手 設(shè)p1p2pn-1是n-1位十進(jìn)制數(shù)，假設(shè)含有偶數(shù)個(gè)5，那么pn取5以外的0，1

8、，2，3，4，6，7，8，9九個(gè)數(shù)中的一個(gè)，假設(shè)p1p2pn-1 只需奇數(shù)個(gè)5，那么pn取5，使p1p2pn-1pn 成為出現(xiàn)偶數(shù)個(gè)5的十進(jìn)制數(shù)。解法1：令an為n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個(gè)5的數(shù)的個(gè)數(shù)， bn為n位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個(gè)5的數(shù)的個(gè)數(shù)。設(shè)序列an的母函數(shù)為A(x)，序列bn的母函數(shù)為B(x)。 119nnnbaa119nnnabb122212212321)( )99)(9 )( xbxbxxBxaxaxxAxaxaaxA_8)()()91 (1axxBxAx119nnnbaa119nnnabb )9 : 9 : 9 : 33432232112baaxbaaxbaax_)()(98)(

9、xxBxxAxA8)()()91( xxBxAx_1)()()91(xxAxBx2123212212999 ( )( )( )B xbbx bxxB xbxbxxA xax a x a1=8, b1=1132.2 2.2 遞推關(guān)系遞推關(guān)系故得關(guān)于母函數(shù)A(x)和B(x)得連立方程組：1)()91()(8)()()91(xBxxxAxxBxAxxxxxD91 91 22)91 (xx280181xx)101)(81 (xx)101)(81(87191 18801811)(2xxxxxxxxA)101)(81 (118 91)101)(81 (1)(xxxxxxxxB0)10987(21)1019

10、817(21)( kkkkxxxxA111029827 kkka2123 ( )A xaa x a x 142.2 2.2 遞推關(guān)系遞推關(guān)系解法二：解法二：n-1n-1位的十進(jìn)制數(shù)的全體共位的十進(jìn)制數(shù)的全體共9 910n-110n-1個(gè)個(gè)( (最高位不為最高位不為0)0)，設(shè)所求數(shù)為設(shè)所求數(shù)為an,an,設(shè)設(shè)A(x)= a1x+a2x2+,A(x)= a1x+a2x2+,按照尾數(shù)能否為按照尾數(shù)能否為5 5分類(lèi)分類(lèi)：尾數(shù)不是為尾數(shù)不是為5 5的：的：9an-19an-1尾數(shù)為尾數(shù)為5 5的，前的，前n-1n-1位有奇數(shù)個(gè)位有奇數(shù)個(gè)5 5：1211099nnnnaaa8 ,1098 121aaan

11、nn121109nnnab )9008 : 908 : 98 : 344233122aaxaaxaax_.)10101(9)(8)(2221xxxxxAxaxA152.2 2.2 遞推關(guān)系遞推關(guān)系xxxxAx10198)()81( 2111)10987(21 )1019817(21)101)(81 ()718()( kkkkxxxxxxxxxxA111029827 kkka驗(yàn)證：a1=8,a2=7316 1不出現(xiàn)某特定元素設(shè)為a1，其組合數(shù)為 ，相當(dāng)于排除a1后從a2,.an 中取r個(gè)做允許反復(fù)的組合。2.2 2.2 遞推關(guān)系遞推關(guān)系例三：從例三：從n個(gè)元素個(gè)元素a1,a2,.an中取中取r個(gè)

12、進(jìn)展允許反個(gè)進(jìn)展允許反復(fù)的組合。假定允許反復(fù)的組合數(shù)用復(fù)的組合。假定允許反復(fù)的組合數(shù)用 表表示，其結(jié)果能夠有以下兩種情況。示，其結(jié)果能夠有以下兩種情況。 ),(rnC), 1(rnC 2至少出現(xiàn)一個(gè)a1，取組合數(shù)為 相當(dāng)于從a1,a2,.an中取r-1個(gè)做允許反復(fù)的組合，然后再加上一個(gè)a1得從n個(gè)元素中取r個(gè)允許反復(fù)的組合。) 1,(rnC), 1() 1,(),(rnCrnCrnC172.2 2.2 遞推關(guān)系遞推關(guān)系), 1() 1,(),(rnCrnCrnC 因 ，故令1)1 , 1(,)1 ,(nnCnnC1)0,(nCxnCxnCxGxnCxnCxxGxnCxnCnCxGnnn)1 ,

13、 1()0, 1()( )1 ,()0,( )()2,()1 ,()0,()(122_ 0)()()1(1xGxGxnnxxxxCxCCxG111 )2, 1()1 , 1()0, 1()( 221系數(shù)(1-x)不是常數(shù)。但n11 -n221x)-(11)(x)-(11 )()1(1)(11)( xGxGxxGxxGnnn18nx)-(11)( xGn 由二項(xiàng)式定理32! 3)2)(1(! 2) 1(1)1 (xnnnxnnnxxn 可得1111 1()()()!( , )!()! !(, )n nnrnrC n rrnrC nrr 200(1)(1)(1)(1)12!()(1)(1)!kkk

14、nkkkxxxxkkxxRkk母函數(shù) 遞推關(guān)系 遞推運(yùn)算 初始值 代數(shù)運(yùn)算： 化為部分分?jǐn)?shù)的算法1)-2-(2 1) 1 ( , 1) 1(2)(hnhnh,)3()2()1()(32xhxhxhxH,)2(2)1(2- )(2 )xhxhxxH_32)2(2)3( )1(2)2()1()()21(xhhxhhxhxHx)1)(21()( xxxxH22331 2 12121 21()()()()kkkxxxx 2.3 2.3 母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 一個(gè)序列和它的母函數(shù)一一對(duì)應(yīng)。給了序列便得知它的母函數(shù)；反之，求得母函數(shù)序列也隨之而定。 為了求滿(mǎn)足某種遞推關(guān)系的序列，可把它轉(zhuǎn)換為求對(duì)應(yīng)的母

15、函數(shù)G(x)，G(x)能夠滿(mǎn)足一代數(shù)方程，或代數(shù)方程組，甚至于是微分方程。 最后求逆變換，即從已求得的母函數(shù) G(x)得到序列an。關(guān)鍵在于要搭起從序列到母函數(shù)，從母函數(shù)到序列這兩座橋。212.3 2.3 母函數(shù)的性質(zhì)母函數(shù)的性質(zhì))(xA)(xB對(duì)應(yīng)的母函數(shù)分別為對(duì)應(yīng)的母函數(shù)分別為、kakb不特別闡明不特別闡明, ,下面假設(shè)下面假設(shè)、兩個(gè)序列兩個(gè)序列iikiikxbxBbxaxAa)()(的母函數(shù)為序列的母函數(shù)為記序列,.2 , 1, )()( )(ibaiffxBxAaii,.3 , 2 , 1 , 0 , .)()( )(2210ibacxcxccxBxAbiii則若22性質(zhì)性質(zhì)1：)(

16、000)(11011xAxxaxaxbxbxBlllllllkblk 0lkalk )()(xAxxBl假設(shè)那么 例. 知 xexxxxA!321132那么xmmmmmexxxxxxB!)(32132123 例. 知 132132xexxxxA!那么）（1321121xmmmmexxxxxB!)(11111231110 00 1123:,.!:, ., ,.!ab11101231110 00123:,.!:, .,.!abmmm-1 性質(zhì)2：lkkab那么llkkkxxaxAxB/)()( 10假設(shè)llkkklllllllllllllxxaxAxxaxaxaaxAxaxaxaxxaxaaxB/

17、 )(/ )()()( 101122102211221 1 證：證： 2210 xbxbbxB)( 例例.35( )sin3!5!xxA xxx 33561111( ) sin/7!9!3!5!B xxxxxxxx 241110 1 0003571007ab:, ,.!:,.! 性質(zhì)3：證：證：0kkiibaxxAxB1)()(假設(shè)那么 ): : : : 1 2102102210100nnaaaabnxaaabxaabxab_)1/()()1/( )1/()1/()1/()(22102210 xxAxxaxaaxxaxxaxaxB25 例. 知xxxxxAn111)(2232)1 (14321

18、)(xxxxxB20)1 (1) 1(xxkkk 類(lèi)似可得：232323k3k 0C(x)(12x3x4x) (1xxx) 13x6x10 x11 (k1)(k2)x2(1x) 0kkiibaxxAxB1)()(假設(shè)那么26kiiakb收斂 若 0kkaxxxAAxB1)()1()(性質(zhì)性質(zhì)4那么 ) 00121120222011:(1):(1):(1)baaaAxbaaAaxbaAaa _)1( )1(1)1()(221202xxxaxxxaxxAxB證xxxAAxxxaaxAxB1)()1 ( )1/()(1)1 ()( 1027 A(x)=a0+a1x+a2x2+, A(x)=a1+2a

19、2x+3a3x2+. 例例. xxxxA1112 23211132xxxxxxx 那么性質(zhì)性質(zhì)5 5kkkab xxAxB假設(shè)假設(shè)那么那么性質(zhì)性質(zhì)6 6kabkk1 xdxxAxxB01假設(shè)假設(shè)那么那么求導(dǎo)積分.)( 32210032xaxaxaxAx28性質(zhì)性質(zhì)7 7022110babababackkkkkkiikiba0假設(shè)假設(shè) xBxAxcxccxC2210那么那么 證證 22100 xbxbbaxC22101xbxbbxa 221022xbxbbxa22102210 xbxbbxaxaa xBxAxC),:1000bac,:201101babac,:30211202bababac_29

20、2.32.3母函數(shù)的性質(zhì)母函數(shù)的性質(zhì) 例. 知 2232111231,A xxxxxB xxxxx 31xxxC30 11232,kk kCk kc 0kikiia b xBxAxC2.4 Fibonacci2.4 Fibonacci數(shù)列數(shù)列 Fibonacci數(shù)列是遞推關(guān)系的又一個(gè)典型問(wèn)題。Fibonacci數(shù)列是以遞歸的方法來(lái)定義：F0 = 0， F1 = 1 ， Fn = Fn - 1 + Fn - 2 1斐波那契數(shù)列由0和1開(kāi)始，之后的斐波那契數(shù)就由之前的兩數(shù)相加。0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,

21、987, 1597, 2584, 4181, 6765, 10946，0不是第一項(xiàng)，而是第0項(xiàng)。31 1150年印度數(shù)學(xué)家研討箱子包裝物件長(zhǎng)寬剛好年印度數(shù)學(xué)家研討箱子包裝物件長(zhǎng)寬剛好 為為1和和2的可行方法數(shù)目時(shí)，首先描畫(huà)這個(gè)數(shù)列。的可行方法數(shù)目時(shí)，首先描畫(huà)這個(gè)數(shù)列。 在西方，在西方，1202年，意大利數(shù)學(xué)家斐波那契出版了他的年，意大利數(shù)學(xué)家斐波那契出版了他的。他在書(shū)中提出了一個(gè)關(guān)于兔子繁衍的問(wèn)題：。他在書(shū)中提出了一個(gè)關(guān)于兔子繁衍的問(wèn)題： 第一個(gè)月有一對(duì)剛誕生的兔子；第一個(gè)月有一對(duì)剛誕生的兔子； 假設(shè)一對(duì)兔子每月能生一對(duì)小兔一雄一雌；假設(shè)一對(duì)兔子每月能生一對(duì)小兔一雄一雌； 而每對(duì)小兔在它出生后

22、的第三個(gè)月里，又能開(kāi)場(chǎng)生一對(duì)小而每對(duì)小兔在它出生后的第三個(gè)月里，又能開(kāi)場(chǎng)生一對(duì)小兔，兔， 兔子永不死去；兔子永不死去； 由一對(duì)出生的小兔開(kāi)場(chǎng)，由一對(duì)出生的小兔開(kāi)場(chǎng)，50個(gè)月后會(huì)有多少對(duì)兔子？個(gè)月后會(huì)有多少對(duì)兔子？ 第第n個(gè)月相比個(gè)月相比n-1個(gè)月多出的兔子數(shù)是個(gè)月多出的兔子數(shù)是n-2個(gè)月的兔子生出個(gè)月的兔子生出來(lái)的，即來(lái)的，即 Fn=Fn-1+Fn-2 32Leonardo of PisaSon of Bonaccio 221)(xFxFxG ): : 23441233FFFxFFFx_)()()(22xGxxxGxxxxGxxGxx)()1 ( 2 設(shè)2.4.12.4.1遞推關(guān)系遞推關(guān)系xB

23、xAxxxxxxxG25112511)2511)(2511 (1)( 21)(250BABA520BABA51 , 51BA2.4.12.4.1遞推關(guān)系遞推關(guān)系111 515151122( )G xxx 251512 ,251512)()( 22251 xx nnnnn111515F()()() ) (2)2255 618.12511nnFF34 1 12nn 2FFFF1 (3) 證明：證明：1211342231 )nnnnnnFFFFFFFFFFFF_ 122221nnnFFFFFF2.4.12.4.1遞推關(guān)系遞推關(guān)系Fn=Fn-1+Fn-235 21352n 12nFFFFF (4) 證

24、明：證明：2221246524321 )nnnFFFFFFFFFFF_nnFFFFF212531 2.4.12.4.1遞推關(guān)系遞推關(guān)系Fn=Fn-1+Fn-236 322212nnn 1FFFF F (5) 證明：證明： )( )()(111123243243231232132221221nnnnnnnnFFFFFFFFFFFFFFFFFFFFFFFFFFF_122221 nnnFFFFF2.4.12.4.1遞推關(guān)系遞推關(guān)系37 一位魔術(shù)師拿著一塊邊長(zhǎng)為8英尺的正方形地毯，對(duì)他的地毯匠朋友說(shuō)：“請(qǐng)您把這塊地毯分成四小塊，再把它們縫成一塊長(zhǎng)13英尺，寬5英尺的長(zhǎng)方 魔術(shù)881350, 1, 1,

25、 2, 3, 5, 8, 13, 21,.35F(n)*F(n) F(n-1)F(n+1) = (-1)nn=0,1,2斐波那契螺旋斐波那契螺旋 392.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 設(shè)函數(shù) 在 點(diǎn)獲得極大值。要求用假設(shè)干次實(shí)驗(yàn)找到 點(diǎn)準(zhǔn)確到一定的程度。最簡(jiǎn)單的方法，把 三等分，令：)(xfx),(ba)(32 ),(3121abaxabax如以下圖：yx0 ab1x2x)(1xf)(2xf)(xfy 402.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 設(shè)函數(shù)y=f(x)在區(qū)間(a,b)上有一單峰極值點(diǎn)，假定為極大點(diǎn)。 所謂單峰極值，即只需一個(gè)極值點(diǎn)，而且當(dāng)x與偏離越

26、大，偏向|f(x)-f() | 也越大。如以下圖：yx0ab412.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 根據(jù) 的大小分別討論如下：)(),(21xfxf 當(dāng) ，那么極大點(diǎn) 必在 區(qū)間上，區(qū)間 可以舍去。)()(21xfxf),(2xa),(2bxyx0)(xfy ab1x2x)()(21xfxfyx0)(1xf)(2xfa2x1x422.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 當(dāng) ，那么極大點(diǎn) 必在 區(qū)間上，區(qū)間 可以舍去。)()(21xfxf),(1bx),(1xayx0)(xfy ab1x2x)()(21xfxfyx0)(1xf)(2xf2x1xb432.4.42.

27、4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 當(dāng) ，那么極大點(diǎn) 必在 區(qū)間上，區(qū)間 和 均可以舍去。)()(21xfxf),(21xx),(1xa),(2bxyx0)(xfy ab1x2x)()(21xfxfyx02x1x)(1xf)(2xf44 可見(jiàn)做兩次實(shí)驗(yàn)，至少可把區(qū)間縮至原來(lái)區(qū)間的2/3，比如 ，進(jìn)一步在 區(qū)間上找極值點(diǎn)。假設(shè)繼續(xù)用三等分法，將面對(duì)著這一實(shí)事，即其中 點(diǎn)的實(shí)驗(yàn)沒(méi)發(fā)揚(yáng)其作用。為此想象在 區(qū)間的兩個(gè)對(duì)稱(chēng)點(diǎn) 分別做實(shí)驗(yàn)。)()(21xfxf),(2xa1x) 1 , 0(xlx,x0)(xfy )(1xf)(2xf0 x1x145 設(shè)保管 區(qū)間，繼續(xù)在 區(qū)間的下面兩個(gè)點(diǎn)x2,(1-

28、x)x 處做實(shí)驗(yàn)，假設(shè)), 0(x), 0(x6)-3-(2 12)(xx那么前一次 的點(diǎn)的實(shí)驗(yàn)，這一次可繼續(xù)運(yùn)用可節(jié)省一次實(shí)驗(yàn)。由(2-3-6)式有x1012 xx618. 0251 x02)618. 0(382. 0618. 010 x1x10.382，0.6180.236，0.3820.146，0.236462.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 這就是所謂的0.618優(yōu)選法。即假設(shè)在 區(qū)間上找單峰極大值時(shí)，可在) 1 , 0(3832. 0618, 01 ,618. 021xx 點(diǎn)做實(shí)驗(yàn)。比如保管區(qū)間 ，由于 ，故只需在 )618. 0 , 0(328. 0)618. 0

29、(2236. 0328. 0618. 0點(diǎn)作一次實(shí)驗(yàn)。472.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 優(yōu)選法中可利用Fibonacci數(shù)列，和0.618法不同之點(diǎn)在于它預(yù)先確定實(shí)驗(yàn)次數(shù)，分兩種情況引見(jiàn)其方法。 (a) 一切能夠?qū)嶒?yàn)數(shù)正好是某個(gè)Fn。102nFnF1nFl這時(shí)兩個(gè)實(shí)驗(yàn)點(diǎn)放在Fn-1和Fn-2兩個(gè)分點(diǎn)上，l假設(shè)Fn-1分點(diǎn)比較好，那么舍去小于Fn-2的部分；l留下的部分共Fn-Fn-2 = Fn-1個(gè)分點(diǎn)，其中第Fn-2和第Fn-3二實(shí)驗(yàn)點(diǎn)，對(duì)應(yīng)的原標(biāo)號(hào)是Fn-2+Fn-2=2Fn-2以及Fn-3+Fn-2=Fn-1,恰好Fn-1點(diǎn)是剛剛留下來(lái)的實(shí)驗(yàn)可以利用。l假設(shè)Fn-

30、2點(diǎn)更好，那么舍去大于Fn-1的部分。l在留下的部分共Fn-1個(gè)分點(diǎn)，下一步Fn-2和Fn-3二實(shí)驗(yàn)點(diǎn)中，恰好Fn-2是剛剛留下來(lái)的實(shí)驗(yàn)可以利用。l可見(jiàn)在Fn個(gè)能夠?qū)嶒?yàn)中，最多用n-1次實(shí)驗(yàn)便可得到所求的極值點(diǎn)。482.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 (b)利用Fibonacci數(shù)列進(jìn)展優(yōu)選不同于 0.618法之點(diǎn),還在于它適宜于參數(shù)只能取整數(shù)數(shù)值的情況.如假設(shè)能夠?qū)嶒?yàn)的數(shù)目比 小,但比 大時(shí),可以虛加幾個(gè)點(diǎn)湊成 個(gè)點(diǎn)，但新添加的點(diǎn)的實(shí)驗(yàn)不用真做，可認(rèn)定比其他點(diǎn)都差的點(diǎn)來(lái)處置。nF1nFnF492.4.42.4.4在選優(yōu)法上的運(yùn)用在選優(yōu)法上的運(yùn)用 定理：測(cè)試定理：測(cè)試n次可將包含單峰極值點(diǎn)的區(qū)間次可將包含單峰極值點(diǎn)的區(qū)間減少到原區(qū)間的減少到原區(qū)間的 ，其中，其中 是恣意小的是恣意小的正整數(shù)，正整數(shù)