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

第頁基礎(chǔ)算法教案目錄TOC\o"1-1"\h\z\u第一課算法簡介 1第二課多精度數(shù)值處理 1第三課排列與組合 6第四課枚舉法 9第五課遞歸與回溯法 25第六課遞推法 42第七課貪心法 50第八課分治法 64第九課模擬法 70習(xí)題 79第一課算法簡介算法是一組（有限個）規(guī)則，它為某個特定問題供應(yīng)了解決問題的運算序列。在信息學(xué)競賽中，就是計算機(jī)解題的過程。在這個過程中，無論是形成解題思路還是編寫算法，都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。計算機(jī)解題的核心是算法設(shè)計。一個算法應(yīng)當(dāng)具有以下五個重要特征：有窮性：一個算法必需能在執(zhí)行有限步之后結(jié)束；準(zhǔn)確性：算法的每一步驟必需準(zhǔn)確定義；輸入：一個算法有零個或多個輸入，以描述運算對象的初始狀況。所謂0個輸入是指算法本身給出了初始條件；輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)處理后的結(jié)果。沒有輸出的算法是毫無意義的；可行性：算法原則上能夠精確的運行，而且其運算規(guī)模是可以承受的。為了獲得一個既有效又優(yōu)美的算法，必需首先了解一些基本的常用算法設(shè)計思路。下面，我們就對構(gòu)成算法所依據(jù)的一些基本方法綻開探討，如遞推法，遞歸法，枚舉法，分治法，模擬法，貪心法等。第二課多精度數(shù)值處理課題：多精度數(shù)值的處理目標(biāo)：知識目標(biāo)：多精度值的加,減,乘,除實力目標(biāo)：多精度值的處理，優(yōu)化！重點：多精度的加,減,乘難點：進(jìn)位及借位處理板書示意：輸入兩個正整數(shù)，求它們的和輸入兩個正整數(shù)，求它們的差輸入兩個正整數(shù)，求它們的積輸入兩個正整數(shù)，求它們的商授課過程：所謂多精度值處理，就是在對給定的數(shù)據(jù)范圍，用語言本身供應(yīng)的數(shù)據(jù)類型無法直接進(jìn)行處理（主要指加減乘除運算），而須要采納特殊的處理方法進(jìn)行?？纯聪旅娴睦?。例1從鍵盤讀入兩個正整數(shù)，求它們的和。分析：從鍵盤讀入兩個數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在pascal語言中任何數(shù)據(jù)類型都有肯定的表示范圍。而當(dāng)兩個被加數(shù)據(jù)大時，上述算法明顯不能求出精確解，因此我們須要尋求另外一種方法。在讀小學(xué)時，我們做加法都采納豎式方法，如圖1。這樣，我們便利寫出兩個整數(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存儲被加數(shù)，b存儲加數(shù)，c存儲結(jié)果}vari,x:integer;begini:=1while(i<=a數(shù)組長度>0)or(i<=b數(shù)組的長度)dobeginx:=a[i]+b[i]+xdiv10;{第i位相加并加上次的進(jìn)位}c[i]:=xmod10;{存儲第i位的值}i:=i+1{位置指針變量}endend;通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：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高精度減法。從鍵盤讀入兩個正整數(shù)，求它們的差。 分析：類似加法，可以用豎式求減法。在做減法運算時，須要留意的是：被減數(shù)必需比減數(shù)大，同時須要處理借位。因此，可以寫出如下關(guān)系式ifa[i]<b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10endc[i]:=a[i]-b[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;{不考慮大小問題，先往高位借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高精度乘法。從鍵盤讀入兩個正整數(shù)，求它們的積。 分析：類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進(jìn)位，同時對每一位進(jìn)乘法運算時，必需進(jìn)行錯位相加，如圖3,圖4。856×25856×254280171221400圖3A3A2A1×B3B2B1C’4C’3C’2C’1C”5C”4C”3C”2C6C5C4C3C2C1圖4Ci=C’i+C”i+…由此可見，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;類似，高精度乘法的參考程序：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{對乘數(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.例４高精度除法。從鍵盤讀入兩個正整數(shù)，求它們的商（做整除）。 分析：做除法時，每一次上商的值都在０～９，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，接著做除法。因此，在做高精度除法時，要涉及到乘法運算和減法運算，還有移位處理。當(dāng)然，為了程序簡潔，可以避開高精度乘法，用0～9次循環(huán)減法取代得到商的值。這里，我們探討一下高精度數(shù)除以單精度數(shù)的結(jié)果，實行的方法是按位相除法。 參考程序： 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.實質(zhì)上，在做兩個高精度運算時候，存儲高精度數(shù)的數(shù)組元素可以不僅僅只保留一個數(shù)字，而實行保留多位數(shù)（例如一個整型或長整型數(shù)據(jù)等），這樣，在做運算（特殊是乘法運算）時，可以減少許多操作次數(shù)。例如圖5就是采納4位保存的除法運算，其他運算也類似。詳細(xì)程序可以修改上述例題予以解決，程序請讀者完成。示例：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)：知識目標(biāo)：如何利用程序就各種排列和組合實力目標(biāo)：排列組合的運用重點：求出n的全排列和從m中取n個的組合難點：算法的理解板書示意：求全排列的算法求組合數(shù)的算法授課過程：例5：有3個人排成一個隊列，問有多少種排對的方法，輸出每一種方案？分析：假如我們將3個人進(jìn)行編號，分別為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.上述狀況特別簡單，因為只有3個人，但當(dāng)有N個人時怎么辦？明顯用循環(huán)不能解決問題。下面我們介紹一種求全排列的方法。設(shè)當(dāng)前排列為P1P2,…,Pn，則下一個排列可按如下算法完成：1．求滿足關(guān)系式Pj-1<Pj的J的最大值，設(shè)為I，即I=max{j|Pj-1<Pj,j=2..n}2．求滿足關(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便是下一個排列。例：設(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的下一個排列。程序設(shè)計如下：programexam5;constmaxn=100;vari,j,m,t:integer;p:array[1..maxn]ofinteger;count:integer;{排列數(shù)目統(tǒng)計變量}beginwrite('m:');readln(m);fori:=1tomdobeginp[i]:=i;write(i)end;writeln;count:=1;repeat{求滿足關(guān)系式Pj-1<Pj的J的最大值，設(shè)為I}i:=m;while(i>1)and(p[i-1]>=p[i])dodec(i);ifi=1thenbreak; {求滿足關(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個人選取M個人出來做嬉戲，共有多少種取法？例如：N=4，M=2時，有12，13，14，23，24，34共六種。分析：因為組合數(shù)跟順序的選擇無關(guān)。因此對同一個組合的不同排列，只需取其最小的一個（即按從小到大排序）。因此，可以設(shè)計如下算法：1．最終一位數(shù)最大可達(dá)N，倒數(shù)第二位數(shù)最大可達(dá)N-1，…，依此類推，倒數(shù)第K位數(shù)最大可達(dá)N-K+1。若R個元素組合用C1C2…CR表示，且假定C1<C2<…<CR,CR<=N-R+I,I=1,2,…,R。2．當(dāng)存在Cj<N-R+J時，其中下標(biāo)的最大者設(shè)為I，即 I=max{J|Cj<N-R+J}，則作Ci:=Ci+1,及之對應(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 {初始化，建立第一個組合}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; {建立下一個組合}fori:=1tomdowrite(c[i]);writeln {輸出}end;End.第四課枚舉法課題：枚舉法目標(biāo)：知識目標(biāo)：枚舉算法的本質(zhì)和應(yīng)用實力目標(biāo)：枚舉算法的應(yīng)用！重點：利用枚舉算法解決實際問題難點：枚舉算法的次數(shù)確定板書示意：簡單枚舉（例7,例8,例9）利用枚舉解決邏輯推斷問題（例10,例11）枚舉解決競賽問題（例12,例13,例14）授課過程：所謂枚舉法,指的是從可能的解集合中一一枚舉各元素,用題目給定的檢驗條件判定哪些是無用的,哪些是有用的.能使命題成立,即為其解。一般思路：對命題建立正確的數(shù)學(xué)模型；依據(jù)命題確定的數(shù)學(xué)模型中各變量的變化范圍（即可能解的范圍）；利用循環(huán)語句,條件推斷語句逐步求解或證明；枚舉法的特點是算法簡單，但有時運算量大。對于可能確定解的值域又一時找不到其他更好的算法時可以采納枚舉法。例7：求滿足表達(dá)式A+B=C的全部整數(shù)解，其中A，B，C為1~3之間的整數(shù)。分析：本題特別簡單，即枚舉全部狀況，符合表達(dá)式即可。算法如下：forA:=1to3doforB:=1to3doforC:=1to3doifA+B=CthenWriteln(A,‘+’,B,‘=’,C);上例采納的就是枚舉法。所謂枚舉法，指的是從可能的解的集合中一一枚舉各元素，用題目給定的檢驗條件判定哪些是無用的，哪些是有用的。能使命題成立的，即為解。從枚舉法的定義可以看出，枚舉法本質(zhì)上屬于搜尋。但及隱式圖的搜尋有所區(qū)分，在采納枚舉法求解的問題時，必需滿足兩個條件：預(yù)先確定解的個數(shù)n；對每個解變量A1，A2，……，An的取值，其變化范圍需預(yù)先確定A1∈{X11，……，X1p}Ai∈{Xi1，……，Xiq}An∈{Xn1，……，Xnk}例7中的解變量有3個：A，B，C。其中A解變量值的可能取值范圍A∈{1，2，3}B解變量值的可能取值范圍B∈{1，2，3}C解變量值的可能取值范圍C∈{1，2，3}則問題的可能解有27個（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）}在上述可能解集合中，滿足題目給定的檢驗條件的解元素，即為問題的解。假如我們無法預(yù)先確定解的個數(shù)或各解的值域，則不能用枚舉，只能采納搜尋等算法求解。由于回溯法在搜尋每個可能解的枚舉次數(shù)一般不止一次，因此，對于同樣規(guī)模的問題，回溯算法要比枚舉法時間困難度稍高。例8給定一個二元一次方程aX+bY=c。從鍵盤輸入a,b,c的數(shù)值，求X在[0，100]，Y在[0，100]范圍內(nèi)的全部整數(shù)解。 分析：要求方程的在一個范圍內(nèi)的解，只要對這個范圍內(nèi)的全部整數(shù)點進(jì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.從上例可以看出，所謂枚舉法,指的是從可能的解集合中一一枚舉各元素,用題目給定的檢驗條件判定哪些是無用的,哪些是有用的.能使命題成立,即為其解。例9奇妙填數(shù)192384576將1～9這九個數(shù)字填入九個空格中。每一橫行的三個數(shù)字組成一個三位數(shù)。假如要使第二行的三位數(shù)是第一行的兩倍,第三行的三位數(shù)是第一行的三倍,應(yīng)怎樣填數(shù)。如圖6:圖6分析：本題目有9個格子，要求填數(shù)，假如不考慮問題給出的條件，共有9！=362880種方案，在這些方案中符合問題條件的即為解。因此可以采納枚舉法。但細(xì)致分析問題，明顯第一行的數(shù)不會超過400，事實上只要確定第一行的數(shù)就可以依據(jù)條件算出其他兩行的數(shù)了。這樣僅需枚舉400次。因此設(shè)計參考程序：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{滿足條件，并數(shù)字都由1~9組成}beginwriteln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.例10在某次數(shù)學(xué)競賽中,A,B,C,D,E五名學(xué)生被取為前五名。請據(jù)下列說法推斷出他們的詳細(xì)名次,即誰是第幾名？條件1:你假如認(rèn)為A,B,C,D,E就是這些人的第一至第五名的名次排列,便大錯。因為:沒猜對任何一個優(yōu)勝者的名次。也沒猜對任何一對名次相鄰的學(xué)生。條件2:你假如按D,A,E,C,B來排列五人名次的話,其結(jié)果是:說對了其中兩個人的名次。還猜中了兩對名次相鄰的學(xué)生的名次順序。分析：本題是一個邏輯推斷題，一般的邏輯推斷題都采納枚舉法進(jìn)行解決。5個人的名次分別可以有5！=120種排列可能，因為120比較小，因此我們對每種狀況進(jìn)行枚舉，然后依據(jù)條件推斷哪些符合問題的要求。依據(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沒猜對一個人的名次}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猜對了兩個人的名次}IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2ThenContinue;{ABCDE沒猜對一對相鄰名次}If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)ThenContinue;{DAECB猜對了兩對相鄰人名次}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：來自不同國家的四位留學(xué)生A,B,C,D在一起交談,他們只會中,英,法,日四種語言中的2種,狀況是,沒有人既會日語又會法語;A會日語,但D不會,A和D能相互交談,B不會英語,但A和C交談時卻要B當(dāng)翻譯,B,C,D三個想相互交談,但找不到共同的語言,只有一種語言3人都會,編程確定A,B,C,D四位留學(xué)生各會哪兩種語言。分析：將中,法,日,英四種語言分別定義為CHN,FRH,JPN,ENG,則四種語言中取兩種共有(CHN,ENG),（CHN,FRH）,(CHN,JPN),(ENG,FRH),(ENG,JPN),(FRH,JPN)六種組合，分別定義為1,2,3,4,5,6。據(jù)已知，沒有人既會日語又會法語;因此，組合6不會出現(xiàn)；A會日語，所以A只可能等于3,5；D不會日語,所以D只可能等于1,2,4；B不會英語，所以B只可能等于2,3；見下表。假如我們對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交談時卻要B當(dāng)翻譯}Can2:=(No[A]*No[C]=[])and(No[A]*No[B]<>[])and(No[B]*No[C]<>[]);{B,C,D三個想相互交談,但找不到共同的語言}Can3:=No[B]*No[C]*No[D]=[];{只有一種語言3人都會}Can4:=Ord(Might(CHN))+Ord(Might(ENG))+Ord(Might(FRH))+Ord(Might(JPN))=1;ifCan1andCan2andCan3andCan4thenPrint(A,B,C,D);end;end.例12古紙殘篇在一位數(shù)學(xué)家的藏書中夾有一張古舊的紙片。紙片上的字早已模糊不清了,只留下曾經(jīng)寫過字的痕跡,依稀還可以看出它是一個乘法算式,如圖7所示。這個算式上原來的數(shù)字是什么呢？夾著這張紙片的書頁上,“素數(shù)”兩個字被醒目的劃了出來。莫非說,這個算式及素數(shù)有什么關(guān)系嗎？有人對此作了深入的探討,果真發(fā)覺這個算式中的每一個數(shù)字都是***×***************圖7素數(shù),***×***************圖7分析：事實上，只要知道乘數(shù)和被乘數(shù)就可以寫出乘法算式，所以我們可以枚舉乘數(shù)及被乘數(shù)的每一位。然后再推斷是不是滿足條件即可。計算量是45=1024，對于計算機(jī)來說，計算量特別小。參考程序：ProgramExam12;ConstSu:Array[1..4]OfLongint=(2,3,5,7);VarA1,A2,A3,B1,B2,X,Y,S:Longint;FunctionKx(S:Longint):Boolean;{推斷一個數(shù)是不是都是由素數(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;{它們分別是兩個四位數(shù)，一個五位數(shù)}If(Kx(X*Su[B1])=False)Or(Kx(X*Su[B2])=False)Or(Kx(X*(Su[B1]*10+Su[B2]))=False)ThenContinue;{滿足其他數(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：時鐘問題（IOI94-4）在圖8所示的3*3矩陣中有9個時鐘，我們的目標(biāo)是旋轉(zhuǎn)時鐘指針，使全部時鐘的指針都指向12點。允許旋轉(zhuǎn)時鐘指針的方法有9種，每一種移動用一個數(shù)字號（1，2，…，9）表示。圖2-11示出9個數(shù)字號及相應(yīng)的受限制的時鐘，這些時鐘在圖中以灰色標(biāo)出，其指針將順時針旋轉(zhuǎn)90度。圖8九種時鐘狀態(tài)圖9九種被圖8九種時鐘狀態(tài)圖9九種被限制方式由輸入文件INPUT.TXT讀9個數(shù)碼，這些數(shù)碼給出了9個時鐘時針的初始位置。數(shù)碼及時刻的對應(yīng)關(guān)系為：0——12點1——3點2——6點3——9點圖2-11中的例子對應(yīng)下列輸入數(shù)據(jù)：330222212輸出數(shù)據(jù)：將一個最短的移動序列（數(shù)字序列）寫入輸出文件OUTPUT.TXT中，該序列要使全部的時鐘指針指向12點，若有等價的多個解，僅需給出其中一個。在我們的例子中，相應(yīng)的OUTPUT.TXT的內(nèi)容為：5849輸入輸出示例：INPUT.TXTOUTPUT.TXT3302222125489詳細(xì)的移動方案如圖10所示。圖10示例移動方案分析：圖10示例移動方案首先，我們分析一下表示時鐘時針初始位置的數(shù)碼j（0≦j≦3）及時刻的對應(yīng)關(guān)系：0——12點1——3點2——6點3——9點每移動一次，時針將順時針旋轉(zhuǎn)90度。由此我們可以得出：對于隨意一個時鐘i（1≦i≦9）來說，從初始位置j動身至少須要Ci=（4-j）mod4次操作，才能使得時針指向12點。而對每種移動方法要么不采納，要么采納1次,2次或3次，因為操作四次以后，時鐘將重復(fù)以前狀態(tài)。因此，9種旋轉(zhuǎn)方案最多產(chǎn)生49個狀態(tài)。移動方案選取及順序無關(guān)。樣例中，最佳移動序列為5849，同樣4589序列也可達(dá)到目標(biāo)。因此，求解過程中可以直接選取序列中從小至大排列的移動序列即可。設(shè)pi表示第i種旋轉(zhuǎn)方法的運用次數(shù)（0≦pi≦3，1≦i≦9）。則可能的解的集合為{P1，P2，……，P9}，該集合共含49個狀態(tài)。從圖2.11中，我們可以分析出9個時鐘分別被哪些方法所限制，見下表：時鐘號限制時鐘方案檢驗條件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è)計如下枚舉算法：forp1:=0to3do forp2:=0to3doforp9:=0to3do ifc1滿足時鐘1andc2滿足時鐘2and...andc9滿足時鐘9then打印解路徑；明顯，上述枚舉算法枚舉了全部49=262144個狀態(tài)，運算量和運行時間頗大。我們可以實行縮小可能解范圍的局部枚舉法，僅枚舉第1,2,3種旋轉(zhuǎn)方法可能取的43個狀態(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代入下述三個檢驗條件C5=(P1+P3+P5+P7+P9)mod4C7=(P4+P7+P8)mod4C9=(P6+P8+P9)mod4一一枚舉，以求得準(zhǔn)確解。由此可見，上述局部枚舉的方法（枚舉狀態(tài)數(shù)為43個）比較全部枚舉的方法（枚舉狀態(tài)數(shù)為49個）來說，由于大幅度削減了枚舉量，減少運算次數(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個時鐘從初始時間到12點的最少移動次數(shù)}{Map:最短移動序列中，數(shù)字（（I+2）mod3）*3+J的次數(shù)}procedureInit;varI,J:Integer;beginAssign(Input,Inp);Reset(Input);forI:=1to3do{讀入9個時鐘指針的初始位置，求出每個時鐘從初始到12點的最少移動次數(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; {計算和輸出最短移動序列}varI,J,K:Integer;begin{枚舉最短移動序列中數(shù)字1,2,3的個數(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個數(shù)的當(dāng)前值，得出數(shù)字4~9的個數(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的個數(shù)滿足檢驗條件，則輸出方案}forI:=1to3doforJ:=1to3doforK:=1toMap[I,J]doWrite((I-1)*3+J);Exit; {找到一個解后退出}end;end;Writeln('NoAnswer!');Close(Output);end;beginInit; Main; end.在上例中，由于事先能夠解除那些明顯不屬于解集的元素，使得算法效率特別高。而減少重復(fù)運算,力求提前計算所需數(shù)據(jù),運用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)進(jìn)行算法優(yōu)化等方法也是優(yōu)化枚舉算法的常用手段。例14：最佳巡游線路（NOI94）某旅游區(qū)的街道成網(wǎng)格狀（圖2.13）。其中東西向的街道都是旅游街，南北向的街道都是林蔭道。由于游客眾多，旅游街被規(guī)定為單行道，游客在旅游街上只能從西向東走，在林陰道上則既可從南向北走，也可以從北向南走。阿龍想到這個旅游區(qū)游玩。他的好友阿福給了他一些建議，用分值表示全部旅游街相鄰兩個路口之間的街道值得巡游的程度，分值時從-100到100的整數(shù)，全部林陰道不打分。全部分值不可能全是負(fù)分。圖11某旅游區(qū)街道示例圖例如圖11是被打過分的某旅游區(qū)的街道圖：圖11某旅游區(qū)街道示例圖阿龍可以從任一個路口開始巡游，在任一個路口結(jié)束巡游。請你寫一個程序，幫忙阿龍找一條最佳的巡游線路，使得這條線路的全部分值總和最大。輸入數(shù)據(jù)：輸入文件是INPUT.TXT。文件的第一行是兩個整數(shù)M和N，之間用一個空格符隔開，M表示有多少條旅游街（1≦M≦100），N表示有多少條林陰道（1≦M≦20001）。接下來的M行依次給出了由北向南每條旅游街的分值信息。每行有N-1個整數(shù)，依次表示了自西向東旅游街每一小段的分值。同一行相鄰兩個數(shù)之間用一個空格隔開。輸出數(shù)據(jù)：輸出文件是OUTPUT.TXT。文件只有一行，是一個整數(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個段，每一段由M條旅游街的對應(yīng)段成，即第J段成為{L1J，L2J，……，LMJ}（1≦J≦N–1）。由于巡游方向規(guī)定橫向自西向東，縱向即可沿林陰道由南向北，亦可由北向南，而橫行的街段有分值，縱行無分值，因此最佳巡游路現(xiàn)必需具備如下三個特征：來自若干個連續(xù)的段，每一個段中取一個分值；每一個分值是所在段中最大的；起點段和終點段隨意，但途經(jīng)段的分值和最大。設(shè)Li為第I個段中的分值最大的段。即Li=Max{L1I，L2I，……，LMI}（1≦I≦N–1）。例如對于樣例數(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ǔ)，我們便可以通過圖示描述解題過程，見圖12。圖12求解過程示例圖我們把將段設(shè)為頂點，所在段的最大分值設(shè)為頂點的權(quán)，各頂點按自西向東的順序相連，組成一條巡游路線。明顯，假如確定西端為起點,東段為終點，則這條巡游路線的總分值最大。圖12求解過程示例圖問題是某些段的最大分值可能是負(fù)值，而最優(yōu)巡游路線的起點和終點隨意，在這種狀況下，上述巡游路線就不肯定最佳了。因此，我們只能枚舉這條巡游路線的全部可能的子路線，從中找出一條子路線II+1……J（1≦I<J≦N–1），使得經(jīng)過頂點的權(quán)和LI+LI+1+……+LJ最大。設(shè)Best為最佳巡游路線的總分值，初始時為0；Sum為當(dāng)前巡游路線的總分值。我們可以得到如下算法：Best:=0;Sum:=0;forI:=1toN–2doforJ:=I+1toN–1dobeginSum:=LI+……+LJ;ifSum>BestthenBest:=Sum;end明顯，這個算法的時間困難度為O（N2）。而N在1~20001之間，時間困難度比較高。于是，我們必需對這個算法進(jìn)行優(yōu)化。仍舊從頂點1開始枚舉最優(yōu)路線。若當(dāng)前子路線延長至頂點I時發(fā)覺總分值Sum≦0，則應(yīng)放棄當(dāng)前子路線。因為無論LI+1為何值，當(dāng)前子路線延長至頂點I+1后的總分值不會大于LI+1。因此應(yīng)當(dāng)從頂點I+1開始重新考慮新的一條子路線。通過這種優(yōu)化，可以使得算法的時間困難度降到了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; {描述每個段的最大分值}procedureInit;varI,J,K:Integer;Buffer:array[1..40960]ofChar; {文件緩沖區(qū)}beginAssign(Input,Inp);Reset(Input);SetTextBuf(Input,Buffer); {開拓文件緩沖區(qū)}Readln(M,N); {讀入旅游街?jǐn)?shù)和林陰道數(shù)}FillChar(Score,Sizeof(Score),$80); {初始化各段的最大分值}forI:=1toMdo {計算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)計當(dāng)前巡游路線的總分值}ifSum>BestthenBest:=Sum; {若當(dāng)前最佳，則登記}ifSum<0thenSum:=0;{若總分值<0，則考慮一條新路線}end;end;beginInit; {輸入數(shù)據(jù)}Main; {主過程}Out; {輸出}end.第五課遞歸及回溯法課題：遞歸及回溯目標(biāo)：知識目標(biāo)：遞歸概念及利用遞歸進(jìn)行回溯實力目標(biāo)：回溯算法的應(yīng)用重點：回溯算法難點：回溯算法的理解板書示意：遞歸的理解利用遞歸回溯解決實際問題（例14,例15,例16,例17,例18）利用回溯算法解決排列問題（例19）授課過程：什么是遞歸？先看大家都熟識的一個民間故事：從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說，從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說……。象這樣，一個對象部分地由它自己組成，或者是按它自己定義，我們稱之是遞歸。例如，我們可以這樣定義N!，N!=N*(N-1)!，因此求N!轉(zhuǎn)化為求(N-1)!。這就是一個遞歸的描述。因此，可以編寫如下遞歸程序：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è)一個未知函數(shù)f，用其自身構(gòu)成的已知函數(shù)g來定義：為了定義f(n)，必需先定義f(n-1)，為了定義f(n-1)，又必需先定義f(n-2)，…，上述這種用自身的簡單狀況來定義自己的方式稱為遞歸定義。遞歸有如下特點： ①它直接或間接的調(diào)用了自己。 ②肯定要有遞歸終止的條件，這個條件通常稱為邊界條件。及遞推一樣，每一個遞推都有其邊界條件。但不同的是，遞推是由邊界條件動身，通過遞推式求f(n)的值，從邊界到求解的全過程特別清晰；而遞歸則是從函數(shù)自身動身來達(dá)到邊界條件，在通過邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果（局部變量和返回地址）保存起來，直至求出遞歸邊界值f(0)=a。然后返回調(diào)用函數(shù)。返回的過程中，中間結(jié)果相繼出棧復(fù)原，f(1)=g(1,a)f(2)=g(2,f(1))……直至求出f(n)=g(n,f(n-1))。遞歸按其調(diào)用方式分直接遞歸——遞歸過程P直接自己調(diào)用自己；間接遞歸——即P包含另一過程D，而D又調(diào)用P；由此可見，遞歸算法的效率往往很低，費時和費內(nèi)存空間。但是遞歸也有其特長，它能使一個蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)困難的程序簡潔精煉，增加可讀性。特殊是在難于找到從邊界到解的全過程的狀況下，假如把問題進(jìn)一步，其結(jié)果仍維持原問題的關(guān)系，則采納遞歸按其調(diào)用方式分直接遞歸——遞歸過程P直接自己調(diào)用自己；間接遞歸——即P包含另一過程D，而D又調(diào)用P；遞歸算法適用的一般場合為：①數(shù)據(jù)的定義形式按遞歸定義。如裴波那契數(shù)列的定義：對應(yīng)的遞歸程序為functionfib(n:Integer):Integer;beginifn=0thenfib:=1 {遞歸邊界}elseifn=1thenfib:=2 {遞歸邊界}elsefib:=fib(n–2)+fib(n–1); {遞歸}end;這類遞歸問題可轉(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)）按遞歸定義。如樹的遍歷，圖的搜尋等。③問題解法按遞歸算法實現(xiàn)。例如回溯法等。對于②和③，可以用堆棧結(jié)構(gòu)將其轉(zhuǎn)換為非遞歸算法，以提高算法的效率以及減少內(nèi)存空間的奢侈。下面以經(jīng)典的N皇后問題為例，看看遞歸法是怎樣實現(xiàn)的，以及比較遞歸算法和非遞歸算法效率上的差別。例15：N皇后問題圖14八皇后的兩組解在N*N的棋盤上放置N個皇后而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置2個皇后），編程求解全部的擺放方法。圖14八皇后的兩組解分析：由于皇后的擺放位置不能通過某種公式來確定，因此對于每個皇后的擺放位置都要進(jìn)行摸索和訂正，這就是“回溯”的思想。在N個皇后未放置完成前，擺放第I個皇后和第I+1個皇后的摸索方法是相同的，因此完全可以采納遞歸的方法來處理。下面是放置第I個皇后的的遞歸算法：ProcedureTry(I:integer)；{搜尋第I行皇后的位置}var j:integer;beginifI=n+1then輸出方案；forj:=1tondo if皇后能放在第I行第J列的位置thenbegin放置第I個皇后；對放置皇后的位置進(jìn)行標(biāo)記；Try（I+1）對放置皇后的位置釋放標(biāo)記； End;End;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; {皇后個數(shù)}procedureOut; {輸出方案}varI:Integer;beginInc(Total);Write(Total:3,‘:’);forI:=1toNdoWrite(X[I]:3);Writeln;end;procedureTry(I:Integer); {搜尋第I個皇后的可行位置}varJ:Integer;beginifI=N+1thenOut;{N個皇后都放置完畢，則輸出解}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皇后問題的非遞歸算法的程序：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; {皇后個數(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]); {找尋一個可以放置的位置}ifX[K]<=NthenifK=NthenOutelsebeginA[X[K]]:=False;B[X[K]+K]:=False;C[X[K]–K]:=False;Inc(K);X[K]:=0; {接著放置下一個皇后}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)含困難關(guān)系的問題，結(jié)構(gòu)變得簡潔精煉。看看下面的例題。例16:新漢諾（hanoi）塔問題設(shè)有n各大小不等的中空圓盤，按從小到大的順序從1到n編號。將這n個圓盤隨意的迭套在三根立柱上，立柱的編號分別為A,B,C，這個狀態(tài)稱之為初始狀態(tài)。問題要求找到一種步數(shù)最少的移動方案，使得從初始狀態(tài)轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)。移動時有如下要求：一次只移動一個盤；不允許把大盤移到小盤上邊；輸入：輸入文件第1行是狀態(tài)中圓盤總數(shù)；第2~4行是分別是初始狀態(tài)中A,B,C柱上的圓盤個數(shù)和從上到下每個圓盤的編號；第5~7行是分別是目標(biāo)狀態(tài)A,B,C柱上的圓盤個數(shù)和從上到下每個圓盤的編號。輸出：每行寫一步的移動方案，格式為：MoveI圓盤formP柱toQ柱。最終輸出最少步數(shù)。輸入樣例（如圖）：6312324516061234560樣例所描述的狀態(tài)如圖15所示。圖15樣例圖圖15樣例圖輸出樣例：分析：要