农夫过河报告(最终版).docx

这最起码是一个报告，虽然我尽力的看，终究还是看不懂。农夫过河算法实验报告 数据结构项目课研究课题组长：崔俊组员：李琦、郑鸿飞、王琅辉、张育博摘要农夫过河问题是应用广度优先搜索和深度优先搜索的典型问题，但这里我们应用了简单的数组，通过层层筛选的手段也解决了同样的问题，其中用到了部分广度优先搜索的思想。前言农夫过河问题描述：一个农夫带着只狼、一只羊和棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。正文1.问题抽象和数据组织农夫过河问题应该应用图的广度优先遍历或者深度优先遍历，但这里我们仅使用简单的线性表数组，通过多重的条件限制，达成目的。这里我们同样用0和1代表农夫、狼、羊、白菜在左岸还是在右岸，并规定0在左，1在右，我们的目的便是从0000通过一系列变换到1111。2.农夫过河算法源代码#include #define MAX 16 /#define 也是一个预处理指令，使用其定义符号法为: #define 符号名 替换列表typedef struct FWSVint farmer;int wolf;int sheep;int vegetable;Item;定义一个类/函数原型/操作： 筛选符合条件的安全的数组成员/操作前：无/操作后：返回安全数组的指针 void screen(void);/操作： 判断下一个数应该取安全数组中那个数/操作前: 传递一个结构体数组成员/操作后：返回另一个结构体数组指针 Item * judge(Item Fwsv); Item safeMAX;int k = 0; /用于计数safe中的总数int main (void)主函数screen();Item * next;类的函数Item first,second,end;first = safe0;end = safek;printf(first:0000n); next = judge(first); for (int count = 0;count farmer + next-wolf + next-sheep + next-vegetable != 0)second = *next;next = judge(second);elsenext+;这是几个意思啊 printf(end:1111n); return 0;void screen(void)利用循环遍历所有的结果 int f = 0,w = 0,s = 0,v = 0;for(f = 0;f 2;f+)for(w = 0;w 2;w+)for(s = 0;s 2;s+)for(v = 0;v 2;v+)if (!(f != s & (s = w | s = v)safek.farmer = f; safek.wolf = w; safek.sheep = s; safek.vegetable = v; k+;Item * judge(Item Fwsv)把结果全部储存在Item *judge(Item Fwsv)中Item * next; Item compare4;next = compare;int x1 = 0;int sum = 0;if (Fwsv.farmer = 0)for (int x = 0;x k;x+) /把出现过的置零操作if(safex.farmer = Fwsv.farmer & safex.wolf = Fwsv.wolf & safex.sheep = Fwsv.sheep & safex.vegetable = Fwsv.vegetable )safex.farmer = 0;safex.wolf = 0;safex.sheep = 0;safex.vegetable = 0;/筛选出农夫状态值与之前相反的 1变0 0变1if(safex.farmer = 1 & (safex.farmer + safex.wolf + safex.sheep + safex.vegetable != 4 )comparex1 = safex;x1+;for (int x2 = 0;x2 4;x2+)/删除状态值与农夫不同但是改变了的sum = Fwsv.farmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable;if (Fwsv.farmer != Fwsv.wolf & comparex2.wolf != Fwsv.wolf) |(Fwsv.farmer != Fwsv.sheep & comparex2.sheep != Fwsv.sheep) | (Fwsv.farmer != Fwsv.vegetable & comparex2.vegetable != Fwsv.vegetable) | (Fwsv.farmer != Fwsv.vegetable & comparex2.vegetable != Fwsv.vegetable)comparex2.farmer = 0; comparex2.wolf = 0; comparex2.sheep = 0; comparex2.vegetable = 0;sum+=2;/对和的限制if(comparex2.farmer + comparex2.wolf + comparex2.sheep + comparex2.vegetable != sum)comparex2.farmer = 0; comparex2.wolf = 0; comparex2.sheep = 0; comparex2.vegetable = 0;printf(-n);for(int x3 = 0;x3 4;x3+)if (comparex3.farmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)printf(上数与：%d%d%d%d相连n,comparex3.farmer,comparex3.wolf,comparex3.sheep,comparex3.vegetabl ）; if (Fwsv.farmer = 1)for (int y = 0;y k;y+)if(safey.farmer = Fwsv.farmer & safey.wolf = Fwsv.wolf & safey.sheep = Fwsv.sheep & safey.vegetable = Fwsv.vegetable )safey.farmer = 0;safey.wolf = 0;safey.sheep = 0;safey.vegetable = 0;if(safey.farmer = 0 & (safey.farmer + safey.wolf + safey.sheep + safey.vegetable != 0 )comparex1 = safey;x1+;for (int x2 = 0;x2 4;x2+)sum = Fwsv.farmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable;if (Fwsv.farmer != Fwsv.wolf & comparex2.wolf != Fwsv.wolf) |(Fwsv.farmer != Fwsv.sheep & comparex2.sheep != Fwsv.sheep) | (Fwsv.farmer != Fwsv.vegetable & comparex2.vegetable != Fwsv.vegetable) | (Fwsv.farmer != Fwsv.vegetable & comparex2.vegetable != Fwsv.vegetable)comparex2.farmer = 0; comparex2.wolf = 0; comparex2.sheep = 0; comparex2.vegetable = 0;printf(-n);for(int x3 = 0;x3 4;x3+)if (comparex3.farmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)printf(上数与：%d%d%d%d相连n,comparex3.farmer,comparex3.wolf,comparex3.sheep,comparex3.vegetable );return next;3.算法功能说明和流程描述首先我们定义了一个结构体Itemtypedef struct FWSV int farmer; int wolf; int sheep; int vegetable;Item;Item中包含了农夫（farmer），狼（wolf），羊（sheep），白菜（vegetable）,用来表示农夫、狼、羊、白菜的状态，并作出规定当为0的时候表示在左岸，当为1的时候表示在右岸，我们的目标便是从0000的状态到1111的状态。定义的应该是字符接下来用一个调用函数screen（）void screen(void) int f = 0,w = 0,s = 0,v = 0;for(f = 0;f 2;f+)for(w = 0;w 2;w+)for(s = 0;s 2;s+)for(v = 0;v 2;v+)if (!(f != s & (s = w | s = v)safek.farmer = f; safek.wolf = w; safek.sheep = s; safek.vegetable = v; k+;函数一连用了4个for循环完成了对0000到1111之间每一位数字的所有排列组合的遍历，虽然这里的时间复杂度直接跃至O(n4)但却是比较全面、写法简单的遍历对所有的可能进行遍历，对出现的所有可能性有预知的了解，而且n仅为2，其中的if语句的判断从所有的排列组合中（总计16种）剔除了不会出现的组合，其中包括：农夫不在，羊吃白菜，狼吃羊等情况。并让符合条件的情况存入了全局变量数组safeMAX中。循环的结果储存在了safeMAX的数组中Item * judge(Item Fwsv)函数是整个算法的核心，思想比较简单但写法繁琐，目的是判断safek数组中符合如题条件的数值，它的参数是上一次的状态值，对于初始时便为0000，它的返回值是一个符合条件的数值的数组首地址next，为了防止有多解的情况我们把符合条件的值存入了一个compare4数组，如果为单解则将compare中其他成员置零，接下来我们拆分着看看这个函数。if (Fwsv.farmer = 0)表示农夫现在在左岸接下来的for循环是对safek数组的遍历，目的是第一轮找出符合条件的值for (int x = 0;x 全体单目第二；所有的单目运算符比如+-+(正)-(负)指针运算*&乘除余三,加减四；这个余是指取余运算即%移位五，关系六；移位运算符：，关系：=等等于(与)不等排第七；即=!=位与异或和位或；这几个都是位运算:位与(&)异或()位或(|)三分天下八九十；逻辑或跟与；逻辑运算符:|和&十二和十一；注意顺序:优先级(|)底于优先级(&)条件高于赋值,三目运算符优先级排到13位只比赋值运算符和,高逗号运算级最低！逗号运算符优先级最低if(safex.farmer = Fwsv.farmer & safex.wolf = Fwsv.wolf & safex.sheep = Fwsv.sheep & safex.vegetable = Fwsv.vegetable )safex.farmer = 0;safex.wolf = 0;safex.sheep = 0;safex.vegetable = 0;/从safek中筛选出农夫状态值与之前相反的并存入compare数组中。因为只有农夫会划船，所以来回农夫的状态必定改变，比如传进来的是0打头的传输出去的必定是1打头的。我们要做的就是从safek中找出农夫状态值与之前相反的数值，总计5个，其中我们把1111的情况也要剔除掉，现在总计4个了，我们把符合要去的数值从16个缩减到10个现在又缩减到4个，接下来我们还要缩减if(safex.farmer = 1 & (safex.farmer + safex.wolf + safex.sheep + safex.vegetable != 4 )comparex1 = safex;x1+;/这里的for便是对compare的遍历了for (int x2 = 0;x2 4;x2+)/上述缩减到4个但是范围还是太大，现在置零状态值与农夫不同但是改变了的。也就是说如果之前与农夫状态值相同，说明和农夫在相同一侧的岸，这时它才有可能改变的机会，要是与农夫之前与农夫状态值不同，说明和农夫相处对岸，这时它改变了，显然是不符合逻辑的，狼，羊，白菜是不会自己游过河的。sum = Fwsv.farmer + Fwsv.wolf + Fwsv.sheep + Fwsv.vegetable;if (Fwsv.farmer != Fwsv.wolf & comparex2.wolf != Fwsv.wolf) |(Fwsv.farmer != Fwsv.sheep & comparex2.sheep != Fwsv.sheep) | (Fwsv.farmer != Fwsv.vegetable & comparex2.vegetable != Fwsv.vegetable) | (Fwsv.farmer != Fwsv.vegetable & comparex2.vegetable != Fwsv.vegetable)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0;sum+=2;/由于船一次只能拉不超过两个，其中一个还要是农夫划船，所以这里我们对和有一个限制。当农夫拉着东西从左岸划向右岸时，总的状态值之和应该等于上一个状态+现在的状态,而现在的状态和必定为2，所以sum+=2。这里我们举个例子就明白了：0000开始，农夫拉着羊从左岸到右岸变成1010（此时的状态和为2），之后农夫划船回来变成0010（此时状态值为1），接着农夫划船拉着狼从左至右变成1110（此时状态和为3，3 = 1 + 2）.if(comparex2.farmer + comparex2.wolf + comparex2.sheep + comparex2.vegetable != sum)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0;printf(-n);/通过上述三种限制，我们已经可以判断出safek中完全符合要求的数值了，可能有一个，可能有两个，也可能多个，接下来的for遍历compare并打印我们需要的结果for(int x3 = 0;x3 4;x3+)if (comparex3.farmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)printf(上数与：%d%d%d%d相连n,comparex3.farmer,comparex3.wolf,comparex3.sheep,comparex3.vegetabl ） if (Fwsv.farmer = 1)/*表示农夫现在在右岸接下来的for循环是对safek数组的遍历，目的是第一轮找出符合条件的值，与Fwsv.farmer = 0的情况一样，