数据结构课程设计报告---农夫过河问题

《数据结构课程设计报告---农夫过河问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录引言21问题描述3基本要求32.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性；32.2设计一个算法求解农夫过河问题，并输出过河方案；33概要设计33.1数据结构的设计。33.1.1农夫过河问题的模型化33.1.2算法的设计44、运行与测试65、总结与心得7附录7参考文献1313引言所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸,需要安全运到北岸。一条小船只能容下他和一件物品,只有农夫能撑船。问农夫怎么能安全过河,当然狼吃羊,羊吃白菜,农夫不能将这两种或三种物品单独放在河

2、的一侧,因为没有农夫的照看,狼就要吃羊,而羊可能要吃白菜?这类问题的实质是系统的状态问题,要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。131问题描述一个农夫带一只狼、一棵白菜和一只羊要从一条河的南岸过到北岸，农夫每次只能带一样东西过河，但是任意时刻如果农夫不在场时，狼要吃羊、羊要吃白菜，请为农夫设计过河方案。基本要求2.1为农夫过河问题抽象数据模型体会数据模型在问题求解中的重要性；2.2设计一个算法求解农夫过河问题，并输出过河方案；3概要设计3.1数据结构的设计。3.1.1农夫

3、过河问题的模型化分析这类问题会发现以下特征:有一组状态(如农夫和羊在南,狼和白菜在北);从一个状态可合法地转到另外几个状态(如农夫自己过河或农夫带着羊过河);有些状态不安全(如农夫在北,其他东西在南);有一个初始状态(都在南);结束状态集(这里只有一个,都在北)。问题表示:需要表示问题中的状态,农夫等位于南P北(每个有两种可能)。可以采用位向量,4个二进制位的0P1情况表示状态,显而易见,共24=16种可能状态。从高位到低位分别表示农夫、狼、白菜和羊。0000(整数0)表示都在南岸,目标状态1111(

4、即整数15)表示都到了北岸。有些状态0011,0101,0111,0001,1100,1001是不允许出现的,因为这些状态是不安全状态。根据上述条件可以画出系统的状态图如图1所示。图1系统状态转换图其中双向的箭头表示状态可逆,即农夫可以带着某种东西过去,也可以带着该东西回来。箭头上的字母表示农夫所携带的东西:f(farmer),w(wolf),g(goat),c(cabbage)分别表示农夫自己、农夫携带狼、农夫携带羊、农夫携带菜过河。现在的问题转化为:找一条合法路径(相邻状态之间的转移合法),从开始

5、状态到某个结束状态,途中不经过不安全状态。133.1.2算法的设计求农夫、狼、白菜和羊的当前状态的函数为每一种状态做测试,状态安全则返回0,否则返回1。安全性判断函数,若状态安全则返回0intfarmer(intlocation)//判断农夫位置对0做与运算，还是原来的数字，用来判断位置{return0!=(location&0x08);}intwolf(intlocation)//判断狼位置{return0!=(location&0x04);}intcabbage(intlocation)//判断白

6、菜位置{return0!=(location&0x02);}intgoat(intlocation)//判断羊的位置{return0!=(location&0x01);}intsafe(intlocation)//若状态安全则返回true{if((goat(location)==cabbage(location))&&(goat(location)!=farmer(location)))return0;if((goat(location)==wolf(location))&&(goat(locatio

7、n)!=farmer(location)))return0;return1;//其他状态是安全的借助于位向量和按位运算符,很容易描述过河动作,这种问题表示的设计使得程序的实现比较容易。算法的基本思想:利用队列moveTo记录可到的尚未向前探试的状态,数组元素route[i]记录状态i的路径[前一状态],-1表示尚未访问。则算法的高级抽象可描速为:{13初始状态出发点入队列;所有其他点状态标记为未访问;while(!isEmptyQueueseq(moveTo)&&(route[15]==-1)){从m

8、oveTo取出一个状态;试探所有由这个状态出发可能到达的状态;if(能到达的状态安全且未访问过){记录到它的路径;压入队列;}}}精化上速算法得到问题的具体算法如下:voidfarmerProblem(){intmovers,i,location,newlocation;introute[16];//记录已考虑的状态路径intprint[MAXNUM];PSeqQueuemoveTo;moveTo=createEmptyQueue_seq();//新的队