数据结构课程设计报告(农夫过河)

《数据结构课程设计报告(农夫过河)》由会员分享，可在线阅读，更多相关《数据结构课程设计报告(农夫过河)（12页珍藏版）》请在毕设资料网上搜索。

1、 1 目录目录 引言 . 2 1 问题描述 2 基本要求 2 2.1 为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性； 2 2.2 设计一个算法求解农夫过河问题，并输出过河方案； 2 3 概要设计 . 2 3.1 数据结构的设计。 2 3.1.1 农夫过河问题的模型化 . 2 3.1.2 算法的设计 3 4、运行与测试 5 5、总结与心得 6 附录 . 6 参考文献 1212 2 引言 所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸, 需要安全运到 北岸。一条小船只能容下他和一件物品, 只有农夫能撑船。问农夫怎么能安全过河, 当 然狼吃羊, 羊吃白菜, 农夫不能将这两种

2、或三种物品单独放在河的一侧, 因为没有农 夫的照看, 狼就要吃羊, 而羊可能要吃白菜? 这类问题的实质是系统的状态问题, 要 寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。 1 问题描述 一个农夫带一只狼、一棵白菜和一只羊要从一条河的南岸过到北岸，农夫每次只能 带一样东西过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃白菜，请为农夫 设计过河方案。 基本要求 2.1 为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性； 2.2 设计一个算法求解农夫过河问题，并输出过河方案； 3 概要设计 3.1 数据结构的设计。 3.1.1 农夫过河问题的模型化 分析这类问题会

3、发现以下特 征: 有一组状态( 如农夫和羊在 南, 狼和白菜在北) ; 从一个 状态可合法地转到另外几个状态 ( 如农夫自己过河或农夫带着羊 过河) ; 有些状态不安全( 如农夫在北, 其他东西在南) ; 有一个初始状态( 都在南) ; 结束状态集( 这里只有一个, 都在北) 。 问题表示: 需要表示问题中的状态, 农夫等位于南P北( 每个有两种可能) 。可以采用 位向量, 4 个二进制位的0P1 情况表示状态, 显而易见, 共24= 16种可能状态。从高位 3 到低位分别表示农夫、 狼、 白菜和羊。 0000( 整数0) 表示都在南岸, 目标状态1111( 即 整数15) 表示都到了北岸。有

4、些状态0011,0101, 0111, 0001, 1100, 1001 是不允许出 现的, 因为这些状态是不安全状态。根据上述条件可以画出系统的状态图如图1 所示。 其中双向的箭头表示状态可逆, 即农夫可以带着某种东西过去, 也可以带着该东西回 来。 箭头上的字母表示农夫所携带的东西: f( farmer) , w(wolf) , g(goat) , c( cabbage) 分别表示农夫自己、 农夫携带狼、 农夫携带羊、 农夫携带菜过河。 现在的问题转化为: 找 一条合法路径( 相邻状态之间的转移合法) , 从开始状态到某个结束状态, 途中不经过 不安全状态。 3.1.2 算法的设计 求农夫、 狼、 白菜和羊的当前状态的函数为每一种状态做测试, 状态安全则返回 0, 否则返回 1。安全性判断函数, 若状态安全则返回 0 int farmer(int location) /判断农夫位置对 0 做与运算，还是原来的数字，用来判 断位置 return 0 != (location int wolf(int location) /判断狼位置 return 0 != (