词条信息

admin
admin
超级管理员
最近编辑者 发短消息   

相关词条

热门词条

更多>>
什么是端口?到底是做什么的呢?
端口一般指两种,一种是硬件比如路由器或者交换机的插网线的端口,一种是软件的逻辑的概念,比如http的80端口!...
7种进阶方法让你快速测试端口连通性
Ping是Windows、Linux和Unix系统下的一个检查网络连通性的命令工具,对于大部分互联网用户来说很...
电脑开机,总需要按F1,是什么原因造成的?
一.主板掉电这个说法是行业内的叫法了,一般是主板的CMOS电池没电了导致的。也是最常见的一种提示你按F1的提示...
社保降费对个人有什么影响?
下调城镇职工基本养老保险单位缴费比例是政府给企业发的一个大红包,特别是对于企业来说是一个利好,但是对个人来说有...
车辆“出险”对下年保费的影响,到底有多大?
【出险对交强险的影响】【出险对商业险的影响】车辆“出险”对下年保费的影响,到底有多大?这里有必要先提下车险第三...
解决网 >>所属分类 >> 程序开发    C/C#   

C语言实现农夫过河代码及解析

标签: C语言 农夫过河 代码解析

顶[0] 发表评论(0) 编辑词条
目录

问题描述编辑本段回目录


  一个农夫在河边带了一只狼、一只羊和一颗白菜,他需要把这三样东西用船带到河的对岸。然而,这艘船只能容下农夫本人和另外一样东西。如果农夫不在场的话,狼会吃掉羊,羊也会吃掉白菜。请编程为农夫解决这个过河问题。


问题分析编辑本段回目录


  根据问题描述可知,该问题涉及的对象较多,而且运算步骤也较为复杂,因此,在使用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][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("nnn");

if(i<Step)

printf(" the %d timen",i+1);

if(i>0 && i<Step)

{

if(a[i][3] == 0) /*农夫在本岸*/

{

printf(" -----> farmer ");

printf("%sn", name[b[i] + 1]);

}

else /*农夫在对岸*/

{

printf(" <----- farmer ");

printf("%sn", name[b[i] + 1]);

}

}

}

printf("nnnn");

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("nn 农夫过河问题,解决方案如下:nnn");

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



 

 

附件列表


按字母顺序浏览:A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

→我们致力于为广大网民解决所遇到的各种电脑技术问题
 如果您认为本词条还有待完善,请 编辑词条

上一篇解读Linux进程
下一篇C语言狼追兔子问题代码解析

0
1. 本站部分内容来自互联网,如有任何版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
2. 本站内容仅供参考,如果您需要解决具体问题,建议您咨询相关领域专业人士。
3. 如果您没有找到需要的百科词条,您可以到百科问答提问或创建词条,等待高手解答。

关于本词条的提问

查看全部/我要提问>>