修道士与野人问题课程设计报告
4星 · 超过85%的资源 需积分: 29 196 浏览量
更新于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)求出所有的解。
2015-11-16 上传
点击了解资源详情
点击了解资源详情
2013-10-14 上传
2012-05-15 上传
点击了解资源详情
cqq20091001234
- 粉丝: 2
- 资源: 10
最新资源
- SSM动力电池数据管理系统源码及数据库详解
- R语言桑基图绘制与SCI图输入文件代码分析
- Linux下Sakagari Hurricane翻译工作:cpktools的使用教程
- prettybench: 让 Go 基准测试结果更易读
- Python官方文档查询库,提升开发效率与时间节约
- 基于Django的Python就业系统毕设源码
- 高并发下的SpringBoot与Nginx+Redis会话共享解决方案
- 构建问答游戏:Node.js与Express.js实战教程
- MATLAB在旅行商问题中的应用与优化方法研究
- OMAPL138 DSP平台UPP接口编程实践
- 杰克逊维尔非营利地基工程的VMS项目介绍
- 宠物猫企业网站模板PHP源码下载
- 52简易计算器源码解析与下载指南
- 探索Node.js v6.2.1 - 事件驱动的高性能Web服务器环境
- 找回WinSCP密码的神器:winscppasswd工具介绍
- xctools:解析Xcode命令行工具输出的Ruby库