还有谁不会解决农夫过河问题

问题描述

设农夫、狼、山羊、白菜都在河的南岸，现在要把它们运送到河的北岸去，农夫有条船，过河时，除农夫外船上至多能载狼、山羊、白菜中的一种。狼要吃山羊，山羊要吃白菜，除非农夫在那里。试规划出一个确保全部都能安全过河的计划。

代码实现

物体状态

首先我们可以定义一个枚举变量，假设河北岸的状态设置为1，河南岸的状态设置为0。每一种物体的表示方式见下表。

物体	farmer	wolf	sheep	cabbage
十进制	8	4	2	1
二进制	1000	0100	0010	0001

enum fwsc 
{farmer = 8, wolf = 4, sheep = 2, cabbage = 1
};

接下来我把这个4位二进制数的所有表示状态写下来：

0000：表示农夫，狼，羊，白菜都在南岸

0001：表示农夫，狼，羊在南岸，白菜在北岸

0010：表示农夫，狼，白菜在南岸，羊在北岸

0011，0100，0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111.

主函数调用

主函数首先定义了一个 16 长度的数组，用来存储某一物体状态是否被访问过，首先全部初始化为 -1 ，表示所有节点均为访问，然后给 route[0] 赋值为 -2，表示该节点已经访问且没有前驱节点。还需要再定义一个变量 currentLocation 表示各个物体的分布状态，该变量最小值为 0 ，最大值为 15 。最后调用农夫运送代码。

int main()
{int route[16], currentLocation = 0;	for (int i = 1; i < 16; i++)route[i] = -1;route[0] = -2;process(route, currentLocation);return 0;
}

农夫运送代码

农夫运送代码执行结束的标志 route[15] != -1，简单的说就是 route 数组最后一个状态1111 被访问过了，即农夫将狼，山羊，白菜全部运送过河。

再定义一个变量 mover ，用于代表移动哪一个物体，mover 一共可以取四个值1，2，4，8。然后使用循环遍历这四个值，只有农夫与待移动的物体在同一岸即((currentLocation & farmer) == 0) == ((currentLocation & mover) == 0)判断的内容。

先讲一下&运算符是什么意思。& 运算符是按位与运算，将十进制转换成二进制运算，对应位置相同为1，不相同为0。举个例子：10 & 8的结果就是8。运算过程如下：
$$\begin{array}{r}1000\\ 1010\\ 1000\end{array}$$
currentLocation& farmer用16种状态值的任意一种值同 farmer 进行按位与得到农夫是在哪一岸，currentLocation & mover用16种状态值的任意一种值同 mover 进行按位与（这里的 mover 代表农夫farmer，狼wolf，羊sheep，白菜cabbage的枚举变量值的任意值）得到了待运送在哪一岸。

如果农夫和物体在同一岸，假设在南岸，那么上诉表达式就是 （10）（10），假假，整体表达式为真，如果农夫和物体在同一岸，假设在北岸，那么上诉表达式就是 （00）（00），真真，整体表达式为真，如果农夫和物体在不同岸，那么就是（10）（00）或者（00）（10），那么就是，假真，真假，整体表达式为假。综上所述，这个表达式的结果如果为真代表农夫和物体在同一岸，如果为假，代表农夫和物体不在同一岸。如果mover代表的物体为农夫，该表达式自然是真。

接下来再看nextLocation = currentLocation ^ (farmer | mover)。

解释之前还是先来讲一下^与|，第一个代表按位异或，第二个代表按位或。按位或是只要对应的两个个二进位有一个为1时，结果位就为1。举个例子：10 | 8的结果就是10。运算过程如下：
$$\begin{array}{r}1000\\ 1010\\ 1010\end{array}$$

按位异或是两个二进位对应位置不同则为1，反之为0。举个例子：10 ^ 8的结果就是2。运算过程如下：
$$\begin{array}{r}1000\\ 1010\\ 0010\end{array}$$
nextLocation = currentLocation ^ (farmer | mover)这句代码的目的是为了预先取得下一个状态。farmer | mover代表用枚举变量里的farmer的取值同mover取值进行按位或，这里farmer的值为8（1000），假设mover为sheep的值，这里就是1000|0010结果为1010，假设当前状态农夫和羊都在南岸，其他两样物体在哪里无所谓，所以用x，y表示，所以当前状态currentlocation的取值为
0x0y，0x0y^ 1010，那么这个异或的结果农夫和羊的二进制位就由原来的0变成了1，假如原来农夫和羊都在北岸，那么就是1x1y^ 1010，那么这个异或的结果农夫和羊的二进制位就由原来的1变成了0，而其他两样东西的二进制位不管你x,y取0还是1，都会保持原值不变，这意味着什么？？意味着这个表达式把当前状态的值经过农夫携带任意在同一侧的物体到对岸而其他两样物体任然在原岸这么一个变化过程，变化到了新的值nextLocation。

例如，当nextLocation为1010 ^ (1000|1000)= 0010时，表示农夫独自从北岸返回南岸。

计算完下一步可能出现的状态之后，就需要判断下一状态是否安全，并且下一状态是否访问过。即isSafe(nextLocation) && route[nextLocation] == -1。

一切条件都满足后，就可以再次建立路径数组，因为路径有多种可能，而一条路径数组只代表一种可能。将route的值对应赋值给nextRoute，然后修改下一状态的值为当前状态，这样就做到了遍历时，所在状态的值为前驱节点。

//农夫运送过程
void process(int route[16], int currentLocation) 
{if (route[15] == -1) {int mover;	//代表移动的哪个物体for (mover = 1; mover <= 8; mover = mover * 2) {if (((currentLocation & farmer) == 0) == ((currentLocation & mover) == 0)){int nextLocation = currentLocation ^ (farmer | mover);	//预先得出下一状态 if (isSafe(nextLocation) && route[nextLocation] == -1) {int nextRoute[16];for (int i = 0; i < 16; i++)nextRoute[i] = route[i];nextRoute[nextLocation] = currentLocation; process(nextRoute, nextLocation); //递归进入下一数组}}}}else {	printRoute(route, 15);}
}

判断是否安全

这里就是判断当前的位置状态是否安全，即当农夫不在的情况下，判断：狼是否和羊在一起；羊是否和白菜在一起。用0表示不安全，1表示安全。

//判断状态是否安全
int isSafe(int currentLocation) 
{int f, w, s, c;f = getLocation(currentLocation, farmer);w = getLocation(currentLocation, wolf);s = getLocation(currentLocation, sheep);c = getLocation(currentLocation, cabbage);if (f != w && w == s) //若农夫不和狼在一侧，而狼却和羊在一侧return 0;else if (f != s && s == c) //若农夫不和羊在一侧，而羊却和白菜在一侧return 0;return 1;
}

获取物体位置

获取位置的代码同样涉及二进制运算，通过switch判断物体是处在南岸还是北岸，南岸为0，北岸为1。例如，传来的两个参数分别为10和8，这时候执行farmer1010 & 1000结果为8，不能与0，最后返回1，即农夫在北岸。

int getLocation(int currentLocation, int fwsc) //找到fwsc在河的哪一侧，0表示在右侧，1表示在左侧
{//若返回值等于0，则表示该物体在河的东侧，即河岸0；若返回值等于1，则表示该物体在河岸西侧，即河岸1.switch (fwsc){case cabbage:if ((currentLocation & cabbage) == 0) //2进制与运算，判断物体是否在河岸0，若在河岸0，则结果为0。return 0;elsereturn 1;break;case sheep:if ((currentLocation & sheep) == 0)return 0;elsereturn 1;break;case wolf:if ((currentLocation & wolf) == 0)return 0;elsereturn 1;break;case farmer:if ((currentLocation & farmer) == 0)return 0;elsereturn 1;break;default:break;}return -1;
}

结果输出

打印函数是一个递归过程，也可以认为是一个倒推过程，从最后的状态1111，依次递归，每次带入其变化的前一个状态进行递归，直到倒推到最开始的0000状态，然后结束递归开始逐步打印整个过河过程。

//打印过河路径
int printRoute(int route[16], int status)
{if (status == 0){printf("过河方法：\n");return 1;}printRoute(route, route[status]);if ((route[status] & farmer) == farmer)printf("农夫在河岸1,");elseprintf("农夫在河岸0,");	if ((route[status] & wolf) == wolf)printf("狼在河岸1,");elseprintf("狼在河岸0,");if ((route[status] & sheep) == sheep)printf("羊在河岸1,");elseprintf("羊在河岸0,");if ((route[status] & cabbage) == cabbage)printf("白菜在河岸1。");elseprintf("白菜在河岸0。");printf("\n");if (status == 15){             printf("农夫在河岸1,狼在河岸1,羊在河岸1,白菜在河岸1。\n");}         return 1;
}

完整代码

先贴上完整版代码，有需要可以自取。

#include<stdio.h>
enum fwsc 
{farmer = 8, wolf = 4, sheep = 2, cabbage = 1
};
int num = 0;//获取物体在河岸哪一侧
int getLocation(int currentLocation, int fwsc) 
{switch (fwsc){case cabbage:if ((currentLocation & cabbage) == 0)return 0;elsereturn 1;		break;case sheep:	if ((currentLocation & sheep) == 0)return 0;elsereturn 1;break;case wolf:if ((currentLocation & wolf) == 0)return 0;elsereturn 1;break;case farmer:if ((currentLocation & farmer) == 0)return 0;elsereturn 1;break;default:break;}return -1;
}//判断状态是否安全
int isSafe(int currentLocation) 
{int f, w, s, c;f = getLocation(currentLocation, farmer);w = getLocation(currentLocation, wolf);s = getLocation(currentLocation, sheep);c = getLocation(currentLocation, cabbage);if (f != w && w == s) return 0;else if (f != s && s == c) return 0;return 1;
}//打印过河路径
int printRoute(int route[16], int status)
{if (status == 0){printf("过河方法%d：\n",num);return 1;}printRoute(route, route[status]);if ((route[status] & farmer) == farmer)printf("农夫在河岸1,");elseprintf("农夫在河岸0,");	if ((route[status] & wolf) == wolf)printf("狼在河岸1,");elseprintf("狼在河岸0,");if ((route[status] & sheep) == sheep)printf("羊在河岸1,");elseprintf("羊在河岸0,");if ((route[status] & cabbage) == cabbage)printf("白菜在河岸1。");elseprintf("白菜在河岸0。");printf("\n");if (status == 15){             printf("农夫在河岸1,狼在河岸1,羊在河岸1,白菜在河岸1。\n");}         return 1;
}
//农夫运送过程
void process(int route[16], int currentLocation) 
{if (route[15] == -1) {int mover; for (mover = 1; mover <= 8; mover = mover * 2) {if (((currentLocation & farmer) == 0) == ((currentLocation & mover) == 0)){int nextLocation = currentLocation ^ (farmer | mover); if (isSafe(nextLocation) && route[nextLocation] == -1) {int nextRoute[16]; for (int i = 0; i < 16; i++)nextRoute[i] = route[i];nextRoute[nextLocation] = currentLocation; process(nextRoute, nextLocation); }}}}else {	printRoute(route, 15);}
}int main()
{int route[16], currentLocation = 0;	for (int i = 1; i < 16; i++)route[i] = -1;route[0] = -2;process(route, currentLocation);return 0;
}