【正文】 { j0,g[i,j]=0 } ? F[i， j]= F[i1， j]+ F[i， j1] { i0,j0,g[i,j]=0 } ? 解決遞推類型問題有三個(gè)重點(diǎn)： ? 一是如何建立正確的遞推關(guān)系式，二是遞推關(guān)系有何性質(zhì)，三是遞推關(guān)系式如何求解。 ? 例題：儲(chǔ)油點(diǎn) ? 一輛卡車欲穿過 1000km的沙漠，卡車耗油為 1L/km，卡車總載油能力為 500L，顯然卡車裝一次油是過不了沙漠的。因此司機(jī)必須設(shè)法在沿途建立幾個(gè)儲(chǔ)油點(diǎn)，使卡車能順利穿越沙漠，試問司機(jī)如何建立這些儲(chǔ)油點(diǎn)？每一儲(chǔ)油點(diǎn)應(yīng)存多少油才能使卡車以消耗最少汽油的代價(jià)通過沙漠（結(jié)果保留小數(shù)點(diǎn)后兩位）？ ? 編程計(jì)算及打印建立的儲(chǔ)油點(diǎn)序號(hào)，個(gè)儲(chǔ)油點(diǎn)距離沙漠邊緣出發(fā)的距離及儲(chǔ)油量。 ? No. distance( km ) oil( L ) ? 1 xxx xxx ? 2 xxx xxx ? 3 xxx xxx ? 分析：先從終點(diǎn)出發(fā)倒推最后一個(gè)儲(chǔ)油點(diǎn)的位置及儲(chǔ)油量，然后再把最后一個(gè)儲(chǔ)油點(diǎn)做為終點(diǎn)，倒推倒數(shù)第二個(gè)儲(chǔ)油點(diǎn)的位置及儲(chǔ)油量， … 。設(shè) dis[i]表示第 i個(gè)儲(chǔ)油點(diǎn)至終點(diǎn)的（ i=0）的距離， oil[i]表示第 i個(gè)儲(chǔ)油點(diǎn)的儲(chǔ)油量。從終點(diǎn)向始點(diǎn)倒推，逐一求出每個(gè)儲(chǔ)油點(diǎn)的位置及儲(chǔ)油量的示意圖如下。 終點(diǎn) 始點(diǎn) i=0 i=1 i=2 i=3 i=n 500 500/3 500/5 ? 從儲(chǔ)油點(diǎn) i向儲(chǔ)油點(diǎn) i+1倒推的策略是，卡車在點(diǎn) i和點(diǎn) i+1間往返若干次。卡車每次返回 i+1處正好耗盡 500L的汽油，而每次從 i+1處出發(fā)時(shí)又必須裝足 500L汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下使 i點(diǎn)儲(chǔ)足 500iL汽油的要求（ 0≤i ≤ n 1）。 ? 第一個(gè)儲(chǔ)油點(diǎn) i=1應(yīng)距離終點(diǎn) i=0處 500km且在該處儲(chǔ)藏 500L汽油，這樣才能保證卡車能由 i=1處到達(dá)終點(diǎn) i=0處。 dis[1]=500。oil[1]=500 ? 為了在 i=1處儲(chǔ)藏 500L汽油，卡車至少?gòu)?i=2處開兩趟滿載油的車至i=1處。所以 i=2處至少儲(chǔ)存了 2 500L汽油，即 oil[2]=500 2=1000另外，再加上從 i=1處返回 i=2處的一趟空載，合計(jì)往返 3次。三次往返路程的耗油量按最省要求只能為 500L，即 d1,2=500/3km ? dis[2]=dis[1]+d1,2=dis[1]+500/3 i=0 i=1 i=2 500 500/3 ? 以此類推，為了在 i=k處儲(chǔ)存 k*500L汽油，卡車至少?gòu)?i=k+1處開 k+1趟滿載車至 i=k處，即 oil[k+1]=(k+1) 500=oil[k]+500，加上從 i=k返回 i=k+1的 k趟返程空車，合計(jì) 2k+1次。這 2k+1次總耗油量按最省要求為 500L，即 dk,k+1=500/(2k+1) km。 ? dis[k+1]=dis[k]+dk,k+1=dis[k]+500/(2k+1) ? 最后， i=n至始點(diǎn)的距離為 1000dis[n]， oil[n]=500*n。為了在 i=n處取得 500*nL汽油，卡車至少?gòu)氖键c(diǎn)開 n+1次滿載車至 i=n，加上從i=n返回始點(diǎn)的 n趟返程空車，合計(jì) 2n+1次， 2n+1趟的總耗油量應(yīng)正好為（ 1000dis[n]） （ 2n+1），即始點(diǎn)藏油為 oil[n]+(1000dis[n]) （ 2n+1） dis[n] 1000－ dis[n] 終點(diǎn) 始點(diǎn) i=0 i=n ? 算法框架： ? k:=1。d:=500。 {從 i=1處開始向始點(diǎn)倒推 } ? dis[1]:=500。oil[1]:=500。 ? repeat ? k:=k+1。 d:=d+500/(2*k1)。 ? dis[k]:=d。 ? oil[k]:=oil[k1]+500。 ? until d=1000。 ? dis[k]:=1000。 {置始點(diǎn)至終點(diǎn)的距離值 } ? d1:=1000dis[k1]。 {求儲(chǔ)油點(diǎn) k處至始點(diǎn)的距離 } ? oil[k]:=d1*(2*k+1)+oil[k1]。 {求始點(diǎn)藏油量 } ? for i:=0 to k do 輸出第 i個(gè)儲(chǔ)油點(diǎn)的距離為 1000dis[ki],儲(chǔ)油量為 oil[ki]。 ? 什么是遞歸？ ? 在遞推中我們由一個(gè)出發(fā)點(diǎn)開始，并且知道未知和已知的關(guān)系我們就可以知道整個(gè)序列的情況，例如：序列的第一個(gè)數(shù)是 2，并且知道該序列的后一項(xiàng)總比前一項(xiàng)大 2，則我們可以推斷出該序列是 … 。 ? 如果用遞推的方法求 1～ 100的累加和，很容易寫出下面的程序： ? Program leijia。 ? Var ? i,s:integer。 ? begin ? s:=0。 ? for i:=1 to 100 do inc(s,i)。 ? writeln(s)。 ? end. ? 我們換著從另一個(gè)角度考慮問題： ? 即求 1～ 100的累加和等于 1～ 99的累加和加上 100，而 1～ 99的累加和等于 1～ 98的累加和加上 99， … ，一般來說用 f(n)表示求 1～ n的累加和，當(dāng) n1時(shí)有： f(n)=n+f(n1) ? 而且我們知道 1的累加和為 1，即 f(1)=1,總結(jié)上面的情況如下： ? f(n)=f(n1)+n n1 ? f(1)=1 n=1 ? 從上面的例子可以看出，要解決一個(gè)較大的問題（ f(100)），可以歸結(jié)為求解一個(gè)較小的問題 (f(99)),而解決較小問題的方法和解決原問題的方法相同但是規(guī)模不斷縮小，當(dāng)問題的規(guī)?？s小到一定程度時(shí)（ n=1）我們知道問題的解（ f(1)=1）。 ? 我們將 f(1)=1這種條件稱為 邊界條件 或者說 遞歸出口 ，它是解決問題的 “ 歸宿 ” ，如果沒有邊界條件遞歸就如同陷入黑洞中永遠(yuǎn)無法得到問題的解?，F(xiàn)在知道 f(1)=1,則 f(2)就知道了解， f(3)… f(100)就得到了解，程序正是在這樣的 “ 原問題 — 邊界條件 — 原問題 ” 的過程中最終解決，而我們只須給出遞歸關(guān)系和邊界條件，過程的實(shí)現(xiàn)由程序設(shè)計(jì)語(yǔ)言自動(dòng)實(shí)現(xiàn)。 ? 例題：用遞歸法求 1—100的累加和。 ? program leijia。 ? var ? n:integer。 ? function f(i:integer):integer。 ? begin ? if i=1 then f:=1 ? else f:=f(i1)+i。 ? end。 ? begin ? readln(n)。 ? writeln(f(n))。 ? end. 觀察程序，如果讀入的數(shù)據(jù)是 0會(huì)怎樣。通過測(cè)試會(huì)發(fā)現(xiàn)，如果讀入數(shù)據(jù)是 0，程序會(huì)報(bào)錯(cuò)退出。這是因?yàn)榘凑丈厦娴某绦驁?zhí)行，f(0)=f(1)+0，要求 f(1)就要求f(2)， … 如此下去 f(i)永遠(yuǎn)無法得到解， “ 遞 ” 的過程一去不復(fù)返，直到耗盡系統(tǒng)分配的空間，怎能“ 歸來 ” 呢。因此，在遞歸程序設(shè)計(jì)中一定要根據(jù)問題的描述選擇合適的遞歸出口。 這種利用遞歸函數(shù)或遞歸方法解決問題的過程稱為遞歸算法。采用遞歸算法來解決時(shí)必須符合三個(gè)條件： 1）可以把一個(gè)問題轉(zhuǎn)化為一個(gè)新問題，而這個(gè)新問題的解決方法仍與原問題的解法相 同；只是所處理的對(duì)象有所不同，但它們只是有規(guī)律的遞增或遞減； 2）可以通過轉(zhuǎn)化過程使問題得到解決； 3）必定要有一個(gè)明確的結(jié)束遞歸的條件，否則遞歸將會(huì)無止境的進(jìn)行下去。 對(duì)于問題的描述或定義本身就是遞歸形式的問題，用遞歸方法可以編寫出非常簡(jiǎn)單、直觀的程序。但是由于遞歸程序在執(zhí)行中需要開辟空間和不斷的調(diào)用返回，這個(gè)過程會(huì)消耗大量的空間和時(shí)間，因此遞歸算法的時(shí)空效率比較差。 ? 例題：利用函數(shù)遞歸調(diào)用求 N!。 ? [問題分析 ]： N!可以用以下遞歸方法表示： N!=n*(n1)! n0 ? N!=1 n=0 ? 從以上表達(dá)式可以看到當(dāng) n0時(shí) n!=n*(n1)!，因此求 n!的問題轉(zhuǎn)化成了求 n*(n1)!的問題，而求（ n1)!的問題與求 n!的解法相同，只是求階乘的對(duì)象的值減去 1。當(dāng) n的值遞減至 0時(shí)， n!=1，從而使遞歸得以結(jié)束。 ? Program jiecheng。 ? var ? n:integer。 ? function fac(x:integer):real。 ? begin ? if x1 ? then fac:=1 ? else fac:=x*fac(x1)。 ? end。 ? begin ? writeln(?input a integer num:?)。 ? readln(n)。 ? writeln(n,?!=?,fac(n))。 ? end. ? 以 fac(4)為例，程序的執(zhí)行過程如下圖所示，其中實(shí)線表示遞歸調(diào)用的過程，虛線表示返回的過程。 fac(4) 4* fac(3) 3* fac(2) 2* fac(1) 1* fac(0) 1 1 2 6 24 邊界條件 ? 例題：利用遞歸調(diào)用技術(shù)求斐波那契數(shù)列的第 N項(xiàng)。斐波那契數(shù)列的前若干項(xiàng)是 1,1,2,3,5,8,13,… 。 ? [問題分析 ]：我們已經(jīng)知道斐波那契數(shù)列的各數(shù)列的產(chǎn)生可用下列公式表示： Ｕ n＝Ｕ n1＋Ｕ n2 n2 ? Ｕ 1＝ 1 Ｕ 2＝１ ? 因此當(dāng) N大于 2時(shí)，求第 N項(xiàng)值可轉(zhuǎn)化為求第 N1項(xiàng)值與第 N2項(xiàng)值的和；而求第 N1項(xiàng)又可轉(zhuǎn)化為求 N2項(xiàng)值與 N3項(xiàng)的和，相應(yīng)地，求 N2項(xiàng)值可轉(zhuǎn)化為求 N3項(xiàng)值和 N4項(xiàng)值的和； …… ；如此反復(fù)，直至轉(zhuǎn)化為求第 1項(xiàng)或第 2項(xiàng)值，而第 1項(xiàng)與第 2項(xiàng)為已知值 1和 2。 ? program fbnq。 ? var ? n:longint。 ? function fac(k:longint):longint。 ? begin ? if k=2 ? then fac:=1 ? else fac:=fac(k1)+fac(k2)。 ? end。 ? begin ? readln(n)。 ? writeln(fac(n))。 ? end. ? 本程序采用了函數(shù)遞歸，函數(shù) F的執(zhí)行比較復(fù)雜。函數(shù) F由于存在著兩次的遞歸調(diào)用，使遞歸調(diào)用產(chǎn)生執(zhí)行流程的 “ 二叉樹 ” 形式，參看示意圖，來理解這個(gè)執(zhí)行過程。為方便起見，設(shè)定 N=5，圖中的數(shù)碼表示遞歸執(zhí)行的順序。 ? 例題：輾轉(zhuǎn)相除法又叫做「歐幾里得算法」，公元前 300 年左右希臘數(shù)學(xué)家歐幾里得在他的著作 《 幾何原本 》 提出。利用這個(gè)方法，可以較快地求出兩個(gè)自然數(shù)的最大公因數(shù)。 ? 我們將兩個(gè)不全為 0的非負(fù)整數(shù) m和 n的最大公約數(shù)記為 gcd(m,n)，代表能夠整除（即余數(shù)為 0） m和 n的最大正整數(shù)。歐幾里得算法基于的方法是重復(fù)應(yīng)用等式 gcd(m,n)=gcd(n,m mod n)，直到 m mod n等于 0。 ? 編寫程序用遞歸的方法求兩個(gè)數(shù) m和 n的最大公約數(shù)（ m0,n0）。 ? [問題分析 ]：由上面的說明總結(jié)出遞歸公式 ? gcd(n,m mod n) m mod n0 ? n m mod n=0 ? program gjl。 ? var m,n,g:integer。 ? function gcd(m,n:integer):integer。 ? var r:integer。 ? begin ? r:=m mod n。 ? if r=0 then gcd:=n else gcd:=gcd(n,r)。 ? end。 ? begin ? readln(m,n)。 ? g:=gcd(m,n)。 ? writeln(39。m=39。,m,39。n=39。,n,39。gcd=39。,g)。 ? end. ? 例題：郵票問題 ? 設(shè)有已知面額的郵票 m種，每種有 n張。問：用總數(shù)不超過 n張的郵票進(jìn)行組合，能組合的郵票面額中可以連續(xù)出現(xiàn)面額數(shù)最多有多少