农夫过河报告

1、这最起码是一个报 告，虽然我尽力的 看，终究还是看不 懂。喜啦啦了喜啦啦了喜啦啦了组员：李琦、郑鸿飞、王琅辉、张育博摘要农夫过河问题是应用广度优先搜索和深度优先搜索的典型问题，但这里我们应用了简单的数 组，通过层层筛选的手段也解决了同样的问题，其中用到了部分广度优先搜索的思想。4、刖百农夫过河问题描述：一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东 西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如 果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白 菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请

2、求出农夫将所有的东西运过河的方 案。正文1 .问题抽象和数据组织农夫过河问题应该应用图的广度优先遍历或者深度优先遍历，但这里我们仅使用简单的线性表0和1代表农夫、狼、数组，通过多重的条件限制，达成目的。这里我们同样用 羊、白菜在左岸还是在右岸，并规定0在左，1在右，我们的目的便是从0000通过一系列变换到1111。2 .农夫过河算法源代码#include #define MAX 16 typedef struct FWSVint farmer;int wolf;int sheep;int vegetable;ltem; armer = f;safek.wolf = w; safek.sheep

3、 = s; safek.vegetable = v; k+;Item * judge(ltem Fwsv) (Item * next;Item compare4;next = compare;intxl = 0;int sum = 0;if = 0)for (int x = 0;x k;x+)armer = & safex.wolf = & safex.sheep safex.vegetable =)safex.farmer = 0;safex.wolf = 0;safex.sheep = 0; safex.vegetable = 0;armer = 1 & (safex.farmer + s

4、afex.wolf + safex.sheep + safex.vegetable != 4 )comparex1 = safex; x1+;for (int x2 = 0;x2 4;x2+)(olf !=| != & comparex2.sheep !=| != & comparex2.vegetable !=| != & comparex2.vegetable !=)comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0;)sum+=2;armer + comparex2.wol

5、f + comparex2.sheep comparex2.vegetable != sum) (comparex2.farmer = 0; comparex2.wolf = 0; comparex2.sheep = 0;comparex2.vegetable = 0;printf(Mnn);for(int x3 = 0;x3 4;x3+) (if (comparex3.farmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)(printf( 上数与：d%d%d%相连 n,comparex3.farmer,com

6、parex3.wolf5comparex3.sheep,comparex3.veget abl );if = 1)(for (int y = 0;y k;y+)(if(safey.farmer = & safey.wolf = & safey.sheep =&safey.vegetable =)safey.farmer = 0;safey.wolf = 0;safey.sheep = 0;safey.vegetable = 0;if(safey.farmer = 0 & (safey.farmer + safey.wolfsafey.sheep + safey.vegetable != 0 )

7、comparex1 = safey;x1+;)for (int x2 = 0;x2 4;x2+)(sum = + + + ;if ( != & comparex2.wolf !=| != & comparex2.sheep !=| != & comparex2.vegetable !=| != & comparex2.vegetable !=) (comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0; )printf(f,nn);for(int x3 = 0;x3 4;x3+)if

8、 (comparex3.farmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)(printf(n 上数与：d%d%d%相连 nH,comparex3.farmer,comparex3.wolf,comparex3.sheep,comparex3.vegetable ); )return next;)3 .算法功能说明和流程描述首先我们定义了一个结构体Item typedef struct FWSVint farmer; int wolf;int sheep;int vegetable;ltem;Item 中包含

9、了农夫(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+) 1for(v = 0;v 2;v+)if (!(f != s & (s = w | s = v)safek.farmer = f;

10、safek.wolf = w;safek.sheep = s;safek.vegetable = v;k+;）函数一连用了4个for循环完成了对0000到1111之间每一位数字的所有排列组合的遍 历，虽然这里的时间复杂度直接跃至0（己）但却是比较全面、写法简单的遍历，而且n仅为2，其中的if语句的判断从所有的排列组合中（总计16种）剔除了不会出现的组合，其中包括：农 夫不在，羊吃白菜，狼吃羊等情况。并让符合条件的情况存入了全局变量数组safeMAX中。Item * judge(ltem Fwsv)函数是整个算法的核心，思想比较简单但写法繁琐，目的是判断 safek数组中符合如题条件的数值，它的

11、参数是上一次的状态值，对于初始时便为0000，它的返回值 是一个符合条件的数值的数组首地址next，为了防止有多解的情况我们把符合条件的值存入了一个compared数组，如果为单解则将compare中其他成员置零，接下来我 们拆分着看看这个函数。if = 0)表示农夫现在在左岸接下来的for循环是对safek数组的遍历，目的是第一轮找出符合 条件的值for (int x = 0;x k;x+)armer = & safex.wolf = & safex.sheep = & safex.vegetable =)safex.farmer = 0;safex.wolf = 0;safex.sheep

12、 = 0;safex.vegetable = 0;armer = 1 & (safex.farmer + safex.wolf + safex.sheep + safex.vegetable != 4 )comparex1 = safex; x1+;olf !=| != & comparex2.sheep !=| != & comparex2.vegetable !=| != & comparex2.vegetable !=) (comparex2.farmer = 0;comparex2.wolf = 0;comparex2.sheep = 0;comparex2.vegetable = 0

13、;sum+=2;+ comparex2.sheep +if(comparex2.farmer+ comparex2.wolfcomparex2.vegetable != sum)(comparex2.farmer = 0;comparex2.wolf = 0;n)；comparex2.sheep = 0; comparex2.vegetable = 0;printf(narmer + comparex3.wolf + comparex3.sheep + comparex3.vegetable != 0)printf(上数与：%d%d%d% 目连 n,comparex3.farmer,compa

14、rex3.wolf,comparex3.sheep,comparex3.vegetabl)if = 1)(/*表示农夫现在在右岸接下来的for循环是对safek数组的遍历，目的是第一轮找出符合条件的值，与=0的情况一样，判断方法与条件也完全相同，只不过对于。打头的情况省去了对和的限制这一条件*/)4 .算法实现与验证L 刍罔孰S国的姿去结构丢作JA去去迪丑衣绘汇左雄”I-IA-fiiatlWW地果出q势值取熊一I 上上起X呼兰业世口二巴吧呼上言十a他坏晅S 1L0H&14上薇_L封乜巴g楚end： tillPress aiy lisy ID首先0000传入judge函数，返回1010，表示00

15、00与1010相连，接下来1010传入，返回0010,现在0000一，接下来0010传入，返回10111110两个，表示0000 1011和1110,我们只取第一个，1011传入，返回0001，传入0001，返回1101，现在是00001011 (还有 1110) -0001-001，接下来传入 1101，返回 0100 和 0101，同理只取第一个，传入0100，返回1110,至此结束整个传递，到达 1111的状态这些数字看着有些不清晰，我们来整理下0000101000101011 000110101000101整理得0000 101000101011 00011010101 11110100,通过图示我们发现农夫过河有两种解(D 农夫、狼、羊、白菜开始都在左岸0000，农夫拉羊从左岸到右岸1010，农夫自己从右 岸到左岸0010，农夫拉着白菜从左岸到右岸1011，农夫把羊从右岸拉回左岸0001，农夫拉着狼从左 岸到右岸1101，农夫自己从右岸到左岸0101，农夫拉着羊从左岸到右岸1111 o(2)农夫、狼、羊、白菜开始都在左岸oo