C语言,农夫过河问题

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

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

首先要表示狼，羊，菜和农夫所在的位置，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))。

#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}

---