农夫过河程序流程图算法的好处

农夫过河程序流程图算法的好处？一个农夫，带着一只狼、一只羊、和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。农夫的面前有一条小船，船小到只能容下他和一件物件。另外，只能农夫会撑船。又因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜而自己离开，也不能留下狼和羊而自己离开。但狼属于食肉动物，不吃白菜。

问农夫采取什么方案才能将所有的东西运过河？

解题思路

农夫过河问题的求解方法是使用广度优先搜索（BFS），即在搜索过程中总是最先搜索下面一步的所有可能状态，然后再进行考虑更后面的各种情况。

要实现广度优先搜索，一般采用队列结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别对其进行处理，处理过程中再把下一步的状态放在队列里。

在采用编程解决农夫过河的问题时，首先需要考虑以下几个问题：

程序中为了方便描述农夫过河过程中几个角色的位置（位于南岸还是北岸），最好的方法是用 4 个二进制数，分别顺序表示农夫、狼、白菜和羊的位置。在本节程序中，用二进制 0 表示某角色在河的南岸，用 1 表示某角色在河的北岸。例如，整数 5（其二进制为 0101），表示农夫和白菜在河的南岸，而狼和羊在北岸。

为了方便获取各个角色当前所在的位置，程序中设置了如下 4 个函数。其中，函数返回值为 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

}

---