农夫过河实验报告

《农夫过河实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.-“数据构造与算法综合实验〞课程设计报告题目：农夫过河问题学院计算机科学技术年级2014级专业计算机科学与技术学号20142060XX高晗日期2016年3月30日星期三成绩..word.zl-.-评语大学计算机科学技术学院、软件学院..word.zl-.-?数据构造与算法综合实验?报告1.系统概述〔1〕一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，那么狼不能吃羊，羊不能吃白菜；否那么狼会吃羊，羊会吃

2、白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。〔2〕为农夫过河问题抽象数据模型，体会数据模型在求解问题中的重要作用。〔3〕掌握顺序表和队列的逻辑构造和存储构造。2.系统需求分析(1)针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个构造体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。(2)题目要求给出四种事物的过河步骤，没有对先后顺序进展约束，这就需要给

3、各个事物依次进展编号，然后依次试探，假设试探成功，进展下一步试探。这就需要使用循环或者递归算法，防止随机盲目运算且保证每种情况均试探到，不承受非法输入。(3)题目要求求出农夫带一只羊，一条狼和一颗白菜过河的方法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述容，并使界面所示方案清晰简洁。..word.zl-.-(4)实验运行环境为VC++6.0.3.系统概要设计(1)数据构造设计要模拟农夫过河

4、的问题，用四位二进制数顺序分别表示农夫，狼，羊，白菜的位置。用0表示农夫或某种东西在河的南岸，1表示在河的北岸。那么问题的初始状态是整数〔二进制数表示为0000〕；问题的终结状态是整数15〔二进制表示为1111〕。00101010用一个整数队列MoveTo把搜索过程中所有可能到达的状态都保存起来。队列中的每一个元素表示一个可以到达的中间状态。另外用一个整数数组route记录被访问过的状态，以及已经被发现的能够到达这些状态的前驱。数组只需使用16个元素，每个元素的初始化值均为-1，每当队列中参加一个新状态时，数组中

5、以该状态做下标的元素改为到达这一状态的前一状态的下标值。所以数组的第i个元素不仅记录状态i是否被过，同时还保存该状态的前驱状态下标。算法完毕后可以利用route数组元素的值生成一个正确的状态路径。系统状态转换构造如图1所示:0000x1011111001000001111101011101..word.zl-.-图1系统状态转换构造图〔2〕软件构造设计农夫过河管理系统根据需求分析中的功能分析，可以提炼出主要有搜索功能，判断事物平安功能，输出过河方案功能。而搜索功能又可以利用不同算法，如广度优先算法，深度优先算法等

6、等。判断事物平安功能需要将事物位置进展分析，通过位置分布的代码来判断当前状态是否平安，使用“与〞位操作来考察狼和羊、羊和白菜是否在同一侧，且它们与农夫不一侧。假设是，该状态即为不平安状态，否那么为平安状态。假设一个状态已经被访问过，或只有农夫一人从南岸过到北岸，那么该状态被判为无效状态。输出功能就是将过河方案在屏幕上进展显示。系统软件构造如图1所示判断平安模块输出模块搜索模块输出过河方案农夫过河问题平安有效路径农夫携带物品深度优先搜索广度优先搜索图1农夫过河管理系统软件模块构造图4.系统详细设计与实现(1)搜索算

7、法设计..word.zl-.-搜索过程可利用广度优先搜索算法从初始状态二进制0000〔全部在河的南岸〕出发，寻找一种全部由平安状态构成的状态序列，它以二进制1111〔全部到达河的北岸〕为最终目标，并且在序列中的每一个状态都可以从前一个状态得到。为防止重复，要求在序列中不出现重复的状态。(2)确定状态的平安有效性的功能模块设计通过位置分布的代码来判断当前状态是否平安，使用“与〞位操作来考察狼和羊、羊和白菜是否在同一侧，且它们与农夫不一侧。假设是，该状态即为不平安状态，否那么为平安状态。假设一个状态已经被访问过，或只

8、有农夫一人从南岸过到北岸，那么该状态被判为无效状态。假设状态平安且有效，那么返回1，否那么返回0。该模块算法流程图如图2所示。开场否全在南岸？..word.zl-.-否是状态是否平安？是是是否重复？否全在北岸？否是完毕图2确定状态的平安有效性的功能模块设计算法流程图〔3〕输出模块设计..word.zl-.-输出农夫过河问题的可行性方案时，可从目标状态〔1111〕开场，将其