第二講--遞推算法.ppt

引例.Fibonacci數(shù)列,Fibonacci數(shù)列的代表問題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖問題”(又稱“Fibonacci問題”)。問題：一個數(shù)列的第0項為0，第1項為1，以后每一項都是前兩項的和，這個數(shù)列就是著名的裴波那契數(shù)列，求裴波那契數(shù)列的第N項。,由問題,可寫出遞推方程,解答,算法：F0:=1;F1:=2;FORi:=2TONDOFi:=Fi1+Fi2;,總結(jié),從這個問題可以看出，在計算裴波那契數(shù)列的每一項目時，都可以由前兩項推出。這樣，相鄰兩項之間的變化有一定的規(guī)律性，我們可以將這種規(guī)律歸納成如下簡捷的遞推關(guān)系式：Fn=g(Fn-1)，這就在數(shù)的序列中，建立起后項和前項之間的關(guān)系。然后從初始條件（或是最終結(jié)果）入手，按遞推關(guān)系式遞推，直至求出最終結(jié)果（或初始值）。很多問題就是這樣逐步求解的。對一個試題，我們要是能找到后一項與前一項的關(guān)系并清楚其起始條件（或最終結(jié)果），問題就可以遞推了，接下來便是讓計算機一步步了。讓高速的計算機從事這種重復(fù)運算，真正起到“物盡其用”的效果。,遞推概念,給定一個數(shù)的序列H0,H1,Hn,若存在整數(shù)n0，使當nn0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hn(0=1,z=x輸入：x,y,z的數(shù)值輸出：成蟲對數(shù)示例：輸入：x=1y=2z=8輸出：37,分析,首先我們來看樣例：每隔1個月產(chǎn)2對卵，求過8月（即第8+1=9月）的成蟲個數(shù),分析,設(shè)數(shù)組Ai表示第i月新增的成蟲個數(shù)。由于新成蟲每過x個月產(chǎn)y對卵，則可對每個Ai作如下操作:Ai+k*x+2:=Ai+k*x+2+Ai*y(1=2)個盤子時，總是先借助c柱把上面的n-1個盤子移動到b柱上，然后把a柱最下面的盤子移動到c柱上；再借助a柱把b柱上的n-1個盤子移動到c柱上；總共移動hn-1+1+hn-1個盤次。hn=2hn-1+1邊界條件：h1=1,例3:平面分割問題,設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點，且任何三條封閉曲線不相交于同一點，問這些封閉曲線把平面分割成的區(qū)域個數(shù)。,分析,設(shè)an為n條封閉曲線把平面分割成的區(qū)域個數(shù)。由圖2可以看出：a2-a1=2；a3-a2=4；a4-a3=6。從這些式子中可以看出an-an-1=2(n-1)。當然，上面的式子只是我們通過觀察4幅圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來試著證明一下。當平面上已有n-1條曲線將平面分割成an-1個區(qū)域后，第n-1條曲線每與曲線相交一次，就會增加一個區(qū)域，因為平面上已有了n-1條封閉曲線，且第n條曲線與已有的每一條閉曲線恰好相交于兩點，且不會與任兩條曲線交于同一點，故平面上一共增加2(n-1)個區(qū)域，加上已有的an-1個區(qū)域，一共有an-1+2(n-1)個區(qū)域。所以本題的遞推關(guān)系是an=an-1+2(n-1)邊界條件是a1=2。,例4：楊輝三角,分析,組合公式的證明：,例5：Catalan數(shù),在一個凸n邊形中，通過不相交于n邊形內(nèi)部的對角線，把n邊形拆分成若干三角形，不同的拆分數(shù)目用hn表示，hn即為Catalan數(shù)。例如五邊形有如下五種拆分方案，故h5=5。求對于一個任意的凸n邊形相應(yīng)的hn。,分析,設(shè)Cn表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個凸n邊形的任意一條邊都必然是一個三角形的一條邊，邊P1Pn也不例外，再根據(jù)“不在同一直線上的三點可以確定一個三角形”，只要在P2，P3，Pn-1點中找一個點Pk(1kn)，與P1、Pn共同構(gòu)成一個三角形的三個頂點，就將n邊形分成了三個不相交的部分(如圖)，我們分別稱之為區(qū)域、區(qū)域、區(qū)域，其中區(qū)域必定是一個三角形，區(qū)域是一個凸k邊形，區(qū)域是一個凸n-k+1邊形，區(qū)域的拆分方案總數(shù)是Ck，區(qū)域的拆分方案數(shù)為Cn-k+1，故包含P1PkPn的n邊形的拆分方案數(shù)為CkCn-k+1種，而Pk可以是P2，P3，Pn-1種任一點，根據(jù)加法原理，凸n邊形的三角拆分方案總數(shù)為:,邊界條件C2=1。,例6：貯油點,一輛重型卡車欲穿過1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過不了沙漠的。因此司機必須設(shè)法在沿途建立若干個貯油點，使卡車能順利穿過沙漠。試問司機如怎樣建立這些貯油點？每一貯油點應(yīng)存儲多少汽油，才能使卡車以消耗最少汽油的代價通過沙漠？編程計算及打印建立的貯油點序號，各貯油點距沙漠邊沿出發(fā)的距離以及存油量。格式如下：No.Distance(k.m.)Oil(litre)12,分析,設(shè)Wayi第i個貯油點到終點（i=0）的距離；oili第i個貯油點的貯油量；我們可以用倒推法來解決這個問題。從終點向始點倒推，逐一求出每個貯油點的位置及存油量。從貯油點i向貯油點i+1倒推的方法是：卡車在貯油點i和貯油點i+1間往返若干次?？ㄜ嚸看畏祷豬+1點時應(yīng)該正好耗盡500公升汽油，而每次從i+1點出發(fā)時又必須裝足500公升汽油。兩點之間的距離必須滿足在耗油最少的條件下，使i點貯足i*500公升汽油的要求（0in-1）。,倒推第一步,第一個貯油點i=1應(yīng)距終點i=0處500km，且在該點貯藏500公升汽油，這樣才能保證卡車能由i=1處到達終點i=0處，這就是說Way1=500；oil1=500；,倒推第二步,為了在i=1處貯藏500公升汽油，卡車至少從I=2處開兩趟滿載油的車至i=1處，所以i=2處至少貯有2*500公升汽油，即oil2=500*2=1000；另外，再加上從i=1返回至i=2處的一趟空載，合計往返3次。三次往返路程的耗油量按最省要求只能為500公升，即d1,2=500/3km，Way2=Way1+d1,2=Way1+500/3,倒推第三步,為了在I=2處貯藏1000公升汽油，卡車至少從I=3處開三趟滿載油的車至I=2處。所以I=3處至少貯有3*500公升汽油，即oil3=500*3=1500。加上I=2至I=3處的二趟返程空車，合計5次。路途耗油亦應(yīng)500公升，即d23=500/5，Way3=Way2+d2,3=Way2+500/5；,倒推第k步,為了在i=k處貯藏k*500公升汽油，卡車至少從i=k+1處開k趟滿載車至i=k處，即oilk+1=(k+1)*500=oilk+500，加上從i=k返回i=k+1的k-1趟返程空間，合計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至始點的距離為1000-Wayn,oiln=500*n。為了在i=n處取得n*500公升汽油，卡車至少從始點開n+1次滿載車至I=n，加上從I=n返回始點的n趟返程空車，合計2n+1次，2n+1趟的總耗油量應(yīng)正好為（1000-Wayn）*(2n+1)