深度优先搜索(pascal).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,深度优先搜索,从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,当这一条路走到,“,尽头,”,而没达到目的地的时候,再倒回,上一个,出发点,从另一个可能出发,继续搜索,.,这种不断,“,倒回 一步,寻找解的方法,称作,回溯法,.,回溯即是较简单、较常用的搜索策略,实质就是一种搜索策略,.,A,B,1,2,3,4,5,6,7,8,9,10,从,A,到,B,的路线,:A-4-6-B,如,:,找一条从,A,到,B,的路线,算法思想,深度优先搜索的搜索策略是：尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为止。,深度优先搜索的基本算法结构,（,1,）递归实现。,Procedure dfs_try(i);,For i:=1 to maxr do,begin,if,子结点,mr,符合条件,then,begin,产生的子结点,mr,入栈；,if,子结点,mr,是目标结点,then,输出；,else dfs_try(i+1);,栈顶元素出栈；,End;,End;,1.,、,问题描述,学校放暑假时，信息学辅导教师有,n,本书要分给参加培训的,n,个学生。如：,A,，,B,，,C,，,D,，,E,共,5,本书要分给参加培训的张、刘、王、李、孙,5,位学生，每人只能选,1,本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。,A,B,C,D,E,张,Y,Y,王,Y,Y,刘,Y,Y,孙,Y,李,Y,Y,输入格式：第一行一个数,n,（学生的个数，书的数量）,以下共,n,行，每行,n,个,0,或,1,（由空格隔开），第,I,行数据表示第,i,个同学对所有书的喜爱情况。,0,表示不喜欢该书，,1,表示喜欢该书。,输出格式：依次输出每个学生分到的书号。,样例：,输入：,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,个人借第,bi,本书,book:array1.maxnof boolean;,booki:,能否可以借第,i,本书,初始,:true,一旦有人借了,:,就改为,:false,算法设计:,procedure try(i:integer);搜索第i个人可以借的书bi,var j:integer;,begin,if i=n+1 then 若书都借出，则输出结果,else,for j:=1 to n do,if 第i个人可以借第j 本书 then,begin,记录下bi;,标记第j本数已被借;,try(i+1);,删除书的被借标志;,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);,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);,readln(n);,for i:=1 to n do,for j:=1 to n do read(ai,j);,try(1);,End.,2.、骑士的游历,设有下图所示的一个棋盘，在棋盘上的A点有一个中国象棋马，并约定,马走的规则：,1、马只向右走；,2、马走“日“字。,找出所有从A到B的路径。,一种方法：,(2 1)(4 0)(5 2)(6 0)(7 2)(8 4),1,1,1,2,3,4,5,6,7,1,2,3,1,分析：,1,、,马跳的方向：,x:array1.4,1.2of integer=,(1,-2),(2,-1),(2,1),(1,2);,4,个方向横向和纵向的增量。,2,、记录马经过的位置坐标,a:array0.8,1.2of integer;,第,i,步所在的位置，,1,：横坐标,2,：纵坐标,递归算法：,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;,记录迷宫坐标,c:array1.maxn,1.maxnof 0.1;,访问标志,:0:,没走,;1:,已走,b:array0.maxn*maxn of integer;,记录路径方向,dx,dy:array1.8of integer;,方向位移,8个方向的位移:,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;,读入数据,:,坐标,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,i);i:,纵坐标,;j:,横坐标,cj,i:=0;,end;,close(input);,递归算法,:,procedure try(i:integer);,搜索第,i,步应到达的位置,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;,x:=1;,y:=1;,try(1);,end.,4,、覆盖问题。,(li1.txt),边长为N（偶数）的正方形，用N*N/2个长为2宽为1的长方形将它全部覆盖。编程打印所有覆盖方法。当N=4时几种覆盖方法的打印格式举例如下：,1,2,2,4,1,3,3,4,5,6,6,8,5,7,7,8,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,输出,:,1224 1122,1334 3344,5668 5566,5778 7788,输入,:4,分析,:,把边长为,n,的正方形划分为,n*n,个边长为,1,的格子,用数组,a,描述覆盖情况：,aI,j,：格子还没被覆盖，否则被编号为,aI,j,的格子覆盖,算法描述：,、先行后列的原则找到一个,aI,j,，即未被覆盖的格子（,i,，,j,）。,、如果行号,(in)and(ai+1,j=0),即正下方的格子未覆盖,那么格子,(I,j),和,(i+1,j),用同一个,1*2,的格子覆盖,.,转向,3.,如果列号,(jn)and(ai,j,=0),即右邻的格子未覆盖,那么格子,(I,j),和,(i,j,),用同一个,1*2,的格子覆盖,.,转向,3,、如果现在已用完了,n,n,长方形，则转向，否则执行,、打印现有的覆盖方案，得到一种覆盖方法。,procedure try(i:integer);,搜索用编号,i,的长方形覆盖的格子：给格子编号,var,j,k:integer;,begin,j:=0;,列初始化,repeat,找,a,j,，,k,的格子,j:=j+1;k:=1;,while(k0)do,inc(k);,until(k=n);,aj,k:=i;,格子（,j,k,）用编号,i,覆盖,if(jn)and(aj+1,k=0)then,正下方格子未覆盖，用,i,覆盖,begin,aj+1,k:=i;,if i*2n*n then,最大编号为,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,begin,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,、黑白棋子,现有,N,个黑棋和,N,个白棋，将这,2N,各棋子放入一个,N*N,棋盘，使每行每列都有一个黑棋和一个白棋。求满足上述要求的布棋方案有多少种。,N=2,时，有以下两种放置方法：,b,w,w,b,w,b,b,w,输出：,const max=10;,type bhxing=array1.maxof shortint;,var,b:array1.max,1.maxof boolean;,棋盘能否可用,bai:array1.maxof boolean;,能否放白棋子,hei:array1.maxof boolean,;,能否放黑棋子,bb:bhxing;,白棋子列号,hh,：,bhxing;,黑棋子列号,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 begin print(bb);print(hh);writeln;inc(t);exit;end;,for i:=1 to n do,搜索第,x,行白棋应放置的列,i,if bx,i and baii then,begin,bx,i:=false;baii:=false;bbx:=i;,for j:=1 to n do,搜索第,x,行黑棋应放置的列,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:=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,sizeof(b),true);,readln(n);,try(1);,writeln(t);,end.,6、数字排列(li3.txt),在一个,N*N,的棋盘上（,1=n=100),填入,1,2,.,n*n,共,n*n,个数，使得任意两个相临的数之合为素数,例如：,n=2,时，有,:1 2 4 3,n=41 2 11 1216 15 8 513 4 9 146 7 10 3,分析：逐行搜索,1,到,n*n,之间的数放在（,i,，,j,）处，依次判断他与上方（,i-1,j,）的数和左边,(I,j-1),的数的和是否为素数，是就放,(I,j),处，再放（,I,j+1);,如果不是素数，则继续在,1,到,n*n,之间,搜索合适的数能放在,(I,j),处。,const maxn=100;,type a=array1.2*maxn*maxnof boolean;,var i,j,k,m,n,x,y,nn:integer;,p:a;,素数表：,pi=true:i,是素数，,pi=false:i,不是素数,b:array1.maxn,1.maxnof integer;,坐标,used:array1.maxn*maxnof boolean;,检查是否该数是否用过,筛选法创建素数表,procedure prime;,var i,j,s:integer;,begin,fillchar(p,sizeof(p),true);,p1:=false;,for i:=2 to,3*n div 2,do,依次搜索素数,i,并筛掉是,i,倍数的数,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 try(x,y,dep:integer);,递归搜索（,x,y,）处放,第,dep,个,数,var i:integer;,begin,if dep=n*n+1 then print else,如果已放了,n*n,个数，得出一种方法,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),如果当前是最右边一列，则转到下一行首列,else,try(x,y+1,dep+1);,继续放当前行的下一列,usedi:=false;,释放标志,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(1,2,2);,writeln(NO);,end.,上机练习题,1.,添加自然数问题。（,add.pas,）,要求找出具有下列性质的数的个数,(,包含输入的自然数,n),：,先输入一个自然数,n(n=500),然后对此自然数按照如下方法进行处理,:,.,不作任何处理,;,.,在它的左边加上一个自然数,但该自然数不能超过原数的一半,;,.,加上数后,继续按此规则进行处理,直到不能再加自然数为止,.,输入文件：,add.in,一行，,n,的值。,输出文件：,add.out,，一行，按照规则可产生的自然数个数。,样例：,输入文件：,6,满足条件的数为 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);,writeln(s),end.,2.,跳马问题。（,jump.pas,）,在,5*5,格的棋盘上，有一个国际象棋的马，它可以朝,8,个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。,输出文件：,jump.out,，一行，路径条数。,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,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:=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.,过河卒,棋盘上,A,点有一个过河卒，需要走到目标,B,点。卒行走的规则：可以向下、或者向右。同时在棋盘上,C,点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。,棋盘用坐标表示，,A,点,(0,0),、,B,点,(n,m)(n,m,为不超过,20,的整数,),，同样马的位置坐标是需要给出的。现在要求你计算出卒从,A,点能够到达,B,点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。,【,输入,】,一行四个数据，分别表示,B,点坐标和马的坐标。,【,输出,】,一个数据，表示所有的路径条数。,【,样例输入,】,6 6 3 2,【,样例输出,】,17,题目分析：,本题是一道典型的深度优先搜索题目。,需要处理好的细节有：,1.,读入“马”的坐标，控制好八个方向。,2.,在（,n,m,）棋盘上控制好“马”所能跳出的边界。,3.,按向下、向右两个方向搜索，只要当前没有走到（,n,m,）点且下一节点未访问过，则搜索。,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.out);rewrite(output);,readln(n,m,x,y);,fillchar(g,sizeof(g),true);,gx,y:=false;,for i:=1 to 8 do,gx+dxi,y+dyi:=false;,ans:=0;,go(0,0);,writeln(ans);,close(input);close(output);,end.,4.,素数环问题。（,sushu.pas,）,把从,1,到,20,这,20,个数摆成一个环，要求相邻的两个数的和是一个素数。,请输出一种摆放方法。,输出文件：,sushu.out,一行，以,1,开始的,20,个整数，中间用一个空格隔开，最后一个数后面没有空格。,program tt;,var a:array 1.20 of integer;,k:integer;,function pd1(j,i:integer):boolean;,begin,pd1:=true;,for k:=1 to i-1 do,if ak=j then begin pd1:=false;exit;end;,end;,function pd2(x:integer):boolean;,begin,pd2:=true;,for k:=2 to trunc(sqrt(x)do,if x mod k=0 then begin pd2:=false;exit;end;,end;,function pd3(j,i:integer):boolean;,begin,if i20 then pd3:=pd2(j+ai-1),else pd3:=pd2(j+ai-1)and pd2(j+1);,end;,procedure print;,begin,for k:=1 to 20 do write(ak:4);,writeln;,end;,procedure try(i:integer);,var j:integer;,begin,for j:=2 to 20 do,begin,if pd1(j,i)and pd3(j,i)then begin,ai:=j;,if i=20 then begin print;halt;end,else try(i+1);,ai:=0;,end;,end;,end;,begin,for k:=1 to 20 do ak:=0;,a1:=1;,try(2);,end.,