广度优先搜索和深度优先搜索训练题.doc

【题目1】N皇后问题(八皇后问题的扩展)【题目2】排球队员站位问题【题目3】把自然数分解为若干个自然数之和。【题目4】把自然数分解为若干个自然数之积。【题目5】马的遍历问题。【题目6】加法分式分解【题目7】地图着色问题【题目8】在n*n的正方形中放置长为2,宽为1的长条块,【题目9】找迷宫的最短路径。（广度优先搜索算法）【题目10】火车调度问题【题目11】农夫过河【题目12】七段数码管问题。【题目13】把1-8这8个数放入下图8个格中,要求相邻的格(横,竖,对角线)上填的数不连续.【题目14】在44的棋盘上放置8个棋,要求每一行,每一列上只能放置2个.【题目15】迷宫问题.求迷宫的路径.(深度优先搜索法)【题目16】一笔画问题【题目17】城市遍历问题.【题目18】棋子移动问题【题目19】求集合元素问题（1,2x+1,3X+1类)【题目】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。const max=8;var i,j:integer;a:array1.max of 0.max; 放皇后数组b:array2.2*max of boolean; /对角线标志数组c:array-(max-1).max-1 of boolean; 对角线标志数组col:array1.max of boolean; 列标志数组total:integer; 统计总数procedure output; 输出var i:integer;begin write(No.:4,total+1:2,); for i:=1 to max do write(ai:3);write( ); if (total+1) mod 2 =0 then writeln; inc(total);end;function ok(i,dep:integer):boolean; 判断第dep行第i列可放否begin ok:=false; if ( bi+dep=true) and ( cdep-i=true) and (adep=0) and (coli=true) then ok:=trueend;procedure try(dep:integer);var i,j:integer;begin for i:=1 to max do 每一行均有max种放法 if ok(i,dep) then begin adep:=i; bi+dep:=false; /对角线已放标志 cdep-i:=false; 对角线已放标志 coli:=false; 列已放标志 if dep=max then output else try(dep+1); 递归下一层 adep:=0; 取走皇后,回溯 bi+dep:=true; 恢复标志数组 cdep-i:=true; coli:=true; end;end;begin for i:=1 to max do begin ai:=0;coli:=true;end; for i:=2 to 2*max do bi:=true; for i:=-(max-1) to max-1 do ci:=true; total:=0; try(1); writeln(total:,total);end.【测试数据】n=8 八皇后问题No. 1 1 5 8 6 3 7 2 4 No. 2 1 6 8 3 7 4 2 5No. 3 1 7 4 6 8 2 5 3 No. 4 1 7 5 8 2 4 6 3No. 5 2 4 6 8 3 1 7 5 No. 6 2 5 7 1 3 8 6 4No. 7 2 5 7 4 1 8 6 3 No. 8 2 6 1 7 4 8 3 5No. 9 2 6 8 3 1 4 7 5 No.10 2 7 3 6 8 5 1 4No.11 2 7 5 8 1 4 6 3 No.12 2 8 6 1 3 5 7 4No.13 3 1 7 5 8 2 4 6 No.14 3 5 2 8 1 7 4 6No.15 3 5 2 8 6 4 7 1 No.16 3 5 7 1 4 2 8 6No.17 3 5 8 4 1 7 2 6 No.18 3 6 2 5 8 1 7 4No.19 3 6 2 7 1 4 8 5 No.20 3 6 2 7 5 1 8 4No.21 3 6 4 1 8 5 7 2 No.22 3 6 4 2 8 5 7 1No.23 3 6 8 1 4 7 5 2 No.24 3 6 8 1 5 7 2 4No.25 3 6 8 2 4 1 7 5 No.26 3 7 2 8 5 1 4 6No.27 3 7 2 8 6 4 1 5 No.28 3 8 4 7 1 6 2 5No.29 4 1 5 8 2 7 3 6 No.30 4 1 5 8 6 3 7 2No.31 4 2 5 8 6 1 3 7 No.32 4 2 7 3 6 8 1 5No.33 4 2 7 3 6 8 5 1 No.34 4 2 7 5 1 8 6 3No.35 4 2 8 5 7 1 3 6 No.36 4 2 8 6 1 3 5 7No.37 4 6 1 5 2 8 3 7 No.38 4 6 8 2 7 1 3 5No.39 4 6 8 3 1 7 5 2 No.40 4 7 1 8 5 2 6 3No.41 4 7 3 8 2 5 1 6 No.42 4 7 5 2 6 1 3 8No.43 4 7 5 3 1 6 8 2 No.44 4 8 1 3 6 2 7 5No.45 4 8 1 5 7 2 6 3 No.46 4 8 5 3 1 7 2 6No.47 5 1 4 6 8 2 7 3 No.48 5 1 8 4 2 7 3 6No.49 5 1 8 6 3 7 2 4 No.50 5 2 4 6 8 3 1 7No.51 5 2 4 7 3 8 6 1 No.52 5 2 6 1 7 4 8 3No.53 5 2 8 1 4 7 3 6 No.54 5 3 1 6 8 2 4 7No.55 5 3 1 7 2 8 6 4 No.56 5 3 8 4 7 1 6 2No.57 5 7 1 3 8 6 4 2 No.58 5 7 1 4 2 8 6 3No.59 5 7 2 4 8 1 3 6 No.60 5 7 2 6 3 1 4 8No.61 5 7 2 6 3 1 8 4 No.62 5 7 4 1 3 8 6 2No.63 5 8 4 1 3 6 2 7 No.64 5 8 4 1 7 2 6 3No.65 6 1 5 2 8 3 7 4 No.66 6 2 7 1 3 5 8 4No.67 6 2 7 1 4 8 5 3 No.68 6 3 1 7 5 8 2 4No.69 6 3 1 8 4 2 7 5 No.70 6 3 1 8 5 2 4 7No.71 6 3 5 7 1 4 2 8 No.72 6 3 5 8 1 4 2 7No.73 6 3 7 2 4 8 1 5 No.74 6 3 7 2 8 5 1 4No.75 6 3 7 4 1 8 2 5 No.76 6 4 1 5 8 2 7 3No.77 6 4 2 8 5 7 1 3 No.78 6 4 7 1 3 5 2 8No.79 6 4 7 1 8 2 5 3 No.80 6 8 2 4 1 7 5 3No.81 7 1 3 8 6 4 2 5 No.82 7 2 4 1 8 5 3 6No.83 7 2 6 3 1 4 8 5 No.84 7 3 1 6 8 5 2 4No.85 7 3 8 2 5 1 6 4 No.86 7 4 2 5 8 1 3 6No.87 7 4 2 8 6 1 3 5 No.88 7 5 3 1 6 8 2 4No.89 8 2 4 1 7 5 3 6 No.90 8 2 5 3 1 7 4 6No.91 8 3 1 6 2 5 7 4 No.92 8 4 1 3 6 2 7 5total:92对于N皇后:皇后 N 4 5 6 7 8 9 10 方案数 2 10 4 40 92 352 724 【题目】排球队员站位问题图为排球场的平面图，其中一、二、三、四、五、六为位置编号，二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻手。队员所穿球衣分别为，号，但每个队 四 三 二 员的球衣都与他们的站位号不同。已知号、号队员不在后排，号、号队员不是二传手，号、号队员不在同一排，号、 五 六 一 号队员不是副攻手。 编程求每个队员的站位情况。【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。【参考程序】type sset=set of 1.6;var a:array1.6of 1.6; d:array1.6of sset; i:integer;procedure output; 输出begin if not( (a3in 2,3,4)= (a4 in2,3,4) then begin 3,4号队员不在同一排 write(number:);for i:=1 to 6 do write(i:8);writeln; write(weizhi:);for i:=1 to 6 do write(ai:8);writeln; end;end;procedure try(i:integer;s:sset); 递归过程 i:第i个人,s:哪些位置已安排人了var j,k:integer;begin for j:=1 to 6 do begin 每个人都有可能站1-6这6个位置 if (j in di) and not(j in s) then begin j不在di中,则表明第i号人不能站j位. j如在s集合中,表明j位已排人了 ai:=j; 第 i 人可以站 j 位 if i6 then try(i+1,s+j) 未安排妥,则继续排下去 else output; 6个人都安排完,则输出 end; end;end;begin for i:=1 to 6 do di:=1.6-i; 每个人的站位都与球衣的号码不同 d1:=d1-1,5,6; d6:=d6-1,5,6; 1,6号队员不在后排 d2:=d2-2,5; d3:=d3-2,5; 2,3号队员不是二传手 d5:=d5-3,6; d6:=d6-3,6; 5,6号队员不是副攻手 try(1,);end.【题目】把自然数分解为若干个自然数之和。【参考答案】 n total 5 7 6 11 7 15 10 42 100 190569291【参考程序】var n:byte; num:array0.255 of byte; total:word;procedure output(dep:byte);var j:byte;begin for j:=1 to dep do write(numj:3);writeln; inc(total);end;procedure find(n,dep:byte); N:待分解的数,DEP:深度 var i,j,rest:byte; begin for i:=1 to n do 每一位从N到1去试 if numdep-10) then begin find(rest,dep+1);end else if rest=0 then output(dep);刚好相等则输出 numdep:=0; end; end;begin 主程序 writeln(input n:);readln(n); fillchar(num,sizeof(num),0); total:=0; num0:=0; find(n,1); writeln(sum=,total);end.【题目】把自然数分解为若干个自然数之积。【参考程序】var path :array1.1000 of integer; total,n:integer;procedure find(k,sum,dep:integer); K:var b,d:Integer;begin if sum=n then 积等于N begin write(n,=,path1); for d:=2 to dep-1 do write(*,pathd); writeln;inc(total); exit; end; if sumn then exit; 累积大于N for b:= trunc(n/sum)+1 downto k do 每一种可能都去试 begin pathdep:=b; find(b,sum*b,dep+1); end;end;beginreadln(n); total:=0;find(2,1,1);writeln(total:,total);readln;end.【题目】马的遍历问题。在的棋盘中，马只能走日字。马从位置(x,y)处出发，把 棋盘的每一格都走一次，且只走一次。找出所有路径。【参考程序】 深度优先搜索法const n=5;m=4;fx:array1.8,1.2of -2.2=(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1), (-2,1),(-1,2); 八个方向增量var dep,i:byte; x,y:byte; cont:integer; 统计总数 a:array1.n,1.mof byte; 记录走法数组procedure output; 输出,并统计总数var x,y:byte;begin cont:=cont+1; writeln; writeln(count=,cont); for y:=1 to n do begin for x:=1 to m do write(ay,x:3); writeln; end; readln; halt;end;procedure find(y,x,dep:byte);var i,xx,yy:integer;begin for i:=1 to 8 do begin xx:=x+fxi,1;yy:=y+fxi,2; 加上方向增量,形成新的坐标 if (xx in 1.m)and(yy in 1.n)and(ayy,xx=0) then 判断新坐标是否出界,是否已走过? begin ayy,xx:=dep; 走向新的坐标 if (dep=n*m) then output else find(yy,xx,dep+1); 从新坐标出发,递归下一层 ayy,xx:=0 回溯,恢复未走标志 end; end;end;begin cont:=0; fillchar(a,sizeof(a),0); dep:=1; writeln(input y,x);readln(y,x); x:=1;y:=1; if (yn) or(xm) then begin writeln(x,y error!);halt;end; ay,x:=1; find(y,x,2); if cont=0 then writeln(No answer!) else write(The End!); readln;end.【题目】加法分式分解。如：1/2=1/4+1/4.找出所有方案。 输入： 为要分解的分数的分母 为分解成多少项【参考程序】program fenshifenjie;const nums=5;var t,m,dep:integer; n,maxold,max,j:longint; path:array0.nums of longint; maxok,p:boolean; sum,sum2:real;procedure print;var i:integer;begin t:=t+1; if maxok=true then begin maxold:=pathm;maxok:=false;end; write (NO.,t); for i:=1 to m do write( ,pathi:4); writeln; if path1=pathm then begin writeln(Ok! total:,t:4);readln;halt;end;end;procedure input;begin writeln (input N:); readln(n); writeln (input M(M=,nums:1,):); readln(m); if (n=0) or (m4) or (nmaxlongint) then begin writeln(Invalid Input!);readln;halt;end;end;function sum1(ab:integer):real;var a,b,c,d,s1,s2:real; i:integer;begin if ab=1 then sum1:=1/path1 else begin a:=path1; b:=1 ; c:=path2; d:=1; for i:=1 to ab-1 do begin s2:=(c*b+a*d); s1:=(a*c); a:=s1; b:=s2; c:=pathi+2; end; sum1:=s2/s1; end;end;procedure back;begin dep:=dep-1; if dep=m-2 then max:=maxold; sum:=sum-1/pathdep; j:=pathdep;end;procedure find;begin repeat dep:=dep+1; j:=pathdep-1-1; p:=false; repeat j:=j+1; if (depm) and (j=1/n then p:=false else begin p:=true; pathdep:=j; sum:=sum+1/pathdep; end else if jmax then back; if dep=m then begin pathdep:=j; sum2:=sum1(m); if (sum2)1/n then p:=false; if (sum2)=1/n then begin print; max:=j; back; end; if (sum2=max) then back; end; until p until dep=0;end;begin INPUT; maxok:=true; for t:=0 to m do patht:=n; dep:=0; t:=0; sum:=0; max:=maxlongint; find; readln;end.【题目】地图着色问题【参考程序】const lin:array1.12,1.12 of 0.1 区域相邻数组,1表示相邻 =(0,1,1,1,1,1,0,0,0,0,0,0), (1,0,1,0,0,1,1,1,0,0,0,0), (1,1,0,1,0,0,0,1,1,0,0,0), (1,0,1,0,1,0,1,0,1,1,0,0), (1,0,0,1,0,1,0,0,0,1,1,0), (1,1,0,0,1,0,1,0,0,0,1,0), (0,1,0,0,0,1,0,1,0,0,1,1), (0,1,1,0,0,0,1,0,1,0,0,1), (0,0,1,1,0,0,0,1,0,1,0,1), (0,0,0,1,1,0,0,0,1,0,1,1), (0,0,0,0,1,1,1,0,0,1,0,1), (0,0,0,0,0,0,1,1,1,1,1,1);var color:array1.12 of byte; color数组放已填的颜色 total:integer;function ok(dep,i:byte):boolean; 判断选用色i是否可用var k:byte; 条件:相邻的区域颜色不能相同begin for k:=1 to dep do if (lindep,k=1) and (i=colork) then begin ok:=false;exit;end; ok:=true;end;procedure output; 输出var k:byte;begin for k:=1 to 12 do write(colork, );writeln; total:=total+1;end;procedure find(dep:byte); 参数dep:当前正在填的层数var i:byte;begin for i:=1 to 4 do begin 每个区域都可能是1-4种颜色 if ok(dep,i) then begin colordep:=i; if dep=12 then output else find(dep+1); colordep:=0; 恢复初始状态,以便下一次搜索 end; end;end;begintotal:=0; 总数初始化fillchar(color,sizeof(color),0);find(1);writeln(total:=,total);end.【参考程序】const lin数组:代表区域相邻情况lin:array1.12 of set of 1.12 = (2,3,4,5,6,1,3,6,7,8,1,2,4,8,9,1,3,5,9,10,1,4,6,10,11, 1,2,5,7,11,12,8,11,6,2,12,9,7,2,3,12,8,10,3,4, 12,9,11,4,5,12,7,10,5,6,7,8,9,10,11);color:array1.4 of char=(r,y,b,g);var a:array1.12 of byte; 因有12个区域,故a数组下标为1-12 total:integer;function ok(dep,i:integer):boolean; 判断第dep块区域是否可填第i种色var j:integer; j 为什么设成局部变量?begin ok:=true; for j:=1 to 12 do if (j in lindep) and (aj=i) then ok:=false;end;procedure output; 输出过程var j:integer; j 为什么设成局部变量?begin inc(total); 方案总数加1 write(total:4); 输出一种方案 for j:=1 to 12 do write(coloraj:2);writeln;end;procedure find(dep:byte);var i:byte; i 为什么设成局部变量?begin for i:=1 to 4 do 每一区域均可从4种颜色中选一 begin if ok(dep,i) then begin 可填该色 adep:=i; 第dep块区域填第i种颜色 if (dep=12) then output 填完12个区域 else find(dep+1); 未填完 adep:=0; 取消第dep块区域已填的颜色 end; end;end;begin 主程序 fillchar(a,sizeof(a),0); 记得要给变量赋初值! total:=0; find(1); writeln(End.);end.【题目】在n*n的正方形中放置长为2,宽为1的长条块,问放置方案如何【参考程序】const n=4;var k,u,v,result:integer; a:array1.n,1.nof char;procedure printf; 输出 begin result:=result+1; 方案总数加1 writeln(- ,result, -); for v:=1 to n do begin for u:=1 to n do write(au,v); writeln end; writeln; end;procedure try; 填放长条块 var i,j,x,y:integer; full:boolean; begin full:=true; if ktrunc(n*n/2) then full:=false;测试是否已放满 if full then printf; 放满则可输出 if not full then begin 未满 x:=0;y:=1; 以下先搜索未放置的第一个空位置 repeat x:=x+1; if xn then begin x:=1;y:=y+1 end until ax,y= ; 找到后,分两种情况讨论 if ax+1,y= then begin 第一种情况:横向放置长条块 k:=k+1; 记录已放的长条数 ax,y:=chr(k+ord(); 放置 ax+1,y:=chr(k+ord(); try; 递归找下一个空位置放 k:=k-1; ax,y:= ; 回溯,恢复原状 ax+1,y:= end; if ax,y+1= then begin 第二种情况:竖向放置长条块 k:=k+1; 记录已放的长条数 ax,y:=chr(k+ord(0); 放置 ax,y+1:=chr(k+ord(0); try; 递归找下一个空位置放 k:=k-1; ax,y:= ; 回溯,恢复原状 ax,y+1:= end; end; end;begin 主程序 fillchar(a,sizeof(a), ); 记录放置情况的字符数组,初始值为空格 result:=0; k:=0; k记录已放的块数,如果k=n*n/2,则说明已放满 try; 每找到一个空位置,把长条块分别横放和竖放试验end.【参考程序】const dai:array 1.2,1.2of integer=(0,1),(1,0);type node=record w,f:integer; end;var a:array1.20,1.20of integer;path:array0.200of node;s,m,n,nn,i,j,x,y,dx,dy,dep:integer;p,px:boolean;procedure inputn;begin write(input n);readln(n);n:=4;nn:=n*n;m:=nn div 2;end;procedure print;var i,j:integer;begininc(s);writeln(no,s);for i:=1 to n do begin for j:=1 to n do write(ai,j:3);writeln; end; writeln;end;function fg(h,v:integer):boolean;var p:boolean;begin p:=false; if (h=n) and (v=n) then if ah,v=0 then p:=true; fg:=p; end;procedure back;begin dep:=dep-1; if dep=0 then begin p:=true ;px:=true;end else begin i:=pathde