1、深度優(yōu)先搜索,從問(wèn)題的某一種可能出發(fā), 搜索從這種情況出發(fā)所能達(dá)到的所有可能, 當(dāng)這一條路走到“ 盡頭 ”而沒(méi)達(dá)到目的地的時(shí)候, 再倒回上一個(gè)出發(fā)點(diǎn), 從另一個(gè)可能出發(fā), 繼續(xù)搜索. 這種不斷“ 倒回 一步尋找解的方法, 稱作 回溯法 . 回溯即是較簡(jiǎn)單、較常用的搜索策略,實(shí)質(zhì)就是一種搜索策略.,從A到B的路線:A-4-6-B,如:找一條從A到B的路線,算法思想 深度優(yōu)先搜索的搜索策略是：盡可能“深”的搜索某一分支。在深度優(yōu)先搜索中，對(duì)于最先發(fā)現(xiàn)的結(jié)點(diǎn)，如果還有以此為起點(diǎn)的未搜索邊，則沿此邊繼續(xù)搜索下去。當(dāng)結(jié)點(diǎn)V的所有邊都已經(jīng)被探尋過(guò)，搜索將回溯到發(fā)現(xiàn)點(diǎn)V的那條邊的始結(jié)點(diǎn)。重復(fù)此過(guò)程直至源結(jié)點(diǎn)

2、可到達(dá)的所有結(jié)點(diǎn)為止。,深度優(yōu)先搜索的基本算法結(jié)構(gòu) （1）遞歸實(shí)現(xiàn)。 Procedure dfs_try(i); For i:=1 to maxr do begin if 子結(jié)點(diǎn)mr符合條件 then begin 產(chǎn)生的子結(jié)點(diǎn)mr入棧； if子結(jié)點(diǎn)mr是目標(biāo)結(jié)點(diǎn) then 輸出； else dfs_try(i+1); 棧頂元素出棧； End; End;,1.、問(wèn)題描述 學(xué)校放暑假時(shí)，信息學(xué)輔導(dǎo)教師有n本書要分給參加培訓(xùn)的n個(gè)學(xué)生。如：A，B，C，D，E共5本書要分給參加培訓(xùn)的張、劉、王、李、孫5位學(xué)生，每人只能選1本。教師事先讓每個(gè)人將自己喜愛(ài)的書填寫在如下的表中，然后根據(jù)他們填寫的表來(lái)分配書

3、本，希望設(shè)計(jì)一個(gè)程序幫助教師求出可能的分配方案，使每個(gè)學(xué)生都滿意。,輸入格式：第一行一個(gè)數(shù)n（學(xué)生的個(gè)數(shù)，書的數(shù)量） 以下共n行，每行n個(gè)0或1（由空格隔開），第I行數(shù)據(jù)表示第i個(gè)同學(xué)對(duì)所有書的喜愛(ài)情況。0表示不喜歡該書，1表示喜歡該書。 輸出格式：依次輸出每個(gè)學(xué)生分到的書號(hào)。 樣例： 輸入：book.in 5 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 1 輸出：book.out 3 1 2 4 5,分析: a:array1.maxn,1.maxnof 0.1; b:array1.maxnof integer; 方案:bi是第i個(gè)人借第bi

4、本書 book:array1.maxnof boolean; booki:能否可以借第i本書, 初始:true,一旦有人借了:就改為:false,算法設(shè)計(jì): procedure try(i:integer);搜索第i個(gè)人可以借的書bi var j:integer; begin if i=n+1 then 若書都借出，則輸出結(jié)果 else for j:=1 to n do if 第i個(gè)人可以借第j 本書 then begin 記錄下bi; 標(biāo)記第j本數(shù)已被借; try(i+1); 刪除書的被借標(biāo)志; end; end;,procedure try(i:integer); var j:intege

5、r; begin if i=n+1 then print else for j:=1 to n do if bookj and (ai,j=1) then begin bi:=j; bookj:=false; try(i+1); bookj:=true; bi:=0; end; end;,procedure print; var i:integer; begin for i:=1 to n-1 do write(bi, ); writeln(BN); end;,主程序: begin fillchar(b,sizeof(b),0); fillchar(book,sizeof(book),true

6、); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); try(1); End.,2.、騎士的游歷 設(shè)有下圖所示的一個(gè)棋盤，在棋盤上的A點(diǎn)有一個(gè)中國(guó)象棋馬，并約定 馬走的規(guī)則： 1、馬只向右走； 2、馬走“日“字。 找出所有從A到B的路徑。,一種方法：(2 1)(4 0)(5 2)(6 0)(7 2)(8 4),1,1,1,分析： 1、馬跳的方向： x:array1.4,1.2of integer= (1,-2),(2,-1),(2,1),(1,2); 4個(gè)方向橫向和縱向的增量。 2、記錄馬經(jīng)過(guò)的位置坐標(biāo) a:array0.8,1

7、.2of integer; 第i步所在的位置，1：橫坐標(biāo) 2：縱坐標(biāo),遞歸算法： procedure try(i:integer);搜索第i步: try(1); var j:integer; begin for j:=1 to 4 do if (ai-1,1+xj,1=0)and(ai-1,1+xj,1=0)and(ai-1,2+xj,2=4) then begin ai,1:=ai-1,1+xj,1; ai,2:=ai-1,2+xj,2; if (ai,1=8) and (ai,2=4) then print(i) else try(i+1); end; end;,procedure pri

8、nt(i:integer); var j:integer; begin inc(t); write(t,:); for j:=1 to i do write(,aj,1, ,aj,2,); writeln; end;,3.、迷宮問(wèn)題 設(shè)有一個(gè)N*N方格的迷宮，入口和出口分別在左上角和右上角。迷宮格子中分別放有0和1，0表示可通，1表示不能，迷宮走的規(guī)則如下圖所示：即從某點(diǎn)開始，有八個(gè)方向可走，前進(jìn)方格中數(shù)字為0時(shí)表示可通過(guò)，為1時(shí)表示不可通過(guò)，要另找路徑。 輸入例子：（從文件中讀取數(shù)據(jù)） 8 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0

9、 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 0 輸出要求：找出一條 從入口（左上角）到出口（又上角）的路徑(不能重復(fù))。 (1,1)-(2,1)-(3,1)-(2,2)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1),分析: a:array1.maxn,1.maxnof 0.1; 記錄迷宮坐標(biāo) c:array1.maxn,1.maxnof 0.1; 訪問(wèn)標(biāo)志:0:沒(méi)走;1:已走 b:array0.maxn*maxn of integer;記錄路徑方向 d

10、x,dy:array1.8of integer; 方向位移,8個(gè)方向的位移: dx1:=0; dy1:=-1; dx2:=1; dy2:=-1; dx3:=1; dy3:=0; dx4:=1; dy4:=1; dx5:=0; dy5:=1; dx6:=-1; dy6:=1; dx7:=-1; dy7:=0; dx8:=-1; dy8:=-1;,讀入數(shù)據(jù): 坐標(biāo) procedure readdata; begin assign(input,a.in); reset(input); readln(n); for i:=1 to n do for j:=1 to n do begin read(aj

11、,i);i:縱坐標(biāo);j:橫坐標(biāo) cj,i:=0; end; close(input);,遞歸算法: procedure try(i:integer);搜索第i步應(yīng)到達(dá)的位置 var k:integer; begin for k:=1 to 8 do begin if (x+dxk=1)and(x+dxk=1)and(y+dyk=n)and (ax+dxk,y+dyk=0)and(cx+dxk,y+dyk=0) then begin x:=x+dxk; y:=y+dyk; cx,y:=1; bi:=k; if (x=n)and(y=1) then begin print(i); halt; en

12、d else try(i+1); cx,y:=0; x:=x-dxk; y:=y-dyk; end; end; end;,輸出一組解: procedure print(i:integer); var j:integer; begin x:=1; y:=1; write(,x,y,); 初始位置 for j:=1 to i do 輸出路線 begin x:=x+dxbj; y:=y+dybj; write(-,(,x,y,); end; writeln; end;,主程序: begin readdata; x:=1; y:=1; try(1); end.,4、覆蓋問(wèn)題。(li1.txt) 邊長(zhǎng)為

13、N（偶數(shù)）的正方形，用N*N/2個(gè)長(zhǎng)為2寬為1的長(zhǎng)方形將它全部覆蓋。編程打印所有覆蓋方法。當(dāng)N=4時(shí)幾種覆蓋方法的打印格式舉例如下：,輸出: 1224 1122 1334 3344 5668 5566 5778 7788,輸入: 4,分析: 把邊長(zhǎng)為n的正方形劃分為n*n個(gè)邊長(zhǎng)為1的格子, 用數(shù)組a描述覆蓋情況：aI,j：格子還沒(méi)被覆蓋，否則被編號(hào)為aI,j的格子覆蓋,算法描述： 、先行后列的原則找到一個(gè)aI,j，即未被覆蓋的格子（i，j）。 、如果行號(hào)(in)and(ai+1,j=0),即正下方的格子未覆蓋,那么格子(I,j)和(i+1,j)用同一個(gè)1*2的格子覆蓋. 轉(zhuǎn)向 3. 如果列號(hào)(

14、jn)and(ai,j=0),即右鄰的格子未覆蓋,那么格子(I,j)和(i,j)用同一個(gè)1*2的格子覆蓋. 轉(zhuǎn)向 3 、如果現(xiàn)在已用完了nn長(zhǎng)方形，則轉(zhuǎn)向，否則執(zhí)行 、打印現(xiàn)有的覆蓋方案，得到一種覆蓋方法。,procedure try(i:integer);搜索用編號(hào)i的長(zhǎng)方形覆蓋的格子：給格子編號(hào) var j,k:integer; begin j:=0;列初始化 repeat找aj，k的格子 j:=j+1;k:=1; while (k0) do inc(k); until (k=n); aj,k:=i;格子（j,k）用編號(hào)i覆蓋 if (jn) and (aj+1,k=0) then正下方格

15、子未覆蓋，用i覆蓋 begin aj+1,k:=i; if i*2n*n then 最大編號(hào)為n*n/2 try(i+1) else print; aj+1,k:=0;回溯 end;,if (kn) and (aj,k+1=0) then 右方方格子未覆蓋，用i覆蓋 begin aj,k+1:=i; if i*2n*n then try(i+1) else print; aj,k+1:=0; 回溯 end; aj,k:=0; 回溯 end;,procedure print; var i,j:integer; begin writeln; inc(t); for i:=1 to n do beg

16、in for j:=1 to n do write(ai,j); writeln; end; end;,主程序： begin readln(n); if odd(n) or (n0) then writeln(Error!) else try(1); end.,5、黑白棋子 現(xiàn)有N個(gè)黑棋和N個(gè)白棋，將這2N各棋子放入一個(gè)N*N棋盤，使每行每列都有一個(gè)黑棋和一個(gè)白棋。求滿足上述要求的布棋方案有多少種。 N=2時(shí)，有以下兩種放置方法：,輸出： ,const max=10; type bhxing=array1.maxof shortint; var b:array1.max,1.maxof boo

17、lean;棋盤能否可用 bai:array1.maxof boolean;能否放白棋子 hei:array1.maxof boolean; ;能否放黑棋子 bb:bhxing;白棋子列號(hào) hh：bhxing; 黑棋子列號(hào) n:integer;t:int64; 初始化： fillchar(bai,sizeof(bai),true); fillchar(hei,sizeof(hei),true); fillchar(b,sizeof(b),true);,procedure try(x:integer);放置第x行的白黑棋子 var i,j:integer; begin if x=n+1 then

18、begin print(bb);print(hh);writeln;inc(t);exit;end; for i:=1 to n do 搜索第x行白棋應(yīng)放置的列i if bx,i and baii then begin bx,i:=false;baii:=false;bbx:=i; for j:=1 to n do 搜索第x行黑棋應(yīng)放置的列j if bx,j and heij then begin bx,j:=false;heij:=false;hhx:=j; try(x+1); bx,j:=true;heij:=true;回溯：釋放黑棋的位置 end; bx,i:=true;baii:=tr

19、ue; 回溯：釋放白棋的位置 end; end;,procedure print(bh:bhxing); var i:integer; begin for i:=1 to n do write(bhi); write( ); end;,主程序： begin fillchar(bai,sizeof(bai),true); fillchar(hei,sizeof(hei),true); fillchar(b,sizeof(b),true); readln(n); try(1); writeln(t); end.,6、數(shù)字排列(li3.txt) 在一個(gè)N*N的棋盤上（1=n=100),填入1,2,.

20、,n*n共n*n個(gè)數(shù)，使得任意兩個(gè)相臨的數(shù)之合為素?cái)?shù) 例如： n=2 時(shí)，有:1 2 4 3 n=41 2 11 1216 15 8 513 4 9 146 7 10 3,分析： 逐行搜索1到n*n之間的數(shù)放在（i，j）處，依次判斷他與上方（i-1,j）的數(shù)和左邊(I,j-1)的數(shù)的和是否為素?cái)?shù)，是就放(I,j)處，再放（I,j+1);如果不是素?cái)?shù)，則繼續(xù)在1到n*n之間搜索合適的數(shù)能放在(I,j)處。,const maxn=100; type a=array1.2*maxn*maxnof boolean; var i,j,k,m,n,x,y,nn:integer; p:a;素?cái)?shù)表：pi=tr

21、ue :i是素?cái)?shù)， pi=false :i不是素?cái)?shù) b:array1.maxn,1.maxnof integer;坐標(biāo) used:array1.maxn*maxnof boolean;檢查是否該數(shù)是否用過(guò),篩選法創(chuàng)建素?cái)?shù)表 procedure prime; var i,j,s:integer; begin fillchar(p,sizeof(p),true); p1:=false; for i:=2 to 3*n div 2 do 依次搜索素?cái)?shù)i并篩掉是i倍數(shù)的數(shù) if pi then begin j:=2*i; while j=2*n*n do begin pj:=false; j:=j+i

22、; end; end; end;,判斷（x,y）位置能否放數(shù)值k的函數(shù) function ok(x,y,k:integer):boolean; begin ok:=true; if x1 then if not (pbx-1,y+k) then ok:=false; if y1 then if not (pbx,y-1+k) then ok:=false; end;,procedure try(x,y,dep:integer);遞歸搜索（x,y）處放第 dep 個(gè)數(shù) var i:integer; begin if dep=n*n+1 then print else 如果已放了n*n個(gè)數(shù)，得出一

23、種方法 for i:=1 to n*n do if not(usedi) and ok(x,y,i) then begin bx,y:=i; usedi:=true; if y=n then try(x+1,1,dep+1) 如果當(dāng)前是最右邊一列，則轉(zhuǎn)到下一行首列 else try(x,y+1,dep+1); 繼續(xù)放當(dāng)前行的下一列 usedi:=false;釋放標(biāo)志 end; end;,procedure print; var i,j:integer; begin for i:=1 to n do begin for j:=1 to n do write(bi,j:4); writeln; e

24、nd; halt; end;,主程序： begin readln(n); if n=1 then begin writeln(NO);halt;end; prime; b1,1:=1; for i:=2 to n*n do usedi:=false; used1:=true; try(1,2,2); writeln(NO); end.,上機(jī)練習(xí)題 1.添加自然數(shù)問(wèn)題。（add.pas） 要求找出具有下列性質(zhì)的數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n)： 先輸入一個(gè)自然數(shù)n(n=500),然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理: . 不作任何處理; . 在它的左邊加上一個(gè)自然數(shù),但該自然數(shù)不能超過(guò)原數(shù)的一半;

25、. 加上數(shù)后,繼續(xù)按此規(guī)則進(jìn)行處理,直到不能再加自然數(shù)為止. 輸入文件：add.in,一行，n的值。 輸出文件：add.out，一行，按照規(guī)則可產(chǎn)生的自然數(shù)個(gè)數(shù)。,樣例： 輸入文件： 6 滿足條件的數(shù)為 6 16 26 126 36 136 輸出文件 6,var n,i:integer; s:real; procedure qiu(x:integer); var k:integer; begin if x0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) end end; begin readln(n); s:=0; qiu(n); write

26、ln(s) end.,2. 跳馬問(wèn)題。（jump.pas） 在5*5格的棋盤上，有一個(gè)國(guó)際象棋的馬，它可以朝8個(gè)方向跳，但不允許出界或跳到已跳過(guò)的格子上，要求求出跳遍整個(gè)棋盤后的不同的路徑條數(shù)。 輸出文件：jump.out，一行，路徑條數(shù)。,program jump; var h:array-1.7,-1.7 of integer; a,b:array1.8 of integer; i,j,num:integer; procedure print; var i,j:integer; begin num:=num+1; if num=5 then begin for i:=1 to 5 do b

27、egin for j:=1 to 5 do write(hi,j:4); writeln; end; writeln; end; end;,procedure try(x,y,i:integer); var j,u,v:integer; begin for j:=1 to 8 do begin u:=x+aj; v:=y+bj; if hu,v=0 then begin hu,v:=i; if i25 then try(u,v,i+1) else print; hu,v:=0 end; end; end;,begin for i:=-1 to 7 do for j:=-1 to 7 do if

28、 (i=1)and(i=1)and(j=5) then hi,j:=0 else hi,j:=1; a1:=2;b1:=1; a2:=1;b2:=2; a3:=-1;b3:=2; a4:=-2;b4:=1; a5:=-2;b5:=-1; a6:=-1;b6:=-2; a7:=1;b7:=-2; a8:=2;b8:=-1; num:=0; h1,1:=1; try(1,1,2); writeln(num); end.,3.過(guò)河卒,棋盤上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤上C點(diǎn)有一個(gè)對(duì)方的馬，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。因此稱

29、之為“馬攔過(guò)河卒”。,棋盤用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n,m)(n,m為不超過(guò)20的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的?，F(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)，假設(shè)馬的位置是固定不動(dòng)的，并不是卒走一步馬走一步。 【輸入】 一行四個(gè)數(shù)據(jù)，分別表示B點(diǎn)坐標(biāo)和馬的坐標(biāo)。 【輸出】 一個(gè)數(shù)據(jù)，表示所有的路徑條數(shù)。 【樣例輸入】 6 6 3 2 【樣例輸出】 17,題目分析： 本題是一道典型的深度優(yōu)先搜索題目。 需要處理好的細(xì)節(jié)有： 1.讀入“馬”的坐標(biāo)，控制好八個(gè)方向。 2.在（n,m）棋盤上控制好“馬”所能跳出的邊界。 3.按向下、向右兩個(gè)方向搜索，只要當(dāng)前沒(méi)有走到（n,m）點(diǎn)且下

30、一節(jié)點(diǎn)未訪問(wèn)過(guò)，則搜索。,program zu; const dx:array1.8 of shortint=(2,1,-1,-2,-2,-1,1,2); dy:array1.8 of shortint=(1,2,2,1,-1,-2,-2,-1); var n,m,x,y:longint; g:array-2.22,-2.22 of boolean; i,ans:longint; procedure go(a,b:longint); begin if (a=n)and(b=m) then inc(ans) else begin if (a+1=n)and ga+1,b=true then go(a+1,b); if (b+1=m)and ga,b+1=true then go(a,b+1); end; end;,begin assign(input,zu.in); reset(input); assign(output,zu.ou