当前位置:首页 >> 学科竞赛 >>

考试题目-宽度优先搜索


第一题

跳 棋(1.PAS)

题目:跳棋的原始状态如下图。其中"0"表示空格,"-"表示白子,"+"表示黑子,"1— —7"表示棋盘格编号。跳棋的规则是: ⒈任意一个棋子可移到相邻的空位上; ⒉可跳过一个或两个棋子到空位上,与跳过的棋子的颜色无关; ⒊棋子向

左向右跳不限。 例如:4 到 1、5 到 4、3 到 5、6 到 3 是成功的四步走法。请编一程序,用 10 步完成从 原始状态跳变成目标状态。要求打印跳每一步后的状态,用数字表示棋盘格子的代号。如果 有多种方法,请都分别打印出来。 1 2 3 4 5 6 7 原始位置 0 - - - + + + 目标位置 + + + - - - 0 输入:原始位置和目标位置,分别占一行,共两行。 0 - - - + + + (原始位置) + + + - - - 0(目标位置) 输出:10 步完成从原始状态跳变成目标状态的过程 START:0 - - - + + + NO.1:- 0 - - + + + NO.2:- + - - 0 + + …… NO.10:+ + + - - - 0 END 输入输出样例: 1.IN 0 - - - + + + + + + - - - 0 1.OUT START:0 - - - + + + NO.1:- 0 - - + + + NO.2:- + - - 0 + + …… NO.10:+ + + - - - 0 END (注意:输入和输出的相邻两个棋子之间没有空格) 分析: ⒈数据库:数组g构成堆栈,存放棋子的状态。 ⒉结点的产生:与空位置间距-3到3的棋子可移入空位,生成新结点状态。 ⒊搜索策略:含有深度界限的深度优先搜索。

program ex143_2; type status=string[7]; {const start='0---+++'; obj='+++---0';} var g: array [0..10] of status; i,j,k: integer; start,obj:string; fin,fout:text; procedure draw;{输出} var i,j: integer; begin writeln(fout,'Start:',start); for i:=1 to 10 do writeln(fout,'No.',i,':',g[i]); writeln(fout,'End'); end; function exampass(w: integer): boolean;{判断有否重复状态} var i: integer; begin for i:=1 to w-1 do if g[i]=g[w] then begin exampass:=false; exit; end; exampass:=true; end; procedure run(t: integer);{搜索生成新结点} var i,k: integer; begin k:=pos('0',g[t-1]); for i:=-3 to 3 do if (i<>0) and (k+i>=1) and (k+i<=7) then begin g[t]:=g[t-1]; g[t,k]:=g[t,k+i]; g[t,k+i]:='0'; if exampass(t) then if g[t]=obj then draw

else if t<10 then run(t+1); end; end; begin assign(fin,'1.in'); assign(fout,'1.out'); reset(fin); rewrite(fout); readln(fin,start); readln(fin,obj); close(fin); g[0]:=start; run(1); close(fout); end.

第二题

跳马程序(2.PAS)

题目:在 5*5 格的棋盘上,从(1,1)点出发,按日字跳马,要求不重复地跳经所有方 格。求出符合要求的所有跳马方案总数 N。 1 1 2 3 4 5 输入: 无 输出:前 5 行表示第一种移动方案。分别是 5*5 格棋盘每个方格被马通过时属于方案 中的第几步。 第六行一个值 N,表示马不重复地跳经所有方格方案总数 输入输出样例: 3 2 4 1 2 3 4 5

2.IN

2.OUT 1 16 11 22 25 10 21 24 17 12 15 2 9 6 23 20 7 4 13 18 3 14 19 8 5 25 (任意范例,可能不准确)

program horse; var a:array[1..5,1..5] of integer; {记每一步走在棋盘的哪一格} b:array[1..5,1..5] of boolean; {棋盘的每一格有没有被走过} u,v:array[1..8] of integer; {8 个方向上的 x,y 增量} i,j,num:integer; fout:text; procedure print; {打印方案} var k,kk:integer; begin num:=num+1; {统计总方案} if num=1 then {打印出前 5 种方案} begin for k:=1 to 5 do {打印本次方案} begin for kk:=1 to 5 do write(fout,a[k,kk],' '); writeln(fout,''); end; end; end; procedure try(i,j,n:integer); {以每一格为阶段,在每一阶段中试遍 8 个方向} var k,x,y:integer; {这三个变量一定要定义局部变量} begin if n>25 then begin print; exit;end ; {达到最大规模打印、统计方案} for k:=1 to 8 do {试遍 8 个方向} begin x:=i+u[k]; y:=j+v[k] ; {走此方向,得到的新坐标} if (x<=5) and (x>=1) and (y<=5) and (y>=1)and b[x,y] then {如果新坐标在棋盘上, 并且这一格可以走} begin b[x,y]:=false; a[x,y]:=n;

try(x,y,n+1); b[x,y]:=true; a[x,y]:=0; end;

{从(x,y)去搜下一步该如何走}

end; end; begin assign(fout,'2.out'); rewrite(fout); u[1]:=1; v[1]:=-2; {8 个方向的 x,y 增量} u[2]:=2; v[2]:=-1; u[3]:=2; v[3]:=1; u[4]:=1; v[4]:=2; u[5]:=-1; v[5]:=2; u[6]:=-2; v[6]:=1; u[7]:=-2; v[7]:=-1; u[8]:=-1; v[8]:=-2; for i:=1 to 5 do {初始化} for j:=1 to 5 do begin a[i,j]:=0; b[i,j]:=true; end; a[1,1]:=1; b[1,1]:=false; {从(1,1)第一步开始走} try(1,1,2); {从(1,1)开始搜第 2 步该怎样走} writeln(fout,num); {输出总方案(304)} close(fout); end.


相关文章:
广度优先搜索训练题
广度优先搜索训练题 一、奇怪的电梯源程序名 可执行文件名 输入文件名 输出文件名 LIFT.PAS LIFT.EXE LIFT.IN LIFT.OUT 呵呵, 有一天我做了一个梦, 梦见了...
广度优先搜索专题训练(题目)
注意力广度训练 暂无评价 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 广度优先搜索专题训练(题目) 隐藏>>...
广度优先搜索和深度优先搜索训练题
广度优先搜索和深度优先搜索训练题_IT/计算机_专业资料。ACM,算法,图,广度优先深度...2014小学教师资格考试《... 2014年幼儿园教师资格考... 2014教师资格中学教育...
2016百度SEM初级认证考试题
2016百度SEM初级认证考试题_计算机硬件及网络_IT/...实际执行结果为高级别优先执行,这一规则适用于: A:...13、网盟推广中,图片创意的大小要控制在多少 A、...
算法分析复习题目及答案
A、定义最优解 重叠性质 37.采用广度优先策略搜索的算法是( A )。 A、分支...2015国考行测模拟试题及历年真题 2015国考申论押密试卷及答案 2015国考面试通关...
深度优先搜索练习题
深度优先搜索练习题_电脑基础知识_IT/计算机_专业资料。深度优先搜索练习题一、...输入: 第一行是 goline 最大边的大小 (不大于 20) , 第二行是施工地点的...
第​二​章​部​分​习​题​参​考​答​案
(参考启发式搜索的全局择优和局部择优算法) A 1 B 4 D 1 2 1 3 E 2 L 4 F 1 2 C 1 G 2 M H I J K 3 1 O 不考虑代价,广度优先搜索过程...
宽度优先搜索解决八数码问题
宽度优先搜索解决八数码问题_计算机软件及应用_IT/计算机_专业资料。八数码问题宽度优先搜索原程序加注释 解八数码问题:任意输入两个九宫格作为初始状态和目标状态,用...
2017年高中信息技术会考上机考试题目及评分标准
2017 学年度密云区高中信息技术 会考上机考试题目及要求一、考试要求 1、每位...请你针对“一带一路”中自己感兴趣的内容搜索资料进行深入了解,并提 炼总结,...
百度初级认证考试题(附答案)
百度初级认证考试题(附答案)_IT认证_资格考试/认证...正确答案是 A;因为再出价方面账户单位越小,优先级...文件大小需要控制在系统限制内 答案解析:正确答案是 ...
更多相关标签:
宽度优先搜索 | 宽度优先搜索算法 | 宽度优先搜索具体应用 | 八数码宽度优先搜索 | 树的宽度优先搜索算法 | 宽度优先搜索策略 | 宽度优先搜索复杂度 | 宽度优先搜索 c语言 |