2、的一般步驟建立遞推關(guān)系式確定邊界條件遞推求解遞推的形式順推法和倒推法例題分析-正推例：有2*n的長(zhǎng)方形方格，用n個(gè)1*2的骨牌鋪滿方格。編寫一個(gè)程序，試對(duì)給出的任意一個(gè)n（n＞0），輸出鋪法總數(shù)。①當(dāng)n=1時(shí)，只能是一種鋪法，鋪法總數(shù)表示為x1=1。②當(dāng)n=2時(shí)，骨牌可以兩個(gè)并列豎排，也可以并列橫排，再無(wú)其他方法，上圖所示，因此，鋪法總數(shù)表示為x2=2。n=2n=3由此可以看出，當(dāng)n=3時(shí)的排列骨牌的方法數(shù)是n=1和n=2時(shí)的排列方法數(shù)之和。推出一般規(guī)律：xn=xn-1+xn-2（n＞2）x1=1x2=2其中xn=xn-1+xn-2就是遞推公式。如當(dāng)n=4時(shí)：x3=x2
3、+x1=3x4=x3+x2=5例題分析—逆推例題：貯油點(diǎn)。一輛重型卡車欲穿過(guò)1000公里的沙漠，卡車耗汽油為1升/公里，卡車總載油能力為500公升。顯然卡車裝一次油是過(guò)不了沙漠的。因此司機(jī)必須設(shè)法在沿途建立若干個(gè)貯油點(diǎn)，使卡車能順利穿過(guò)沙漠。試問(wèn)司機(jī)如怎樣建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存儲(chǔ)多少汽油，才能使卡車以消耗最少汽油的代價(jià)通過(guò)沙漠？編程計(jì)算及打印建立的貯油點(diǎn)序號(hào)，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量。格式如下：No.Distance(k.m.)Oil(litre)1××××2××××……………分析設(shè)Way[i]——第i個(gè)貯油點(diǎn)到終點(diǎn)（i=0）的距離；oil[i]—
4、—第i個(gè)貯油點(diǎn)的貯油量；我們可以用倒推法來(lái)解決這個(gè)問(wèn)題。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)貯油點(diǎn)的位置及存油量。從貯油點(diǎn)i向貯油點(diǎn)i+1倒推的方法是：卡車在貯油點(diǎn)i和貯油點(diǎn)i+1間往返若干次。卡車每次返回i+1點(diǎn)時(shí)應(yīng)該正好耗盡500公升汽油，而每次從i+1點(diǎn)出發(fā)時(shí)又必須裝足500公升汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下，使i點(diǎn)貯足i*500公升汽油的要求（0≦i≦n-1）。倒推第一步第一個(gè)貯油點(diǎn)i=1應(yīng)距終點(diǎn)i=0處500km，且在該點(diǎn)貯藏500公升汽油，這樣才能保證卡車能由i=1處到達(dá)終點(diǎn)i=0處，這就是說(shuō)Way[1]=500；oil[1]=500；倒推第二步為
5、了在i=1處貯藏500公升汽油，卡車至少?gòu)腎=2處開(kāi)兩趟滿載油的車至i=1處，所以i=2處至少貯有2*500公升汽油，即oil[2]=500*2=1000；另外，再加上從i=1返回至i=2處的一趟空載，合計(jì)往返3次。三次往返路程的耗油量按最省要求只能為500公升，即d1,2=500/3km，Way[2]=Way[1]+d1,2=Way[1]+500/3倒推第三步為了在I=2處貯藏1000公升汽油，卡車至少?gòu)腎=3處開(kāi)三趟滿載油的車至I=2處。所以I=3處至少貯有3*500公升汽油，即oil[3]=500*3=1500。加上I=2至I=3處的二趟返程空車，合計(jì)5次。路途耗
6、油亦應(yīng)500公升，即d23=500/5，Way[3]=Way[2]+d2,3=Way[2]+500/5；倒推第k步……為了在i=k處貯藏k*500公升汽油，卡車至少?gòu)膇=k+1處開(kāi)k趟滿載車至i=k處，即oil[k+1]=(k+1)*500=oil[k]+500，加上從i=k返回i=k+1的k-1趟返程空間，合計(jì)2k-1次。這2k-1次總耗油量按最省要求為500公升，即dk,k+1=500/(2k-1)Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1)；i=n的情形i=n至始點(diǎn)的距離為1000-Way[n],oil[n]=500*n。為了在
7、i=n處取得n*500公升汽油，卡車至少?gòu)氖键c(diǎn)開(kāi)n+1次滿載車至I=n，加上從I=n返回始點(diǎn)的n趟返程空車，合計(jì)2n+1次，2n+1趟的總耗油量應(yīng)正好為（1000-Way[n]）*(2n+1)，即始點(diǎn)藏油為oil[n]+(1000-Way[n])*(2n+1)。遞推算法特點(diǎn)：1、一個(gè)問(wèn)題的求解需要一系列的計(jì)算，在已知條件和所求問(wèn)題之間總存在著某種互相聯(lián)系的關(guān)系。2、在計(jì)算時(shí)，如果可以找到前后過(guò)程之間的數(shù)量關(guān)系,即遞推式。3、而從已知條件推導(dǎo)出問(wèn)題解的方法叫順推，從問(wèn)題出發(fā)逐步推到已知條件的方法叫逆推。
