398做网站彩铃,成都市学校网站建设,tom企业邮箱官网,免费网站奖励自己的软件题目描述#xff1a;农夫需要把狼、羊、菜和自己运到河对岸去#xff0c;只有农夫能够划船#xff0c;而且船比较小#xff0c;除农夫之外每次只能运一种东西#xff0c;还有一个棘手问题#xff0c;就是如果没有农夫看着#xff0c;羊会偷吃菜#xff0c;狼会吃羊。请…题目描述农夫需要把狼、羊、菜和自己运到河对岸去只有农夫能够划船而且船比较小除农夫之外每次只能运一种东西还有一个棘手问题就是如果没有农夫看着羊会偷吃菜狼会吃羊。请考虑一种方法让农夫能够安全地安排这些东西和他自己过河。想这个问题一连想了好几天本人没有系统的学过算法有些概念也不是很清楚只因解决问题为目标。尝试过图论解决但用floyed算法只能算出最短路径值如何输出过程一直没想出好的解决方法。然后看了下面这篇文章尝试抛弃图论用树的思想来解决这个问题。建议阅读下面代码时先看看这篇文章。参考资料http://blog.csdn.net/orbit/article/details/7563220在写代码时本人采用了上述文章中的思想又借鉴了图论中存储结点的一些方法。我觉得这样写应该非常容易看懂了。具体思路见代码。1 #include 2 #define INF 99993 //8个动作4 char *action[8]{农夫单独过河,农夫带狼过河,农夫带羊过河,农夫带菜过河,5 农夫单独返回,农夫带狼返回,农夫带羊返回,农夫带菜返回};6 //10种状态7 char *state[10]{人狼羊菜,人狼羊,人狼菜,人羊菜,人羊,狼菜,狼,羊,菜,空};89 //状态转换规则GA[i][j]k 表示【状态i】可以通过【动作k】转换到【状态j】GA[i][j]INF表示不可直接转换10 int GA[10][10]{INF,INF,INF,INF,INF, 2,INF,INF,INF,INF,11 INF,INF,INF,INF,INF,INF, 2, 1,INF,INF,12 INF,INF,INF,INF,INF, 0, 3,INF, 1,INF,13 INF,INF,INF,INF,INF,INF,INF, 3, 2,INF,14 INF,INF,INF,INF,INF,INF,INF, 0,INF, 2,15 6,INF, 4,INF,INF,INF,INF,INF,INF,INF,16 INF, 6, 7,INF,INF,INF,INF,INF,INF,INF,17 INF, 5,INF, 7, 4,INF,INF,INF,INF,INF,18 INF,INF, 5, 6,INF,INF,INF,INF,INF,INF,19 INF,INF,INF,INF, 6,INF,INF,INF,INF,INF};2021 //记录每一步的动作22 int record_action[20];23 //记录每一步动作后的状态24 int record_state[20];2526 //搜索从第step步开始、第i个结点到第n个结点的过程(step从0算起)27 void search(int i,int n,int step)28 {29 int k;//动作30 int j;//可能要转换到的状态31 if(in)32 {33 for(k0;k34 printf(step %d: %s左岸还剩 %s\n,k1,action[record_action[k]],state[record_state[k]]);35 printf(step count:%d\n\n,step);36 return;37 }38 //查找在当前【状态i】下能转换到的【其它状态j】并且【状态j】不能在之前出现过39 //查找时可能会出现多个 j所以这是一个多叉树40 for(k0;k8;k)41 {42 for(j0;j10;j)43 if(GA[i][j]!INFGA[i][j]k)//判断状态i能否通过动作k转换到状态j44 {45 int m;46 //下面这个循环是判断状态j在之前是否出现过47 for(m0;m48 if(jrecord_state[m])break;49 if(m50 //如果j满足前面所有条件则记录这一步51 record_action[step]k; //第step步所使用的动作52 record_state[step]j; //第step步所转换的状态53 search(j,n,step1); //继续搜索下一步54 }55 }5657 }58 int main()59 {60 search(0,9,0);61 return 0;62 }来源https://www.cnblogs.com/zandbin/p/5341656.html
