第二講--遞推算法課件

1、引例引例.Fibonacci數(shù)列數(shù)列 Fibonacci數(shù)列的代表問(wèn)題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問(wèn)題”(又稱(chēng)“Fibonacci問(wèn)題”)。 問(wèn)題：一個(gè)數(shù)列的第0項(xiàng)為0，第1項(xiàng)為1，以后每一項(xiàng)都是前兩項(xiàng)的和，這個(gè)數(shù)列就是著名的裴波那契數(shù)列，求裴波那契數(shù)列的第N項(xiàng)。 由問(wèn)題,可寫(xiě)出遞推方程解答2120121nffnnfnnn算法：F0 := 1; F1 := 2;FOR i := 2 TO N DO Fi := Fi 1 + Fi 2;總結(jié) 從這個(gè)問(wèn)題可以看出，在計(jì)算裴波那契數(shù)列的每一項(xiàng)目時(shí)，都可以由前兩項(xiàng)推出。這樣，相鄰兩項(xiàng)之間的變化有一定的規(guī)律性，我們可

2、以將這種規(guī)律歸納成如下簡(jiǎn)捷的遞推關(guān)系式：Fn=g(Fn-1)，這就在數(shù)的序列中，建立起后項(xiàng)和前項(xiàng)之間的關(guān)系。然后從初始條件（或是最終結(jié)果）入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果（或初始值）。很多問(wèn)題就是這樣逐步求解的。 對(duì)一個(gè)試題，我們要是能找到后一項(xiàng)與前一項(xiàng)的關(guān)系并清楚其起始條件（或最終結(jié)果），問(wèn)題就可以遞推了，接下來(lái)便是讓計(jì)算機(jī)一步步了。讓高速的計(jì)算機(jī)從事這種重復(fù)運(yùn)算，真正起到“物盡其用”的效果。遞推概念 給定一個(gè)數(shù)的序列給定一個(gè)數(shù)的序列H0,H1,Hn,若存在若存在整數(shù)整數(shù)n0，使當(dāng)，使當(dāng)nn0時(shí)時(shí),可以用等號(hào)可以用等號(hào)(或大于號(hào)、或大于號(hào)、小于號(hào)小于號(hào))將將Hn與其前面的某些項(xiàng)與其前

3、面的某些項(xiàng)Hn(0i=1,y=1,z=x 輸入：x,y,z的數(shù)值 輸出：成蟲(chóng)對(duì)數(shù) 示例：輸入：x=1 y=2 z=8輸出：37分析 首先我們來(lái)看樣例：每隔1個(gè)月產(chǎn)2對(duì)卵，求過(guò)8月（即第8+1=9月）的成蟲(chóng)個(gè)數(shù)月份123456789新增卵 0222610142646成蟲(chóng)111357132337分析 設(shè)數(shù)組Ai表示第i月新增的成蟲(chóng)個(gè)數(shù)。 由于新成蟲(chóng)每過(guò)x個(gè)月產(chǎn)y對(duì)卵，則可對(duì)每個(gè)Ai作如下操作: Ai+k*x+2:=Ai+k*x+2+Ai*y (1=k,i+k*x+2z+1 end; begin readln(x,y,z); a1:=1;初始化 for i:=1 to z do add(i);對(duì)每個(gè)

4、AI進(jìn)行遞推 ans:=0; for i:=1 to z+1 do ans:=ans+ai;累加總和 writeln(ans); end.例例2 : Hanoi塔問(wèn)題塔問(wèn)題 Hanoi塔由n個(gè)大小不同的圓盤(pán)和三根木柱a,b,c組成。開(kāi)始時(shí)，這n個(gè)圓盤(pán)由大到小依次套在a柱上，如圖1所示。要求把a(bǔ)柱上n個(gè)圓盤(pán)按下述規(guī)則移到c柱上：(1)一次只能移一個(gè)圓盤(pán)；(2)圓盤(pán)只能在三個(gè)柱上存放；(3)在移動(dòng)過(guò)程中，不允許大盤(pán)壓小盤(pán)。 問(wèn)將這n個(gè)盤(pán)子從a柱移動(dòng)到c柱上，總計(jì)需要移動(dòng)多少個(gè)盤(pán)次？ a b c 圖1分析 設(shè)hn為n 個(gè)盤(pán)子從a柱移到c柱所需移動(dòng)的盤(pán)次。顯然，當(dāng)n=1時(shí)，只需把a(bǔ) 柱上的盤(pán)子直接移動(dòng)

5、到c柱就可以了，故h1=1。當(dāng)n=2時(shí)，先將a柱上面的小盤(pán)子移動(dòng)到b柱上去；然后將大盤(pán)子從a柱移到c 柱；最后，將b柱上的小盤(pán)子移到c柱上，共記3個(gè)盤(pán)次，故h2=3。以此類(lèi)推，當(dāng)a柱上有n(n=2)個(gè)盤(pán)子時(shí)，總是先借助c柱把上面的n-1個(gè)盤(pán)子移動(dòng)到b柱上，然后把a(bǔ)柱最下面的盤(pán)子移動(dòng)到c柱上；再借助a柱把b柱上的n-1個(gè)盤(pán)子移動(dòng)到c柱上；總共移動(dòng)hn-1+1+hn-1個(gè)盤(pán)次。 hn=2hn-1+1 邊界條件：h1=1例例3 :平面分割問(wèn)題平面分割問(wèn)題 設(shè)有n條封閉曲線(xiàn)畫(huà)在平面上，而任何兩條封閉曲線(xiàn)恰好相交于兩點(diǎn)，且任何三條封閉曲線(xiàn)不相交于同一點(diǎn)，問(wèn)這些封閉曲線(xiàn)把平面分割成的區(qū)域個(gè)數(shù)。分析 設(shè)an

6、為n條封閉曲線(xiàn)把平面分割成的區(qū)域個(gè)數(shù)。 由圖2可以看出：a2-a1=2；a3-a2=4；a4-a3=6。從這些式子中可以看出an-an-1=2(n-1)。當(dāng)然，上面的式子只是我們通過(guò)觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來(lái)試著證明一下。當(dāng)平面上已有n-1條曲線(xiàn)將平面分割成an-1個(gè)區(qū)域后，第n-1條曲線(xiàn)每與曲線(xiàn)相交一次，就會(huì)增加一個(gè)區(qū)域，因?yàn)槠矫嫔弦延辛薾-1條封閉曲線(xiàn)，且第n條曲線(xiàn)與已有的每一條閉曲線(xiàn)恰好相交于兩點(diǎn)，且不會(huì)與任兩條曲線(xiàn)交于同一點(diǎn)，故平面上一共增加2(n-1)個(gè)區(qū)域，加上已有的an-1個(gè)區(qū)域，一共有an-1 + 2(n-1)個(gè)區(qū)域。所以本題的遞推關(guān)系是 a

7、n=an-1+2(n-1) 邊界條件是a1=2。例例4：楊輝三角 分析組合公式的證明：CCCrnrnrn111)!()!1() 1()!1( !)!1(111rnrnrnrnCCrnrn！CCCrnrnrnrnrnrnrrnrnn)!( !)!( !)!1()() 1(111！例例5：Catalan數(shù)數(shù) 在一個(gè)凸n邊形中，通過(guò)不相交于n邊形內(nèi)部的對(duì)角線(xiàn)，把n邊形拆分成若干三角形，不同的拆分?jǐn)?shù)目用hn表示，hn即為Catalan數(shù)。例如五邊形有如下五種拆分方案，故h5=5。求對(duì)于一個(gè)任意的凸n邊形相應(yīng)的hn。分析設(shè)Cn表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個(gè)凸n邊形的任意一條邊都必然是

8、一個(gè)三角形的一條邊，邊P1 Pn也不例外，再根據(jù)“不在同一直線(xiàn)上的三點(diǎn)可以確定一個(gè)三角形”，只要在P2，P3，Pn-1點(diǎn)中找一個(gè)點(diǎn)Pk(1kn)，與P1、Pn 共同構(gòu)成一個(gè)三角形的三個(gè)頂點(diǎn)，就將n邊形分成了三個(gè)不相交的部分(如圖)，我們分別稱(chēng)之為區(qū)域、區(qū)域、區(qū)域，其中區(qū)域必定是一個(gè)三角形，區(qū)域是一個(gè)凸k邊形，區(qū)域是一個(gè)凸n-k+1邊形，區(qū)域的拆分方案總數(shù)是Ck，區(qū)域的拆分方案數(shù)為Cn - k + 1，故包含P1PkPn的n 邊形的拆分方案數(shù)為CkCn-k+1種，而Pk可以是P2，P3，Pn-1種任一點(diǎn)，根據(jù)加法原理，凸n邊形的三角拆分方案總數(shù)為:112inniiCC邊界條件C2=1。例例6：貯

9、油點(diǎn) 一輛重型卡車(chē)欲穿過(guò)1000公里的沙漠，卡車(chē)耗汽油為1升/公里，卡車(chē)總載油能力為500公升。顯然卡車(chē)裝一次油是過(guò)不了沙漠的。因此司機(jī)必須設(shè)法在沿途建立若干個(gè)貯油點(diǎn)，使卡車(chē)能順利穿過(guò)沙漠。試問(wèn)司機(jī)如怎樣建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存儲(chǔ)多少汽油，才能使卡車(chē)以消耗最少汽油的代價(jià)通過(guò)沙漠？ 編程計(jì)算及打印建立的貯油點(diǎn)序號(hào)，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量。格式如下：No. Distance(k.m.) Oil(litre)1 2 分析 設(shè)Wayi第i個(gè)貯油點(diǎn)到終點(diǎn)（i=0）的距離； oili第i個(gè)貯油點(diǎn)的貯油量； 我們可以用倒推法來(lái)解決這個(gè)問(wèn)題。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)貯油點(diǎn)的位置及存

10、油量。 從貯油點(diǎn)i向貯油點(diǎn)i+1倒推的方法是：卡車(chē)在貯油點(diǎn)i和貯油點(diǎn)i+1間往返若干次?？ㄜ?chē)每次返回i+1點(diǎn)時(shí)應(yīng)該正好耗盡500公升汽油，而每次從i+1點(diǎn)出發(fā)時(shí)又必須裝足500公升汽油。兩點(diǎn)之間的距離必須滿(mǎn)足在耗油最少的條件下，使i點(diǎn)貯足i*500公升汽油的要求（0in-1）。倒推第一步 第一個(gè)貯油點(diǎn)i=1應(yīng)距終點(diǎn)i=0處500km，且在該點(diǎn)貯藏500公升汽油，這樣才能保證卡車(chē)能由i=1處到達(dá)終點(diǎn)i=0處，這就是說(shuō) Way1=500；oil1=500； 倒推第二步為了在i=1處貯藏500公升汽油，卡車(chē)至少?gòu)腎=2處開(kāi)兩趟滿(mǎn)載油的車(chē)至i=1處，所以i=2處至少貯有2*500公升汽油，即oil2=

11、500*2=1000；另外，再加上從i=1返回至i=2處的一趟空載，合計(jì)往返3次。三次往返路程的耗油量按最省要求只能為500公升，即d1,2=500/3km，Way2=Way1+d1,2=Way1+500/3倒推第三步 為了在I=2處貯藏1000公升汽油，卡車(chē)至少?gòu)腎=3處開(kāi)三趟滿(mǎn)載油的車(chē)至I=2處。所以I=3處至少貯有3*500公升汽油，即oil3=500*3=1500。加上I=2至I=3處的二趟返程空車(chē)，合計(jì)5次。路途耗油亦應(yīng)500公升，即d23=500/5， Way3=Way2+d2,3=Way2+500/5；倒推第k步 為了在i=k處貯藏k*500公升汽油，卡車(chē)至少?gòu)膇=k+1處開(kāi)k趟

12、滿(mǎn)載車(chē)至i=k處，即oilk+1=(k+1)*500=oilk+500，加上從i=k返回i=k+1的k-1趟返程空間，合計(jì)2k-1次。這2k-1次總耗油量按最省要求為500公升，即dk,k+1=500/(2k-1) Wayk+1=Wayk+dk,k+1=Wayk+500/(2k-1)；i=n的情形 i=n至始點(diǎn)的距離為1000-Wayn,oiln=500*n。為了在i=n處取得n*500公升汽油，卡車(chē)至少?gòu)氖键c(diǎn)開(kāi)n+1次滿(mǎn)載車(chē)至I=n，加上從I=n返回始點(diǎn)的n趟返程空車(chē)，合計(jì)2n+1次，2n+1趟的總耗油量應(yīng)正好為（1000-Wayn）*(2n+1)，即始點(diǎn)藏油為oiln+(1000-Wayn)*(2n+1)。精品課件精品課件！精品課件精品課件！動(dòng)態(tài)規(guī)劃與遞推的關(guān)系遞推的關(guān)系 上題實(shí)質(zhì)上是