农夫过河问题

#include <stdioh>

#include <stdlibh>

#include <stringh>

#define MAX_STEP 20

/二维数组a的行下标表示次数，列下标分别表示: 0 - 狼，1－羊，2－菜，3－农夫，值表示：0－本岸，1－对岸

如：a[2][0]=1表示狼在第二次后在对岸/

int a[MAX_STEP][4]; //初始状态都未赋值,默认为0， 意思是4个都在本岸

int b[MAX_STEP]; //数组b是用来存放每一步 *** 作的动作对象，如b[0]=1,那么就表示第一步农民“带羊”（name[b[0]+1]即name[2]），这个说明只是打个比方

char name[] =

{

"空手",

"带狼",

"带羊",

"带菜"

};

void search(int iStep)

{

int i;

if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4)

//递归的结束条件，最后的结果，即4个都到对岸后，分别输入每一步的 *** 作

{

for (i = 0; i < iStep; i++)

{

if (a[i][3] == 0) //a[i][3]表示农夫，因为每次农夫必须动，所以根据农夫的位置来判断本次的行动，也就是农夫在本岸的话动作应该是带XX到对岸

{

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

}

else //否则相反

{

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

}

}

printf("\n");

return;

}

//下面这个for语句是一个比较的语句，处理的问题是，当第n步移动后，如果跟前面某一步移动后的状态时一样的，那么表示没有意义，结束本次递归，防止进入死循环

for (i = 0; i < iStep; i++)

{

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

{

return;

}

}

//下面这个if表示当本次是这种情况：农夫和羊没在一起，而且羊和狼在一起或者羊和菜在一起，那么就会违反规则，则结束本次调用

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

{

return;

}

//排除了前面的特殊情况，下面进入真正的递归阶段

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

{

b[iStep] = i; //将第istep步骤的 *** 作赋值给b[istep],默认为-1,即最后输出的时候是name[b[i] + 1]表示空手

memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])); //一维数组的复制,将二维数组上一行赋值给下一行

a[iStep + 1][3] = 1 - a[iStep + 1][3]; //由于0表示本岸，1表示对岸，1-值表示交换，即每次农夫是必须动的。

if (i == -1)

//如果i==-1就递归下一次，这里表示只有农夫运动

{

search(iStep + 1);

}

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

//从0到2表示 0 - 狼，1－羊，2－菜，判断是否跟农夫在一边，在一边才可能被带走

{

a[iStep + 1][i] = a[iStep + 1][3]; //表示i被带走了，那么下一次的值因为是跟农夫一样的

search(iStep + 1);

}

}

}

int main()

{

search(0);

return 0;

}

/大体思路是：用递归的方法，一个结束条件是4个都到对岸，二个递归中断条件是1)本次移动后，跟之前的某一次状态一样，那么重复，没意义，中断；2)本次

移动后，违反了规则，羊或者菜被吃了，中断本次调用。其他则进入下一次迭代。/

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

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

首先要表示狼，羊，菜和农夫所在的位置，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 = 0; i < iStep; i++)

{

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 = 0; i < iStep; i++)

{

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

{

return;

}

}

判定是否会死循环，如果当前状态在以前出现过，那么就会出现死循环。用当前这步的状态a[iStep]和以前的所有步a[i] (i=0; i <iStep; i++)比较。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 = -1; i <= 2; i++)

{

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))。

以上就是关于农夫过河问题全部的内容，包括:农夫过河问题、农夫过河问题。急急急、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！