没有合适的资源?快使用搜索试试~ 我知道了~
首页修道士与野人问题课程设计报告
修道士与野人问题课程设计报告
4星 · 超过85%的资源 需积分: 29 55 下载量 79 浏览量
更新于2023-03-16
4
收藏 304KB DOC 举报
这是一个古典问题。假设有n个修道士和n个野人准备渡河,但只有一条能容纳c人的小船,为了防止野人侵犯修道士,要求无论在何处,修道士的个数不得少于野人的人数(除非修道士个数为0)。如果两种人都会划船,试设计一个算法,确定他们能否渡过河去,若能,则给出一个小船来回次数最少的最佳方案。 要求: (1)用一个三元组(x1,x2,x3)表示渡河过程中各个状态。其中,x1表示起始岸上修道士个数,x2表示起始岸上野人个数,x3表示小船位置(0——在目的岸,1——在起始岸)。例如(2,1,1)表示起始岸上有两个修道士,一个野人,小船在起始岸一边。 采用邻接表做为存储结构,将各种状态之间的迁移图保存下来。 (2)采用广度搜索法,得到首先搜索到的边数最少的一条通路。 (3)输出数据 若问题有解(能渡过河去),则输出一个最佳方案。用三元组表示渡河过程中的状态,并用箭头指出这些状态之间的迁移: 目的状态←…中间状态←…初始状态。 若问题无解,则给出“渡河失败”的信息。 (4)求出所有的解。
资源详情
资源推荐
6.修道士与野人问题
这是一个古典问题。假设有 n 个修道士和 n 个野人准备渡河,但只有一条能容纳 c 人
的小船,为了防止野人侵犯修道士,要求无论在何处,修道士的个数不得少于野人的人数
(除非修道士个数为 0)。如果两种人都会划船,试设计一个算法,确定他们能否渡过河
去,若能,则给出一个小船来回次数最少的最佳方案。
要求:
(1)用一个三元组(x1,x2,x3)表示渡河过程中各个状态。其中,x1 表示起始岸上修
道士个数,x2 表示起始岸上野人个数,x3 表示小船位置(0在目的岸,1在起始
岸)。例如(2,1,1)表示起始岸上有两个修道士,一个野人,小船在起始岸一边。
采用邻接表做为存储结构,将各种状态之间的迁移图保存下来。
(2)采用广度搜索法,得到首先搜索到的边数最少的一条通路。
(3)输出数据
若问题有解(能渡过河去),则输出一个最佳方案。用三元组表示渡河过程中的状态,
并用箭头指出这些状态之间的迁移:
目的状态←…中间状态←…初始状态。
若问题无解,则给出“渡河失败”的信息。
(4)求出所有的解。
1.需求分析
有 n 个修道士和 n 个野人准备渡河,但只有一条能容纳 c 人的小船,为了防止野人侵
犯修道士,要求无论在何处,修道士的个数不得少于野人的人数,否则修道士就会有危险,
设计一个算法,确定他们能否渡过河去,若能,则给出一个小船来回次数最少的最佳方案
用三元组(x1,x2,x3)来表示渡河过程中各个状态,其中,x1 表示起始岸上修道士个数,
x2 表示起始岸上野人个数,x3 表示小船位置(0在目的岸,1在起始岸)。若问题
有解(能渡过河去),则输出一个最佳方案。用三元组表示渡河过程中的状态,并用箭头
指出这些状态之间的迁移:目的状态←…中间状态←…初始状态,若问题无解,则给出“渡
河失败”的信息。
2.设计
2.1 设计思想
(1)数据结构设计
逻辑结构设计: 图型结构
存储结构设计: 链式存储结构
采用这种数据结构的好处:便于采用广度搜索法,得到首先搜索到的边数最少的一
条通路,输出一个最佳方案,采用图的邻接表存储结构搜索效率较高。
(2)算法设计
算法设计的总体设计思路为:在得到修道士人数和小船的容纳人数后,用 boatcase 得
到所有情况,然后再进行安全性检查,以减去修道士少于野人的情况,接着用孩子兄弟结
点表示法,将去对面的路作为孩子结点,路与路是兄弟关系,到达另一边时,同样以这种
方法,直到找到(0,0,0)。主要分为 4 个模块:boatcase 生成所有情况,BFS 得到边数最
少的最佳方案,safe 安全性检测,print 输出安全渡河的全过程。
各个模块要完成的主要功能分别为:
生成模块:生成所有的可能渡河情况
安全检测模块:对所有的可能渡河情况进行安全检测,,以减去修道士少于野人的情况
广度搜索模块:采用广度搜索法,得到首先搜索到的边数最少的一条通路
输出模块:输出所有安全渡河的全过程
主程序的流程图:
调用函数 Linkinit( )来进行初始化
调用函数 Insertson( )来插入结点
调用函数 guangdu( )
调用函数 print( )
2.2 设计表示
(1)函数调用关系图
guangdu boatcase safe insertson
insertbro
print
建立邻接表
把 初 始 状 态 插
入邻接表中
进行广搜找到成
功的方案
打印输出各种方
案
(2)函数接口规格说明
void Linkinit(Link **head)
void insertson(Link *head, DataType x)
void insertbro(Link *head,DataType x)
int boatcase(DataType x,int n)
void guangdu(Link *p,int n,int c)
int safe(DataType x,int n)
void print(Link *q,Link *p)
2.3 详细设计
生成模块
!!"#$
!!"#!
%
%
%
&
!!"#$'
!!"#!'
%
!!"#$'
%
%
!(!
%
安全检测模块
$!))$**$!))
$**$**$&**!**!&
!(!
!(!
%
广度搜索模块
+$,(,$(-.'
-.'/'
0
1, 1,2,3(
/
/456--7
1,
3/$
!&3
0$/$$!!"#$
0!/$!!!"#!
0 /$
/
0
1,2 77
4
剩余15页未读,继续阅读
cqq20091001234
- 粉丝: 2
- 资源: 10
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功