狼羊白菜实验报告.doc

《狼羊白菜实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南京邮电大学通达学院程序设计(上机)报告题目:R004M,P005H专业网络工程学生姓名班级学号指导教师日期评分细则评分项优秀良好中等及格不及格遵守机房规章制度上机表现学习态度基础知识水平程序设计能力课题功能实现情况算法设计合理性用户界面友好性报告书写认真程度报告内容完整性文字表达清楚程度问题回答准确性评分等级教师签名：年月日备注注：评分等级分为五种：优秀、良好、中等、及格、不及格狼羊白菜过河程序实验报告一．问题描述一个人带着一只羊，一条狼和一颗白菜想过河，假设他每次只能带一只羊，或者一条狼，或者一

2、颗白菜过河，并限定人不在场时，狼和羊，或羊和白菜不能单独在一起，试编写程序求出他带一只羊，一条狼和一颗白菜过河的办法。二．结构图过河农夫选择相斥共存程序运行输出结果三、结构设计1、狼和羊、羊和白菜不能单独在一起，涉及对象较多，而且运算步骤方法较为复杂，要用程序语言实现，需要将具体实例数字化。针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个二维数组或者结构体来实现对四个对象狼、羊、白菜和一个人的表示。对于岸的两侧可以用0或者1来表示，以实现在程序设计中的简便性。2、对狼羊白菜

3、的过河步骤，没有顺序的约束，因此需要给各个事物依次进行编号，然后依次尝试，若成功，进行下一步，使用循环或者递归算法进行程序3、程序使用递归算法，为了方便将各个实例数字化。定义二维数组inta[M][4]存储每一步中各个对象所处的位置，用0-3分别表示二维数组的一维下标。具体对应为：wolf-0goat-1cabbage-2people-3将本岸和对岸数字化，其对应为：本（东）岸-0对（西）岸-1具体对应实例比如在第3步之后狼在本岸，羊在对岸，白菜在本岸，农夫在对岸，则其存储结果为：a[3][0]a[

4、3][1]a[3][2]a[3][3]0101最初存储状态为：a[0][0]a[0][1]a[0][2]a[0][3]0000成功渡河之后，二维数组存储应为：a[istep][0]a[istep][1]a[istep][2]a[istep][3]1111因此a[iStep][0]+a[iStep][1]+a[iStep][2]+a[iStep][3]==4。题目要求狼和羊、羊和白菜不能在一起，即出现以下情况：a[iStep][1]!=a[iStep][3]&&(a[iStep][2]==a[iSte

5、p][1]

6、

7、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)

8、;}elseif(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时仍无符合条件的方式，则渡河失败。在

9、递归的过程中每进行一步都需要判断是否需要继续进行此次操作，具体的判断为：（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[iSte

10、p][2]==a[iStep][1]

11、

12、a[iStep][0]==a[iStep][1])){return;}四、处理流程图：search（iStep）人狼羊白菜在本岸输出解决方案YYN狼羊白菜单独在一起？Yreturn此状态态与前面相同？结束search(istep+1)i++i<=2?i=-1NYNNY五、源程序#include#include#include#defineM10inta[M][4];int