算法实验报告：罗密欧与朱丽叶迷宫求解(共13页)

1、精选优质文档-倾情为你奉上专心-专注-专业河南科技大学课程设计报告课程名称：课程名称：算法设计与分析 设计题目设计题目：罗密欧与朱丽叶迷宫求解问题 院院 系：系： 电子信息工程学院 专专 业：业： 计算机科学与技术 班班 级：级： 计算机 092 班 学生姓名学生姓名: : 学学 号号:09* 起止日期起止日期: 2011 年 5 月 28 日 - 2011 年 6 月 3 日 指导教师指导教师: 孙士保、张明川、冀治航 精选优质文档-倾情为你奉上专心-专注-专业课程设计题目罗密欧与朱丽叶的迷宫问题姓名*学号*班级092 班系别电子信息工程学院专业计算机科学与技术组别1 人组长*组员*指导教师

2、姓名孙士保、张明川、冀治航课程设计目的进一步巩固 C 程序设计和算法设计与分析的基础知识，提升结构化程序、模块化程序设计的方法和能力， 深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。设计环境1. PC 兼容机 2Windows 2000/XP 操作系统3TC 集成开发环境或其他 C 语言开发环境课程设计要求和任务要求：1熟练掌握回溯法，能够利用回溯法解决实际问题；2使用文件进行存储和管理。程序启动时可从文件中读取信息，或

3、从键盘输入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存到文件中；3不同的功能使用不同的函数实现（模块化） ，对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。4对系统进行功能模块分析、画出总流程图和各模块流程图；5用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单；6通过命令行相应选项能直接进入某个相应菜单选项的功能模块；7所有程序需调试通过。任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括：1确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线；2程序能够演示一条罗密欧找到朱丽叶的路线过程等。课程设计工作进度计

4、划序 号起止日期工 作 内 容1下发任务书，分组，选定课题，查阅相关资料2总体设计，划分模块3编制源程序4上机调试，修改、完善系统5程序检查6撰写说明书精选优质文档-倾情为你奉上专心-专注-专业河南科技大学课程设计任务书 课程名称课程名称：算法设计与分析 题题 目目：罗密欧与朱丽叶迷宫求解问题院院 系：系： 电子信息工程学院 班班 级：级： 计算机科学与技术 092 班 学生姓名学生姓名: : * 指导教师指导教师: 孙士保、张明川、冀治航 起止日期起止日期: 2011 年 5 月 28 日 - 2011 年 6 月 3 日精选优质文档-倾情为你奉上专心-专注-专业 目录目录.22.3 函数之

5、间的关系.3第三章编写代码及运行程序.33.1 源程序.33.2 操作及运行结果.63.3 设计的心得体会.7精选优质文档-倾情为你奉上专心-专注-专业第一章第一章 需求分析需求分析1.1 课程设计题目课程设计题目对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少弯道路程序能够演示一条罗密欧找到朱丽叶的路线过程等1.2 课程设计任务及要求课程设计任务及要求罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个 mn 的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这 mn 个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任 何位置均可沿 8 个方向进入未封闭的房间。罗密欧位于迷

6、宫的。 (p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。1.3 软硬件软硬件运行环境及开发工具运行环境及开发工具硬件：装有 windows 操作系统的计算机软件：Visual C+6.0 精选优质文档-倾情为你奉上专心-专注-专业 第二章第二章 程序概要设计程序概要设计 2.1 系统流程图系统流程图 2.2 函数的划分：函数的划分： （1）函数 1：bool trackback (int x,int y) 递归调用

7、trackback 函数求出最优路径。（2）函数 2：void isfull() 判断房间是否全部走完（3）函数3：void main() 主函数初始化迷宫数组，并调用trackback函数输出一条迷宫路线。 输入 m,n,k,p,q,r,s -1-dirs count-0dep=m*n-k&x=r&y=s&dirsbest是 否 dirscountbest=dirs;count=1;1-.i 1-jbestwij=boardij+1-j直到 ji直到iip=x+diri0q=y+diri1x0&x0&ydirs boardpq=0;boardpq=de

8、p+1 di!=idirs+1-dis 直到ri=8 输出 best ,count *bestw精选优质文档-倾情为你奉上专心-专注-专业2.3函数之间的关系函数之间的关系： 如下图： main 函数 isfull 函数 调用 trackbask 函数 递归调用 trackbask 函数 输出结果 第三章第三章 编写代码及运行程序编写代码及运行程序3.1 源程序源程序#include int m,n,k;/m*n 迷宫，k 个封闭房间int x,y;/迷宫中 封闭房间的坐标int p,q,r,s;/罗密欧与朱丽叶的坐标int *square;/存储迷宫int *dir;/用来记录每一步的方向i

9、nt level(0);/记录正在探测第几步int finalLevel(0);/初始化为零int *result;/记录结果int *path;int turn(999);/记录最小拐弯数int dirx8=0,0,1,1,1,-1,-1,-1;/8 个方向变量int diry8=1,-1,-1,0,1,-1,0,1;bool trackback(int p,int q );bool IsFull();void main()int i, j;cin m n k;精选优质文档-倾情为你奉上专心-专注-专业result = new int *2;result0 = new int n*m;res

10、ult1 = new int n*m;path = new int *2;path0 = new int n*m;path1 = new int n*m;dir = new int m*n;square = new int *m+2;/m+2 是为了方便边界处理for ( i=0; im+2; i+ )squarei=new int n+2;/n+2 是也是为了方便边界处理for(i=0; im+2; i+)/初始化 square 迷宫for(j=0; jn+2; j+)squareij=0;for(i=0; ixy;squarexy=-1;/=边界处理=for ( i=0, j=0; im+

11、2; i+ )squareij = 1;for ( i=0, j=0; jn+2; j+ )squareij = 1;for ( i=m+1,j=0; jn+2; j+ )squareij = 1;for ( j=n+1,i=0; ipqrs;dir0 = -1;/方向初始化trackback( p, q );/回溯cout turn - 1 endl;/输出转弯数for ( i = 0; i finalLevel; i+ )精选优质文档-倾情为你奉上专心-专注-专业squareresult0iresult1i = i + 1;for ( i = 1; i m + 1; i+)/打印迷宫for

12、( int j = 1; j n + 1; j+)cout squareij ;cout endl; bool trackback(int p,int q )/回溯过程/=将 p、q 放入 path 中=path0level=p;path1level=q;level+;/走出一步squarepq = 1;/标记起点已经走过/=if ( p = r & q = s )/找到朱丽叶后求转弯数，最小者保存之if ( IsFull() )/如果所有房间已经走过int count(0);for ( int i = 1; i level; i+ )if ( diri != diri-1 ) cou

13、nt+;/若下一次的方向不同于上一次的方向，判定为一次转弯if ( count turn )/找出最小转弯数并保存之finalLevel = level;/记录最后的步数turn = count;for ( int i = 0; i level; i+ )/保存最优路径result0i = path0i;result1i = path1i;squarepq = 0;/若已经找到朱丽叶房间未走完，则重新置起点为 0level-;/后退return false;/该路径不是答案，剪掉该子树/退出找到朱丽叶的状态精选优质文档-倾情为你奉上专心-专注-专业for ( int i = 0; i 8; i

14、+ )/以下是未找到朱丽叶的状态 向八个方向搜索int x, y;x = p + dirxi;y = q + diryi;if ( squarexy = 0 ) /若该房间没进入过，则标记其方向并进一步搜索dirlevel = i;trackback( x, y);squarepq = 0; /回到上一步level-;/回到上一步return true;/不需剪掉该子树bool IsFull()/判断是否走满每个房间for ( int i = 1; i = m; i+ )for ( int j= 1; j = n; j+ )if ( squareij = 0 )return false;ret

15、urn true;3.2 操作及运作结果操作及运作结果输入输出并显示迷宫结果如下：精选优质文档-倾情为你奉上专心-专注-专业3.4 设计的心得体会设计的心得体会 通过本次课程设计的训练，增加了我学习算法的兴趣，虽然还不是很明白其中的具体内容，但已发现算法分析与程序设计的乐趣。老师给了我们四个题目供选择，从选题到完成程序一步步操作实验不仅对题目有了深入的了解，还达到了熟练使用 C 语言编程的能力。虽然还有很多复杂的问题是我们的能力所不及的，但我相信通过一次次实际的训练操作会使我们的解决问题的能力一步步有所提高。这次程序设计是让我们学到了好多知识，但也暴露了我们在程序设计中的不足。让我们更深一步体会到了上机实训的重要性。学校给我们安排实训是为培养学生在实践中培养独立分析问题和解决问题的作风和能力，提高实际操作水。让我们了解到除了学习基础知识之外上机实验也是必不可少的，只有通过多次的操作实验才能够提高自己的解决问题能力精选优质文档-倾情为你奉上专心-专注-专业计算机系课程设计指导教师评分表课程设计题目姓名学号专业班级指导教师评语指导教师评语