深度優(yōu)先搜索(pascal)

1、深度優(yōu)先搜索深度優(yōu)先搜索 從問(wèn)題的某一種可能出發(fā)從問(wèn)題的某一種可能出發(fā), , 搜索從這種情況出發(fā)所能達(dá)搜索從這種情況出發(fā)所能達(dá)到的所有可能到的所有可能, , 當(dāng)這一條路走到當(dāng)這一條路走到“ “ 盡頭盡頭 ” ”而沒(méi)達(dá)到目的地而沒(méi)達(dá)到目的地的時(shí)候的時(shí)候, , 再倒回再倒回上一個(gè)上一個(gè)出發(fā)點(diǎn)出發(fā)點(diǎn), , 從另一個(gè)可能出發(fā)從另一個(gè)可能出發(fā), , 繼續(xù)搜繼續(xù)搜索索. . 這種不斷這種不斷“ “ 倒回倒回 一步一步 尋找解的方法尋找解的方法, , 稱作稱作 回溯法回溯法 . 回溯即是較簡(jiǎn)單、較常用的搜索策略回溯即是較簡(jiǎn)單、較常用的搜索策略,實(shí)質(zhì)就是一種搜索實(shí)質(zhì)就是一種搜索策略策略. .AB1234567

2、8910從從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)可到達(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

3、輸出； else dfs_try(i+1); 棧頂元素出棧；End;End;1.、問(wèn)題描述問(wèn)題描述 學(xué)校放暑假時(shí)，信息學(xué)輔導(dǎo)教師有學(xué)校放暑假時(shí)，信息學(xué)輔導(dǎo)教師有n本書(shū)要分給參加培訓(xùn)的本書(shū)要分給參加培訓(xùn)的n個(gè)學(xué)生。如：個(gè)學(xué)生。如：A，B，C，D，E共共5本書(shū)要分給參加培訓(xùn)的張、劉、王、李、孫本書(shū)要分給參加培訓(xùn)的張、劉、王、李、孫5位學(xué)生，每人只能選位學(xué)生，每人只能選1本。教師事先讓每個(gè)人將自己喜愛(ài)的書(shū)填寫(xiě)在如下的表中，然后根據(jù)他們填寫(xiě)的本。教師事先讓每個(gè)人將自己喜愛(ài)的書(shū)填寫(xiě)在如下的表中，然后根據(jù)他們填寫(xiě)的表來(lái)分配書(shū)本，希望設(shè)計(jì)一個(gè)程序幫助教師求出可能的分配方案，使每個(gè)學(xué)生都滿表來(lái)分配書(shū)本，希望設(shè)

4、計(jì)一個(gè)程序幫助教師求出可能的分配方案，使每個(gè)學(xué)生都滿意。意。ABCDE張YY王YY劉YY孫Y李YY輸入格式：第一行一個(gè)數(shù)輸入格式：第一行一個(gè)數(shù)n（學(xué)生的個(gè)數(shù)，書(shū)的數(shù)量）（學(xué)生的個(gè)數(shù)，書(shū)的數(shù)量） 以下共以下共n行，每行行，每行n個(gè)個(gè)0或或1（由空格隔開(kāi)），第（由空格隔開(kāi)），第I行數(shù)據(jù)表示第行數(shù)據(jù)表示第i個(gè)同學(xué)個(gè)同學(xué)對(duì)所有書(shū)的喜愛(ài)情況。對(duì)所有書(shū)的喜愛(ài)情況。0表示不喜歡該書(shū)，表示不喜歡該書(shū)，1表示喜歡該書(shū)。表示喜歡該書(shū)。輸出格式：依次輸出每個(gè)學(xué)生分到的書(shū)號(hào)。輸出格式：依次輸出每個(gè)學(xué)生分到的書(shū)號(hào)。樣例：樣例：輸入：book.in50 0 1 1 01 1 0 0 00 1 1 0 00 0 0 1 0

5、0 1 0 0 1輸出：book.out3 1 2 4 5分析分析: a:array1.maxn,1.maxnof 0.1; b:array1.maxnof integer; 方案方案:bi是第是第i個(gè)人借第個(gè)人借第bi本書(shū)本書(shū) book:array1.maxnof boolean; booki:能否可以借第能否可以借第i本書(shū)本書(shū), 初始初始:true,一旦有人借了一旦有人借了:就改為就改為:false算法設(shè)計(jì)算法設(shè)計(jì):procedure try(i:integer);搜索第搜索第i個(gè)人可以借的書(shū)個(gè)人可以借的書(shū)bi var j:integer; begin if i=n+1 then 若書(shū)都借

6、出，則輸出結(jié)果若書(shū)都借出，則輸出結(jié)果 else for j:=1 to n do if 第第i個(gè)人可以借第個(gè)人可以借第j 本書(shū)本書(shū) then begin 記錄下記錄下bi; 標(biāo)記第標(biāo)記第j本數(shù)已被借本數(shù)已被借; try(i+1); 刪除書(shū)的被借標(biāo)志刪除書(shū)的被借標(biāo)志; end; end;procedure try(i:integer); var j:integer; 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); book

7、j:=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); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); try(1);End.2.、騎士的游歷、騎士的游歷設(shè)有下圖所示的一個(gè)棋盤(pán)，在棋盤(pán)上的設(shè)有下圖所示的一個(gè)棋盤(pán)，在棋盤(pán)上的

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

9、：橫坐標(biāo)：橫坐標(biāo) 2：縱坐標(biāo)：縱坐標(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(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)記錄迷宮坐標(biāo) c:array1.maxn,1.maxnof 0.1; 訪問(wèn)標(biāo)志訪

10、問(wèn)標(biāo)志:0:沒(méi)走沒(méi)走;1:已走已走 b:array0.maxn*maxn of integer;記錄路徑方向記錄路徑方向 dx,dy:array1.8of integer; 方向位移方向位移 8個(gè)方向的位移個(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ù)讀入數(shù)據(jù): 坐標(biāo)坐標(biāo)procedure readdata;begin assign(input,a.in

11、); reset(input); readln(n); for i:=1 to n do for j:=1 to n do begin read(aj,i);i:縱坐標(biāo);j:橫坐標(biāo) cj,i:=0; end; close(input);遞歸算法遞歸算法:procedure try(i:integer);搜索第搜索第i步應(yīng)到達(dá)的位置步應(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,(,x,y,); end; writeln; end;主程序主程序:begin readdata

12、; x:=1; y:=1; try(1);end.4、覆蓋問(wèn)題。、覆蓋問(wèn)題。(li1.txt) 邊長(zhǎng)為N（偶數(shù)）的正方形，用N*N/2個(gè)長(zhǎng)為2寬為1的長(zhǎng)方形將它全部覆蓋。編程打印所有覆蓋方法。當(dāng)N=4時(shí)幾種覆蓋方法的打印格式舉例如下：12241334566857781122334455667788輸出:1224 11221334 33445668 55665778 7788輸入: 4分析分析: 把邊長(zhǎng)為把邊長(zhǎng)為n的正方形劃分為的正方形劃分為n*n個(gè)邊長(zhǎng)為個(gè)邊長(zhǎng)為1的格子的格子,用數(shù)組用數(shù)組a描述覆蓋情況：描述覆蓋情況：aI,j：格子還沒(méi)被覆蓋，否則被編號(hào)為：格子還沒(méi)被覆蓋，否則被編號(hào)為aI,j

13、的的格子覆蓋格子覆蓋算法描述：算法描述：、先行后列的原則找到一個(gè)、先行后列的原則找到一個(gè)aI,j，即未被覆蓋的格子（，即未被覆蓋的格子（i，j）。）。、如果行號(hào)、如果行號(hào)(in)and(ai+1,j=0),即正下方的格子未覆蓋即正下方的格子未覆蓋,那么格子那么格子(I,j)和和(i+1,j)用用同一個(gè)同一個(gè)1*2的格子覆蓋的格子覆蓋. 轉(zhuǎn)向轉(zhuǎn)向 3.如果列號(hào)如果列號(hào)(jn)and(ai,j=0),即右鄰的格子未覆蓋即右鄰的格子未覆蓋,那么格子那么格子(I,j)和和(i,j)用同一個(gè)用同一個(gè)1*2的格子覆蓋的格子覆蓋. 轉(zhuǎn)向轉(zhuǎn)向 3、如果現(xiàn)在已用完了、如果現(xiàn)在已用完了nn長(zhǎng)方形，則轉(zhuǎn)向，否則執(zhí)行

14、長(zhǎng)方形，則轉(zhuǎn)向，否則執(zhí)行、打印現(xiàn)有的覆蓋方案，得到一種覆蓋方法。、打印現(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正下方格子未覆蓋，用i覆蓋 begin aj+1,k:=i; if i*2n*n then 最大編號(hào)為n*n/2

15、 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 begin for j:=1 to n do write(ai,j); writeln; end;end;主程序主程序

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

17、1.max,1.maxof boolean;棋盤(pán)能否可用棋盤(pán)能否可用 bai:array1.maxof boolean;能否放白棋子能否放白棋子 hei:array1.maxof boolean; ;能否放黑棋子能否放黑棋子 bb:bhxing;白棋子列號(hào)白棋子列號(hào) hh：bhxing; 黑棋子列號(hào)黑棋子列號(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);放

18、置第放置第x行的白黑棋子行的白黑棋子 var i,j:integer; begin if x=n+1 then begin print(bb);print(hh);writeln;inc(t);exit;end; for i:=1 to n do 搜索第搜索第x行白棋應(yīng)放置的列行白棋應(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)放置的列行黑棋應(yīng)放置的列j if bx,j and heij then begin bx,j:=false;heij:=fal

19、se;hhx:=j; try(x+1); bx,j:=true;heij:=true;回溯：釋放黑棋的位置回溯：釋放黑棋的位置 end; bx,i:=true;baii:=true; 回溯：釋放白棋的位置回溯：釋放白棋的位置 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,s

20、izeof(b),true); readln(n); try(1); writeln(t);end.6、數(shù)字排列、數(shù)字排列(li3.txt)在一個(gè)在一個(gè)N*N的棋盤(pán)上（的棋盤(pán)上（1=n=100),填入填入1,2,.,n*n共共n*n個(gè)個(gè)數(shù)，使得任意兩個(gè)相臨的數(shù)之合為素?cái)?shù)數(shù)，使得任意兩個(gè)相臨的數(shù)之合為素?cái)?shù)例如：例如：n=2 時(shí)，有時(shí)，有:1 2 4 3n=41 2 11 1216 15 8 513 4 9 146 7 10 3分析：分析： 逐行搜索逐行搜索1到到n*n之間的數(shù)放在（之間的數(shù)放在（i，j）處，依次判斷他與）處，依次判斷他與上方（上方（i-1,j）的數(shù)和左邊）的數(shù)和左邊(I,j-1)

21、的數(shù)的和是否為素?cái)?shù)，是就放的數(shù)的和是否為素?cái)?shù)，是就放(I,j)處，再放（處，再放（I,j+1);如果不是素?cái)?shù)，則繼續(xù)在如果不是素?cái)?shù)，則繼續(xù)在1到到n*n之間之間搜索搜索合適的數(shù)能放在合適的數(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ù)表：素?cái)?shù)表：pi=true :i是素?cái)?shù)，是素?cái)?shù)， pi=false :i不是素?cái)?shù)不是素?cái)?shù) b:array1.maxn,1.maxnof integer;坐標(biāo)坐標(biāo) used:array1.maxn*maxnof b

22、oolean;檢查是否該數(shù)是否用過(guò)檢查是否該數(shù)是否用過(guò)篩選法創(chuàng)建素?cái)?shù)表篩選法創(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 j1 then if not (pbx-1,y+k) then ok:=false; if y1 then if not (pbx,y-1+k) then ok:=false;end;procedure t

23、ry(x,y,dep:integer);遞歸搜索（遞歸搜索（x,y）處放）處放第第 dep 個(gè)個(gè)數(shù)數(shù)var i:integer;begin if dep=n*n+1 then print else 如果已放了如果已放了n*n個(gè)數(shù)，得出一種方法個(gè)數(shù)，得出一種方法 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)到下一行首列如果當(dāng)前是最右邊一列，則轉(zhuǎn)到下一行首列 else try(x,y+1,dep+1)

24、; 繼續(xù)放當(dāng)前行的下一列繼續(xù)放當(dāng)前行的下一列 usedi:=false;釋放標(biāo)志釋放標(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; end; 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

25、(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ù)的一半; . 加上數(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

26、; 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) endend;begin readln(n); s:=0; qiu(n); writeln(s)end. 2. 跳馬問(wèn)題。（jump.pas） 在5*5格的棋盤(pán)上，有一個(gè)國(guó)際象棋的馬，它可以朝8個(gè)方向跳，但不允許出界或跳到已跳過(guò)的格子上，要求求出跳遍整個(gè)棋盤(pán)后的不同的路徑條數(shù)。 輸出文件：jump.out，一行，路徑條數(shù)。 program jump; var h:array-1.

27、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 begin 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

28、:=x+aj; v:=y+bj; if hu,v=0 then begin hu,v:=i; if 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ò)河卒 棋盤(pán)上A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右

29、。同時(shí)在棋盤(pán)上C點(diǎn)有一個(gè)對(duì)方的馬，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。因此稱之為“馬攔過(guò)河卒”。 棋盤(pán)用坐標(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.讀入“馬”

30、的坐標(biāo)，控制好八個(gè)方向。 2.在（n,m）棋盤(pán)上控制好“馬”所能跳出的邊界。 3.按向下、向右兩個(gè)方向搜索，只要當(dāng)前沒(méi)有走到（n,m）點(diǎn)且下一節(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