郑 州 轻 工 业学院 课 程 设 计 任 务 书 题目 农夫过河 专业、班级 计算机科学与技术 学号 姓名 主要内容： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会 吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而 狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 基本要求: 编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。 主要参考资料: 数据结构 严蔚敏 完 成 期 限： 2012/6/21 指导教师签名： 课程负责人签名： 年 月 日 2 郑 州 轻 工 业 学 院 本 科 数 据 结 构 课 程 设 计 总 结 报 告 设计题目：农夫过河 学生姓名： 系 别：计算机与通信工程学院 专 业：计算机科学与技术 班 级：计算机科学与技术 学 号： 指导教师： 2 0 1 2 年 6 月 2 1 日 3 一， 设计题目 问题描述： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二， 运行环境（软、硬件环境） VC6.0 Window s7 系统 三， 算法设计的思想 对于这个问题，我们需要先自动生成图的邻接矩阵来存储，主要方法是先生成各种安全状态结点，存放在顶点向量中；再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边，并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用递归深度优先搜索求出从 顶点（0，0，0，0）到顶点（1，1，1，1）的一条简 单 路 径 ，这样 做 只能搜到一种合 理 方法，因 为 深度优先搜索遍 历 一个图的时 候 每 一个结点只能被 访 问一次 。 四 ， 算法的流 程 图 要写 算法的流 程 图，必 须 要先很 了解 自己的函 数 结构，我先在纸 上 手 动的把整 个过程 在纸 上 画 一遍 ，了解 它的大 体 流 程 ，然 后把各个函 数 给分 开，下面...
VIP
