农夫过河问题(c++编写)

1、问题描述从前，一个农夫带着一只狼，一只羊和一棵白菜要河（注意该狼被农夫训服了，但还会吃羊）。他要将所有东西安全的带到河的对岸，不幸的是河边只有一条船，只能装下农夫和他的一样东西，并且农夫必须每次都随船过，因为只有他能撑船。在无人看管的情况下，狼要吃羊，羊要吃白菜，因此，农夫不能在河的某边岸上单独留下狼和羊，也不能单独留下羊和白菜。那么农夫如何才能使三样东西平安过河呢？2、需求分析1）、农夫必须把狼，羊，白菜全部都载过河，且一次只能载一个；2）、要求狼和羊不能单独在一起，羊和白菜也不能单独在一起，即要么羊单独在河的一边，要么羊和农夫在一起。 3、系统概述设计对于上述情况，可以将河的两岸抽象成成数学问题，即将河的本岸抽象成数字0，将对岸抽象成1；且将狼，羊，白菜，农夫，分别抽象成数字0，1，2，3。而用数组aij（取值只能为0和1）表示第i次运载是，j（j=0,1,2,3。分别表示狼，羊，白菜，农夫）所在的位置。而用bi表示第i次运载时船上运载的东西（因为农夫每次都必须在船上，所以不用记录，除非穿上只有农夫一人）。如此一来，是否全部过河的问题就转化为判断ai0，ai1，ai2，ai3是否全为1了，即相加之和是否为4的问题了；而四者中的两者是否能在一起的问题就转化它们各自的aij是否相等的问题了。4、系统详细设计创建一个数组aMAXTIMES4用于存放农夫，狼，羊，白菜的位置，用0表示本岸，1表示对岸 ；bMAXTIMES用于存放狼，羊，白菜，农夫的编号; 0: 狼，1:羊，2:白菜，3:农夫；编写一个递归函数Ferry(int ferryTimes)，其中ferryTimes为渡河次数，在函数中，应考虑3个问题：1）、用aferryTimes0 + aferryTimes1 + aferryTimes2 + aferryTimes3 = 4语句判断是否全部到达对岸，如果是，则直接输出结果，否则，考虑第二个问题；2）、狼和羊是否单独在一起，羊和白菜是否单独在一起，用语句aferryTimes1 != aferryTimes3 & (aferryTimes2 = aferryTimes1 | aferryTimes0 = aferryTimes1)来实现；3）、如果上两个条件都不满，则可执行运输的动作，但每次都应考虑，该运输情况以前是否执行过（即两岸以及船上的东西以及各自位置和以前完全相同），如果没被执行过，则可以保存此时四者各自的状态，并递归的进行下一次运载。5、系统测试6、经验总结解决实际问题时，应先分析实际问题，找出实际问题的所有约束条件，然后对问题进行数学模型的抽象化，抓主要因素，省去一些不需要的因素，将其抽象为数学问题，然后再从整体上设计算法，搭建程序的框架，最后一步步完善细节，这样做，会使本来毫无头绪的问题变得清晰起来。7、参考文献C+程序设计 数据结构算法设计与分析程序代码如下：#include #include #include using namespace std;const int MAXTIMES = 20; int aMAXTIMES4;/存放农夫，狼，羊，白菜的位置，用0表示本岸，1表示对岸 char *name = 狼, 羊, 白菜, 农夫自己; int bMAXTIMES; /用于存放狼，羊，白菜，农夫的编号; 0: 狼，1:羊，2:白菜，3:农夫 void Ferry(int ferryTimes) /ferryTimes为渡河次数 int i;if (aferryTimes0 + aferryTimes1 + aferryTimes2 + aferryTimes3 = 4) /都到达对岸 for (i = 0; i ferryTimes; i+) if (ai3 = 0) coutttt载namebi到对岸endl; else coutttt载namebi回本岸endl; coutendl; return; /狼单独和羊在一起以及羊和白菜单独在一起的情况if (aferryTimes1 != aferryTimes3 & (aferryTimes2 = aferryTimes1 | aferryTimes0 = aferryTimes1) return; /用于判断此种情况在前searchTimes次运载过程中是否已经出现过，若出现过则不用记录for (i = 0; i ferryTimes; i+) for(int j = 0; j 4; j+)if(aferryTimesj != aij)break;if(j = 4)return; /若没有出现，则将运载后抵达另一岸的结果记录下来，并进行下一次运载for (i = 0; i = 3; i+) bferryTimes = i; aferryTimes + 10 = aferryTimes0;aferryTimes + 11 = aferryTimes1;aferryTimes + 12 = aferryTimes2;aferryTimes + 13 = 1 - aferryTimes3; if (aferryTimesi = aferryTimes3) aferryTimes + 1i = aferryTimes + 13; Ferry(ferryTimes + 1