本帖最后由 secret 于 2020-6-28 09:31 编辑
问题描述一个农夫在河边带了一只狼、一只羊和一颗白菜，他需要把这三样东西用船带到河的对岸。然而，这艘船只能容下农夫本人和另外一样东西。如果农夫不在场的话，狼会吃掉羊，羊也会吃掉白菜。请编程为农夫解决这个过河问题。问题分析根据问题描述可知，该问题涉及的对象较多，而且运算步骤也较为复杂，因此，在使用C语言实现时，首先需要将具体问题数字化。
由于整个过程的实现需要多步，而不同步骤中各个事物所处的位置不同，因此可以定义一个二维数组或者结构体来表不四个对象狼（wolf）、羊（goat）、白菜（cabbage）和农夫（farmer）。对于东岸和西岸，可以用east和west表示，也可以用0和1来表示， 以保证在程序设计中的简便性。
题目要求
给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，再进行下一步试探。因此，解决该问题可以使用循环或者递归算法，以避免随机盲目运算而且保证每种情况都可以试探到。
题目要求
求出农夫带一只羊，一条狼和一颗白菜过河的所有办法，所以依次成功返回运算结果后，需要继续运算，直至求出所有结果，即给出农夫不同的过河方案。算法设计本程序使用递归算法，定义二维数组int a[N][4]存储每一步中各个事物所处的位置。二维数组的一维下标表示当前进行的步骤，第二维下标可能的取值为0〜3，在这里规定它与四种事物的具体对应关系为：0——狼、1——羊、2——白菜、3——农夫。接着再将东岸和西岸数字化，用0表示东岸，1表示西岸，该信息存储在二维数组的对应元素中。
定义Step变量表示渡河的步骤，则成功渡河之后，a数组中的存储状态为:
a[Step][0] 1
a[Step][1] 1
a[Step][2] 1
a[Step][3] 1
因为成功渡河后，狼、羊、白菜和农夫都在河的西岸，因此有：a[Step][0]+a[Step][1]+a[Step][2]+a[Step][3]=4 题目中要求狼和羊、羊和白菜不能在一起，因此若有下述情况出现：a[Step][1]!=a[Step][3] && (a[Step][2]==a[Step][1] || a[Step][0]=a[Step][1]) 则发生错误，应返回操作。
在程序实现时，除了定义a数组来存储每一步中各个对象所处的位置以外，再定义一维数组b[N]来存储每一步中农夫是如何过河的。
程序中实现递归操作部分的核心代码为：- for(i=-1; i<=2; i++)
- {
- b[Step]=i;
- memcpy(a[Step+1], a[Step], 16); /*复制上一步状态，进行下一步移动*/
- a[Step+1][3]=1-a[Step+1][3]; /*农夫过去或者回来*/
- if(i == -1)
- {
- search(Step+1); /*进行第一步*/
- }
- else
- if(a[Step][i == a[Step][3]) /*若该物与农夫同岸，带回*/
- {
- a[Step+1]=a[Step+1][3]; /*带回该物*/
- search(Step+1); /*进行下一步*/
- }
- }
每次循环从-1到2依次代表农夫渡河时为一人、带狼、带羊、带白菜通过，利用语句“b[Step] = i”分别记录每一步中农夫的渡河方式，语句“a[Step+1] = a[Step+1][3]”是利用赋值方式使该对象与农夫一同到对岸或者回到本岸。若渡河成功，则依次输出渡河方式。“i<=2”为递归操作的界限，若i=2时仍无符合条件的方式，则渡河失败。
上面代码表示若当前步骤能使各值均为1，则渡河成功，输出结果，进入回归步骤。若当前步骤与以前的步骤相同，则返回操作，代码如下：- if(memcmp(a,a[Step],16) == 0)
- {
- return 0;
- }
若羊和农夫不在一块而狼和羊或者羊和白菜在一块，则返回操作，判断代码如下：- if(a[Step][1]!=a[Step][3 && (a[Step][2 == a[Step][1 || a[Step][0 == a[Step][1]))
- {
- return 0;
- }
下面是完整的代码：- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define N 15
- int a[N][4];
- int b[N];
- char *name[]=
- {
- " ",
- "and wolf",
- "and goat",
- "and cabbage"
- };
- int search(int Step)
- {
- int i;
- /*若该种步骤能使各值均为1，则输出结果，进入回归步骤*/
- if(a[Step][0]+a[Step][1]+a[Step][2]+a[Step][3 == 4)
- {
- for(i=0; i<=Step; i++) /*能够依次输出不同的方案*/
- {
- printf("east: ");
- if(a[0 == 0)
- printf("wolf ");
- if(a[1 == 0)
- printf("goat ");
- if(a[2 == 0)
- printf("cabbage ");
- if(a[3 == 0)
- printf("farmer ");
- if(a[0 && a[1 && a[2 && a[3])
- printf("none");
- printf(" ");
- printf("west: ");
- if(a[0 == 1)
- printf("wolf ");
- if(a[1 == 1)
- printf("goat ");
- if(a[2 == 1)
- printf("cabbage ");
- if(a[3 == 1)
- printf("farmer ");
- if(!(a[0 || a[1 || a[2 || a[3]))
- printf("none");
- printf("\n\n\n");
- if(i<Step)
- printf(" the %d time\n",i+1);
- if(i>0 && i<Step)
- {
- if(a[3 == 0) /*农夫在本岸*/
- {
- printf(" -----> farmer ");
- printf("%s\n", name[b[i + 1]);
- }
- else /*农夫在对岸*/
- {
- printf(" <----- farmer ");
- printf("%s\n", name[b[i + 1]);
- }
- }
- }
- printf("\n\n\n\n");
- return 0;
- }
- for(i=0; i<Step; i++)
- {
- if(memcmp(a,a[Step],16) == 0) /*若该步与以前步骤相同，取消操作*/
- {
- return 0;
- }
- }
- /*若羊和农夫不在一块而狼和羊或者羊和白菜在一块，则取消操作*/
- if(a[Step][1]!=a[Step][3 && (a[Step][2 == a[Step][1 || a[Step][0 == a[Step][1]))
- {
- return 0;
- }
- /*递归，从带第一种动物开始依次向下循环，同时限定递归的界限*/
- for(i=-1; i<=2; i++)
- {
- b[Step]=i;
- memcpy(a[Step+1], a[Step], 16); /*复制上一步状态，进行下一步移动*/
- a[Step+1][3]=1-a[Step+1][3]; /*农夫过去或者回来*/
- if(i == -1)
- {
- search(Step+1); /*进行第一步*/
- }
- else
- if(a[Step][i == a[Step][3]) /*若该物与农夫同岸，带回*/
- {
- a[Step+1]=a[Step+1][3]; /*带回该物*/
- search(Step+1); /*进行下一步*/
- }
- }
- return 0;
- }
- int main()
- {
- printf("\n\n 农夫过河问题，解决方案如下：\n\n\n");
- search(0);
- return 0;
- }
运行结果：
农夫过河问题，解决方案如下：
east: wolf goat cabbage farmer west: none
the 1 timeeast: wolf cabbage west: goat farmer
the 2 time <----- farmer east: wolf cabbage farmer west: goat
the 3 time -----> farmer and wolfeast: cabbage west: wolf goat farmer
the 4 time <----- farmer and goateast: goat cabbage farmer west: wolf
the 5 time -----> farmer and cabbageeast: goat west: wolf cabbage farmer
the 6 time <----- farmer east: goat farmer west: wolf cabbage
the 7 time -----> farmer and goateast: none west: wolf goat cabbage farmer east: wolf goat cabbage farmer west: none
the 1 timeeast: wolf cabbage west: goat farmer
the 2 time <----- farmer east: wolf cabbage farmer west: goat
the 3 time -----> farmer and cabbageeast: wolf west: goat cabbage farmer
the 4 time <----- farmer and goateast: wolf goat farmer west: cabbage
the 5 time -----> farmer and wolfeast: goat west: wolf cabbage farmer
the 6 time <----- farmer east: goat farmer west: wolf cabbage
the 7 time -----> farmer and goateast: none west: wolf goat cabbage farmer | 
