信息學(xué)奧賽基礎(chǔ)算法教案

第頁(yè)基礎(chǔ)算法教案目錄TOC\o"1-1"\h\z\u第一課算法簡(jiǎn)介 1第二課多精度數(shù)值處理 1第三課排列與組合 6第四課枚舉法 9第五課遞歸與回溯法 25第六課遞推法 42第七課貪心法 50第八課分治法 64第九課模擬法 70習(xí)題 79第一課算法簡(jiǎn)介算法是一組（有限個(gè)）規(guī)則，它為某個(gè)特定問(wèn)題供應(yīng)了解決問(wèn)題的運(yùn)算序列。在信息學(xué)競(jìng)賽中，就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中，無(wú)論是形成解題思路還是編寫(xiě)算法，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。計(jì)算機(jī)解題的核心是算法設(shè)計(jì)。一個(gè)算法應(yīng)當(dāng)具有以下五個(gè)重要特征：有窮性：一個(gè)算法必需能在執(zhí)行有限步之后結(jié)束；準(zhǔn)確性：算法的每一步驟必需準(zhǔn)確定義；輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，以描述運(yùn)算對(duì)象的初始狀況。所謂0個(gè)輸入是指算法本身給出了初始條件；輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)處理后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的；可行性：算法原則上能夠精確的運(yùn)行，而且其運(yùn)算規(guī)模是可以承受的。為了獲得一個(gè)既有效又優(yōu)美的算法，必需首先了解一些基本的常用算法設(shè)計(jì)思路。下面，我們就對(duì)構(gòu)成算法所依據(jù)的一些基本方法綻開(kāi)探討，如遞推法，遞歸法，枚舉法，分治法，模擬法，貪心法等。第二課多精度數(shù)值處理課題：多精度數(shù)值的處理目標(biāo)：知識(shí)目標(biāo)：多精度值的加,減,乘,除實(shí)力目標(biāo)：多精度值的處理，優(yōu)化！重點(diǎn)：多精度的加,減,乘難點(diǎn)：進(jìn)位及借位處理板書(shū)示意：輸入兩個(gè)正整數(shù)，求它們的和輸入兩個(gè)正整數(shù)，求它們的差輸入兩個(gè)正整數(shù)，求它們的積輸入兩個(gè)正整數(shù)，求它們的商授課過(guò)程：所謂多精度值處理，就是在對(duì)給定的數(shù)據(jù)范圍，用語(yǔ)言本身供應(yīng)的數(shù)據(jù)類(lèi)型無(wú)法直接進(jìn)行處理（主要指加減乘除運(yùn)算），而須要采納特殊的處理方法進(jìn)行。看看下面的例子。例1從鍵盤(pán)讀入兩個(gè)正整數(shù)，求它們的和。分析：從鍵盤(pán)讀入兩個(gè)數(shù)到兩個(gè)變量中，然后用賦值語(yǔ)句求它們的和，輸出。但是，我們知道，在pascal語(yǔ)言中任何數(shù)據(jù)類(lèi)型都有肯定的表示范圍。而當(dāng)兩個(gè)被加數(shù)據(jù)大時(shí)，上述算法明顯不能求出精確解，因此我們須要尋求另外一種方法。在讀小學(xué)時(shí)，我們做加法都采納豎式方法，如圖1。這樣，我們便利寫(xiě)出兩個(gè)整數(shù)相加的算法。856+2551111圖1A3856+2551111圖1A3A2A1+B3B2B1C4C3C2C1圖2A[1]=6,A[2]=5,A[3]=8,B[1]=5,B[2]=5,B[3]=2,C[4]=1,C[3]=1,C[2]=1,C[1]=1,兩數(shù)相加如圖2所示。由上圖可以看出：C[i]:=A[i]+B[i];ifC[i]>10thenbeginC[i]:=C[i]mod10;C[i+1]:=C[i+1]+1end;因此，算法描述如下：procedureadd(a,b;varc);{a,b,c都為數(shù)組，a存儲(chǔ)被加數(shù)，b存儲(chǔ)加數(shù)，c存儲(chǔ)結(jié)果}vari,x:integer;begini:=1while(i<=a數(shù)組長(zhǎng)度>0)or(i<=b數(shù)組的長(zhǎng)度)dobeginx:=a[i]+b[i]+xdiv10;{第i位相加并加上次的進(jìn)位}c[i]:=xmod10;{存儲(chǔ)第i位的值}i:=i+1{位置指針變量}endend;通常，讀入的兩個(gè)整數(shù)用可用字符串來(lái)存儲(chǔ)，程序設(shè)計(jì)如下：programexam1;constmax=200;vara,b,c:array[1..max]of0..9;n:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputaugend:');readln(n);lena:=length(n);{加數(shù)放入a數(shù)組}fori:=1tolenadoa[lena-i+1]:=ord(n[i])-ord('0');write('Inputaddend:');readln(n);lenb:=length(n);{被加數(shù)放入b數(shù)組}fori:=1tolenbdob[lenb-i+1]:=ord(n[i])-ord('0');i:=1;while(i<=lena)or(i<=lenb)dobeginx:=a[i]+b[i]+xdiv10;{兩數(shù)相加，然后加前次進(jìn)位}c[i]:=xmod10;{保存第i位的值}i:=i+1end;ifx>=10then{處理最高進(jìn)位}beginlenc:=i;c[i]:=1endelselenc:=i-1;fori:=lencdownto1dowrite(c[i]);{輸出結(jié)果}writelnend.例2高精度減法。從鍵盤(pán)讀入兩個(gè)正整數(shù)，求它們的差。 分析：類(lèi)似加法，可以用豎式求減法。在做減法運(yùn)算時(shí)，須要留意的是：被減數(shù)必需比減數(shù)大，同時(shí)須要處理借位。因此，可以寫(xiě)出如下關(guān)系式ifa[i]<b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10endc[i]:=a[i]-b[i]類(lèi)似，高精度減法的參考程序：programexam2;constmax=200;vara,b,c:array[1..max]of0..9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputminuend:');readln(n1);write('Inputsubtrahend:');readln(n2);{處理被減數(shù)和減數(shù)}if(length(n1)<length(n2))or(length(n1)=length(n2))and(n1<n2)thenbeginn:=n1;n1:=n2;n2:=n;write('-'){n1<n2,結(jié)果為負(fù)數(shù)}end;lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');i:=1;while(i<=lena)or(i<=lenb)dobeginx:=a[i]-b[i]+10+x;{不考慮大小問(wèn)題，先往高位借10}c[i]:=xmod10;{保存第i位的值}x:=xdiv10-1;{將高位借掉的1減去}i:=i+1end;lenc:=i;while(c[lenc]=0)and(lenc>1)dodec(lenc);{最高位的0不輸出}fori:=lencdownto1dowrite(c[i]);writelnend.例3高精度乘法。從鍵盤(pán)讀入兩個(gè)正整數(shù)，求它們的積。 分析：類(lèi)似加法，可以用豎式求乘法。在做乘法運(yùn)算時(shí)，同樣也有進(jìn)位，同時(shí)對(duì)每一位進(jìn)乘法運(yùn)算時(shí)，必需進(jìn)行錯(cuò)位相加，如圖3,圖4。856×25856×254280171221400圖3A3A2A1×B3B2B1C’4C’3C’2C’1C”5C”4C”3C”2C6C5C4C3C2C1圖4Ci=C’i+C”i+…由此可見(jiàn)，Ci跟A[i]*B[j]乘積有關(guān)，跟上次的進(jìn)位有關(guān)，還跟原Ci的值有關(guān)，分析下標(biāo)規(guī)律，有x:=A[i]*B[j]+xDIV10+C[i+j-1];C[i+j-1]:=xmod10;類(lèi)似，高精度乘法的參考程序：programexam3;constmax=200;vara,b,c:array[1..max]of0..9;n1,n2:string;lena,lenb,lenc,i,j,x:integer;beginwrite('Inputmultiplier:');readln(n1);write('Inputmultiplicand:');readln(n2);lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');fori:=1tolenadobeginx:=0; forj:=1tolenbdobegin{對(duì)乘數(shù)的每一位進(jìn)行處理}x:=a[i]*b[j]+xdiv10+c[i+j-1];{當(dāng)前乘積+上次乘積進(jìn)位+原數(shù)}c[i+j-1]:=xmod10;end;c[i+j]:=xdiv10;{進(jìn)位}end;lenc:=i+j;while(c[lenc]=0)and(lenc>1)dodec(lenc);fori:=lencdownto1dowrite(c[i]);writelnend.例４高精度除法。從鍵盤(pán)讀入兩個(gè)正整數(shù)，求它們的商（做整除）。 分析：做除法時(shí)，每一次上商的值都在０～９，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，接著做除法。因此，在做高精度除法時(shí)，要涉及到乘法運(yùn)算和減法運(yùn)算，還有移位處理。當(dāng)然，為了程序簡(jiǎn)潔，可以避開(kāi)高精度乘法，用0～9次循環(huán)減法取代得到商的值。這里，我們探討一下高精度數(shù)除以單精度數(shù)的結(jié)果，實(shí)行的方法是按位相除法。 參考程序： programexam4;constmax=200;vara,c:array[1..max]of0..9;x,b:longint;n1,n2:string;lena:integer;code,i,j:integer;beginwrite('Inputdividend:');readln(n1);write('Inputdivisor:');readln(n2);lena:=length(n1);fori:=1tolenadoa[i]:=ord(n1[i])-ord('0');val(n2,b,code); {按位相除}x:=0;fori:=1tolenadobeginc[i]:=(x*10+a[i])divb;x:=(x*10+a[i])modb;end; {顯示商}j:=1;while(c[j]=0)and(j<lena)doinc(j);{去除高位的0}fori:=jtolenadowrite(c[i]);writelnend.實(shí)質(zhì)上，在做兩個(gè)高精度運(yùn)算時(shí)候，存儲(chǔ)高精度數(shù)的數(shù)組元素可以不僅僅只保留一個(gè)數(shù)字，而實(shí)行保留多位數(shù)（例如一個(gè)整型或長(zhǎng)整型數(shù)據(jù)等），這樣，在做運(yùn)算（特殊是乘法運(yùn)算）時(shí)，可以減少許多操作次數(shù)。例如圖5就是采納4位保存的除法運(yùn)算，其他運(yùn)算也類(lèi)似。詳細(xì)程序可以修改上述例題予以解決，程序請(qǐng)讀者完成。示例：123456789÷45=1’示例：123456789÷45=1’2345’6789÷45=274’3484∵1div45=0，1mod45=1∴取12345div45=274∵12345mod45=15∴取156789div45=3484∴答案為2743484,余數(shù)為156789mod45=9圖5第三課排列及組合課題：排列及組合目標(biāo)：知識(shí)目標(biāo)：如何利用程序就各種排列和組合實(shí)力目標(biāo)：排列組合的運(yùn)用重點(diǎn)：求出n的全排列和從m中取n個(gè)的組合難點(diǎn)：算法的理解板書(shū)示意：求全排列的算法求組合數(shù)的算法授課過(guò)程：例5：有3個(gè)人排成一個(gè)隊(duì)列，問(wèn)有多少種排對(duì)的方法，輸出每一種方案？分析：假如我們將3個(gè)人進(jìn)行編號(hào)，分別為1,2,3，明顯我們列出全部的排列，123，132，213，231，312，321共六種?？捎醚h(huán)枚舉各種狀況，參考程序：programexam5;var i,j,k:integer;begin forI:=1to3doforj:=1to3do fork:=1to3doif(i+j+k=6)and(i*j*k=6)thenwriteln(i,j,k);end.上述狀況特別簡(jiǎn)單，因?yàn)橹挥?個(gè)人，但當(dāng)有N個(gè)人時(shí)怎么辦？明顯用循環(huán)不能解決問(wèn)題。下面我們介紹一種求全排列的方法。設(shè)當(dāng)前排列為P1P2,…,Pn，則下一個(gè)排列可按如下算法完成：1．求滿(mǎn)足關(guān)系式Pj-1<Pj的J的最大值，設(shè)為I，即I=max{j|Pj-1<Pj,j=2..n}2．求滿(mǎn)足關(guān)系式Pi-1<Pk的k的最大值，設(shè)為j，即J=max{K|Pi-1<Pk,k=1..n}3．Pi-1及Pj互換得(P)=P1P2,…,Pn4．(P)=P1P2,…,Pi-1Pi,…,Pn部分的順序逆轉(zhuǎn)，得P1P2,…,Pi-1PnPn-1,…,Pi便是下一個(gè)排列。例：設(shè)P1P2P3P4=34211．I=max{j|Pj-1<Pj,j=2..n}=22．J=max{K|Pi-1<Pk,k=1..n}=23．P1及P2交換得到43214．4321的321部分逆轉(zhuǎn)得到4123即是3421的下一個(gè)排列。程序設(shè)計(jì)如下：programexam5;constmaxn=100;vari,j,m,t:integer;p:array[1..maxn]ofinteger;count:integer;{排列數(shù)目統(tǒng)計(jì)變量}beginwrite('m:');readln(m);fori:=1tomdobeginp[i]:=i;write(i)end;writeln;count:=1;repeat{求滿(mǎn)足關(guān)系式Pj-1<Pj的J的最大值，設(shè)為I}i:=m;while(i>1)and(p[i-1]>=p[i])dodec(i);ifi=1thenbreak; {求滿(mǎn)足關(guān)系式Pi-1<Pk的k的最大值，設(shè)為j}j:=m;while(j>0)and(p[i-1]>=p[j])dodec(j);ifj=0thenbreak; {Pi-1及Pj互換得(P)=P1P2,…,Pm}t:=p[i-1];p[i-1]:=p[j];p[j]:=t;{Pi,…,Pm的順序逆轉(zhuǎn)}forj:=1to(m-i+1)div2dobegint:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=tend;{打印當(dāng)前解}fori:=1tomdowrite(p[i]);inc(count);writeln;untilfalse;writeln(count)End.例6：求N個(gè)人選取M個(gè)人出來(lái)做嬉戲，共有多少種取法？例如：N=4，M=2時(shí)，有12，13，14，23，24，34共六種。分析：因?yàn)榻M合數(shù)跟順序的選擇無(wú)關(guān)。因此對(duì)同一個(gè)組合的不同排列，只需取其最小的一個(gè)（即按從小到大排序）。因此，可以設(shè)計(jì)如下算法：1．最終一位數(shù)最大可達(dá)N，倒數(shù)第二位數(shù)最大可達(dá)N-1，…，依此類(lèi)推，倒數(shù)第K位數(shù)最大可達(dá)N-K+1。若R個(gè)元素組合用C1C2…CR表示，且假定C1<C2<…<CR,CR<=N-R+I,I=1,2,…,R。2．當(dāng)存在Cj<N-R+J時(shí)，其中下標(biāo)的最大者設(shè)為I，即 I=max{J|Cj<N-R+J}，則作Ci:=Ci+1,及之對(duì)應(yīng)的操作有Ci+1:=Ci+1，Ci+2:=Ci+1+1，….，CR:=CR-1+1參考程序：programexam6;constmaxn=10;vari,j,n,m:integer;c:array[1..maxn]ofinteger; {c數(shù)組記錄當(dāng)前組合}BeginWrite('n&m:');readln(n,m);fori:=1tomdobegin {初始化，建立第一個(gè)組合}c[i]:=i;write(c[i]);end;writeln;whilec[1]<n-m+1dobeginj:=m;while(c[j]>n-m+1)and(j>0)dodec(j); {求I=max{J|Cj<N-R+J}}c[j]:=c[j]+1;fori:=j+1tomdoc[i]:=c[i-1]+1; {建立下一個(gè)組合}fori:=1tomdowrite(c[i]);writeln {輸出}end;End.第四課枚舉法課題：枚舉法目標(biāo)：知識(shí)目標(biāo)：枚舉算法的本質(zhì)和應(yīng)用實(shí)力目標(biāo)：枚舉算法的應(yīng)用！重點(diǎn)：利用枚舉算法解決實(shí)際問(wèn)題難點(diǎn)：枚舉算法的次數(shù)確定板書(shū)示意：簡(jiǎn)單枚舉（例7,例8,例9）利用枚舉解決邏輯推斷問(wèn)題（例10,例11）枚舉解決競(jìng)賽問(wèn)題（例12,例13,例14）授課過(guò)程：所謂枚舉法,指的是從可能的解集合中一一枚舉各元素,用題目給定的檢驗(yàn)條件判定哪些是無(wú)用的,哪些是有用的.能使命題成立,即為其解。一般思路：對(duì)命題建立正確的數(shù)學(xué)模型；依據(jù)命題確定的數(shù)學(xué)模型中各變量的變化范圍（即可能解的范圍）；利用循環(huán)語(yǔ)句,條件推斷語(yǔ)句逐步求解或證明；枚舉法的特點(diǎn)是算法簡(jiǎn)單，但有時(shí)運(yùn)算量大。對(duì)于可能確定解的值域又一時(shí)找不到其他更好的算法時(shí)可以采納枚舉法。例7：求滿(mǎn)足表達(dá)式A+B=C的全部整數(shù)解，其中A，B，C為1~3之間的整數(shù)。分析：本題特別簡(jiǎn)單，即枚舉全部狀況，符合表達(dá)式即可。算法如下：forA:=1to3doforB:=1to3doforC:=1to3doifA+B=CthenWriteln(A,‘+’,B,‘=’,C);上例采納的就是枚舉法。所謂枚舉法，指的是從可能的解的集合中一一枚舉各元素，用題目給定的檢驗(yàn)條件判定哪些是無(wú)用的，哪些是有用的。能使命題成立的，即為解。從枚舉法的定義可以看出，枚舉法本質(zhì)上屬于搜尋。但及隱式圖的搜尋有所區(qū)分，在采納枚舉法求解的問(wèn)題時(shí)，必需滿(mǎn)足兩個(gè)條件：預(yù)先確定解的個(gè)數(shù)n；對(duì)每個(gè)解變量A1，A2，……，An的取值，其變化范圍需預(yù)先確定A1∈{X11，……，X1p}Ai∈{Xi1，……，Xiq}An∈{Xn1，……，Xnk}例7中的解變量有3個(gè)：A，B，C。其中A解變量值的可能取值范圍A∈{1，2，3}B解變量值的可能取值范圍B∈{1，2，3}C解變量值的可能取值范圍C∈{1，2，3}則問(wèn)題的可能解有27個(gè)（A，B，C）∈{（1，1，1），（1，1，2），（1，1，3），（1，2，1），（1，2，2），（1，2，3），（3，3，1），（3，3，2），（3，3，3）}在上述可能解集合中，滿(mǎn)足題目給定的檢驗(yàn)條件的解元素，即為問(wèn)題的解。假如我們無(wú)法預(yù)先確定解的個(gè)數(shù)或各解的值域，則不能用枚舉，只能采納搜尋等算法求解。由于回溯法在搜尋每個(gè)可能解的枚舉次數(shù)一般不止一次，因此，對(duì)于同樣規(guī)模的問(wèn)題，回溯算法要比枚舉法時(shí)間困難度稍高。例8給定一個(gè)二元一次方程aX+bY=c。從鍵盤(pán)輸入a,b,c的數(shù)值，求X在[0，100]，Y在[0，100]范圍內(nèi)的全部整數(shù)解。 分析：要求方程的在一個(gè)范圍內(nèi)的解，只要對(duì)這個(gè)范圍內(nèi)的全部整數(shù)點(diǎn)進(jìn)行枚舉，看這些點(diǎn)是否滿(mǎn)足方程即可。參考程序：programexam8;vara,b,c:integer;x,y:integer;beginwrite('Inputa,b,c:');readln(a,b,c);forx:=0to100dofory:=0to100doifa*x+b*y=cthenwriteln(x,'',y);end.從上例可以看出，所謂枚舉法,指的是從可能的解集合中一一枚舉各元素,用題目給定的檢驗(yàn)條件判定哪些是無(wú)用的,哪些是有用的.能使命題成立,即為其解。例9奇妙填數(shù)192384576將1～9這九個(gè)數(shù)字填入九個(gè)空格中。每一橫行的三個(gè)數(shù)字組成一個(gè)三位數(shù)。假如要使第二行的三位數(shù)是第一行的兩倍,第三行的三位數(shù)是第一行的三倍,應(yīng)怎樣填數(shù)。如圖6:圖6分析：本題目有9個(gè)格子，要求填數(shù)，假如不考慮問(wèn)題給出的條件，共有9！=362880種方案，在這些方案中符合問(wèn)題條件的即為解。因此可以采納枚舉法。但細(xì)致分析問(wèn)題，明顯第一行的數(shù)不會(huì)超過(guò)400，事實(shí)上只要確定第一行的數(shù)就可以依據(jù)條件算出其他兩行的數(shù)了。這樣僅需枚舉400次。因此設(shè)計(jì)參考程序：programexam9;vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;beginfori:=1to3doforj:=1to9doifj<>ithenfork:=1to9doif(k<>j)and(k<>i)thenbegins:=i*100+j*10+k;{求第一行數(shù)}if3*s<1000thenif(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then{滿(mǎn)足條件，并數(shù)字都由1~9組成}beginwriteln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.例10在某次數(shù)學(xué)競(jìng)賽中,A,B,C,D,E五名學(xué)生被取為前五名。請(qǐng)據(jù)下列說(shuō)法推斷出他們的詳細(xì)名次,即誰(shuí)是第幾名？條件1:你假如認(rèn)為A,B,C,D,E就是這些人的第一至第五名的名次排列,便大錯(cuò)。因?yàn)?沒(méi)猜對(duì)任何一個(gè)優(yōu)勝者的名次。也沒(méi)猜對(duì)任何一對(duì)名次相鄰的學(xué)生。條件2:你假如按D,A,E,C,B來(lái)排列五人名次的話,其結(jié)果是:說(shuō)對(duì)了其中兩個(gè)人的名次。還猜中了兩對(duì)名次相鄰的學(xué)生的名次順序。分析：本題是一個(gè)邏輯推斷題，一般的邏輯推斷題都采納枚舉法進(jìn)行解決。5個(gè)人的名次分別可以有5！=120種排列可能，因?yàn)?20比較小，因此我們對(duì)每種狀況進(jìn)行枚舉，然后依據(jù)條件推斷哪些符合問(wèn)題的要求。依據(jù)已知條件，A<>1,B<>2,C<>3,D<>4,E<>5,因此解除了一種可能性，只有4！=24種狀況了。參考程序：ProgramExam10;VarA,B,C,D,E:Integer;Cr:Array[1..5]OfChar;BeginForA:=1To5DoForB:=1To5DoForC:=1To5DoForD:=1To5DoForE:=1To5DoBegin{ABCDE沒(méi)猜對(duì)一個(gè)人的名次}If(A=1)Or(B=2)Or(C=3)Or(D=4)Or(E=5)ThenContinue;If[A,B,C,D,E]<>[1,2,3,4,5]ThenContinue;{他們名次互不重復(fù)}{DAECB猜對(duì)了兩個(gè)人的名次}IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2ThenContinue;{ABCDE沒(méi)猜對(duì)一對(duì)相鄰名次}If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)ThenContinue;{DAECB猜對(duì)了兩對(duì)相鄰人名次}IfOrd(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2ThenContinue;Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';Cr[D]:='D';Cr[E]:='E';Writeln(Cr[1],'',Cr[2],'',Cr[3],'',Cr[4],'',Cr[5]);End;End.例11：來(lái)自不同國(guó)家的四位留學(xué)生A,B,C,D在一起交談,他們只會(huì)中,英,法,日四種語(yǔ)言中的2種,狀況是,沒(méi)有人既會(huì)日語(yǔ)又會(huì)法語(yǔ);A會(huì)日語(yǔ),但D不會(huì),A和D能相互交談,B不會(huì)英語(yǔ),但A和C交談時(shí)卻要B當(dāng)翻譯,B,C,D三個(gè)想相互交談,但找不到共同的語(yǔ)言,只有一種語(yǔ)言3人都會(huì),編程確定A,B,C,D四位留學(xué)生各會(huì)哪兩種語(yǔ)言。分析：將中,法,日,英四種語(yǔ)言分別定義為CHN,FRH,JPN,ENG,則四種語(yǔ)言中取兩種共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),(ENG,FRH),(ENG,JPN),(FRH,JPN)六種組合，分別定義為1,2,3,4,5,6。據(jù)已知，沒(méi)有人既會(huì)日語(yǔ)又會(huì)法語(yǔ);因此，組合6不會(huì)出現(xiàn)；A會(huì)日語(yǔ)，所以A只可能等于3,5；D不會(huì)日語(yǔ),所以D只可能等于1,2,4；B不會(huì)英語(yǔ)，所以B只可能等于2,3；見(jiàn)下表。假如我們對(duì)A,B,C,D分別進(jìn)行枚舉，依據(jù)判定條件，即可找到答案。(CHN,ENG)(CHN,FRH)(CHN,JPN)(ENG,FRH)(ENG,JPN)A×××B×××CD××程序如下：programEXAM11;typeLanguage=(CHN,ENG,FRH,JPN);TNoSet=setofLanguage;constNo:array[1..5]ofTNoSet=([CHN,ENG],[CHN,FRH],[CHN,JPN],[ENG,FRH],[ENG,JPN]);varA,B,C,D:1..5;Can1,Can2,Can3,Can4:Boolean;functionMight(Lang:Language):Boolean;varBool:Boolean;beginBool:=false;ifNo[A]*No[A]*No[C]=[Lang]thenBool:=True;ifNo[A]*No[B]*No[D]=[Lang]thenBool:=True;ifNo[A]*No[C]*No[D]=[Lang]thenBool:=True;ifNo[B]*No[C]*No[D]=[Lang]thenBool:=True;Might:=Boolend;procedurePrint(A,B,C,D:Integer);procedureShow(P:Integer;Ch:Char);varI:Integer;Lang:Language;beginWrite(ch,':');forLang:=CHNtoJPNdoifLanginNo[P]thencaseLangofCHN:Write('CHN':5);FRH:Write('FRH':5);JPN:Write('JPN':5);ENG:Write('ENG':5);end;Writeln;end;beginShow(A,'A');Show(B,'B');Show(C,'C');Show(D,'D');end;beginforA:=3to5doifA<>4thenforB:=2to3doforC:=1to5doforD:=1to4doifD<>3thenbegin{A和D能相互交談}Can1:=No[A]*No[D]<>[];{A和C交談時(shí)卻要B當(dāng)翻譯}Can2:=(No[A]*No[C]=[])and(No[A]*No[B]<>[])and(No[B]*No[C]<>[]);{B,C,D三個(gè)想相互交談,但找不到共同的語(yǔ)言}Can3:=No[B]*No[C]*No[D]=[];{只有一種語(yǔ)言3人都會(huì)}Can4:=Ord(Might(CHN))+Ord(Might(ENG))+Ord(Might(FRH))+Ord(Might(JPN))=1;ifCan1andCan2andCan3andCan4thenPrint(A,B,C,D);end;end.例12古紙殘篇在一位數(shù)學(xué)家的藏書(shū)中夾有一張古舊的紙片。紙片上的字早已模糊不清了,只留下曾經(jīng)寫(xiě)過(guò)字的痕跡,依稀還可以看出它是一個(gè)乘法算式,如圖7所示。這個(gè)算式上原來(lái)的數(shù)字是什么呢？夾著這張紙片的書(shū)頁(yè)上,“素?cái)?shù)”兩個(gè)字被醒目的劃了出來(lái)。莫非說(shuō),這個(gè)算式及素?cái)?shù)有什么關(guān)系嗎？有人對(duì)此作了深入的探討,果真發(fā)覺(jué)這個(gè)算式中的每一個(gè)數(shù)字都是***×***************圖7素?cái)?shù),***×***************圖7分析：事實(shí)上，只要知道乘數(shù)和被乘數(shù)就可以寫(xiě)出乘法算式，所以我們可以枚舉乘數(shù)及被乘數(shù)的每一位。然后再推斷是不是滿(mǎn)足條件即可。計(jì)算量是45=1024，對(duì)于計(jì)算機(jī)來(lái)說(shuō)，計(jì)算量特別小。參考程序：ProgramExam12;ConstSu:Array[1..4]OfLongint=(2,3,5,7);VarA1,A2,A3,B1,B2,X,Y,S:Longint;FunctionKx(S:Longint):Boolean;{推斷一個(gè)數(shù)是不是都是由素?cái)?shù)組成}BeginKx:=True;WhileS<>0DoBeginIfNot((SMod10)In[2,3,5,7])ThenBeginKx:=False;Exit;End;S:=SDiv10;End;End;BeginForA1:=1To4DoForA2:=1To4DoForA3:=1To4DoForB1:=1To4DoForB2:=1To4DoBeginX:=Su[A1]*100+Su[A2]*10+Su[A3];{X為被乘數(shù)}IfX*Su[B1]<1000ThenContinue;IfX*Su[B2]<1000ThenContinue;IfX*(Su[B1]*10+Su[B2])<10000ThenContinue;{它們分別是兩個(gè)四位數(shù)，一個(gè)五位數(shù)}If(Kx(X*Su[B1])=False)Or(Kx(X*Su[B2])=False)Or(Kx(X*(Su[B1]*10+Su[B2]))=False)ThenContinue;{滿(mǎn)足其他數(shù)都是由質(zhì)數(shù)構(gòu)成}Writeln('',Su[A1],Su[A2],Su[A3]);Writeln('*',Su[B1],Su[B2]);Writeln('');Writeln('',X*Su[B2]);Writeln('',X*Su[B1]);Writeln('');Writeln('',X*(Su[B1]*10+Su[B2]));End;End.例13：時(shí)鐘問(wèn)題（IOI94-4）在圖8所示的3*3矩陣中有9個(gè)時(shí)鐘，我們的目標(biāo)是旋轉(zhuǎn)時(shí)鐘指針，使全部時(shí)鐘的指針都指向12點(diǎn)。允許旋轉(zhuǎn)時(shí)鐘指針的方法有9種，每一種移動(dòng)用一個(gè)數(shù)字號(hào)（1，2，…，9）表示。圖2-11示出9個(gè)數(shù)字號(hào)及相應(yīng)的受限制的時(shí)鐘，這些時(shí)鐘在圖中以灰色標(biāo)出，其指針將順時(shí)針旋轉(zhuǎn)90度。圖8九種時(shí)鐘狀態(tài)圖9九種被圖8九種時(shí)鐘狀態(tài)圖9九種被限制方式由輸入文件INPUT.TXT讀9個(gè)數(shù)碼，這些數(shù)碼給出了9個(gè)時(shí)鐘時(shí)針的初始位置。數(shù)碼及時(shí)刻的對(duì)應(yīng)關(guān)系為：0——12點(diǎn)1——3點(diǎn)2——6點(diǎn)3——9點(diǎn)圖2-11中的例子對(duì)應(yīng)下列輸入數(shù)據(jù)：330222212輸出數(shù)據(jù)：將一個(gè)最短的移動(dòng)序列（數(shù)字序列）寫(xiě)入輸出文件OUTPUT.TXT中，該序列要使全部的時(shí)鐘指針指向12點(diǎn)，若有等價(jià)的多個(gè)解，僅需給出其中一個(gè)。在我們的例子中，相應(yīng)的OUTPUT.TXT的內(nèi)容為：5849輸入輸出示例：INPUT.TXTOUTPUT.TXT3302222125489詳細(xì)的移動(dòng)方案如圖10所示。圖10示例移動(dòng)方案分析：圖10示例移動(dòng)方案首先，我們分析一下表示時(shí)鐘時(shí)針初始位置的數(shù)碼j（0≦j≦3）及時(shí)刻的對(duì)應(yīng)關(guān)系：0——12點(diǎn)1——3點(diǎn)2——6點(diǎn)3——9點(diǎn)每移動(dòng)一次，時(shí)針將順時(shí)針旋轉(zhuǎn)90度。由此我們可以得出：對(duì)于隨意一個(gè)時(shí)鐘i（1≦i≦9）來(lái)說(shuō)，從初始位置j動(dòng)身至少須要Ci=（4-j）mod4次操作，才能使得時(shí)針指向12點(diǎn)。而對(duì)每種移動(dòng)方法要么不采納，要么采納1次,2次或3次，因?yàn)椴僮魉拇我院?，時(shí)鐘將重復(fù)以前狀態(tài)。因此，9種旋轉(zhuǎn)方案最多產(chǎn)生49個(gè)狀態(tài)。移動(dòng)方案選取及順序無(wú)關(guān)。樣例中，最佳移動(dòng)序列為5849，同樣4589序列也可達(dá)到目標(biāo)。因此，求解過(guò)程中可以直接選取序列中從小至大排列的移動(dòng)序列即可。設(shè)pi表示第i種旋轉(zhuǎn)方法的運(yùn)用次數(shù)（0≦pi≦3，1≦i≦9）。則可能的解的集合為{P1，P2，……，P9}，該集合共含49個(gè)狀態(tài)。從圖2.11中，我們可以分析出9個(gè)時(shí)鐘分別被哪些方法所限制，見(jiàn)下表：時(shí)鐘號(hào)限制時(shí)鐘方案檢驗(yàn)條件11,2,4C1=(P1+P2+P4)mod421,2,3,5C2=(P1+P2+P3+P5)mod432,3,6C3=(P2+P3+P6)mod441,4,5,7C4=(P1+P4+P5+P7)mod451,3,5,7,9C5=(P1+P3+P5+P7+P9)mod463,5,6,9C6=(P3+P5+P6+P9)mod474,7,8C7=(P4+P7+P8)mod485,7,8,9C8=(P5+P7+P8+P9)mod496,8,9C9=(P6+P8+P9)mod4因此我們可以設(shè)計(jì)如下枚舉算法：forp1:=0to3do forp2:=0to3doforp9:=0to3do ifc1滿(mǎn)足時(shí)鐘1andc2滿(mǎn)足時(shí)鐘2and...andc9滿(mǎn)足時(shí)鐘9then打印解路徑；明顯，上述枚舉算法枚舉了全部49=262144個(gè)狀態(tài)，運(yùn)算量和運(yùn)行時(shí)間頗大。我們可以實(shí)行縮小可能解范圍的局部枚舉法，僅枚舉第1,2,3種旋轉(zhuǎn)方法可能取的43個(gè)狀態(tài)，依據(jù)這三種旋轉(zhuǎn)方法的當(dāng)前狀態(tài)值，由下述公式P4=order(C1-P1-P2);P5=order(C2-P1-P2-P3);P6=order(C3-P2-P3);P7=order(C4-P1-P4-P5);P8=order(C8-P5-PP9);P9=order(C6-P3-P5-P6);其中得出其余P4……P9的相應(yīng)狀態(tài)值。然后將P1，P2，…，P9代入下述三個(gè)檢驗(yàn)條件C5=(P1+P3+P5+P7+P9)mod4C7=(P4+P7+P8)mod4C9=(P6+P8+P9)mod4一一枚舉，以求得準(zhǔn)確解。由此可見(jiàn)，上述局部枚舉的方法（枚舉狀態(tài)數(shù)為43個(gè)）比較全部枚舉的方法（枚舉狀態(tài)數(shù)為49個(gè)）來(lái)說(shuō)，由于大幅度削減了枚舉量，減少運(yùn)算次數(shù)，因此其時(shí)效顯著改善，是一種優(yōu)化了的算法。程序如下：programIOI94_4;constInp='input.txt';Outp='output.txt';varClock,Map:array[1..3,1..3]ofInteger;{Clock：第((I+2)mod3)*3+J個(gè)時(shí)鐘從初始時(shí)間到12點(diǎn)的最少移動(dòng)次數(shù)}{Map:最短移動(dòng)序列中，數(shù)字（（I+2）mod3）*3+J的次數(shù)}procedureInit;varI,J:Integer;beginAssign(Input,Inp);Reset(Input);forI:=1to3do{讀入9個(gè)時(shí)鐘指針的初始位置，求出每個(gè)時(shí)鐘從初始到12點(diǎn)的最少移動(dòng)次數(shù)}forJ:=1to3dobeginRead(Clock[I,J]);Clock[I,J]:=(4-Clock[I,J])mod4;end;Close(Input);end;functionOrder(K:Integer):Integer;varc:Integer;begin c:=k; whilec<0doinc(c,4);whilec>4thendec(c,4);Order:=k;end;procedureMain; {計(jì)算和輸出最短移動(dòng)序列}varI,J,K:Integer;begin{枚舉最短移動(dòng)序列中數(shù)字1,2,3的個(gè)數(shù)可能取的43種狀態(tài)}Assign(Output,Outp);Rewrite(Output);forMap[1,1]:=0to3doforMap[1,2]:=0to3doforMap[1,3]:=0to3dobeginMap[2,1]:=Order(Clock[1,1]-Map[1,1]-Map[1,2]);Map[2,3]:=Order(Clock[1,3]-Map[1,2]-Map[1,3]);Map[2,2]:=Order(Clock[1,2]-Map[1,1]-Map[1,2]-Map[1,3]);Map[3,1]:=Order(Clock[2,1]-Map[1,1]-Map[2,1]-Map[2,2]);Map[3,3]:=Order(Clock[2,3]-Map[1,3]-Map[2,2]-Map[2,3]);Map[3,2]:=Order(Clock[3,2]-Map[3,1]-Map[3,3]-Map[2,2]);{依據(jù)數(shù)字1,2,3個(gè)數(shù)的當(dāng)前值，得出數(shù)字4~9的個(gè)數(shù)}if((Map[2,1]+Map[3,1]+Map[3,2])mod4=Clock[3,1])and((Map[2,3]+Map[3,2]+Map[3,3])mod4=Clock[3,3])and((Map[2,2]+Map[1,1]+Map[1,3]+Map[3,1]+Map[3,3])mod4=Clock[2,2])thenbegin{若數(shù)字4~9的個(gè)數(shù)滿(mǎn)足檢驗(yàn)條件，則輸出方案}forI:=1to3doforJ:=1to3doforK:=1toMap[I,J]doWrite((I-1)*3+J);Exit; {找到一個(gè)解后退出}end;end;Writeln('NoAnswer!');Close(Output);end;beginInit; Main; end.在上例中，由于事先能夠解除那些明顯不屬于解集的元素，使得算法效率特別高。而減少重復(fù)運(yùn)算,力求提前計(jì)算所需數(shù)據(jù),運(yùn)用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)進(jìn)行算法優(yōu)化等方法也是優(yōu)化枚舉算法的常用手段。例14：最佳巡游線路（NOI94）某旅游區(qū)的街道成網(wǎng)格狀（圖2.13）。其中東西向的街道都是旅游街，南北向的街道都是林蔭道。由于游客眾多，旅游街被規(guī)定為單行道，游客在旅游街上只能從西向東走，在林陰道上則既可從南向北走，也可以從北向南走。阿龍想到這個(gè)旅游區(qū)游玩。他的好友阿福給了他一些建議，用分值表示全部旅游街相鄰兩個(gè)路口之間的街道值得巡游的程度，分值時(shí)從-100到100的整數(shù)，全部林陰道不打分。全部分值不可能全是負(fù)分。圖11某旅游區(qū)街道示例圖例如圖11是被打過(guò)分的某旅游區(qū)的街道圖：圖11某旅游區(qū)街道示例圖阿龍可以從任一個(gè)路口開(kāi)始巡游，在任一個(gè)路口結(jié)束巡游。請(qǐng)你寫(xiě)一個(gè)程序，幫忙阿龍找一條最佳的巡游線路，使得這條線路的全部分值總和最大。輸入數(shù)據(jù)：輸入文件是INPUT.TXT。文件的第一行是兩個(gè)整數(shù)M和N，之間用一個(gè)空格符隔開(kāi)，M表示有多少條旅游街（1≦M≦100），N表示有多少條林陰道（1≦M≦20001）。接下來(lái)的M行依次給出了由北向南每條旅游街的分值信息。每行有N-1個(gè)整數(shù)，依次表示了自西向東旅游街每一小段的分值。同一行相鄰兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。輸出數(shù)據(jù)：輸出文件是OUTPUT.TXT。文件只有一行，是一個(gè)整數(shù)，表示你的程序找到的最佳巡游線路的總分值。輸入輸出示例：INPUT.TXTOUTPUT.TXT36-50–4736–30–2317–19–34–13–8-42–3–4334–4584分析：設(shè)Lij為第I條旅游街上自西向東第J段的分值（1≦I≦M，1≦J≦N–1）。例如樣例中L12=17，L23=-34，L34=34。我們將網(wǎng)格狀的旅游區(qū)街道以林蔭道為界分為N–1個(gè)段，每一段由M條旅游街的對(duì)應(yīng)段成，即第J段成為{L1J，L2J，……，LMJ}（1≦J≦N–1）。由于巡游方向規(guī)定橫向自西向東，縱向即可沿林陰道由南向北，亦可由北向南，而橫行的街段有分值，縱行無(wú)分值，因此最佳巡游路現(xiàn)必需具備如下三個(gè)特征：來(lái)自若干個(gè)連續(xù)的段，每一個(gè)段中取一個(gè)分值；每一個(gè)分值是所在段中最大的；起點(diǎn)段和終點(diǎn)段隨意，但途經(jīng)段的分值和最大。設(shè)Li為第I個(gè)段中的分值最大的段。即Li=Max{L1I，L2I，……，LMI}（1≦I≦N–1）。例如對(duì)于樣例數(shù)據(jù)：L1=Max（-50，17，-42）=17；L2=Max（-47，-19，-3）=-3；L3=Max（36，-34，-43）=36；L4=Max（-30，-13，34）=34；L5=Max（-23，-8，-45）=-8；有了以上的基礎(chǔ)，我們便可以通過(guò)圖示描述解題過(guò)程，見(jiàn)圖12。圖12求解過(guò)程示例圖我們把將段設(shè)為頂點(diǎn)，所在段的最大分值設(shè)為頂點(diǎn)的權(quán)，各頂點(diǎn)按自西向東的順序相連，組成一條巡游路線。明顯，假如確定西端為起點(diǎn),東段為終點(diǎn)，則這條巡游路線的總分值最大。圖12求解過(guò)程示例圖問(wèn)題是某些段的最大分值可能是負(fù)值，而最優(yōu)巡游路線的起點(diǎn)和終點(diǎn)隨意，在這種狀況下，上述巡游路線就不肯定最佳了。因此，我們只能枚舉這條巡游路線的全部可能的子路線，從中找出一條子路線II+1……J（1≦I<J≦N–1），使得經(jīng)過(guò)頂點(diǎn)的權(quán)和LI+LI+1+……+LJ最大。設(shè)Best為最佳巡游路線的總分值，初始時(shí)為0；Sum為當(dāng)前巡游路線的總分值。我們可以得到如下算法：Best:=0;Sum:=0;forI:=1toN–2doforJ:=I+1toN–1dobeginSum:=LI+……+LJ;ifSum>BestthenBest:=Sum;end明顯，這個(gè)算法的時(shí)間困難度為O（N2）。而N在1~20001之間，時(shí)間困難度比較高。于是，我們必需對(duì)這個(gè)算法進(jìn)行優(yōu)化。仍舊從頂點(diǎn)1開(kāi)始枚舉最優(yōu)路線。若當(dāng)前子路線延長(zhǎng)至頂點(diǎn)I時(shí)發(fā)覺(jué)總分值Sum≦0，則應(yīng)放棄當(dāng)前子路線。因?yàn)闊o(wú)論LI+1為何值，當(dāng)前子路線延長(zhǎng)至頂點(diǎn)I+1后的總分值不會(huì)大于LI+1。因此應(yīng)當(dāng)從頂點(diǎn)I+1開(kāi)始重新考慮新的一條子路線。通過(guò)這種優(yōu)化，可以使得算法的時(shí)間困難度降到了O（N）。優(yōu)化后的算法描述如下:Best:=0;Sum:=0;forI:=1toN–1dobeginSum:=Sum+LI;ifSum>BestthenBest:=Sum;ifSum<0thenSum:=0;end程序描述如下：{$R-,S-,Q-}{$M65520,0,655360}programNoi94;constMaxN=20001; {林陰道數(shù)的上限}Inp='input.txt';Outp='output.txt';varM,N:Word; {旅游街?jǐn)?shù)和林陰道數(shù)}Best:Longint; {最佳巡游路線的總分值}Score:array[1..MaxN]ofShortInt; {描述每個(gè)段的最大分值}procedureInit;varI,J,K:Integer;Buffer:array[1..40960]ofChar; {文件緩沖區(qū)}beginAssign(Input,Inp);Reset(Input);SetTextBuf(Input,Buffer); {開(kāi)拓文件緩沖區(qū)}Readln(M,N); {讀入旅游街?jǐn)?shù)和林陰道數(shù)}FillChar(Score,Sizeof(Score),$80); {初始化各段的最大分值}forI:=1toMdo {計(jì)算1~N–1段的最大分值}forJ:=1toN-1dobeginRead(K);ifK>Score[J]thenScore[J]:=K;end;Close(Input); end;procedureOut;beginAssign(Output,Outp);Rewrite(Output);Writeln(Best);Close(Output);end;procedureMain;varI:Integer;Sum:Longint; {當(dāng)前巡游路線的總分值}begin{最佳巡游路線的總分值和當(dāng)前巡游路線的總分值初始化}Best:=0;Sum:=0;forI:=1toN-1dobegin {順序枚舉巡游路線的總分值}Inc(Sum,Score[I]); {統(tǒng)計(jì)當(dāng)前巡游路線的總分值}ifSum>BestthenBest:=Sum; {若當(dāng)前最佳，則登記}ifSum<0thenSum:=0;{若總分值<0，則考慮一條新路線}end;end;beginInit; {輸入數(shù)據(jù)}Main; {主過(guò)程}Out; {輸出}end.第五課遞歸及回溯法課題：遞歸及回溯目標(biāo)：知識(shí)目標(biāo)：遞歸概念及利用遞歸進(jìn)行回溯實(shí)力目標(biāo)：回溯算法的應(yīng)用重點(diǎn)：回溯算法難點(diǎn)：回溯算法的理解板書(shū)示意：遞歸的理解利用遞歸回溯解決實(shí)際問(wèn)題（例14,例15,例16,例17,例18）利用回溯算法解決排列問(wèn)題（例19）授課過(guò)程：什么是遞歸？先看大家都熟識(shí)的一個(gè)民間故事：從前有座山，山上有座廟，廟里有一個(gè)老和尚在給小和尚講故事，故事里說(shuō)，從前有座山，山上有座廟，廟里有一個(gè)老和尚在給小和尚講故事，故事里說(shuō)……。象這樣，一個(gè)對(duì)象部分地由它自己組成，或者是按它自己定義，我們稱(chēng)之是遞歸。例如，我們可以這樣定義N!，N!=N*(N-1)!，因此求N!轉(zhuǎn)化為求(N-1)!。這就是一個(gè)遞歸的描述。因此，可以編寫(xiě)如下遞歸程序：programFactorial;varN:Integer;T:Longint;functionFac(N:Integer):Longint;beginifN=0thenFac:=1elseFac:=N*Fac(N-1)end;beginWrite('N=');Readln(N);T:=Fac(N);Writeln('N!=',T);end.圖13圖13遞歸調(diào)用示例圖設(shè)一個(gè)未知函數(shù)f，用其自身構(gòu)成的已知函數(shù)g來(lái)定義：為了定義f(n)，必需先定義f(n-1)，為了定義f(n-1)，又必需先定義f(n-2)，…，上述這種用自身的簡(jiǎn)單狀況來(lái)定義自己的方式稱(chēng)為遞歸定義。遞歸有如下特點(diǎn)： ①它直接或間接的調(diào)用了自己。 ②肯定要有遞歸終止的條件，這個(gè)條件通常稱(chēng)為邊界條件。及遞推一樣，每一個(gè)遞推都有其邊界條件。但不同的是，遞推是由邊界條件動(dòng)身，通過(guò)遞推式求f(n)的值，從邊界到求解的全過(guò)程特別清晰；而遞歸則是從函數(shù)自身動(dòng)身來(lái)達(dá)到邊界條件，在通過(guò)邊界條件的遞歸調(diào)用過(guò)程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果（局部變量和返回地址）保存起來(lái)，直至求出遞歸邊界值f(0)=a。然后返回調(diào)用函數(shù)。返回的過(guò)程中，中間結(jié)果相繼出棧復(fù)原，f(1)=g(1,a)f(2)=g(2,f(1))……直至求出f(n)=g(n,f(n-1))。遞歸按其調(diào)用方式分直接遞歸——遞歸過(guò)程P直接自己調(diào)用自己；間接遞歸——即P包含另一過(guò)程D，而D又調(diào)用P；由此可見(jiàn)，遞歸算法的效率往往很低，費(fèi)時(shí)和費(fèi)內(nèi)存空間。但是遞歸也有其特長(zhǎng)，它能使一個(gè)蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)困難的程序簡(jiǎn)潔精煉，增加可讀性。特殊是在難于找到從邊界到解的全過(guò)程的狀況下，假如把問(wèn)題進(jìn)一步，其結(jié)果仍維持原問(wèn)題的關(guān)系，則采納遞歸按其調(diào)用方式分直接遞歸——遞歸過(guò)程P直接自己調(diào)用自己；間接遞歸——即P包含另一過(guò)程D，而D又調(diào)用P；遞歸算法適用的一般場(chǎng)合為：①數(shù)據(jù)的定義形式按遞歸定義。如裴波那契數(shù)列的定義：對(duì)應(yīng)的遞歸程序?yàn)閒unctionfib(n:Integer):Integer;beginifn=0thenfib:=1 {遞歸邊界}elseifn=1thenfib:=2 {遞歸邊界}elsefib:=fib(n–2)+fib(n–1); {遞歸}end;這類(lèi)遞歸問(wèn)題可轉(zhuǎn)化為遞推算法，遞歸邊界為遞推的邊界條件。例如上例轉(zhuǎn)化為遞推算法即為functionfib(n:Integer):Integer;beginf[0]:=1;f[1]:=2; {遞推邊界}forI:=2tondof[I]:=f[I–1]+f[I–2];fib:=f(n);end;②數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義。如樹(shù)的遍歷，圖的搜尋等。③問(wèn)題解法按遞歸算法實(shí)現(xiàn)。例如回溯法等。對(duì)于②和③，可以用堆棧結(jié)構(gòu)將其轉(zhuǎn)換為非遞歸算法，以提高算法的效率以及減少內(nèi)存空間的奢侈。下面以經(jīng)典的N皇后問(wèn)題為例，看看遞歸法是怎樣實(shí)現(xiàn)的，以及比較遞歸算法和非遞歸算法效率上的差別。例15：N皇后問(wèn)題圖14八皇后的兩組解在N*N的棋盤(pán)上放置N個(gè)皇后而彼此不受攻擊（即在棋盤(pán)的任一行，任一列和任一對(duì)角線上不能放置2個(gè)皇后），編程求解全部的擺放方法。圖14八皇后的兩組解分析：由于皇后的擺放位置不能通過(guò)某種公式來(lái)確定，因此對(duì)于每個(gè)皇后的擺放位置都要進(jìn)行摸索和訂正，這就是“回溯”的思想。在N個(gè)皇后未放置完成前，擺放第I個(gè)皇后和第I+1個(gè)皇后的摸索方法是相同的，因此完全可以采納遞歸的方法來(lái)處理。下面是放置第I個(gè)皇后的的遞歸算法：ProcedureTry(I:integer)；{搜尋第I行皇后的位置}var j:integer;beginifI=n+1then輸出方案；forj:=1tondo if皇后能放在第I行第J列的位置thenbegin放置第I個(gè)皇后；對(duì)放置皇后的位置進(jìn)行標(biāo)記；Try（I+1）對(duì)放置皇后的位置釋放標(biāo)記； End;End;N皇后問(wèn)題的遞歸算法的程序如下：programN_Queens;constMaxN=100; {最多皇后數(shù)}varA:array[1..MaxN]ofBoolean; {豎線被限制標(biāo)記}B:array[2..MaxN*2]ofBoolean; {左上到右下斜線被限制標(biāo)記}C:array[1–MaxN..MaxN–1]ofBoolean;{左下到右上斜線被限制標(biāo)記}X:array[1..MaxN]ofInteger; {記錄皇后的解}Total:Longint; {解的總數(shù)}N:Integer; {皇后個(gè)數(shù)}procedureOut; {輸出方案}varI:Integer;beginInc(Total);Write(Total:3,‘:’);forI:=1toNdoWrite(X[I]:3);Writeln;end;procedureTry(I:Integer); {搜尋第I個(gè)皇后的可行位置}varJ:Integer;beginifI=N+1thenOut;{N個(gè)皇后都放置完畢，則輸出解}forJ:=1toNdoifA[J]andB[J+I]andC[J–I]thenbeginX[I]:=J;A[J]:=False;B[J+I]:=False;C[J–I]:=False;Try(I+1); {搜尋下一皇后的位置}A[J]:=True;B[J+I]:=True;C[J–I]:=True;end;end;beginWrite(‘QueensNumbers=‘);Readln(N);FillChar(A,Sizeof(A),True);FillChar(B,Sizeof(B),True);FillChar(C,Sizeof(C),True);Try(1);Writeln(‘Total=‘,Total);end.N皇后問(wèn)題的非遞歸算法的程序：programN_Queens;constMaxN=100; {最多皇后數(shù)}varA:array[1..MaxN]ofBoolean; {豎線被限制標(biāo)記}B:array[2..MaxN*2]ofBoolean; {左上到右下斜線被限制標(biāo)記}C:array[1–MaxN..MaxN–1]ofBoolean;{左下到右上斜線被限制標(biāo)記}X:array[1..MaxN]ofInteger; {記錄皇后的解}Total:Longint; {解的總數(shù)}N:Integer; {皇后個(gè)數(shù)procedureOut; {輸出方案}varI:Integer;beginInc(Total);Write(Total:3,‘:’);forI:=1toNdoWrite(X[I]:3);Writeln;end;procedureMain; varK:Integer;beginX[1]:=0;K:=1;whileK>0dobeginifX[K]<>0thenbeginA[X[K]]:=True;B[X[K]+K]:=True;C[X[K]–K]:=True;end;Inc(X[K]);while(X[K]<=N)andnot(A[X[K]]andB[X[K]+K]andC[X[K]–K])doInc(X[K]); {找尋一個(gè)可以放置的位置}ifX[K]<=NthenifK=NthenOutelsebeginA[X[K]]:=False;B[X[K]+K]:=False;C[X[K]–K]:=False;Inc(K);X[K]:=0; {接著放置下一個(gè)皇后}endelseDec(K); {回溯}end;end;beginWrite(‘QueensNumber=‘);Readln(N);FillChar(A,Sizeof(A),True);FillChar(B,Sizeof(B),True);FillChar(C,SizeofI,True);Main;Writeln(‘Total=‘,Total);end.運(yùn)用遞歸可以使蘊(yùn)含困難關(guān)系的問(wèn)題，結(jié)構(gòu)變得簡(jiǎn)潔精煉。看看下面的例題。例16:新漢諾（hanoi）塔問(wèn)題設(shè)有n各大小不等的中空?qǐng)A盤(pán)，按從小到大的順序從1到n編號(hào)。將這n個(gè)圓盤(pán)隨意的迭套在三根立柱上，立柱的編號(hào)分別為A,B,C，這個(gè)狀態(tài)稱(chēng)之為初始狀態(tài)。問(wèn)題要求找到一種步數(shù)最少的移動(dòng)方案，使得從初始狀態(tài)轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)。移動(dòng)時(shí)有如下要求：一次只移動(dòng)一個(gè)盤(pán)；不允許把大盤(pán)移到小盤(pán)上邊；輸入：輸入文件第1行是狀態(tài)中圓盤(pán)總數(shù)；第2~4行是分別是初始狀態(tài)中A,B,C柱上的圓盤(pán)個(gè)數(shù)和從上到下每個(gè)圓盤(pán)的編號(hào)；第5~7行是分別是目標(biāo)狀態(tài)A,B,C柱上的圓盤(pán)個(gè)數(shù)和從上到下每個(gè)圓盤(pán)的編號(hào)。輸出：每行寫(xiě)一步的移動(dòng)方案，格式為：MoveI圓盤(pán)formP柱toQ柱。最終輸出最少步數(shù)。輸入樣例（如圖）：6312324516061234560樣例所描述的狀態(tài)如圖15所示。圖15樣例圖圖15樣例圖輸出樣例：分析：要