算法课程设计25289

《算法课程设计25289》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、河南科技大学课程设计报告课程名称：软件专题训练设计题目：罗密欧与朱丽叶迷宫问题院系：专业：班级：学生姓名:学号:起止日期:2011年5月28日~2011年6月3日指导教师:软件专题训练目录第一章需求分析21.1课程设计题目21.2课程设计任务及要求21.3开发环境2第二章开发环境概要设计32.1程序设计流程图3第三章详细设计33.1程序中各函数的功能设计及流程图3第四章系统调试与程序源代码44.1程序结果显示及系统调试问题44.2程序源代码7第五章课程设计体会13参考文献13-1-软件专题训练第一章需求分析1.1课程设计题目罗密欧与朱丽

2、叶身处一个m×n的迷宫中。每个方格表示迷宫的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8个方向进入为封闭的房间。罗密欧位于迷宫的（p,q）方格中，他必须找出一条通向朱丽叶所在的（r，s）方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使达到朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出一条这样的通路。1.2课程设计任务及要求要求：1．熟练掌握回溯法，能够利用回溯法解决实际问题；2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或

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

4、；2．程序能够演示一条罗密欧找到朱丽叶的路线过程等。1.3开发环境1.PC兼容机2．Windows2000/XP操作系统3．TC集成开发环境或其他C语言-14-软件专题训练第一章开发环境概要设计2.1程序设计流程图Ncount==0?=调用函数print()Yopen()==1调用函数mazef()、search()YYN结束i==2?N输入hh==1?i==1?调用新建文件savefileYY开始输入i图2.1主函数流程图主函数：它实现的主要功能就是建立和更新文件，读取文件中数据，并且实现整个程序的运行，还有打印显示要求的结果。第二章

5、详细设计3.1程序中各函数的功能设计及流程图一、函数功能设计1.文件新建和更新函数-14-软件专题训练savefile()，用来将从键盘输入的数据存放到文件input.txt中。文件中的数据有：罗密欧与朱丽叶迷宫的行数、列数、封闭房间数、封闭房间的位置、罗密欧的位置以及朱丽叶的位置。打开文件函数open(),用来读取input.txt文件中的数据供后来的函数使用，若找不到显示“文件不能打开！”。2．初始化迷宫数组及判断函数函数mazef()用来初始化迷宫，如果迷宫中的房间可以通过则标记为0，若不能通过则标记为-1，罗密欧的初始位置标记为

6、1。函数中还包含了将迷宫图显示到屏幕上。函数stepok()用来判断在寻找路径搜索八个方向时是否越界，该函数返回值为false和true。3.保存搜索到的解的函数及打印通路函数函数save()用来保存已经搜索到的符合要求的解，并将其存放在bestb[][]数组中。函数print()用来显示已经找到的迷宫的通路，该函数提供了两种显示方法，一种是迷宫图的方法，即在二维迷宫数组，通过显示数字i来表示第i步走过该位置。另一种是以位置坐标形式单步显示出来。4.搜索函数函数search()是整个程序的核心函数，该函数通过递归回溯的方法搜索，如果找到

7、朱丽叶则程序结束并得到结果。第一章系统调试与程序源代码4.1程序结果显示及系统调试问题程序结果显示：程序开始运行是的界面：新建文件的界面：-14-软件专题训练选择继续后的显示结果：-14-软件专题训练输出路径选择1后的结果显示：输出路径选择2后的结果显示：结束操作退出选择0后的结果显示：如果没有找到文件的显示界面：系统调试问题最初程序运行时没有办法单步显示路径，后来加了一个系统控制system(“pause”);但是其显示的界面为：-14-软件专题训练虽然显示了单步运行的效果，可是并不希望显示“请按任意键继续...”这几个字。后来将于句

8、改为system(“pause>nul”);显示的界面就成了：4.2程序源代码#include#includeintm,n,k,p,q,x1,y1;inta,b;//a