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

《广度优先搜索和深度优先搜索训练题 .pdf》由会员分享，可在线阅读，更多相关《广度优先搜索和深度优先搜索训练题 .pdf（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【题目 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、放置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;/对角线标志数组 对角线标志数组 col:array1.max

3、of boolean;列标志数组 total:integer;统计总数 procedure output;输出 var i:integer;begin 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 40 页 -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+de

4、p=true)and(cdep-i=true)and(adep=0)and(coli=true)then ok:=true end;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;取走皇后,回溯

5、 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);名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 40 页 -writeln(total:,total);end.【测试数据】n=8 八皇后问题 No.1 1 5 8 6 3 7 2 4 No.2 1 6 8 3

6、7 4 2 5 No.3 1 7 4 6 8 2 5 3 No.4 1 7 5 8 2 4 6 3 No.5 2 4 6 8 3 1 7 5 No.6 2 5 7 1 3 8 6 4 No.7 2 5 7 4 1 8 6 3 No.8 2 6 1 7 4 8 3 5 No.9 2 6 8 3 1 4 7 5 No.10 2 7 3 6 8 5 1 4 No.11 2 7 5 8 1 4 6 3 No.12 2 8 6 1 3 5 7 4 No.13 3 1 7 5 8 2 4 6 No.14 3 5 2 8 1 7 4 6 No.15 3 5 2 8 6 4 7 1 No.16 3 5 7 1

7、 4 2 8 6 No.17 3 5 8 4 1 7 2 6 No.18 3 6 2 5 8 1 7 4 No.19 3 6 2 7 1 4 8 5 No.20 3 6 2 7 5 1 8 4 No.21 3 6 4 1 8 5 7 2 No.22 3 6 4 2 8 5 7 1 No.23 3 6 8 1 4 7 5 2 No.24 3 6 8 1 5 7 2 4 No.25 3 6 8 2 4 1 7 5 No.26 3 7 2 8 5 1 4 6 No.27 3 7 2 8 6 4 1 5 No.28 3 8 4 7 1 6 2 5 No.29 4 1 5 8 2 7 3 6 No.30

8、 4 1 5 8 6 3 7 2 No.31 4 2 5 8 6 1 3 7 No.32 4 2 7 3 6 8 1 5 No.33 4 2 7 3 6 8 5 1 No.34 4 2 7 5 1 8 6 3 No.35 4 2 8 5 7 1 3 6 No.36 4 2 8 6 1 3 5 7 No.37 4 6 1 5 2 8 3 7 No.38 4 6 8 2 7 1 3 5 No.39 4 6 8 3 1 7 5 2 No.40 4 7 1 8 5 2 6 3 No.41 4 7 3 8 2 5 1 6 No.42 4 7 5 2 6 1 3 8 No.43 4 7 5 3 1 6 8

9、 2 No.44 4 8 1 3 6 2 7 5 No.45 4 8 1 5 7 2 6 3 No.46 4 8 5 3 1 7 2 6 No.47 5 1 4 6 8 2 7 3 No.48 5 1 8 4 2 7 3 6 No.49 5 1 8 6 3 7 2 4 No.50 5 2 4 6 8 3 1 7 No.51 5 2 4 7 3 8 6 1 No.52 5 2 6 1 7 4 8 3 No.53 5 2 8 1 4 7 3 6 No.54 5 3 1 6 8 2 4 7 No.55 5 3 1 7 2 8 6 4 No.56 5 3 8 4 7 1 6 2 No.57 5 7 1

10、 3 8 6 4 2 No.58 5 7 1 4 2 8 6 3 No.59 5 7 2 4 8 1 3 6 No.60 5 7 2 6 3 1 4 8 No.61 5 7 2 6 3 1 8 4 No.62 5 7 4 1 3 8 6 2 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 40 页 -No.63 5 8 4 1 3 6 2 7 No.64 5 8 4 1 7 2 6 3 No.65 6 1 5 2 8 3 7 4 No.66 6 2 7 1 3 5 8 4 No.67 6 2 7 1 4 8 5 3 No.68 6 3 1 7 5 8 2 4 No.69 6 3

11、1 8 4 2 7 5 No.70 6 3 1 8 5 2 4 7 No.71 6 3 5 7 1 4 2 8 No.72 6 3 5 8 1 4 2 7 No.73 6 3 7 2 4 8 1 5 No.74 6 3 7 2 8 5 1 4 No.75 6 3 7 4 1 8 2 5 No.76 6 4 1 5 8 2 7 3 No.77 6 4 2 8 5 7 1 3 No.78 6 4 7 1 3 5 2 8 No.79 6 4 7 1 8 2 5 3 No.80 6 8 2 4 1 7 5 3 No.81 7 1 3 8 6 4 2 5 No.82 7 2 4 1 8 5 3 6 No

12、.83 7 2 6 3 1 4 8 5 No.84 7 3 1 6 8 5 2 4 No.85 7 3 8 2 5 1 6 4 No.86 7 4 2 5 8 1 3 6 No.87 7 4 2 8 6 1 3 5 No.88 7 5 3 1 6 8 2 4 No.89 8 2 4 1 7 5 3 6 No.90 8 2 5 3 1 7 4 6 No.91 8 3 1 6 2 5 7 4 No.92 8 4 1 3 6 2 7 5 total:92 对于 N 皇后:皇后N 4 5 6 7 8 9 10 方案数2 10 4 40 92 352 724【题目】排球队员站位问题图为排球场的平面图，其

13、中一、二、三、四、五、六为位置编号，二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻手。队员所穿球衣分别为，号，但每个队 四 三 二 员的球衣都与他们的站位号不同。已知号、号队员不在后排，号、号队员不是二传手，号、号队员不在同一排，号、五 六 一 号队员不是副攻手。编程求每个队员的站位情况。【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。【参考程序】type sset=set of 1.6;var a:array1.6of 1.6;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 40 页 -

14、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 fo

15、r 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号队员不在后排

16、d2:=d2-2,5;d3:=d3-2,5;2,3号队员不是二传手 d5:=d5-3,6;d6:=d6-3,6;5,6号队员不是副攻手 try(1,);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 40 页 -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 wr

17、ite(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);名师资料总结-精品资料欢迎下载-名师精心整理-第 6

18、页，共 40 页 -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);

19、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;begin readln(n);total:=0;find(2,1,1);writeln(total:,total);readln;end.【题目】马的遍历问题。在的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。名师资料总结-精品资料欢迎下载-名师精心整理-第 7

20、页，共 40 页 -【参考程序】深度优先搜索法 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 be

21、gin 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

22、,xx,dep+1);从新坐标出发,递归下一层 ayy,xx:=0 回溯,恢复未走标志 end;end;end;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 40 页 -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

23、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:=f

24、alse;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;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 40 页 -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 wr

25、iteln(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 名师资

26、料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 40 页 -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=

27、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;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 40 页 -begin INPUT;maxok:=true;for t:=0 to m do patht:=n;dep:=0;t:=0;sum:=0;max:=maxlongint;find;readln;end.【

28、题目】地图着色问题【参考程序】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

29、,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;名师资料总结-精品

30、资料欢迎下载-名师精心整理-第 12 页，共 40 页 -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)

31、;colordep:=0;恢复初始状态,以便下一次搜索 end;end;end;begin total:=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

32、,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 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 40 页 -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 o

33、k:=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 种颜色

34、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.);名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 40 页 -end.【题目】在 n*n的正方形中放置长为2,宽为 1 的长条块,问放置方案如何【参考程序】const n=4;var k,u,v,result:integer;a:array1.n,1.no

35、f 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 fu

36、ll 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;名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 40 页 -ax,y:=;回溯,恢复原状 ax+1,y:=end;if ax,y

37、+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

38、 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;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 40 页 -end;procedure print;var i,j:integ

39、er;begin inc(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

40、 begin i:=pathdep.w;j:=pathdep.f;x:=(i-1)div n)+1;y:=i mod n;if y=0 then y:=n;dx:=x+daij,1;dy:=y+daij,2;ax,y:=0;adx,dy:=0;end;end;begin 名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 40 页 -inputn;s:=0;fillchar(a,sizeof(a),0);x:=0;y:=0;dep:=0;path0.w:=0;path0.f:=0;repeat dep:=dep+1;i:=pathdep-1.w;repeat i:=i+1;x:=(

41、i-1)div n)+1;y:=i mod n;if y=0 then y:=n;px:=false;if fg(x,y)then begin j:=0;p:=false;repeat inc(j);dx:=x+daij,1;dy:=y+daij,2;if fg(dx,dy)and(j=2 then back else p:=false;until p;end else if i=nn then back else px:=false;until px;until dep=0;readln;end.【题目】找迷宫的最短路径。（广度优先搜索算法）名师资料总结-精品资料欢迎下载-名师精心整理-第

42、18 页，共 40 页 -【参考程序】uses crt;const migong:array 1.5,1.5 of integer=(0,0,-1,0,0),(0,-1,0,0,-1),(0,0,0,0,0),(0,-1,0,0,0),(-1,0,0,-1,0);迷宫数组 fangxiang:array 1.4,1.2 of-1.1=(1,0),(0,1),(-1,0),(0,-1);方向增量数组 type node=record lastx:integer;上一位置坐标 lasty:integer;nowx:integer;当前位置坐标 nowy:integer;pre:byte;本结点由哪

43、一步扩展而来 dep:byte;本结点是走到第几步产生的 end;var lujing:array1.25 of node;记录走法数组 closed,open,x,y,r:integer;procedure output;var i,j:integer;begin for i:=1 to 5 do begin for j:=1 to 5 do write(migongi,j:4);writeln;end;i:=open;repeat with lujingi do write(nowy:2,nowx:2,5)or(y5)or(x1)or(y1)or(migongy,x0)then begin

44、 未出界,未走过则可视为新的结点 inc(open);队列尾指针加1 with lujingopen do begin 记录新的结点数据 nowx:=x;nowy:=y;lastx:=lujingclosed.nowx;新结点由哪个坐标扩展而来 lasty:=lujingclosed.nowy;dep:=lujingclosed.dep+1;新结点走到第几步 pre:=closed;新结点由哪个结点扩展而来 end;migongy,x:=lujingclosed.dep+1;当前结点的覆盖范围 if(x=5)and(y=5)then begin 输出找到的第一种方案 writeln(ok,th

45、ats all right);output;halt;end;end;end;until closed=open;直到首指针大于等于尾指针,即所有结点已扩展完 end.【题目】火车调度问题【参考程序】const max=10;type shuzu=array1.max of 0.max;var stack,exitout:shuzu;n,total:integer;名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 40 页 -procedure output(exitout:shuzu);var i:integer;begin for i:=1 to n do write(exi

46、touti:2);writeln;inc(total);end;procedure find(dep,have,rest,exit_weizhi:integer;stack,exitout:shuzu);dep:步数,have:入口处有多少辆车;rest:车站中有多少车;exit_weizhi:从车站开出后,排在出口处的位置;stack:车站中车辆情况数组;exitout:出口处车辆情况数组 var i:integer;begin 分入站,出站两种情况讨论 if have0 then begin 还有车未入站 stackrest+1:=n+1-have;入站 if dep=2*n then o

47、utput(exitout)else find(dep+1,have-1,rest+1,exit_weizhi,stack,exitout);end;if rest0 then begin 还有车可出站 exitoutexit_weizhi+1:=stackrest;出站 if dep=2*n then output(exitout)经过 2n 步后,输出一种方案 else find(dep+1,have,rest-1,exit_weizhi+1,stack,exitout);end;end;begin writeln(input n:);readln(n);fillchar(stack,si

48、zeof(stack),0);fillchar(exitout,sizeof(exitout),0);total:=0;find(1,n,0,0,stack,exitout);writeln(total:,total);readln;end.名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 40 页 -【解法 2】用穷举二进制数串的方法完成.uses crt;var i,n,m,t:integer;a,s,c:array1.1000 of integer;procedure test;var t1,t2,k:integer;notok:boolean;begin t1:=0;k:

49、=0;t2:=0;i:=0;notok:=false;repeat 二进制数串中,0 表示出栈,1 表示入栈 i:=i+1;数串中第 I 位 if ai=1 then begin 第 I 位为 1,则表示车要入栈 inc(k);栈中车数 inc(t1);入栈记录,T1 为栈指针,S 为栈数组 st1:=k;end else 第 I 位为 0,车要出栈 if t11)and(at1)do begin at:=0;dec(t);at:=at+1;end;until a1=2;readln;end.N:4 6 7 8 TOTAL:14 132 429 1430【题目】农夫过河。一个农夫带着一只狼，一

50、只羊和一些菜过河。河边只有一条一船，由于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊要吃菜，请问农夫如何才能使三样东西平安过河。【算法分析】将问题数字化。用代表狼，代表羊，代表菜。则在河某一边物体的分布有以下种情况。物体个数 分布情况1,2 1,3 2,3 1,2,3 代码之和 是否相克相克相克当（两物体在一起而且）代码和为或时，必然是相克物体在一起的情况。【参考程序】const wt:array0.3of string5=(,WOLF,SHEEP,LEAVE);var left,right:array1.3 of integer;what,i,total,left_r