农夫携物过河程序.docVIP

题目内容：有一农夫要将自己的羊、蔬菜和狼等3件物品运过河。但农夫过河时所用的船每次最多只能装其中的一件物品，而这3件物品之间又存在一定的制约关系：羊不能单独和狼以及不能和蔬菜在一起，因为狼要吃羊，羊也能吃蔬菜。试构造出问题模式以编程实现这一问题的求解。 问题分析和任务定义： 根据对象的状态分为过河（1）和不过河（0），此对象集合就构成了一个状态空间。问题就是在这个状态空间内有哪些信誉好的足球投注网站一条从开始状态到结束状态的安全路径。显然，其初始状态为四对象都不过河，结束状态为四对象全部过河。这里用无向图来处理，并采用邻接矩阵存储。对于农夫，狼，羊，蔬菜组成一个4位向量，即图的顶点（F，W，S，V），状态空间为16，初始状态为（0000），目标为（1111）。解决问题的方法是，找到所有的安全状态，并在其中有哪些信誉好的足球投注网站出一条（0000）到（1111）的路径。对当前对象是否安全的判断，若当农夫与羊不在一起时，狼与羊或羊与蔬菜在一起是不安全的，其他情况是安全的。有哪些信誉好的足球投注网站一条可行路径时，采用深度优先有哪些信誉好的足球投注网站DFS_path，每个时刻探索一条路径，并记录访问过的合法状态，一直向前探视，直到走不通时回溯。显然，应该用数组来保存访问过的状态，以便回溯。显然农夫每次状态都在改变，最多也就能带一件东西过河，故有哪些信誉好的足球投注网站条件是，在顶点（F，W，S，V）的转换中，狼，羊，蔬菜三者的状态不能大于一个，即只有一个发生改变或者都不变。 数据的输入形式和输入值的范围：本程序不需要输入数据，故不存在输入形式和输 入值的范围。 结果的输出形式：在屏幕上显示安全状态的转换，即一条安全路径。 数据结构的选择概要设计 ⑴数据结构的选择：本程序采用无向图处理。 #define MaxNumVertices 10 //最大顶点数 typedef struct //图的顶点类型 { int Farmer,Wolf,Sheep,Veget;//存储农夫，狼，羊，蔬菜的状态 }VexType; typedef struct//图的各项信息 { int VertexNum,CurrentEdges; //图的当前顶点数和边数 VexType VerticesList[MaxNumVertices]; //顶点向量（代表顶点） int Edge[MaxNumVertices][MaxNumVertices];//邻接矩阵 //用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 }AdjGraph; ⑵为了实现上述程序的功能，需要：①生成所有安全的图的顶点；②查找顶点的位置；③判断目前（F，W，S，V）是否安全，安全返回1，否则返回0；④判断顶点i和顶点j之间是否可转换，可转换返回真，否则假；⑤深度优先有哪些信誉好的足球投注网站从u到v的简单路径；⑥输出从u到v的简单路径，即顶点序列中不重复出现的路径。 ⑶本程序包含7个函数： 主函数main（） 生成所有安全的图的顶点函数CreateG（） 查找顶点位置函数locate（） 判断目前状态（F，W，S，V）是否安全的函数is_safe（） 判断顶点i和顶点j之间是否可转换的函数is_connected（） 深度优先有哪些信誉好的足球投注网站从u到v的简单路径的函数DFS_path 输出从u到v的简单路径，即顶点序列中不重复出现的路径print_path（） 各函数关系如下： 图1 各函数关系图 详细设计和编码 实现概要设计中定义的所有数据类型，对每个操作作出伪码算法。 ⑴数据结构 #define MaxNumVertices 10 //最大顶点数 typedef struct //图的顶点类型 { int Farmer,Wolf,Sheep,Veget; }VexType; typedef struct { int VertexNum,CurrentEdges; //图的当前顶点数和边数 VexType VerticesList[MaxNumVertices]; //顶点向量（代表顶点） int Edge[MaxNumVertices][MaxNumVertices];//邻接矩阵 //用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 }AdjGraph; ⑵图的基本操作 1.查找顶点（F，W，S，V）在图中的位置 int locate(AdjGraph *G,int F,int W,int S,int V) { int i; for(i=0;iG-VertexNum;i++) if(G-VerticesList[i].Farmer==F G-VerticesList[i].Wolf==W G-VerticesList[i].Sheep=