回溯算法設(shè)計(jì)

1、rogram p4(input，output)；procedure rever； var c：char； begin read(c)； if c! then rever; write(c)； end；begin 主程序 rever；end運(yùn)行：輸入 hey!輸出 !yeh。c 是過程rever的局部變量。每一次遞歸調(diào)用，都要為局部變量重新分配單元，因此各層的變量c實(shí)際上是不同的量，它們分別用于保存執(zhí)行本層調(diào)用時的輸入值。 例3：輸入一串以!結(jié)束的字符，按逆序輸出。1procedure rever； var c：char； begin read(c)； if c! then rever; wri

2、te(c)； end；hey!c=hprocedure rever； var c：char； begin read(c)； if c! then rever; write(c)； end；procedure rever； var c：char； begin read(c)； if c! then rever; write(c)； end；procedure rever； var c：char； begin read(c)； if c! then rever; write(c)； end；c=ec=yc=!2 程序中的遞歸過程圖解如下： 整個遞歸過程可視為由往返雙向“運(yùn)動”組成，先是逐層遞進(jìn)，逐

3、層打開新的“篇章”，（有可能無具體計(jì)算值）當(dāng)最終遞進(jìn)達(dá)到邊界，執(zhí)行完本“層”的語句，才由最末一“層”逐次返回到上“層”，每次返回均帶回新的計(jì)算值，直至回到第一次由主程序調(diào)用的地方，完成對原問題的處理。 procedure num(x: integer） begin if x=5 then a:=10 else begin num(x+1); a:=a+2 end end;3回溯4計(jì)算機(jī)求解的過程在狀態(tài)空間尋找機(jī)內(nèi)解, 可以看成是從初始狀態(tài)出發(fā),搜索目標(biāo)狀態(tài)(解所在的狀態(tài))的過程。狀態(tài)空間初始狀態(tài)目標(biāo)狀態(tài)搜索搜索的過程可描述為：S0S1Sn，其中S0為初態(tài)，Sn為終態(tài)。或者說(S0)且(Sn)，

4、這里稱為初始條件，稱為終止條件。5求解是狀態(tài)空間的搜索求解的過程可以描述為對狀態(tài)空間的搜索S0S11S12S1k Sn1SniSnm其中S0為初始狀態(tài)，不妨設(shè)Sni為終止?fàn)顟B(tài)S0Sni問題求解就是通過搜索，尋找出一條從初始狀態(tài)S0到終止?fàn)顟B(tài)Sni的路徑。6幾種搜索方法狀態(tài)空間的搜索實(shí)際上是一種樹/DAG（Directed Acyclic Graph ）的搜索，常用的方法有：廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索從初始狀態(tài)開始，逐層地進(jìn)行搜索。從初始狀態(tài)開始，逐個分枝地進(jìn)行搜索。從初始狀態(tài)開始，每次選擇最有可能達(dá)到終止?fàn)顟B(tài)的結(jié)點(diǎn)進(jìn)行搜索。7三種搜索的優(yōu)劣之處一般來說，三種搜索方法各有優(yōu)劣之處：廣度優(yōu)

5、先搜索和深度優(yōu)先搜索優(yōu)點(diǎn)：一定能找到解；缺點(diǎn)：時間復(fù)雜性大。啟發(fā)式搜索優(yōu)點(diǎn)：一般來說能較快地找到解，即其時間復(fù)雜性小；缺點(diǎn)：需要設(shè)計(jì)一個評價函數(shù)，并且評價函數(shù)的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣。8當(dāng)需要找出問題的解集，或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。在問題的解空間樹中，回溯法按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；

6、否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘?回溯法的算法框架5.1.1 問題的解空間應(yīng)用回溯法解問題時，首先應(yīng)明確定義問題的解空間。問題的解空間應(yīng)至少包含問題的一個(最優(yōu))解。通常將解空間組織成樹或圖的形式。問題的解向量：回溯法希望一個問題的解，能夠表示成一個n元式(x1,x2,xn)的形式。顯約束：對分量xi的取值限定隱約束：為滿足問題的解，而對不同分量之間施加的約束。解空間：對于問題的一個實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個解空間。例如，對于有n種可選物品的0-1背包問題，其解空間由長度為n的0-1向量組成。n=3時的0-1背包問題用完全二叉樹表示的解空間10

7、回溯法的基本思想擴(kuò)展結(jié)點(diǎn):一個正在產(chǎn)生兒子的結(jié)點(diǎn)活結(jié)點(diǎn):一個自身已生成但其兒子還沒有全部生成的節(jié)點(diǎn)死結(jié)點(diǎn):一個所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)深度優(yōu)先的問題狀態(tài)生成法：如果對一個擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個兒子（如果存在）寬度優(yōu)先的問題狀態(tài)生成法：在一個擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)?；厮莘ǎ簽榱吮苊馍赡切┎豢赡墚a(chǎn)生最佳解的問題狀態(tài)，要不斷地利用限界函數(shù)(bounding function)來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問題的計(jì)算量。具有限界函數(shù)的深度優(yōu)

8、先生成法稱為回溯法。11基本思想：確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)，以深度優(yōu)先的方式搜索整個解空間。開始結(jié)點(diǎn)就成為一個活結(jié)點(diǎn)，同時也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)，搜索向縱深方向移至一個新結(jié)點(diǎn)。這個新結(jié)點(diǎn)就成為一個新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時，應(yīng)往回移動（回溯）至最近的一個活結(jié)點(diǎn)處，并使這個活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時為止。 12可重復(fù)的全排列假設(shè)是由1-3組成的3位數(shù)program expl;var

9、i,j,k:integer;begin for i:=1 to 3 do for j:=1 to 3 do for k:=1 to 3 do writeln(i, ,j, ,k);end.13如果是5位呢？更多位呢？不定位呢？14program expl_dg;var a:array1.10 of integer;procedure print;var i:integer;begin for i:=1 to 3 do write(ai, ); writeln;end;procedure work(x:integer);var i:integer;begin if x3 then begin p

10、rint ;exit;end; for i:=1 to 3 do begin ax:=i; work(x+1); end;end;begin work(1);end.試一試，如果n位，nn then begin print;exit;end; for i:=1 to n do if try(x,i)=true then begin ax:=i; work(x+1); end;end;begin readln(n); work(1);end.剪枝16關(guān)于回溯法搜索的遞歸程序框架全排列算法的遞歸解法為例做個介紹：constn=5;vara:array1.nofinteger;記錄搜索的解e:arr

11、ay1.nofboolean;標(biāo)記數(shù)組用于記錄i是否已經(jīng)用過 初始狀態(tài)都是falseprocedureprint;vari:integer;beginfori:=1tondowrite(ai,); end;proceduresearch(deep:integer);deep是搜索深度vari:integer;beginifdeepnthenbeginprint;輸出結(jié)果exit;退出本層，回溯end;fori:=1tondoifei=falsethenbegin如果i沒有用過,限定條件ei:=true;標(biāo)記為用過iadeep:=i;記錄該位置的元素為isearch(deep+1);搜索deep

12、+1個位置上的元素ei:=false;回溯之后取消i元素的已用標(biāo)記end;end;在很多題目中，限定條件需要用鄰接矩陣等數(shù)據(jù)表示，這個限定條件就是輸出結(jié)果中需要滿足的條件，具體的可以根據(jù)題目來修改。17var i,k,n:integer; x:array1.9 of integer;function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if( )then begin place:=false; break end ; end;procedure print; var i:i

13、nteger; begin for i:=1 to n do write(xi, ); writeln; end;數(shù)字排列問題的遞歸實(shí)現(xiàn)xi=xkprocedure try(k:integer); var i :integer; begin if( )then begin print; exit; end; for i:=1 to n do begin ( ); if( )then try(k+1) end end;begin readln(n); try(1);end.knxk:=iplace(k)18四色問題有形如下列圖形的地圖，圖中每一塊區(qū)域代表一個省份，現(xiàn)請你用紅（1）、蘭（2）、黃（

14、3）、綠（4）四種顏色給這些省份填上顏色，要求每一省份用一種顏色，且任意兩個相鄰省份的顏色不能相同，請給出一種符合條件的填色方案。地圖用無向圖的形式給出，每個省份代表圖上的一個頂點(diǎn)，邊代表兩個省份是相鄰的。返回到題目列表19四色問題輸入70 1 0 0 0 0 11 0 1 1 1 1 10 1 0 1 0 0 00 1 1 0 1 0 00 1 0 1 0 1 00 1 0 0 1 0 11 1 0 0 0 1 0輸出1 2 1 3 1 3 41234567返回到題目列表20四色問題要得到一種可行的填色方案，比較直接的做法就是一個省一個省的填色，在填色的過程中去檢查是否和周圍省份的顏色存在沖

15、突。從第一個省份開始，對每個省份依次嘗試四種顏色，判斷當(dāng)然選擇的顏色是否和相鄰的省份相同。若都不相同，則將此省份填上當(dāng)前的顏色。若存在相同，則取下一種顏色繼續(xù)嘗試。若四種顏色都不能填上，則退回上一個省份并選擇下一種顏色繼續(xù)嘗試。當(dāng)最后一個省份也被填色后就找到一組可行解。返回到題目列表21四色問題procedure search(m: integer); / 遞歸搜索第m個省份begin if m n then / 是否所有省份都已經(jīng)填色 begin write(s1); / 已全部填色，輸出結(jié)果，終止程序 for j := 2 to n do write( , sj); writeln; ha

16、lt end else / 還未全部填色 for j := 1 to 4 do / 依次用四種顏色對當(dāng)前省份填色 begin if 可以 then 同相鄰的塊沒有色彩沖突 begin / 沒有沖突 sm := j; / 記錄當(dāng)前省份顏色 search(m + 1); / 遞歸檢查下一個省份 end; end;end;n塊，m代表當(dāng)前在填第幾塊22以一個 m*n的長方陣表示迷宮，0和1 分別表示迷宮中的通路和障礙（如下圖所示）。設(shè)計(jì)一個程序，對任意設(shè)定的迷宮，如果只能按上下左右四個方向移動，求出一條從入口到出口的通路?；虻贸鰶]有通路的結(jié)論。在方陣中，允許運(yùn)動的方向?yàn)樯舷伦笥?，因此，對于每個狀態(tài)，

17、都有四個方向可以擴(kuò)展搜索，為了簡化程序，我們可以設(shè)計(jì)增量數(shù)組描述不同的運(yùn)動方向。另外，為了回避邊沿位置移動方向的限制（如上邊沿的位置不能再向上移動等），可以對方陣進(jìn)行擴(kuò)充，增加一圈且有障礙。如圖所示。迷宮問題23const maxm=10; maxn=10;const dx:array1.4 of integer=(-1,1,0,0); 上下左右方向 dy:array1.4 of integer=(0,0,-1,1);type address=record x,y:integer; end;var a:array0.maxm+1,0.maxn+1 of integer;step:array1.

18、maxm*maxn of address;m,n,x0,y0,x1,y1:integer;procedure init;var i,j:integer;begin readln(m,n); for i:=0 to m+1 do for j:=0 to n+1 do ai,j:=1; for i:=1 to m do for j:=1 to n do read(ai,j); readln(x0,y0); readln(x1,y1); step1.x:=x0; step1.y:=y0;end;procedure print(steps:integer);var i:integer;begin fo

19、r i:=1 to steps-1 do write(,stepi.x,stepi.y,)-); writeln(,stepsteps.x,stepsteps.y,); halt;end;procedure try(i:integer);var j,x,y:integer;beginfor j:=1 to 4 do begin x:=stepi-1.x+dxj; y:=stepi-1.y+dyj; if ax,y=0 then begin stepi.x:=x; stepi.y:=y; ax,y:=-1; if (x=x1) and (y=y1) then print(i) else try(

20、i+1); ax,y:=0; end; end;end;begin init; ax0,y0:=1;try(2);end.2425問題描述 在nn的國際象棋盤上，放置n個皇后，使任何一個皇后都不能吃掉另一個,要使任何一個皇后都不能吃掉另一個，需滿足的條件是：同一行、同一列、同一對角線上只能有一個皇后。求放置方法. 如:n=4時,有以下2種放置方法.N皇后問題輸出：2 4 1 33 1 4 226n皇后問題返回到題目列表27n皇后問題的解空間就應(yīng)該是1n全排列的一部分。解空間的長度是n。解空間的組織形式是一棵n叉樹，一個可行的解就是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的一條路徑?？刂撇呗詣t是當(dāng)前皇后與前面所有的皇

21、后都不同列和不同對角線。返回到題目列表28var x:array1.n of integer; a:array1.n of boolean; 列控制標(biāo)志：true：可以放，false：不能放 b:array2.2*n of boolean; 左上右下方斜線控制標(biāo)志，true：可以放，false：不能放 c:array1-n.n-1of boolean; 左下右上方斜線控制標(biāo)志，true：可以放，false：不能放初始時： fillchar(x,sizeof(x),0); fillchar(a,sizeof(a),true); fillchar(b,sizeof(b),true); fillch

22、ar(c,sizeof(c),true);1 1*1 21 31 42 12 22 3*2 4*3 13 23 33 44 14 2*4 34 429procedure try(i:integer); var j:integer; begin if i=n+1 then print else for j:=1 to n do if aj and bi+j and ci-j then begin xi:=j; aj:=false; 列控制標(biāo)志 bi+j:=false; 左上右下方斜線控制標(biāo)志 ci-j:=false; 左下右上方斜線控制標(biāo)志 try(i+1); 如果不能遞歸進(jìn)行，既aj and

23、bi+j and ci-j=false： 無法放置i+1個皇后，說明當(dāng)前皇后i放置不正確，要回溯，消除標(biāo)志 aj:=true; bi+j:=true; ci-j:=true end; end;begintry(1)end.30四皇后問題的遞歸實(shí)現(xiàn)const n=;var i,j,k:integer;x:array1.n of integer; 保存第i個皇后的列號function place(k:integer):boolean; var i:integer; begin place:=true; for i:=1 to k-1 do if(xi=xk)or(abs(xi-xk)=abs(i-

24、k) then place:=false; end;procedure print; var i:integer; begin for i:=1 to n do write(xi:4); writeln; end;procedure try(k:integer); var i:integer; begin if( ) then begin print; ( ) end; for i:=( )do begin ( ); if place(k) then( ); end; end ;begin try(1);擺放第一個皇后end.k=n+1xk:=itry(k+1)1 to n exit 皇后序號

25、擺放下一個皇后因?yàn)閺牡趇個皇后到第i+1個皇后的擺放方法是相同的,所以可以用遞歸的方法.31跳馬問題在nm棋盤上有一中國象棋中的馬：馬走日字；馬只能往右走。請你找出一條可行路徑，使得馬可以從棋盤的左下角（1，1）走到右上角（n，m）。返回到題目列表32跳馬問題輸入：9 5輸出：(1,1)-(3,2)-(5,1)-(6,3)-(7,1)-(8,3)-(9,5)返回到題目列表33跳馬問題馬走日字，當(dāng)馬一開始在黃點(diǎn)時，它下一步可以到達(dá)的點(diǎn)有以下的八個，但由于題目規(guī)定了只能往右走的限制，所以它只能走到四個綠色點(diǎn)之一。34跳馬問題當(dāng)馬一開始位于左下角的時候，根據(jù)規(guī)則，它只有兩條線路可以選擇（另外兩條超出

26、棋盤的范圍），我們無法預(yù)知該走哪條，故任意選擇一條，到達(dá)A1。AA1A235跳馬問題當(dāng)?shù)竭_(dá)A1點(diǎn)后，又有三條線路可以選擇，于是再任意選擇一條，到達(dá)B1。從B1再出發(fā)，又有兩條線路可以選擇，先選一條，到達(dá)C1。AA1A2B1B2B3C1C236跳馬問題從C1出發(fā)，可以有三條路徑，選擇D1。但到了D1以后，我們無路可走且D1也不是最終目標(biāo)點(diǎn)，因此，選擇D1是錯誤的，我們退回C1重新選擇D2。同樣D2也是錯誤的。再回到C1選擇D3。D3只可以到E1，但E1也是錯誤的。返回D3后，沒有其他選擇，說明D3也是錯誤的，再回到C1。此時C1不再有其他選擇，故C1也是錯誤的，退回B1，選擇C2進(jìn)行嘗試。AA1

27、A2B1B2B3C1C2D1D2D3E137跳馬問題從C2出發(fā)，有四條路徑可以選擇，選擇D4，從D4出發(fā)又有兩條路徑，選擇E1錯誤，返回D4選擇E2，從E2出發(fā)有兩條路徑，先選擇F1錯誤，返回E2選擇B，而B恰好是我們要到達(dá)的目標(biāo)點(diǎn)，至此，一條路徑查找成功。AA1A2B1B2B3C2E2BD4E1F138跳馬問題從上面的分析我們可以得知：在無法確定走哪條線路的時候，任選一條線路進(jìn)行嘗試；當(dāng)從某點(diǎn)出發(fā)，所有可能到達(dá)的點(diǎn)都不能到達(dá)終點(diǎn)時，說明此點(diǎn)是一個死節(jié)點(diǎn)，必須回溯到上一個點(diǎn)，并重新選擇一條新的線路進(jìn)行嘗試。39為了描述路徑，我們最直接的方法就是記錄路徑上所有點(diǎn)的坐標(biāo)。但比較繁瑣。如果我對馬可以

28、走到的四個點(diǎn)都編上號（方向），那么我們很容易得到每一個方向上兩個坐標(biāo)和原位置的關(guān)系。同時，四個方向都有了編號，那么在選擇路徑的時候也就可以不采用任選的方式了，只需按照編號依次嘗試就可以了。401234增量數(shù)組：dx = (1, 2, 2, 1)dy = (-2, -1, 1, 2)若馬所處的位置為(x,y)，則其下一步可以到達(dá)的四個位置分別是(x+1, y-2)，(x+2, y-1)，(x+2, y+1)，(x+1, y+2)。在使用增量數(shù)組后，只要知道方向t，下一步的位置就是(x+dxt, y+dyt)。41為了判斷棋子是否落在棋盤上，我們還必須知道當(dāng)前棋子（擴(kuò)展節(jié)點(diǎn)）的位置信息。而用一系列

29、的方向來表示就比較麻煩，因此，我們另外使用兩個變量來保存當(dāng)前棋子的坐標(biāo)。但這時千萬要注意的是一定要在回溯的時候，修改當(dāng)前棋子的坐標(biāo)。跳馬問題的解空間是從左下角到右上角的所有路徑。解空間的長度是所有路徑中最長的路徑的長度。解空間的組織形式是一棵四叉樹，一個可行的解就是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的一條路徑?？刂撇呗詣t是馬必須在棋盤內(nèi)。42分析：1、馬跳的方向： x:array1.4,1.2of integer= (1,-2),(2,-1),(2,1),(1,2); 4個方向橫向和縱向的增量。2、記錄馬經(jīng)過的位置坐標(biāo) a:array1.16,1.2of integer; 第i步所在的位置，1：橫坐標(biāo) 2：縱

30、坐標(biāo)3、馬的當(dāng)前位置：（aI,1,aI,2）下一個位置可能是：(aI,1+xj,1,aI,2+xj,2) 1=j=0)and(ai,1+xj,1=0)and(ai,2+xj,2=m)判界 then begin ai+1,1:=ai,1+xj,1; ai+1,2:=ai,2+xj,2; try(i+1); end; end;begin assign(output,house1.out); rewrite(output); readln(n,m); t:=0; a1,1:=0;起始位置作為第1個點(diǎn),x,y為0 a1,2:=0; try(1); close(output);end.45求最少步到達(dá)B

31、點(diǎn)。Best:最短路線，a：臨時得到的一個路線。Min：最少步。procedure try(i:integer); 搜索到當(dāng)前第i個點(diǎn) var j:integer; begin if (ai,1=n) and (ai,2=m)and(imin) then begin min:=i;best:=a;exit;end; 記下當(dāng)前最短路徑和最少步數(shù) if (ai,1n) or (ai,2m)and(i=min) then exit; 剪枝優(yōu)化 for j:=1 to 4 do if (ai,1+xj,1=0)and(ai,1+xj,1=0)and(ai,2+xj,2=m) then begin ai

32、+1,1:=ai,1+xj,1; ai+1,2:=ai,2+xj,2; try(i+1); end; end;19 1946跳馬問題（思考）在本例中，我們只要求輸出一條可行路徑，如果我們需要輸出所有的可行路徑，怎樣改動此程序呢？如果我們把問題改成“在nm的棋盤上有一騎士，開始時，騎士在點(diǎn)(x,y)，現(xiàn)在請你找出一條可行的路徑，使得騎士可以不重復(fù)的走遍棋盤上的每一個點(diǎn)?！钡脑?，又要如何編寫此程序呢？470,1背包問題已知一個容量大小為M重量的背包和N種物品，每種物品的重量為Wi。若將物品放入背包將得到Pi的效益，求怎樣選取物品將得到效益最大返回到題目列表輸入：第一行一個整數(shù)，為背包的容量M；第二

33、行一個整數(shù)，為物品的種數(shù)； 第三行個整數(shù)為各物品的重量；第四行個整數(shù)分別為個物品的價值輸出：第一行為最大總價值；第二行為裝入的各物品的重量（未裝的物品用）； 第三行為裝入的各物品的價值 （未裝的物品用）48算法分析本題可以用遞歸求解：設(shè)當(dāng)前有N個物品，容量為M；因?yàn)檫@些物品要么選，要么不選，我們假設(shè)選的第一個物品編號為I（1I-1號物品不選），問題又可以轉(zhuǎn)化為有N-I個物品（即第I+1N號物品），容量為M-Wi的子問題如此反復(fù)下去，然后在所有可行解中選一個效益最大的便可。另外，為了優(yōu)化程序，我們定義一個函數(shù)如下：FI表示選第IN個物品能得到的總效益。不難推出：FN=PnFI=FI+1+Pi（I

34、=1N-1）假設(shè)當(dāng)前已選到第I號物品，如果當(dāng)前搜索的效益值+FI+1的值仍然比當(dāng)前的最優(yōu)值小，則沒有必要繼續(xù)搜索下去。返回到題目列表49算法框架procedure search(i:integer; j:byte);遞歸求解var k:byte;begin if now+fjans then begin 修改最優(yōu)解 ans:=now; out:=ou; end; for k:=j to n do 選取物品 if wk=i then begin now:=now+pk; ouk:=true; search(i-wk,k+1); now:=now-pk; ouk:=false; end;end;5

35、0 某鄉(xiāng)有n個村莊(1n40)，有一個售貨員，他要到各個村莊去售貨，各村莊之間的路程s(0s1000)是已知的，且A村到B村與B村到A村的路大多不同。為了提高效率，他從商店出發(fā)到每個村莊一次，然后返回商店所在的村，假設(shè)商店所在的村莊為1，他不知道選擇什么樣的路線才能使所走的路程最短。請你幫他選擇一條最短的路。 輸入:村莊數(shù)n和各村之間的路程(均是整數(shù))。 輸出:最短的路程。 樣例輸入: 3 村莊數(shù) 0 2 l 村莊1到各村的路程 1 0 2 村莊2到各村的路程 2 1 0 村莊3到各村的路程 樣例輸出: 3售貨員的難題 51 算法分析： 題目給定的村莊數(shù)不多(040)，所以可以用回溯的方法，從

36、起點(diǎn)出發(fā)找出所有經(jīng)過其他各村莊的回路，計(jì)算其中的最短路程。用一個過程road(step，line：byte)來描述走的狀況，其中step是當(dāng)前已到過的村莊數(shù)、line是當(dāng)前所在的村莊。如果stepn，接下去只能回起點(diǎn)了，此時看第line個村莊到起點(diǎn)的路程加上已走的總路程，如果它比最小值還小則替換最小值。如果step還小于n，那么將還沒有到過的村莊一個一個地試過去，再調(diào)用下一步road(step+1，新到的村莊號)。52var a:array1.40,1.40 of integer; n,i,j:integer; min,m:longint; bj:array1.40 of boolean;be

37、gin readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); fillchar(bj,sizeof(bj),true); min:=99999999; m:=0; road(1,1); writeln(min);end. procedure road(step,line:byte); var i,j,k:byte; begin if（ ）then begin if m+aline,1min then min:=m+aline,1; exit; end; for i:=2 to n do if(iline)and（ ）then begi

38、n m:=m+aline,i; bjline:=false; if mmin then（ ); m:=m-aline,i; （ ）; end; end;step=nbjiroad(step+1,i)bjline:=true滿足最優(yōu)性要求剪枝恢復(fù)其遞歸前的值53計(jì)算拆分方案 給定一個正整數(shù)，假設(shè) 0A1=A2=A3.=As 滿足 A1+A2+A3+.+As=，那么我們稱序列A1 A2As為的一個拆分。現(xiàn)在要求的拆分?jǐn)?shù)目。（nrest then（ ）;剪枝 for i:=low to rest do 枚舉ad的所有可能值 begin ad:=i; if adn then dfs( ); end;

39、end; begin read(n); dfs( ); writeln(Total=,total);end. 1,1,nrest=0inc(total)exitd+1,i,rest-ilow為當(dāng)前ad的下界,rest為還剩下多少要拆分.56 問題描述: 將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。 例如：n=7，k=3，下面三種分法被認(rèn)為是相同的： 1，1，5 ; 1，5，1 ; 5，1，1 ; 問有多少種不同的分法。 輸入：n，k ( 6n=200， 2=k=6 ) 輸出：一個整數(shù)，即不同的分法。 樣例 輸入：7 3 輸出：4 四種分法為：1，1，5 ;1，2，4

40、;1，3，3 ;2，2，3; 測試3、數(shù)的劃分（ 01年復(fù)賽）577=1+6 =2+5 =3+4 分析：按份數(shù)遞增的順序拆分，且被拆分的整數(shù)按遞增順序排列（避免重復(fù)）。第一個數(shù)要小于等于 7 div 37=1+1+5 =1+2+4 =1+3+3第二個數(shù)要小于等于 6 div 27=2+2+3第二個數(shù)要小于等于 5 div 258var n,k,i:integer; tot:longint; a:array1.6 of integer;procedure sum( kx:integer); var m , L:integer; begin if kx=k then begin tot:=tot+

41、1; exit; end; L:=akx; for m:=akx-1 to L div (k-kx+1) do begin akx:=m; akx+1:=L-m; sum(kx+1); end; end; begin read(n,k); tot:=0; for i:=1 to n div k do begin a1:=i; a2:=n-i; sum(2); end; writeln(tot);end.kx為整數(shù)序號 已將n拆成k份按遞增要求枚舉n拆成兩份的所有可能方案從第二個數(shù)出發(fā)遞歸拆分按遞增要求窮舉akx 拆成兩份的所有可能方案 59測試4、選數(shù)( 01年復(fù)賽） 已知n（1=n=20）個

42、整數(shù)x1,x2,xn（1=xi=5000000），以及一個整數(shù)k（k1)是否為素?cái)?shù)最簡單的方法就是看是否存在一個素?cái)?shù)a(a=sqrt(P)是P的約數(shù)，如果不存在，該數(shù)就為素?cái)?shù)。 由于在此題中1=xi=5000000,n=20,所以要判斷的數(shù)P不會超過100000000，sqrt(p)=10000，因此，為了加快速度，我們可以先將210000之間的素?cái)?shù)保存到一個數(shù)組里（共1229個），這樣速度估計(jì)將提高56倍。 61var n,k: integer; ans,i: longint; x: array1 . 20 of longint; p: array1 . 1229 of integer;fu

43、nction ss( i:longint ):boolean; var j:longint; begin j:=2; while i mod j0 do j:=j+1; if jsqrt(i) then ss:=true else ss:=false; end;procedure create; var s:integer; i:longint; begin s:=0; for i:=2 to 10000 do if ss ( i ) then begin s:=s+1; ps:=i; end; end;function fit( sum:longint ):boolean; var max,

44、m:integer; begin max:=trunc( sqrt(sum) )+1; m:=1; while ( sum mod pm0 ) and ( pm=max then fit:=true else fit:=false; end;判斷i是否是素?cái)?shù)建立10000以內(nèi)的素?cái)?shù)集合判斷k個整數(shù)之和是否為素?cái)?shù)62procedure solve(left,now,all:longint); begin if ( left n-now+1 ) then exit;剪枝 if ( left=0 ) then begin if fit(all) then ans:=ans+1; exit; end;

45、 solve( left , now+1 , all ); solve( left-1,now+1,all+xnow ); end;begin create;建立10000以內(nèi)的素?cái)?shù)表 readln(n,k); for i:=1 to n do read(xi); ans:=0; solve( k,1,0 ); writeln(ans);end.目前組合和為all，還需從第xnow.xn中選出left個數(shù)。 如余下的數(shù)已不足left個，則回溯當(dāng)前組合不選xnow當(dāng)前組合選取xnow63測試5、合理排列(04年江蘇) 問題描述： 由m個A，n個B組成若干個排列，從某個排列的位置1開始數(shù)，數(shù)到任意

46、位置時都能保證A的個數(shù)不少于B的個數(shù)，則稱該排列為合理排列。 如當(dāng)m=2,n=2時，排列有:AABB（合理） ABAB（合理） ABBA（不合理）BBAA（不合理），合理排列有2種。 又如當(dāng)m=3,n=2時合理排列有5種：AAABB、AABAB、AABBA、ABAAB、ABABA輸入輸出： 輸入只有一行兩個整數(shù)m,n（1=n=m0 then begin 放A的情況 a:=a-1; w:=w+1; try(k+1); w:=w-1; a:=a+1; end; if (w0)and(b0) then begin 放B的情況 b:=b-1; w:=w-1; try(k+1); w:=w+1; b:=

47、b+1; end; end;begin readln(a,b); n:=a+b; 排列的長度 a:=a-1; w:=1; 第1個字符必定為A s:=0; try(2); writeln(s);end.65測試6、構(gòu)造字串 生成長度為n的字串，其字符從26個英文字母的前p(p26)個字母中選取，使得沒有相鄰的子序列相等。例如p=3，n=5時 a b c b a滿足條件 a b c b c不滿足條件 輸入：n，p 輸出：所有滿足條件的字串 66copy(s,length(s)-i+1,i)copy(s,length(s)-2*i+1,i)1= i=at div 2s=abcba i=1時，abi=

48、2時，babcs=abcbc i=1時，cbi=2時，bc=bc67var n,p,L:integer; t:longint; ed:char;可選字母集中的最大字母 s:string;滿足條件的字串procedure solve(at:integer); var ch:char; i:integer; begin if at=n+1 then begin writeln(s); inc(t); exit end; for ch:=a to ed do begin s:=s+ch; L:=length(s); i:=1;i是子串長度 while(i=at div 2)and(copy(s,L-

49、i+1,i)copy(s,L-2*i+1,i) do inc(i); if iat div 2 then solve(at+1); delete(s,length(s),1); end; end;搜索范圍：a. chr(ord(a)+p-1) 約束條件：當(dāng)前字串沒有相鄰子串相等的情況 遞歸擴(kuò)展下一個字母begin主程序 readln(n,p); ed:=chr( ord(a) + p - 1); s:=; tl:=0; solve(1); writeln(Total=,tl);end.待擴(kuò)展的字母序號at 68 【問題描述】 棋盤上A點(diǎn)有一個過河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或

50、者向右。同時在棋盤上C點(diǎn)有一個對方的馬，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對方馬的控制點(diǎn)。因此稱之為“馬攔過河卒”。 棋盤用坐標(biāo)表示，A點(diǎn)(0, 0)、B點(diǎn)(n, m)(n, m為不超過20的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的?，F(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)，假設(shè)馬的位置是固定不動的，并不是卒走一步馬走一步。 【輸入】 一行四個數(shù)據(jù)，分別表示B點(diǎn)坐標(biāo)和馬的坐標(biāo)。 【輸出】 一個數(shù)據(jù)，表示所有的路徑條數(shù)。 【樣例】 輸入:6 6 3 3 輸出:6測試7、馬攔過河卒（02年復(fù)賽）69const dx:array1.8 of integer=(-2,-1,1,2,2,1,-1

51、,-2); dy:array1.8 of integer=(1,2,2,1,-1,-2,-2,-1);var n,m,x,y,i,j: byte; g:array0.20,0.20 of 0.1; c:longint;procedure sol(x,y:integer); var i:integer; begin if (x=n) and (y=m) then begin c:=c+1; exit; end; if (ym) and (gx,y+1=0) then sol(x,y+1); if (x=0) and (x+dxi=0) and (y+dyi=m) then gx+dxi,y+dy

52、i:=1; sol(0,0); writeln(c);end.x,y為當(dāng)前馬所在的位置 目標(biāo)回溯向右走向下走計(jì)算馬的控制點(diǎn) 70測試8、01字符串問題問題描述： 輸出僅由0和1組成的長度為n的字符串，并且其中不可含有三個連續(xù)的相同字串。 輸入：字符串長度n（n0 do begin p:=x;q:=y;r:=z; while (rn then begin tot:=tot+2; exit; end; listlev:=0;先填0 if right(lev) then search(lev+1); listlev:=1;后填1 if right(lev) then search(lev+1); e

53、nd;begin readln(n); list1:=0;第一位為0 lev:=1; tot:=0; search(2); writeln(tot);end. 序列的對稱性：01100110011073測試9.錯排問題(02年初賽) 在書架上放有編號為1 ，2 ，n的n本書?，F(xiàn)將n本書全部取下然后再放回去，當(dāng)放回去時要求每本書都不能放在原來的位置上。 例如：n = 3時： 原來位置為：1 2 3 放回去時只能為：3 1 2 或 2 3 1 這兩種 問題：求當(dāng)n = 5時滿足以上條件的放法共有多少種？74var a:array1.50 of integer; s:set of 1.50; n,n

54、um:integer;procedure print; var i:integer; begin inc(num); write(No.,num, ); for i:=1 to n do write(ai:4); writeln; end;procedure cuopai(k:integer); var i:integer; begin if ( )then begin print; exit; end; for i:=1 to n do if not(i in s)and ( ) then begin ak:=i; s:=s+i; ( ) ; ak:=0; ( ); end; end;beg

55、in readln(n); ( ); num:=0; cuopai(1); writeln(Total=,num);end.s:=ikcuopai(k+1)k=n+1s:=s-i75測試10.公園門票每張5角，如果有2n個人排隊(duì)購票，每人一張，并且其中一半人恰有角錢，另一半人恰有元錢，而票房無零錢可找，那么有多少種方法將這2n個人排成一列，順次購票，使得不至于因票房無零錢可找而耽誤時間？ 2n個0與1組成的數(shù)，從最左邊算起，任何位置0的個數(shù)不得小于1的個數(shù)，這樣的排列有多少種？ 76const maxn=10;var a:array1.maxn*2 of integer; n,num:inte

56、ger;procedure try(k,n0,n1:integer); var i,j:integer; begin if( )then begin inc(num); write(No.,num, ); for i:=1 to 2*n do write(ai:2); writeln; ( ); end; if(n0=n1)and(n0n)then begin ak:=0; try( ); end;if( )and(n0n1n0=nexitn0是有角錢的人數(shù),n1是有元錢的人數(shù)77測試11 、棋盤覆蓋 有邊長為N（偶數(shù)）的正方形，用N*N/2個長為2、寬為1的長方形將它全部覆蓋，請找出所有覆蓋

57、方法。如N=4時的一種覆蓋方法及輸出格式如下所示。1224133456685778輸出：（數(shù)字為長方形編號）1 2 2 41 3 3 45 6 6 85 7 7 878var n:integer; t:longint; a:array1.10,1.10 of integer;procedure print; var i,j:integer; begin （ ）; for i:=1 to n do begin for j:=1 to n do write(ai,j:5); writeln; end; end;procedure try(i:integer); var j,k:integer; b

58、egin j:=0; repeat找到第一個未覆蓋的空格(j,k) j:=j+1; k:=1; while(k=n)and( ) do inc(k); until k=n; aj,k:=i; if (jn)and(aj+1,k=0)then begin aj+1,k:=i; if i*2n*n then try(i+1) else print; （ ）; end; if (kn)and(aj,k+1=0)then begin aj,k+1:=i; if i*20aj+1,k:=0aj,k+1:=0aj,k:=0inc(t)79測試12、組合的輸出【問題描述】 排列與組合是常用的數(shù)學(xué)方法，其中組

59、合就是從n個元素中抽出r個元素(不分順序且rn)，我們可以簡單地將n個元素理解為自然數(shù)1，2，n，從中任取r個數(shù)。 現(xiàn)要求你輸出所有的組合。 例如n5，r3，所有組合為： 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5【輸入】 一行兩個自然數(shù)n、r(1n21，1rn)?！据敵觥?所有的組合，每一個組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字符的位置，所有的組合也按字典順序。80const max=20;var a:array0.maxof integer; n,r:1.max;procedure compa

60、ges (k:integer); var i,j:integer; begin for i:=（ ）do begin ak:=i; if（ ）then begin for j:=1 to r do write(aj:3); writeln; end else（ ）; end; end;begin readln(n,r); compages(1); 從第一個元素開始選取組合數(shù)end.ak-1+1 to n-(r-k)k=rcompages(k+1)當(dāng)前所選元素最小為前一個元素加1，最大為n-(r-k)，因?yàn)楹竺孢€有(r-k)個元素要選取，至少為每次選取留一個.81例1、翻硬幣(03年初賽題) 題