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

考试题目-宽度优先搜索


第一题

跳 棋(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.


相关文章:
广度优先搜索和深度优先搜索训练题
广度优先搜索和深度优先搜索训练题_IT/计算机_专业资料。ACM,算法,图,广度优先深度...2014小学教师资格考试《... 2014年幼儿园教师资格考... 2014教师资格中学教育...
宽度优先搜索解决八数码问题
宽度优先搜索解决八数码问题_计算机软件及应用_IT/计算机_专业资料。八数码问题宽度优先搜索原程序加注释 解八数码问题:任意输入两个九宫格作为初始状态和目标状态,用...
算法分析复习题目及答案
B )。 D、回溯法 37.采用广度优先策略搜索的算法是( A、分支界限法 B、...算法分析与设计考试复习... 13页 2下载券 算法分析与设计复习题答... 暂无评价...
广度优先搜索专题训练(题目)
注意力广度训练 暂无评价 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 广度优先搜索专题训练(题目) 隐藏>>...
考试作业题目指南1
jmydyy@sina.com 密码 111111 考试作业题目指南(下列内容选一,题目自己定,3000 字左右) (一)与健康相关的问题: 1、健康与保健意识; 2、健康与心理; 3、健康...
广度优先搜索专题训练(题目,11月22日修改)
广度优先搜索专题训练(题目,11月22日修改) 隐藏>> 广度优先搜索专题训练(报告命名:年级 专业 姓名+专题名字 专业+姓名 专题名字) 广度优先搜索专题训练(报告命名:...
速卖通考试题目2016714
AliExpress 无忧物流-优先 C. AliExpress 无忧物流-标准 D. 线下中国邮政 o ...搜索人气 o o o o 相关知识点 数据纵横相关 (不定项选择,共 3 题,每题 ...
信息检索考试题目参考
"; "C 题名"; 97. "在百度中搜索关于浙江工业大学图书馆的有关信息时,最...种期刊优先以电子方式出版, 大大提高了文献 网上出版的速度和效率,优先以电子...
算法分析期末试题集答案
回溯法在问题的解空间树中,按(D)策略,从根结点出发搜索解空间树。 A. 广度...{u} for each vertex do 4 3 四、算法理解题(本题 10 分) 根据优先队列...
深度优先和宽度优先搜索
深度优先和宽度优先搜索_IT/计算机_专业资料。穷举法是指在一个有穷的可能的解...2014年6月大学英语六级考试真题及答案 2014年12月大学四级冲刺试题及答案 2014年...
更多相关标签:
宽度优先搜索 | 宽度优先搜索算法 | 八数码宽度优先搜索 | 树的宽度优先搜索算法 | 宽度优先搜索n皇后 | 解释宽度优先搜索 | 用宽度优先搜索 迷宫 | 人工智能宽度优先搜索 |