数据结构,农夫过河。详细讲述过河 #include<stdio.h> //0代表在河的这边;1代表在河的对岸 struct Condition{ int farmer; int wolf; int sheep; int cabbage; }; struct Condition conditions[100];//结构体条件数组 char * action [100]; void takeWolfOver(int i) //把狼来过去 { action[i]="把狼过去.---->对岸"; conditions[i+1].wolf=1; conditions[i+1].sheep=conditions[i].sheep; conditions[i+1].cabbage=conditions[i].cabbage; } void takeWolfBack(int i)/*把狼带回来*/ { action[i]="带狼回来.本岸<---(wolf)"; conditions[i+1].wolf=0; conditions[i+1].sheep=conditions[i].sheep; conditions[i+1].cabbage=conditions[i].cabbage; } void takeSheepOver(int i)/*把羊带过去*/ { action[i]="带羊过去.(sheep)--->对岸"; conditions[i+1].wolf=conditions[i].wolf; conditions[i+1].sheep=1; conditions[i+1].cabbage=conditions[i].cabbage; } void takeSheepBack(int i)/*把羊带回来*/ { action[i]="带羊回来.本岸<---(sheep)"; conditions[i+1].wolf=conditions[i].wolf; conditions[i+1].sheep=0; conditions[i+1].cabbage=conditions[i].cabbage; } void takeCabbageOver(int i)/*把菜带过去*/ { action[i]="带菜过去.(cabbage)--->对岸"; conditions[i+1].wolf=conditions[i].wolf; conditions[i+1].sheep=conditions[i].sheep; conditions[i+1].cabbage=1; } void takeCabbageBack(int i)/*把菜带回来*/ { action[i]="带菜回来.本岸<---(cabbage)"; conditions[i+1].wolf=conditions[i].wolf; conditions[i+1].sheep=conditions[i].sheep; conditions[i+1].cabbage=0; } void getOverBarely(int i)/*过河时的情况*/ { action[i]="空手过去.(barely)--->对岸"; conditions[i+1].wolf=conditions[i].wolf; conditions[i+1].sheep=conditions[i].sheep; conditions[i+1].cabbage=conditions[i].cabbage;/*全不动*/ } void getBackBarely(int i)/*返回时的情况*/ { action[i]="空手回来.本岸<---(barely)"; conditions[i+1].wolf=conditions[i].wolf; conditions[i+1].sheep=conditions[i].sheep; conditions[i+1].cabbage=conditions[i].cabbage; } void showSolution(int i)/*显示解决方法*/ { int c; printf("\n"); printf("%s\n","解决办法:"); for(c=0;c<i;c++) { printf("step%d:%s\n",c+1,action[c]);/*换行输出*/ } printf("%s\n","Successful!"); } void tryOneStep(int i)/*再试一遍*/ { int c; int j; if(i>=100)/*检查循环是否出现问题*/ { printf("%s\n","渡河步骤达到100步出错"); return; } if(conditions[i].farmer==1&&conditions[i].wolf==1&&conditions[i].sheep==1&&conditions[i].cabbage==1)/*检查是否都过河*/ { showSolution(i);/*是的,都过河了.返回*/ return; } if((conditions[i].farmer!=conditions[i].wolf&&conditions[i].wolf==conditions[i].sheep)||(conditions[i].farmer!=conditions[i].sheep&&conditions[i].sheep==conditions[i].cabbage))/*检查是否丢失,出错*/ { /*不,狼会吃掉羊,或者羊会吃掉菜的*/ return; } /*检查条件是否满足*/ for(c=0;c<i;c++) { if(conditions[c].farmer==conditions[i].farmer&&conditions[c].wolf==conditions[i].wolf&&conditions[c].sheep==conditions[i].sheep&&conditions[c].cabbage==conditions[i].cabbage) { return; } } j=i+1; if(conditions[i].farmer==0)/*农夫在河这边*/ { conditions[j].farmer=1; getOverBarely(i); tryOneStep(j); if(conditions[i].wolf==0)/*如果狼没带过去*/ { takeWolfOver(i); tryOneStep(j); } if(conditions[i].sheep==0) { takeSheepOver(i); tryOneStep(j); } if(conditions[i].cabbage==0) { takeCabbageOver(i); tryOneStep(j); } }else{ conditions[j].farmer=0; getBackBarely(i); tryOneStep(j); if(conditions[i].wolf==1) { takeWolfBack(i); tryOneStep(j); } if(conditions[i].sheep==1) { takeSheepBack(i); tryOneStep(j); } if(conditions[i].cabbage==1) { takeCabbageBack(i); tryOneStep(j); } } } int main()/*主函数*/ { printf("问题:农夫过河.一个农夫带着一只狼,一只羊和一些菜过河.河边只有一条一船,由于船太小,只能装下农夫和他的一样东西"); printf("在无人看管的情况下,狼要吃羊,羊要吃菜,请问农夫如何才能使三样东西平安过河.\n"); conditions[0].farmer=0;/*设置初始值*/ conditions[0].wolf=0; conditions[0].sheep=0; conditions[0].cabbage=0;/*使用循环递回寻找解决办法*/ tryOneStep(0); return 0; }
- 粉丝: 0
- 资源: 1
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助