logo资料库

算法实验报告：罗密欧与朱丽叶迷宫求解.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.09M 资料格式：doc 举报 版权申诉
第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
资料共13页，剩余部分请下载后查看
    目录
    第一章 需求分析
    1.1课程设计题目
    1.2 课程设计任务及要求
    1.3 软硬件运行环境及开发工具
    河 南 科 技 大 学 课 程 设 计 报 告 课程名称：算法设计与分析 设计题目：罗密欧与朱丽叶迷宫求解问题 院 专 班 系： 电子信息工程学院 业： 计算机科学与技术 级： 计算机 092 班 学生姓名: 学 号:09************ 起止日期: 2011 年 5 月 28 日 - 2011 年 6 月 3 日 指导教师: 孙士保、张明川、冀治航
    课程设计题目 罗密欧与朱丽叶的迷宫问题 姓名 *** 学号 091040602** 班级 092 班 系别 电子信息工程学院 专业 计算机科学与技术 组别 组员 1 人 组长 *** *** 指导教师姓名 孙士保、张明川、冀治航 课程 设计 目的 设计 环境 课程 设计 要求 和任 务 进一步巩固 C 程序设计和算法设计与分析的基础知识，提升结构化程序、 模块化程序设计的方法和能力，深入理解数据结构的基本理论，掌握数据存储结 构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本 方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养 独立分析问题和解决问题的作风和能力。 1. PC 兼容机 3．TC 集成开发环境或其他 C 语言开发环境 2．Windows 2000/XP 操作系统 要求：1．熟练掌握回溯法，能够利用回溯法解决实际问题； 2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输 入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存 到文件中； 3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接 口要注释清楚。对程序其它部分也进行必要的注释。 4．对系统进行功能模块分析、画出总流程图和各模块流程图； 5．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以 反复使用，最好使用菜单； 6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块； 7．所有程序需调试通过。 任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括： 1．确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线； 2．程序能够演示一条罗密欧找到朱丽叶的路线过程等。 课程设计工作进度计划 序 号 起止日期 工 作 内 容 1 2 3 4 5 下发任务书，分组，选定课题，查阅相关资料 总体设计，划分模块 编制源程序 上机调试，修改、完善系统 程序检查
    6 撰写说明书 河 南 科 技 大 学 课 程 设 计 任 务 书 课程名称：算法设计与分析 题 目：罗密欧与朱丽叶迷宫求解问题 院 班 系： 电子信息工程学院 级： 计算机科学与技术 092 班 学生姓名: *** 指导教师: 孙士保、张明川、冀治航
    起止日期: 2011 年 5 月 28 日 - 2011 年 6 月 3 日 目录 第一章 需求分析 ...........................................................................................................5 1.1 课程设计题目 ........................................................................................................... .........5 1.2 课程设计任务及要求 ..................................................................................................... 5 1.3 软硬件运行环境及开发工具 ..............................................................................................5 第二章 程序概要设计...............................................................................................................2 2.1 系统流程图 ....................................................................................................... .........错误！ 未定义书签。 2.2 函数的划分 .......................................................................................................错误！未定义 书签。 2.3 函数之间的关系 .......................................................................................................3 第三章 编写代码及运行程序..............................................................................................3 3.1 源程序..................................................................................................................................3 3.2 操作及运行结果..................................................................................................................6 3.3 设计的心得体会..................................................................................................................7
    第一章 需求分析 1.1 课程设计题目 对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少 弯道路 程序能够演示一条罗密欧找到朱丽叶的路线过程等 1.2 课程设计任务及要求 罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个 m×n 的迷宫中，如图所 示。每一个方格表示迷宫中的一个房间。这 m×n 个房间中有一些房间是封闭的， 不允许任何人进入。在迷宫中任 何位置均可沿 8 个方向进入未封闭的房间。罗 密欧位于迷宫的。 (p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方 格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到 达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算 法帮助罗密欧找出这样一条路。 1.3 软硬件运行环境及开发工具 硬件：装有 windows 操作系统的计算机 软件：Visual C++6.0
    第二章 程序概要设计 2.1 系统流程图 输入 m,n,k,p,q,r,s count->0 -1->dirs dep=m*n-k&&x=r&&y=s&&dirs<=best 是 dirs count 是 best=dirs; count=1; 1-.>i 1->j bestw[i][j] =board[i][ j]+1->j 直到 j<=n i=i->i 直到 i<=m z zhai return di!=i 是 dirs-1->dirs board[p][q]=0; 输出 best ,count **bestw dep=m*n-k||x=r &&y=s||dirs>best 是 return 否 否 1->i p=x+dir[i][0] q=y+dir[i][1] x>0&& x<=m&& y>0&& y<=n&& board[x][y]=0 是 board[p][q]=dep +1 di!=i dirs+1->dis 直到 ri<=8 2.2 函数的划分： （1）函数 1：bool trackback (int x,int y) 递归调用 trackback 函数求出最 优路径。 （2）函数 2：void isfull() 判断房间是否全部走完
    （3）函数3：void main() 主函数初始化迷宫数组，并调用trackback函数输 出一条迷宫路线。 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;//用来记录每一步的方向 int level(0);//记录正在探测第几步 int finalLevel(0);//初始化为零 int **result;//记录结果 int **path; int turn(999);//记录最小拐弯数 int dirx[8]={0,0,1,1,1,-1,-1,-1};//8 个方向变量 int diry[8]={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]; result[0] = new int [n*m]; result[1] = new int [n*m]; path = new int *[2]; path[0] = new int [n*m]; path[1] = new int [n*m]; dir = new int [m*n]; square = new int *[m+2];//m+2 是为了方便边界处理 for ( i=0; i>x>>y; square[x][y]=-1; } //=================边界处理===================== for ( i=0, j=0; i>p>>q>>r>>s;
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料