罗密欧与朱丽叶迷宫求解问题.doc

河南科技大学课 程 设 计 说 明 书课程名称 软件专题训练 题 目 罗密欧与朱丽叶迷宫求解问题院 系 电子信息工程学院计算机系班 级 计算机科学与技术103班学生姓名 指导教师 孙士保、冀治航 日 期 2012.5.212012.5.27河南科技大学课 程 设 计 任 务 书课程名称 算法设计与分析 题 目 罗密欧与朱丽叶的迷宫问题 院 系 电子信息工程学院计算机系班 级 计算机103班学生姓名 魏 鹏 超指导教师 孙士保、冀治航 日 期 2012.5.212012.5.27 罗密欧与朱丽叶的迷宫问题课程设计题目罗密欧与朱丽叶的迷宫问题姓名学号班级计算机10级系别计算机科学与技10级专业计算机科学与技术组别组长组员指导教师姓名孙士保、冀治航课程设计目的进一步巩固C程序设计和算法设计与分析的基础知识，提升结构化程序、模块化程序设计的方法和能力，深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。设计环境1. PC兼容机 2Windows 2000/XP操作系统3TC集成开发环境或其他C语言开发环境课程设计要求和任务要求：1熟练掌握回溯法，能够利用回溯法解决实际问题；2使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存到文件中；3不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。4对系统进行功能模块分析、画出总流程图和各模块流程图；5用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单；6通过命令行相应选项能直接进入某个相应菜单选项的功能模块；7所有程序需调试通过。任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括：1确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线；2程序能够演示一条罗密欧找到朱丽叶的路线过程等。课程设计工作进度计划序 号起止日期工 作 内 容12012.5.21下发任务书，分组，选定课题，查阅相关资料22012.5.22总体设计，划分模块，编制源程序32012.5.23上机调试，修改、完善系统42012.5.25程序检查，撰写说明书，上交报告河南科技大学课程设计报告课程名称 软件专题训练 题 目 罗密欧与朱丽叶的迷宫问题 院 系： 电子信息工程学院计算机系 专 业： 计算机科学与技术 班 级： 计算机10级 学生姓名: 学 号: 起止日期: 2012年5月21日 2012年5月27日 指导教师: 孙士保、冀治航 4罗密欧与朱丽叶的迷宫问题目录第一章 需求分析41.1课程设计题目41.2 课程设计任务及要求41.3运行环境及开发工具4第二章 概要设计 52.1系统流程图 5第三章 详细设计63.1函数划分63.2函数之间的关系6第四章 系统调试与操作说明74.1系统调试及操作说明7第五章 课程设计总结体会85.1课程设计总结85.2致谢85.3参考文献8第一章 需求分析1.1课程设计题目罗密欧与朱丽叶的迷宫问题1.2 课程设计任务及要求1、 对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少转弯道路2、程序能够演示一条罗密欧找到朱丽叶的路线过程等罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的 (p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。1.3运行环境及开发工具硬件：装有windows操作系统的计算机软件：Visual C+6.0第二章 概要设计2.1系统流程图输入m,n,k,x,y,x1,y1-1->dirs best->1000 count->0dep=m*n-k&&x=x1&&y=y1&&dirs<=best是 否 否dirs<best是 否 best=dirs;count=1;1->i1->jbestbij=boardijj+1->j直到j<=ni+i->i直到i<=mcount+1->countreturndep=m*n-k|x=x1&&y=y1|dirs>best是 否 1->ip=x+dxiq=y+dyix>0&&x<=m&&y>0&&y<=n&&boardxy=0是 dirs+1->dirs直到 i<=8 di!=i是dirs-1->dirs boardpq=0;boardpq=dep+1di!=i dirs+1->dirs直到 i<=8 输出best,count*bestb第三章 详细设计3.1函数划分（1）函数1：bool stepok(int x,int y) 判断是（x,y）否越界。（2）函数2：void save() 保存一条转弯最少的路径（3）函数3：void search(int dep,int x,int y,int di) 在当前位置（x,y）按照八个方向搜索，dep用于标记已经走过的房间数,di表示八个方向。（4）函数4：void main() 主函数初始化迷宫数组，并调用search函数输出一条迷宫路线。3.2函数之间的关系：主函数调用search函数，search函数调用stepok和save函数完成搜索。如下图： main函数 save函数 调用search函数 递归调用search函数 调用stepok函数 输出结果第四章 系统调试与操作说明4.1系统调试及操作说明先是输入迷宫中的各个参数： （1）、迷宫的行列数及封闭房间个数m,n,k分别是3，4，2。 （2）、2个封闭房间的坐(p,q)分别是（1，2），（3，4）。 （3）、罗密欧与朱丽叶的坐标(x,y),(x1,y1)分别是（1，1），（2，2）。 输出： 输出一条迷宫路线：(1,1)à(2,1) à(3,1) à(3,2) à(2,3) à(1,4) à(1,3) à(2,4) à(3,3) à(2,2) 1 -1 7 6 2 10 5 8 3 4 9 -1 第五章 课程设计总结体会5.1课程设计总结通过本次课程设计的训练，增加了我学习算法的兴趣，虽然还不是很明确其中的具体内容，但已发现算法分析与程序设计的乐趣。老师给了我们四个题目供选择，从选题到完成程序一步步操作实验不仅对题目有了深入的了解，还达到了熟练使用C语言编程的能力。虽然还有很多复杂的问题是我们的能力所不及的，但我相信通过一次次实际的训练操作会使我们的解决问题的能力一步步有所提高。本次程序不是很复杂，只要对算法的有深入的认识与掌握就可以得到输出的结果。但程序中涉及到了多个参数，在上机实验过程中通过一次次实验对算法一步步执行中，彻底弄明白其中的各个参数及函数的作用及用法，特别是对回溯法有了更深的理解。在程序的编写输入输出的过程中虽然其中遇到了很多错误与困难，但正是在解决这些错误与困难的过程中才会使我们的能力有所提高，知识有所更深入的理解，并进一步巩固了C程序设计和算法设计与分析的基础知识，增强对算法的理解能力，提高软件设计能力，熟练掌握了回溯法，能够利用回溯法解决实际问题。虽然只是短短一星期但同学们都在努力学习与实践，我知道只靠这些时间来练习远远不够的，只有平时多练习，才会达到老师对我们的要求。这次程序设计是让我们学到了好多知识，但也暴露了我们在程序设计中的不足。让我们更深一步体会到了上机实训的重要性。学校给我们安排实训是为培养学生在实践中培养独立分析问题和解决问题的作风和能力，提高实际操作水。让我们了解到除了学习基础知识之外上机实验也是必不可少的，只有通过多次的操作实验才能够提高自己的解决问题能力。5.2 致谢感谢本次试验中给予技术等指导的孙士保、冀治航老师，因为他们的指导，本次试验中的部分问题都得到了解决，并且学到了很多东西。感谢张强，于文帅等同学的帮助，和他们探讨问题，解决问题，不但学会了更多的东西，更加深了同学之间的友谊。5.3参考文献计算机算法设计与分析教材（第三版）C/C+程序设计教程（第二版）数据结构（c语言）教材源码#include<iostream>using namespace std;int dir92=0,0,0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1;/行走的路线int count;int dirs,best;int board2020,bestw2020;int m,n,k;int lx,ly,zx,zy;bool comp(int x,int y) /判断是坐标是否越界if(x>0&&x<=n&&y>0&&y<=m&&boardxy=0) return true;else return false;static void save()/保存一条转弯最少的路径int i,j;for(i=1;i<=n;i+) for(j=1;j<=m;j+) bestwij=boardij;void search(int dep,int x,int y,int di)if(dep=m*n-k&&x=zx&&y=zy&&dirs<=best)/dep用于标记已经走过的房间数 di表示八个方向 if(dirs<best) best=dirs; count=1; save(); else count+; return;if(dep=m*n-k|x=zx&&y=zy|dirs>best) return; else for(int i=1;i<=8;i+) if(comp(x+diri0,y+diri1) boardx+diri0y+diri1=dep+1; if(di!=i) dirs+; search(dep+1,x+diri0,y+diri1,i); if(di!=i) dirs-; boardx+diri0y+diri1=0; int main() cout<<"请设置迷宫的行数：" /初始化迷宫数组 cin>>n; cout<<endl;cout<<"请设置迷宫的列数："cin>>m; cout<<endl;cout<<"请设置要封闭的房间个数："cin>>k;cout<<endl;int i,j;int c,d;memset(board,0,sizeof(board); for(i=0;i<k;i+)/设置封锁的房间位置cout<<"请设置封锁的第"<<i+1<<"个房间所在的行和列：" cin>>c>>d; boardcd=-1;cout<<"请设置罗密欧所在房间的行和列："cin>>lx>>ly;cout<<"请设置朱丽叶所在的房间行和列："cin>>zx>>zy;boardlxly=1;best=m*n;dirs=-1;cout<<"迷宫初始化如下："<<endl;cout<<"其中0表示未到的房间，-1表示封闭的房间"<<endl;for(i=0;i<n;i+) for(j=0;j<m;j+) cout<<boardi+1j+1<<" " cout<<endl;search(1,lx,ly,0); /输出一条迷宫路线。cout<<"最少转弯次数："<<best <<"次"<<endl;cout<<"有不同的最少转弯次数："<<count<<"次"<<endl;cout<<"其中迷宫的一条最少转弯道路如下："<<endl;for(i=1;i<=n;i+) for(j=1;j<=m;j+) cout<<bestwij<<" " cout<<endl;课程设计题目罗密欧与朱丽叶的迷宫问题姓名学号专业班级指导教师评语： 指导教师签名： 年 月 日成绩评定项 目分 值评 分 要 素成 绩1设计过程中出勤、学习态度等方面20上机出勤及端正的学习态度、认真刻苦程度等2软件设计质量40采用的算法、设计方案，设计结果，界面友好等方面进行综合评定3 答辩20能简明扼要地阐述设计的主要内容，能准确流利地回答各种问题4设计报告书写10条理清晰，表述清楚、措词得当5 实际动手能力10组长全面负责，承担复杂的模块设计分值就高总 成 绩 14