深度优先搜索(pascal)PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,深度优先搜索,1,从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,当这一条路走到,“,尽头,”,而没达到目的地的时候,再倒回,上一个,出发点,从另一个可能出发,继续搜索.这种不断,“,倒回 一步,寻找解的方法,称作 回溯法.,回溯即是较简单、较常用的搜索策略,实质就是一种搜索策略.,A,B,1,2,3,4,5,6,7,8,9,10,从A到B的路线:A-4-6-B,如:找一条从A到B的路线,2,算法思想,深度优先搜索的搜索策略是：尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为止。,3,深度优先搜索的基本算法结构,（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;,4,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,5,输入格式：第一行一个数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,6,分析:,a:array1.maxn,1.maxnof 0.1;,b:array1.maxnof integer;,方案:bi是第i个人借第bi本书,book:array1.maxnof boolean;,booki:能否可以借第i本书,初始:true,一旦有人借了:就改为:false,7,算法设计:,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;,8,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;,9,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.,10,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,11,分析：,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：纵坐标,12,递归算法：,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),15,分析:,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;,16,读入数据:坐标,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);,17,递归算法:,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;,19,主程序:,begin,readdata;,x:=1;,y:=1;,try(1);,end.,20,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,21,分析:,把边长为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,、如果现在已用完了nn长方形，则转向，否则执行,、打印现有的覆盖方案，得到一种覆盖方法。,22,procedure try(i:integer);搜索用编号i的长方形覆盖的格子：给格子编号,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）用编号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;,23,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.,24,5,、黑白棋子,现有,N,个黑棋和,N,个白棋，将这,2N,各棋子放入一个,N*N,棋盘，使每行每列都有一个黑棋和一个白棋。求满足上述要求的布棋方案有多少种。,N=2,时，有以下两种放置方法：,b,w,w,b,w,b,b,w,输出：,25,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);,26,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;,27,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.,28,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,29,分析：逐行搜索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;检查是否该数是否用过,30,筛选法创建素数表,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;,32,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;,33,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;,34,主程序：,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.,35,上机练习题,1.添加自然数问题。（add.pas）,要求找出具有下列性质的数的个数(包含输入的自然数n)：,先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理:,.不作任何处理;,.在它的左边加上一个自然数,但该自然数不能超过原数的一半;,.加上数后,继续按此规则进行处理,直到不能再加自然数为止.,输入文件：add.in,一行，n的值。,输出文件：add.out，一行，按照规则可产生的自然数个数。,36,样例：,输入文件：,6,满足条件的数为 6,16,26,126,36,136,输出文件,6,37,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.,38,2.跳马问题。（jump.pas）,在5*5格的棋盘上，有一个国际象棋的马，它可以朝8个方向跳，但不允许出界或跳到已跳过的格子上，要求求出跳遍整个棋盘后的不同的路径条数。,输出文件：jump.out，一行，路径条数。,39,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;,40,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.,42,3.过河卒,棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。,43,棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过20的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。,【输入】,一行四个数据，分别表示B点坐标和马的坐标。,【输出】,一个数据，表示所有的路径条数。,【样例输入】,6 6 3 2,【样例输出】,17,44,题目分析：,本题是一道典型的深度优先搜索题目。,需要处理好的细节有：,1.读入“马”的坐标，控制好八个方向。,2.在（n,m）棋盘上控制好“马”所能跳出的边界。,3.按向下、向右两个方向搜索，只要当前没有走到（n,m）点且下一节点未访问过，则搜索。,45,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;,46,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.,47,4.素数环问题。（sushu.pas）,把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。,请输出一种摆放方法。,输出文件：sushu.out,一行，以1开始的20个整数，中间用一个空格隔开，最后一个数后面没有空格。,48,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;,49,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;,50,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.,51,