南京邮电大学通达学院 程序设计(上机)报告
题目:R004M,P005H
专 业 网络工程 学 生 姓 名 班 级 学 号 指 导 教 师 日 期
评分项 遵守机房规章制度 优秀 良好 中等 及格 不及格 评上机表现 学习态度 基础知识水平 程序设计能力 课题功能实现情况 算法设计合理性 用户界面友好性 报告书写认真程度 报告内容完整性 文字表达清楚程度 问题回答准确性 注：评分等级分为五种：优秀、良好、中等、及格、不及格
分 细 则 评分等级 教师签名： 年 月 日 备注
狼羊白菜过河程序实验报告
一．问题描述
一个人带着一只羊，一条狼和一颗白菜想过河，假设他每次只能带一只羊，或者一条狼，或者一颗白菜过河，并限定人不在场时，狼和羊，或羊和白菜不能单独在一起，试编写程序求出他带一只羊，一条狼和一颗白菜过河的办法。 二．结构图
过河 农夫选择相斥共存程序运行输出结果三、结构设计
1、 狼和羊、羊和白菜不能单独在一起，涉及对象较多，而且运算步骤方法较为复杂，要用程序语言实现，需要将具体实例数字化。针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个二维数组或者结构体来实现对四个对象狼、羊、白菜和一个人的表示。对于岸的两侧可以用0或者1来表示，以实现在程序设计中的简便性。
2、对狼羊白菜的过河步骤，没有顺序的约束，因此需要给各个事物依次进行编号，然后依次尝试，若成功，进行下一步，使用循环或者递归算法进行程序 3、程序使用递归算法，为了方便将各个实例数字化。定义二维数组int a[M][4]存储每一步中各个对象所处的位置，用0-3分别表示二维数组的一维下标。具体对应为：wolf-0 goat-1 cabbage-2 people-3
将本岸和对岸数字化，其对应为：本（东）岸-0 对（西）岸-1
具体对应实例比如在第3步之后狼在本岸，羊在对岸，白菜在本岸，农夫在对岸，则其存储结果为：
a[3][0] a[3][1] a[3][2] a[3][3]
0 1 0 1
最初存储状态为：a[0][0] a[0][1] a[0][2] a[0][3] 0 0 0 0 成功渡河之后，二维数组存储应为：
a[istep][0] a[istep][1] a[istep][2] a[istep][3] 1 1 1 1
因此a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4。 题目要求狼和羊、羊和白菜不能在一起，即出现以下情况：
a[iStep][1] != a[iStep][3] && (a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1])则出现错误，应返回操作。
开始 a[0][0]=0,a[0][1]=0,a[0][2]=0,a[0][3]=0 递归
结束 同时定义一维数组b[M]来存储每一步中人是如何过河的。设计程序中实现递归操作部分的核心程序为： for(i=-1;i<=2;i++) {b[iStep] = i;
memcpy(a[iStep+1],a[iStep],16); a[iStep+1][3]=1-a[iStep+1][3];
if(i==-1) {
search(iStep+1); }
else if(a[iStep][i] == a[iStep][3]) {a[iStep+1][i] = a[iStep+1][3];
search(iStep+1); } }
每次循环从-1到2依次代表渡河时为一人、带狼、带羊、带白菜通过，利用语句 “b[iStep] = i”分别记录每一步中渡河方式，“a[iStep + 1][i] = a[iStep + 1][3]”即利用赋值方式使狼或羊或白菜与人一同到对岸或者回到本岸。若渡河成功，则依次输出渡河方式。“i<=2”即为操作的限制，当若i=2时仍无符合条件的方式，则渡河失败。
在递归的过程中每进行一步都需要判断是否需要继续进行此次操作，具体的判断为：（1）若该步骤能使各值均为1，则渡河成功，输出结果。
if(a[iStep][0]+a[iStep][1]+a[iStep][2]+a[iStep][3]==4){?? return} （2）若该步与以前步骤相同，返回操作。 if(memcmp(a[i],a[iStep],16)==0) { return;}
（3）若羊和人不在一块而狼和羊或者羊和白菜在一块，则返回操作。 if(a[iStep][1]!=a[iStep][3]&&(a[iStep][2]==a[iStep][1]||a[iStep][0] == a[iStep][1])) {return;}
狼羊白菜实验报告
