一个C语言经典编写的经典小游戏，带注释和解析

定义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][i]=a[Step 1][3]; /*带回该物*/ search(Step 1); /*进行下一步*/ } }

每次循环从-1到2依次代表农夫渡河时为一人、带狼、带羊、带白菜通过，利用语句“b[Step] = i”分别记录每一步中农夫的渡河方式，语句“a[Step 1][i] = a[Step 1][3]”是利用赋值方式使该对象与农夫一同到对岸或者回到本岸。若渡河成功，则依次输出渡河方式。“i<=2”为递归操作的界限，若i=2时仍无符合条件的方式，则渡河失败。

上面代码表示若当前步骤能使各值均为1，则渡河成功，输出结果，进入回归步骤。若当前步骤与以前的步骤相同，则返回操作，代码如下：

if(memcmp(a[i],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[i][0] == 0) printf("wolf "); if(a[i][1] == 0) printf("goat "); if(a[i][2] == 0) printf("cabbage "); if(a[i][3] == 0) printf("farmer "); if(a[i][0] && a[i][1] && a[i][2] && a[i][3]) printf("none"); printf(" "); printf("west: "); if(a[i][0] == 1) printf("wolf "); if(a[i][1] == 1) printf("goat "); if(a[i][2] == 1) printf("cabbage "); if(a[i][3] == 1) printf("farmer "); if(!(a[i][0] || a[i][1] || a[i][2] || a[i][3])) printf("none"); printf("\n\n\n"); if(i<Step) printf(" the %d time\n",i 1); if(i>0 && i<Step) { if(a[i][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[i],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][i]=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 time east: wolf cabbage west: goat farmer the 2 time <----- farmer east: wolf cabbage farmer west: goat the 3 time -----> farmer and wolf east: cabbage west: wolf goat farmer the 4 time <----- farmer and goat east: goat cabbage farmer west: wolf the 5 time -----> farmer and cabbage east: goat west: wolf cabbage farmer the 6 time <----- farmer east: goat farmer west: wolf cabbage the 7 time -----> farmer and goat east: none west: wolf goat cabbage farmer east: wolf goat cabbage farmer west: none the 1 time east: wolf cabbage west: goat farmer the 2 time <----- farmer east: wolf cabbage farmer west: goat the 3 time -----> farmer and cabbage east: wolf west: goat cabbage farmer the 4 time <----- farmer and goat east: wolf goat farmer west: cabbage the 5 time -----> farmer and wolf east: goat west: wolf cabbage farmer the 6 time <----- farmer east: goat farmer west: wolf cabbage the 7 time -----> farmer and goat east: none west: wolf goat cabbage farmer