三件有制约关是系物品过河问题.doc

《数据结构项目实践》集中上机 1．实验题目 三件有制约关系物品过河问题（90分） 有一人要将自己的兔子、蔬菜和狐狸等三件物品运过河。但过河所用的船每次只能装其中的两件，而这三件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模型，并编程实现这一问题的求解。 ? 2．数据输入和输出 输出时我尽力使界面做的漂亮，使问题求解的最终结果显而易见。由于我们考虑到问题的具体实现，所以将运行出的结果（矩阵形式）特地转化成文字语言并且输出。 ? 3.数据结构及其存储结构 (1)选择对应的数据结构，由于问题的实现是寻找一条路径，那么主要的数据结构就应该是图或者是树，对这个问题我选择图。 (2)选择存储结构，由于问题的规模很小，且总的状态种类很少，所以，我选择邻接矩阵作为图的存储结构。 ? 4.算法的基本思想 算法的思想其实很简单，首先在创立节点时利用is_safe()函数就将不安全的结点全部排除，再利用is_connected（）函数 就可将每个结点的后继结点得到。之后利用深度优先有哪些信誉好的足球投注网站就可以找到实现这一问题的路径。 问题的分析 ①每一个物体都只有两个状态，在原岸或者在对岸 ②从整体上看又有很多种不同的状态(如农夫和羊在对岸,狼和白菜在原岸) ③从一个状态可合法地转到另外几个状态(如农夫自己过河或农夫带着羊过河) ; ④有些状态不安全(如农夫在对岸,其他东西在原岸) ; ⑤有一个初始状态(都在原岸)，有一个结束状态集(都在对岸)。 问题模型的建立 问题的模型建立：为了方便解决问题，又结合实际问题的特征，我们可以将这个问题模型化。首先，采用二进制中的0/1表示每一个物体的两种状态，用一个四位的二进制数表示一种整体的状态，这样就使原来的问题变的更加易于理解，有利于我们找到合适的数据结构类型来实现问题。 根据对象的状态分为过河（1）和不过河（0），此对象集合就构成了一个状态空间。问题就是在这个状态空间内有哪些信誉好的足球投注网站一条从开始状态到结束状态的安全路径。显然，其初始状态为四个对象都不过河（都为0），结束状态为四对象全部过河（都是1）。状态到下一状态可以通过合法的途径获得，即有哪些信誉好的足球投注网站条件明确。 这其中可以根据相互之间的制约关系，排除不合法的状态。通过分析得到的各种状态间的关系转换图如下图 系统状态转换关系图 ? 其中双向的箭头表示状态可逆,即农夫可以带着某种东西过去,也可以带着该东西回来。箭头上的字母表示农夫所携带的东西:Fa (Farmer) ,Fo(Fox) ,R(Rabbit),V(Vegetable)分别表示农夫自己、农夫携带狐狸、农夫携带兔子、农夫携带菜过河。 5.调试通过的源程序 #includestdio.h #define VEX_NUM 10 //最大顶点数 typedef enum { FALSE,TRUE} Boolean; typedef struct { int Farmer,Fox,Rabbit,Veget; }VexType;//定义结点 typedef struct{ int vexnum,e; VexType vexs[VEX_NUM]; int adj[VEX_NUM][VEX_NUM]; }AdjGraph;//图的存储结构——邻接矩阵 Boolean visited[VEX_NUM]; int path[VEX_NUM],y[VEX_NUM]; int locate(AdjGraph *G,int Fa,int Fo,int R,int V) //查找顶点（Farmer，Fox，Rabbit，Vegetable）在顶点向量中的位置 { int i; for(i=0;iG-vexnum;i++) if(G-vexs[i].Farmer==FaG-vexs[i].Fox==FoG-vexs[i].Rabbit==RG-vexs[i].Veget==V) return(i); return(-1); } int is_safe(int Fa,int Fo,int R,int V) { if(Fa!=R(Fo==R||R==V))//fa!=r? return(0); else return(1); } int is_connected(AdjGraph *G,int i,int j) { int k; y[0]=0; k=0; if(G-vexs[i].Fox!=G-vexs[j].Fox) k++; if(G-vexs[i].Rabbit!=G-vexs[j].Rabbit) k++; if(G-vexs[i].Veget!=G-vexs[j].Veget) k++; if(G-vexs[i].Farmer!=G-vexs[j].Farmerk=1)