农夫过河程序设计.docx

农夫过河程序设计.docx农夫过何程莎彼奸
姓 名： 潘强辉
专 业： 计算机科学与技术
班 级： 0203108
指导教师： 李秀坤
哈尔滨工业大学计算机学院
二00四年六月
农夫过河问题用邻接表结构建图，主要用了对图进行先深搜索的操作。
实现语言：C语言
编程环境：Turbo C
程序实现功能：显示安全过河的每一个方案及步骤。
关键字
farmer wolf sheep vegetable 状态 邻接表
问题描述
图的大作业：
问题描述:有一农夫带着一条狼，一只羊和一筐菜，，农 夫每次只能带一样东西过河，而且如果没有农夫看管，则狼会吃羊，:农夫怎样过河 才能把每个东西安全地送过河？
基本要求：
将上述问题用图表示出来；
选择图的一种存储结构，编写一个自动生成该图的算法；
在2的基础上编写解该题的算法.
算法描述
算法由来：根据《数字逻辑》和布尔代数的思想，才想到用先深搜索图的算法。
1、 把farmer,wolf,sheep,vegetable在河两岸的所有不同状态用用。和1表示出来，
如下：
0000 0001 0010 0044 0100 0101 W40 W44
WQQ 4W 1010 1011 UQQ 1101 1110 1111
2、 根据题中的条件限制，可以判断：0011 0110 0111 1000 1001 1100这六个状态是 不可能存在的。
3、 把剩余的十个状态进行编号
aOOOO b0001
fl010 glOll
cOOlO
hllOl
dOlOO
illlO
eOlOl jllH
4、让电脑根据条件自动生成邻接表：
条件：①farmer的状态总是在0、1交替变化的；
②由于农夫每次只能带一样东西过河，所以每次wolf,sheep,vegetable最多只有
一个变化;
例如：状态b只可能变化到状态g或状态h,而不可能变化到其它状态。
因此可以得到以下邻接表：
把a至Uj重新编号为0到9,艮|3：
a—f—A
0—5—A
b—g—h—/\
1 一 6一7一 A
c—f—g—i — A
2一5一6一8一 A
d—h—i —/\
3一7一8一 A
e—h—j —A
4—7—9—A
f—a—c—A
5一0一2一 A
g—b 一 c—A
6一 1一2一 A
h—b—d—e—A
7一 1 一 3一4一 A
i—c—d—/\
8一2一 3一 A
j — e—A
9—4一/\
逻辑图如下:
5、 根据邻接表，用先深搜索图的方法进行搜索，从结点a直到找到结点j为止，然后重新 搜索，把从a到j的路都找到，打印出来，并保存到数组中。
6、 根据数组中保存的路，把a到j表示的状态重新还原为0、1的组合，当为。时在桥的左 边，当为1时在桥的右边。并逐步打印出来。
7、 程序结束。
数据结构设置:
输入状态:
state
a
b
c
d
e
f
g
h
i
j
farmer
0
0
0
0
0
1
1
1
1
1
wolf
0
0
0
1
1
0
0
1
1
1
sheep
0