数据结构课程设计实验报告--177.doc

数据结构课程设计报告 姓名：陈白杨 班级：软092 老师：王森玉 学号：099074177 实验一：农夫过河问题 题目：农夫过河问题 问题描述：从前，一人农夫带着一只狼，一只羊和一棵白菜（注意该狼已被农夫驯服了，但还是会吃羊）。他要将所有东西安全的带到河的对岸。不幸的是河边只有一条小船，只能装下农夫和他的一样东西，并且农夫必须每次都随船过河，因为只有他能撑船。在无人看管的情况下，狼要吃羊，羊要吃白菜，因此，农夫不能在河的某边岸上单独留下狼和羊，也不能单独留下羊和白菜。那么农夫如何才能使三样东西平安过河呢？ 三．源代码 /*农夫过河问题*/ #include stdio.h #include stdlib.h #include string.h #define MAX_STEP 20 /*二维数组a的行下标表示次数，列下标分别表示: 0 - 狼，1－羊，2－菜，3－农夫，值表示：0－本岸，1－对岸 如：a[2][0]=1表示狼在第二次后在对岸*/ int a[MAX_STEP][4]; //初始状态都未赋值,默认为0， 意思是4个都在本岸 int b[MAX_STEP]; //数组b是用来存放每一步操作的动作对象，如b[0]=1,那么就表示第一步农民“带羊”（name[b[0]+1]即name[2]），这个说明只是打个比方 char *name[] = { 空手, 带狼, 带羊, 带菜 }; void search(int iStep) { int i; if (a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4) //递归的结束条件，最后的结果，即4个都到对岸后，分别输入每一步的操作 { for (i = 0; i iStep; i++) { if (a[i][3] == 0) //a[i][3]表示农夫，因为每次农夫必须动，所以根据农夫的位置来判断本次的行动，也就是农夫在本岸的话动作应该是带XX到对岸 { printf(%s到对岸\n, name[b[i] + 1]); } else //否则相反 { printf(%s回本岸\n, name[b[i] + 1]); } } printf(\n); return; } //下面这个for语句是一个比较的语句，处理的问题是，当第n步移动后，如果跟前面某一步移动后的状态时一样的，那么表示没有意义，结束本次递归，防止进入死循环 for (i = 0; i iStep; i++) { if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0) { return; } } //下面这个if表示当本次是这种情况：农夫和羊没在一起，而且羊和狼在一起或者羊和菜在一起，那么就会违反规则，则结束本次调用 if (a[iStep][1] != a[iStep][3] (a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1])) { return; } //排除了前面的特殊情况，下面进入真正的递归阶段 for (i = -1; i = 2; i++) { b[iStep] = i; //将第istep步骤的操作赋值给b[istep],默认为-1,即最后输出的时候是name[b[i] + 1]表示空手 memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])); //一维数组的复制,将二维数组上一行赋值给下一行 a[iStep + 1][3] = 1 - a[iStep + 1][3]; //由于0表示本岸，1表示对岸，1-值表示交换，即每次农夫是必须动的。 if (i == -1) //如果i==-1就递归下一次，这里表示只有农夫运动 { search(iStep + 1); } else if (a[iStep][i] == a[iStep][3]) //从0到2表示 0 - 狼，1－羊，2－菜，判断是否跟农夫在一边，在一边才可能被带走 { a[iStep + 1][i] = a[iStep + 1][3]; //表示i被带走了，那么下一次的值因为是跟农夫一样的 search(iStep + 1); } } } int main() { s