C语言解决农夫过河难题

[复制链接]

133

主题

368

帖子

1395

积分

单晶硅锭

Rank: 3Rank: 3

积分
1395
查看: 14回复: 2 发表于 2020-6-28 09:27:10   只看该作者
本帖最后由 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

42

主题

211

帖子

439

积分

二氧化硅

Rank: 2

积分
439
发表于 2020-6-28 09:37:30   只看该作者
谢谢分享 有借鉴的作用

20

主题

103

帖子

246

积分

二氧化硅

Rank: 2

积分
246
发表于 2020-6-28 09:38:10   只看该作者
谢谢老师分享
快速回复 返回顶部 返回列表