资源描述：
《实验6：农夫、狼、羊和菜问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验6：农夫、狼、羊和菜问题一、实验目的：1.会定义图的抽象数据类型；2.熟悉图的基本结构，掌握程序中的用户头文件、实现文件和主文件Z间的相互关系及各自的作用；3.熟悉对图的-•些基木操作和具体的函数定义；4.掌握在实际问题屮运用所学知识解决实际问题的方法和步骤。二、实验内容描述：有一农夫带着一条狼、一只羊和一筐菜，想从河的左岸乘船到右岸。但由于船太小，农夫每次只能带一样东西过河，而且，如果没有农夫看管，则狼会吃羊，羊会吃菜。问农夫怎样过河才能把每样东西安全地送过河。三、实验要求：1.将上述问题用图表示出来；2.选择图的一种存储结构，编写一个自动生成该图的算法；3•在上
2、述基础上编写求解该问题的算法程序，并用此程序上机运行、调试，4.屏幕显示结果，能结合程序进行分析。四、问题分析：该问题从表面上看，并不是一个图的问题，但可以把它用图表示出来，从而转换为一个图的问题。在这个问题的解决过程中，农夫需要多次架船往返于两岸Z间，每次可以带一•样东西或者自己单独过河，每一次过河都会使农夫、狼、羊和菜所处的位置发生变化。如果用一个四元组(Fanner,Wolf,Sheep,Veget)表示当前农夫、狼、羊和菜所处的位置，其中每个元素可以是0或1,0表示在左岸，1表示在右岸。这样，对这四个元素的不同取值可以构成16种不同的状态,初始时的状态则为(0,
3、0,0,0),最终要达到的廿标为(1,1,1,1)。状态之间的转换可以有下面四种情况：(1)农夫不带任何东西过河，可表示为：(Farmer,Wolf,Sheep,Vegct)aFELnRcr,Wolf,Sheep,Vegct)(2)当农夫和狼在和同位置时，表示农夫带狼过河，即当Farmer=Wolf时：(Farmer,Wolf,Sheep,Veget)([Farmer,!Wolf,Sheep,Veget)(3)当农夫和羊在相同位置时，表示农夫带羊过河，即当Farmer=Sheep时：(Farmer,Wolf,Sheep,Veget)(!Feinncr',Wolf,!Sh
4、eep,Vcgct)(1)当农夫和菜在相同位置时，表示农夫带菜过河，即当Farmer=Veget时：(Farmer,Wolf,Sheep,Veget)([Farmer,Wolf,Sheep,!Veget)在这16种状态中，冇些状态是不安全的，是不允许出现的，如(1,1,0,0)表示农夫和狼在右岸，而羊和菜在左岸，这样羊会吃掉菜。如果从16种状态中删去这些不安全状态，将剩余的安全状态之间根据上面的转换关系连接起来，就得到如下图所示的图。图1农夫、狼、羊和菜问题的状态图这样，原始问题就转换为在这个图中寻找一条从顶点(0,0,0,0)到顶点(1,1,1,1)的路径的问题。五、
5、存储结构：采用邻接矩阵和邻接表都可以完成求图屮两顶点间的路径问题，这里，我们不妨采用邻接矩阵存储结构。其中图的每个顶点结点包括四个域，类型定义为：typedefstruct/*定义图的顶点类型*/{intFarmer,Wolf,Sheep,Veget;}VexType;图的邻接矩阵存储结构定义为：/*最大顶点个数*/ttdcfineVEX-NUM10typedefstructintvexnum,c;VexTypevex[VEX-NUM];intadj[VEX-NUM][VEX-NUM];/*图的当前顶点数和边数*//*顶点向量*//*邻接矩阵*/}AdjGraph;六、
6、算法思想：在这个问题屮，首先需要自动生成图的邻接矩阵存储，具体方法是先生成各种安全状态结点，存放在顶点向量屮；再根据状态Z间的转换关系形成顶点Z间的所有边，保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用深度优先搜索思想求出从顶点(o,o,0,0)到顶点(1,1,1,1)的一条简单路径。七、实验程序：#include^defineVEXNUM10typedefenum{FALSE,TRUE}Boolean;typedefstruct{intFarmer,Wolf,Sheep,Veget;}VexType;typedefstruct{intvexn
7、um,e;VexTypevexs[VEX_NUM];intadj[VEX_NUM][VEX_NUM];}AdjGraph;Booleanvisited[VEX_NUM];intpath[VEXNUM];intlocate(AdjGraph^G,intF,intW,intS,intV)inti;for(i=0;ivexnum;i++)if(G->vexs[i].Farmer==F&&G->vexs[i].Wolf==W&&G->vexs[i].Sheep二二S&&G->vexs[i].Veget==V)return(i);retur
