资源描述：
《农夫过河问题的算法与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、农夫过河问题的算法与实现院（系）名称专业班级学号学生姓名指导教师目录引言1一.问题的描述2二.需求分析3三•概要设计43.1数据结构的设计43.2算法的设计53.3抽象数据类型的设计5四.详细设计64.1算法的主要思想64.2主要功能函数设计74.3算法的实现7五•代码实现10六.测试与运行186.1测试工具186.2运行结果18七.总结与体会19八.参考文献20农夫过河问题的算法与实现引言所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸，需要安全运到北岸。一条小船只能容下他和一件物品，只有农夫能撑船。问农夫怎么能安全过河，当然狼吃羊，羊吃白菜，农夫不能将这两种或三种物品单独放在河的
2、一侧，因为没有农夫的照看，狼就要吃羊，而羊可能要吃白菜？这类问题的实质是系统的状态问题，要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径.一.问题的描述任何的实际问题，都可以抽象成固定的数学模型，然后再根据模型解决问题。这样就可以不考虑繁琐的实际过程，从而简化问题。在我们的问题屮，过河与没过河是两种不同的状态。农夫、狼、羊和菜，分别处于这两种状态。而，如果把他们看成一个系统，则农夫、狼、羊和菜的不同状态组合成系统的2的4次方种，即16种状态。但在系统的16种状态中，有些不满足题给条件，应给予剔除。剔除的判断条件：羊跟狼、菜状态相同，口不同于农夫的状态。当我们挑选好一系列系统的
3、合法状态后，我们的问题就清晰了很多。我们不妨设，没过河状态为0,过河为1。我们的问题就抽象为，系统从初始状态(0000),经过有限的合法状态，到达最终状态(1111)的过程。系统不同的合法状态之间,可能，有的有路，有的则不能到达。具体的判断条件是，农夫可以与一件物品同时边，或自己单独变。根据这一个条件，我们可以抽象出一个图来：系统的每一种状态视为一个节点，满足条件的节点间有一条路。这样问题就抽彖为，在无向图中找一条路。二、需求分析1、针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况,可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示
4、，以实现在程序设计中的简便性。2、题目要求给岀四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到。3、题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。4、输出界而要求具有每一步中农夫所带对彖及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。一.概要设计3.1数据结构的设计利用图论知识求解的过程。假设分别用farmer表示农夫,wolf表示狼,
5、sheep表示羊，veget表示白菜。初始状态是f、w、s、v都在原岸，即初始状态A为={f,w,s,v},在原岸全部可能出现的状态为以下16种：fwsv>fwv>fsv、wsv、fw、fs、fv、ws、wv、sv、f、w、s^v、O,这里0表示原岸是空集，即人、狼、羊、白菜都已运到河的对岸去了。根据题意可以得到，这16种情况中有6种情况是不允许出现的。它们是：WSV（狼、羊、白菜）、fw（农夫、狼）、fv（农夫、白菜）、WS（狼、羊）、SV（羊、白菜）、f（农夫）。如fv表示人和白菜在原岸，而狼和羊在对岸，这显然是不行的。因此，允许出现的情况只有10种。我们构造一个图，它的顶点就是这10种状
6、态。如果船某次从河的一岸划往另一岸时，使原岸的状态从孑变成X,我们就作一条从孑到*的弧，这样就可以得到如下图所示的有向图由于船是在两岸间往返的，那么“过河”问题就转换成在上图中找出一条由结点/ksy到结点0的路径，这条路径中相邻的两条弧或者都是由同一点引出的,或者都是进入同一个结点的，这样的路径是很容易找到的。从图中得到两条这样的路径，路径一：人狼羊白菜f狼白菜f人狼白菜f白菜f人羊白菜f羊f人羊fe,路径二：人狼羊口菜狼口菜人狼口菜狼人狼羊羊人羊,它们的长度都是7,也就是说，农夫至少要经过7次摆渡才能将狼、羊、白菜都安全摆渡到对岸，可以有两种方案。如果要求解至少需要摆渡的次数，那就是去
7、找路径长度最小的路径。从上面的分析得知，需要在图屮找出一条从顶点/Vsy到顶点e的最短路径。采用广度优先搜索算法：用一个具有四个元素的数组来表示人、狼、羊、白菜在原岸的状态。初始顶点H为人、狼、羊、白菜都在原岸，即H={1,1,1,1},当人或某一件物品在对岸时，相应的数组元素值置为0。扩展新顶点所用的运算算符有以下四种情况：①农夫独自摆渡过河，②农夫带着狼摆渡过河，③农夫带着羊摆渡过河，④农夫带
