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

农夫过河程序流程图算法的好处,第1张

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

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

解题思路

农夫过河问题的求解方法是使用广度优先搜索(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

}


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/11524245.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-16
下一篇 2023-05-16

发表评论

登录后才能评论

评论列表(0条)

保存