資源描述：
《實(shí)用算法(基礎(chǔ)算法-遞推法).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、實(shí)用算法(基礎(chǔ)算法-遞推法-01)????有一類試題，每相鄰兩項(xiàng)數(shù)之間的變化有一定的規(guī)律性，我們可將這種規(guī)律歸納成如下簡(jiǎn)捷的遞推關(guān)系式：???Fn=g(Fn-1)???這就在數(shù)的序列中，建立起后項(xiàng)和前項(xiàng)之間的關(guān)系，然后從初始條件(或最終結(jié)果)入手，一步步地按遞推關(guān)系遞推，直至求出最終結(jié)果(或初始值)。很多程序就是按這樣的方法逐步求解的。如果對(duì)一個(gè)試題，我們要是能找到后一項(xiàng)與前一項(xiàng)的關(guān)系并清楚其起始條件(最終結(jié)果)，問題就好解決，讓計(jì)算機(jī)一步步算就是了，讓高速的計(jì)算機(jī)做這種重復(fù)運(yùn)算，可真正起到“物盡其用”的效果。???遞推分倒推法和順推法兩種形式。一般分析思路：???i
2、f求解條件F1???????thenbegin{倒推}???????????由題意(或遞推關(guān)系)確定最終結(jié)果Fa；???????????求出倒推關(guān)系式Fi-1=g'(Fi);???????????i=n;{從最終結(jié)果Fn出發(fā)進(jìn)行倒推}???????????while當(dāng)前結(jié)果Fi非初始值F1do由Fi-1=g(F1)倒推前項(xiàng)；???????????輸出倒推結(jié)果F1和倒推過程；???????????end{then}???????elsebegin{順推}???????????由題意(或順推關(guān)系)確定初始值F1(邊界條件)；???????????求出順推關(guān)系式F1=g(F
3、i-1);???????????i=1;{由邊界條件F1出發(fā)進(jìn)行順推}???????????while當(dāng)前結(jié)果Fi非最終結(jié)果Fndo由Fi=g(Fi-1)順推后項(xiàng)；???????????輸出順推結(jié)果Fn和順推過程；???????end;{else}一、倒推法???所謂倒推法，就是在不知初始值的情況下，經(jīng)某種遞推關(guān)系而獲知問題的解或目標(biāo)，再倒推過來，推知它的初始條件。因?yàn)檫@類問題的運(yùn)算過程是一一映射的，故可分析得其遞推公式。然后再從這個(gè)解或目標(biāo)出發(fā)，采用倒推手段，一步步地倒推到這個(gè)問題的初始陳述。???下面舉例說明。[例1]貯油點(diǎn)???一輛重型卡車欲穿過1000公里的沙
4、漠，卡車耗油為1升/公里，卡車總載油能力為500公升。顯然卡車一次是過不了沙漠的。因此司機(jī)必須設(shè)法在沿途建立幾個(gè)儲(chǔ)油點(diǎn)，使卡車能順利穿越沙漠，試問司機(jī)如何建立這些儲(chǔ)油點(diǎn)？每一儲(chǔ)油點(diǎn)應(yīng)存多少油，才能使卡車以消耗最少油的代價(jià)通過沙漠？算法分析：???編程計(jì)算及打印建立的貯油點(diǎn)序號(hào)，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量。???????No.???????Distance(k.m.)???????oil(litre)???????1???????????????XX???????????????XX???????2???????????????XX?????????????
5、??XX???????3???????????????XX???????????????XX???????...??????????????.....?????????????......???設(shè)dis[i]??為第i個(gè)貯油點(diǎn)至終點(diǎn)(i=0)的距離；?????oil[i]??為第i個(gè)貯油點(diǎn)的存貯油量；???我們可以用倒推法來解決這個(gè)問題。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)貯油點(diǎn)的位置及存油量。下圖表示倒推時(shí)的返回點(diǎn)：????從貯油點(diǎn)i向貯油點(diǎn)i+1倒推的策略是，卡車在點(diǎn)i和點(diǎn)i+1間往返若干次?？ㄜ嚸看畏祷豬+1處時(shí)正好耗盡500公升汽油，而每次從i+1出發(fā)時(shí)又必須裝足5
6、00公升汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下使i點(diǎn)貯足i*500分升汽油的要求(0<=i<=n-1)。具體地講，第一個(gè)貯油點(diǎn)i=1應(yīng)距終點(diǎn)i=0處500km且在該處貯藏500公升汽油，這樣才能保證卡車能由i=1處到達(dá)終點(diǎn)i=0處，這就是說???dis[1]=500???????oil[1]=500;???為了在i=1處貯藏500公升汽油，卡車至少從i=2處開兩趟滿載油的車至i=1處。所以i=2處至少貯有2*500公升汽油，即oil[2]=500*2=1000。另外，再加上從i=1返回至i=2處的一趟空載，合計(jì)往返3次。三次往返路程的耗油量按最省要求只能為50
7、0公升。即d12=500/3km???????dis[2]=dis[1]+d12=dis[1]+500/3?????為了在i=2處貯存1000公升汽油，卡車至少從i=3處開三趟滿載油的車至i=2處。報(bào)以i=3處至少貯有3*500公升汽油，即oil[3]=500*3=1500。加上i=2至i=3處的二趟返程空車，合計(jì)5次。路途耗油量也應(yīng)為500公升，即d23=500/5,???????dis[3]=dis[2]+d23=dis[2]+500/5;?????依此類推，為了在i=k處貯藏k*500公升汽油，卡車至少從i=k+1處開k趟滿載車至i=k處，即?
