农夫过河问题

这个问题我做过 （假设农夫现在的位置是A 对岸是B）

农夫 狼 羊 白菜的问题

首先农夫和羊先到B

接着农夫一人回到A（羊在B）

然后农夫和白菜到B（此时农夫和羊和白菜都在B）

之后农夫和羊到A（只有白菜在B）

然后农夫和狼到B（A有羊 B有白菜和狼）

之后农夫在去一趟A把羊带上 到B就可以了

简单的说

首先 A狼首神和白菜------------------------B农夫和羊

农夫回去 A农夫、狼和白菜----------------B羊

农夫载白菜过河 A狼---------------------------------B农夫、羊和白菜

农夫再和羊液芹拍一起渡回去 A农夫、狼和羊-------------------B白菜

农夫带闹羡狼过河 A羊---------------------------------B农夫、狼和白菜

农夫再次肚子回去 A农夫和羊-------------------------B狼和白菜

农夫最后带羊过河 A（无）----------------------------B农夫、狼、羊和白菜

运行结果如下： 带手灶羊到对岸 空手回本岸 带狼到对岸 带羊回本岸 带菜到对岸 空手回本岸 带羊到对岸 带羊到对岸 空手回本岸 带菜到对岸 带羊毕汪扮回本岸 带狼到对岸 空手回本岸 带羊到对岸 以上是找出的所有解，共有两个解。 程序如下： #include <stdio.h>#include <stdlib.h>#include <string.h> #define MAX_STEP 20 //index: 0 - 狼，1－羊，2－菜，3－农夫，value：0－本岸，1－对岸 int a[MAX_STEP][4]int b[MAX_STEP] char *name[] = { "空手", "带狼", "带羊", "带菜" } void search(int iStep) { int i if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4) { for (i = 0i <iStepi++) {if (a[i][3] == 0){ printf("%s到对岸\n", name[b[i] + 1]) }else{ printf("%s回本岸\n", name[b[i] + 1]) } } printf("陵稿\n") return } for (i = 0i <iStepi++) { if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0) {return } } if (a[iStep][1] != a[iStep][3] &&(a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1])) { return } for (i = -1i <= 2i++) { b[iStep] = i memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])) a[iStep + 1][3] = 1 - a[iStep + 1][3] if (i == -1) {search(iStep + 1) } else if (a[iStep][i] == a[iStep][3]) {a[iStep + 1][i] = a[iStep + 1][3] search(iStep + 1) } } } int main() { search(0) return 0}

程序就是求解农夫过河问题：

农夫带着一狼，一羊和一些菜过河。河边只有一船，一次农夫只能带一样东西。无人时，狼要吃羊，羊要吃菜，程序将找出所有农夫过河的方案。

首先要表示狼，羊，菜和农夫所在的位置，4者的位置有本岸和对岸两种情况，分别用0和1表示，4者，所以用一个有4元素的数组。为了要记录每一步，程序中使用了一个二维数组a[MAX_STEP][4]，记录每一步4者所在位置。第一步就是a[0]，第二布是a[1]...而，a[0][0]就表示第一步狼在本岸(0)还是对岸(1)，a[0][1]表示第一步羊在本岸还是对岸......

为了记录每一次农夫过河时的状态，使用了一个数组b[MAX_STEP]，数组中的元素的值可能为-1, 0, 1, 2，分别表示农夫在过河时，是空手，带狼，带羊，悉塌谈带菜。

第一步的状态是狼，羊，菜和农夫都在本案，所以a[0][0]到a[0][3]都是0，本来应该初始化一下，但a是全局变量，所以自动初始化为0，所以程序中省下了这一步。

search是一个递归函数，通过不断的查找可能的下一步，找出一个方案，是一种深度优先搜索。

a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4意味着第 iStep时，a[iStep][0]到a[iStep][3]都为1，表示4者都到了对岸。所以输出结果。

for (i = 0i <iStepi++)

{

if (a[i][3] == 0)

{

printf("%s到对岸\n", name[b[i] + 1])

}

else

{

printf("%s回本岸\n", name[b[i] + 1])

}

}

输出每一步

a[i][3]是农夫在本岸还是对岸，如果为0，在本岸，下一步肯定是到对岸，所以打印"睁碰...到对岸"，而name[b[i]+1]找出对应带的东西的描述。

for (i = 0i <iStepi++)

{

if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0)

{

return

}

}

判定是否会死循环，如果当前状态在以前出现过，那么就会出现死循环。用当前这步的状态a[iStep]和以前的所有步a[i] (i=0i <iStepi++)比较。memcmp是内存比较函数，可以用于比较数组，返回值为0，表示数组衫侍中所有值相同。

如果相同，就直接返回，不再查找。

if (a[iStep][1] != a[iStep][3] &&(a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1]))

{

return

}

判定羊会吃菜，或狼会吃羊的情况。

当农夫和羊在一起的时候，狼不会吃羊，羊也不会吃菜，所以只有当农夫和羊不在一起(a[iStep][1] != a[iStep][3])时，才可能发生“吃”的状态。

而且“吃”的情况必须是在菜和羊在一起(a[iStep][2] == a[iStep][1])或者羊和狼在一起(a[iStep][0] == a[iStep][1])

发生吃的情况是，返回，不再查找。

for (i = -1i <= 2i++)

{

b[iStep] = i

memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1]))

a[iStep + 1][3] = 1 - a[iStep + 1][3]

if (i == -1)

{

search(iStep + 1)

}

else if (a[iStep][i] == a[iStep][3])

{

a[iStep + 1][i] = a[iStep + 1][3]

search(iStep + 1)

}

}

但现在，已经确保了上一步是“安全”的，可以继续查找。

-1, 0, 1, 2分别表示渡河时4种情况，空手，带狼，带羊，带菜。

memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1]))复制当前步的数组到下一步。

农夫的状态肯定会发生改变，所以a[iStep + 1][3] = 1 - a[iStep + 1][3]因为当a为0或1时，a = 1 - a会使a在0和1之间切换。

如果i== -1，表示空手，狼，羊，菜的状态都不会发生改变，所以直接搜索下一步(search(iStep + 1))

否则要被带过去的东西(0, 1, 2分别表示0, 1, 2)的状态需要改变。

要带的东西必须和农夫同在本案或对岸(a[iStep][i] == a[iStep][3])，才可能带得了。只有在这种情况下，使要带的东西的状态和农夫相同(a[iStep + 1][i] = a[iStep + 1][3])，并开始下一步的搜索(search(iStep + 1))。

---