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

考试题目-宽度优先搜索


第一题

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



相关文章:
历年百度笔试题面试题集总
历年百度笔试题面试题集总_面试_求职/职场_实用文档。1:堆和栈的区别,什么...3:广度优先搜索算法 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索...
广度优先搜索专题训练(题目)
注意力广度训练 暂无评价 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 广度优先搜索专题训练(题目) 隐藏>>...
人工智能复习资料整理(修正版-如发现计算错误请指出)
常用盲目搜索算法:宽度优先搜索、深度优先搜索和等代价搜索。 二、问答题(计算题)(60 分) 1. 状态空间表示法(画图+解释) (考试时,只需写出以下红色边框图片的...
北大数据结构与算法期末考试模拟试卷
北大数据结构与算法期末考试模拟试卷_教育学_高等教育_教育专区。2014年春季北大...边上的权值 __都相等__ 时,宽度优先搜索算法可用来解决单源最短路径问 题?...
广度优先搜索初级题目
广度优先搜索初级题目及代码分享广度优先搜索初级题目及代码分享隐藏>> 广度优先搜索初级题目 邮递员问题 题目描述: 有一个邮递员要在 n 个城市之间来回送信。但有...
考试题05
考试题05_IT认证_资格考试/认证_教育专区。课程名称 专业 算法设计与分析 ...(5 分) e5 e 2 6 1 e1 3 e4 e3 5 e 4 2 4、使用宽度优先搜索方法...
搜索试题集
搜索试题集_IT认证_资格考试/认证_教育专区。noi 计算机 竞赛 信息学 奥林匹克...【execans.2 为深度优先搜索,广度优先搜索类,及技巧性题目题解】 【题目 1】...
宽度优先搜索解决八数码问题
宽度优先搜索解决八数码问题_计算机软件及应用_IT/计算机_专业资料。八数码问题宽度优先搜索原程序加注释 解八数码问题:任意输入两个九宫格作为初始状态和目标状态,用...
深度与广度优先搜索:迷宫问题
《数据结构课程设计》报告 题目:深度与广度优先搜索 --迷宫问题 专 业 计算机科学与技术 李柏 B 计算机 115 1110704512 巩永旺 2013 年 1 月 11 日 学生姓名...
[数据结构]深度与广度优先搜索:迷宫问题
11 7 参考文献 数据结构课程设计——深度与广度优先搜索:迷宫问题 1 设计题目 ...2014证券从业资格考试 2014证券资格证券交易高分突破试卷及答案 2014年证券考试《投...
更多相关标签: