农夫过河问题(数据结构课设)
发布时间：2024-08-25
用VC可以实现,绝对的!
#include "stdafx.h"
#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] = "带狼过去. (wolf)--->对岸";
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)";
用VC可以实现,绝对的!
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 &&
用VC可以实现,绝对的!
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;
用VC可以实现,绝对的!
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;
}
农夫过河问题(数据结构课设).doc
将本文的Word文档下载到电脑
