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

考试题目-宽度优先搜索


第一题

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


相关文章:
人工智能复习资料整理(修正版-如发现计算错误请指出)
常用盲目搜索算法:宽度优先搜索、深度优先搜索和等代价搜索。 二、问答题(计算题)(60 分) 1. 状态空间表示法(画图+解释) (考试时,只需写出以下红色边框图片的...
广度优先搜索初级题目
广度优先搜索初级题目及代码分享广度优先搜索初级题目及代码分享隐藏>> 广度优先搜索初级题目 邮递员问题 题目描述: 有一个邮递员要在 n 个城市之间来回送信。但有...
广度优先搜索专题训练(题目,11月22日修改)
广度优先搜索专题训练(题目,11月22日修改) 隐藏>> 广度优先搜索专题训练(报告命名:年级 专业 姓名+专题名字 专业+姓名 专题名字) 广度优先搜索专题训练(报告命名:...
深度与广度优先搜索:迷宫问题
深度与广度优先搜索:迷宫问题_计算机软件及应用_IT/计算机_专业资料。《数据结构课程设计》报告 题目:深度与广度优先搜索 --迷宫问题 专 业 计算机科学与技术 李柏...
广度优先搜索 实例
广度优先搜索 实例_IT/计算机_专业资料。搜索引擎 优化广度优先搜索 实例【例题】...2014年各行业从业资格考试 2014年国家司法考试案例分析模拟题 2014年证劵市场基础...
第​二​章​部​分​习​题​参​考​答​案
(参考启发式搜索的全局择优和局部择优算法) 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 不考虑代价,广度优先搜索过程...
清华08计算机考研试题_研究生入学考试_高等教育_教育专区
宽度优先搜索; 2. 深度优先搜索; 3. A 算法。其中各节点旁标记的是该节点的...在本版的精华区里可以找到 05 至 07 年历年的应用方向笔试题目, 这些试题具有...
历年百度笔试题面试题集总
历年百度笔试题面试题集总_面试_求职/职场_实用文档。1:堆和栈的区别,什么...3:广度优先搜索算法 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索...
研究生考试题(GIS智能化)
研究生考试题(GIS智能化) 2008年考研2008年考研隐藏>> “地理信息智能化处理”...1、编程实现宽度优先搜索、深度优先搜索、等代价搜索、启发式搜索中的一种搜索方...
算法设计与分析2014试题A卷
考试形式 姓名 一、简答题(每小题 8 分,共 40 分)写出回溯算法的一般模式...请简述广度优先搜索算法的基本思想。 简述分治法与动态规划算法的区别于共同点? ...
更多相关标签: