农夫过河实验报告.doc

“数据结构与算法综合实验”课程设计报告题目： 农夫过河问题学 院计算机科学技术年 级2014级专 业计算机科学与技术学 号20142060姓 名高晗日 期2016年3月30日星期三成 绩评 语黑龙江大学计算机科学技术学院、软件学院数据结构与算法综合实验报告1. 系统概述（1）一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。（2）为农夫过河问题抽象数据模型，体会数据模型在求解问题中的重要作用。 （3）掌握顺序表和队列的逻辑结构和存储结构。2.系统需求分析 (1)针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。 (2)题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到，不接受非法输入。 (3)题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。 (4)实验运行环境为VC+6.0.3.系统概要设计(1)数据结构设计 要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫，狼，羊，白菜的位置。用0表示农夫或某种东西在河的南岸，1表示在河的北岸。则问题的初始状态是整数（二进制数表示为0000）；问题的终结状态是整数15（二进制表示为1111） 。 00101010 用一个整数队列MoveTo把搜索过程中所有可能达到的状态都保存起来。队列中的每一个元素表示一个可以到达的中间状态。另外用一个整数数组route记录被访问过的状态，以及已经被发现的能够到达这些状态的前驱。 数组只需使用16个元素，每个元素的初始化值均为-1，每当队列中加入一个新状态时，数组中以该状态做下标的元素改为到达这一状态的前一状态的下标值。所以数组的第i个元素不仅记录状态i是否被过，同时还保存该状态的前驱状态下标。算法结束后可以利用route数组元素的值生成一个正确的状态路径。系统状态转换结构如图1所示:0000x1011111001000001111101011101图1系统状态转换结构图 （2）软件结构设计农夫过河管理系统根据需求分析中的功能分析，可以提炼出主要有搜索功能，判断事物安全功能，输出过河方案功能。而搜索功能又可以利用不同算法，如广度优先算法，深度优先算法等等。判断事物安全功能需要将事物位置进行分析，通过位置分布的代码来判断当前状态是否安全，使用“与”位操作来考察狼和羊、羊和白菜是否在同一侧，且它们与农夫不一侧。若是，该状态即为不安全状态，否则为安全状态。若一个状态已经被访问过，或只有农夫一人从南岸过到北岸，则该状态被判为无效状态。输出功能就是将过河方案在屏幕上进行显示。系统软件结构如图1所示判断安全模块输出模块搜索模块输出过河方案 农夫过河 问题安全有效路径农夫携带物品深度优先搜索广度优先搜索图1农夫过河管理系统软件模块结构图4.系统详细设计与实现(1)搜索算法设计搜索过程可利用广度优先搜索算法从初始状态二进制0000（全部在河的南岸）出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111（全部到达河的北岸）为最终目标，并且在序列中的每一个状态都可以从前一个状态得到。为避免重复，要求在序列中不出现重复的状态。(2)确定状态的安全有效性的功能模块设计通过位置分布的代码来判断当前状态是否安全，使用“与”位操作来考察狼和羊、羊和白菜是否在同一侧，且它们与农夫不一侧。若是，该状态即为不安全状态，否则为安全状态。若一个状态已经被访问过，或只有农夫一人从南岸过到北岸，则该状态被判为无效状态。若状态安全且有效，则返回1，否则返回0。该模块算法流程图如图2所示。 开始否 全在南岸？ 否是 状态是否安全？ 是是 是否重复？否 全在北岸？否是结束 图2 确定状态的安全有效性的功能模块设计算法流程图 （3）输出模块设计输出农夫过河问题的可行性方案时，可从目标状态（1111）开始，将其记入队列（或栈）中，然后再找出其前驱，记入队列（或栈）中，然后在找其前驱，直到找到的是开始状态（0000）为止。要求输出时根据位置分布代码（即4位二进制数）各个位置上的0、1代码所表示的含义输出容易理解的文字。5.系统测试 对于该程序而言并没有实际输入，需要观察的就是输出结果。对于该程序的测试及其测试用例如表3所示。表3输出测试用例测试内容测试用例 预期结果实际结果 输出过河方案具体步骤 无第0步：南岸 农夫 狼 白菜 羊 北岸第1步：南岸 狼 白菜 北岸 农夫 羊第2步：南岸 农夫 狼 白菜 北岸 羊第3步：南岸 狼 北岸 农夫 羊 白菜 第4步：南岸 农夫 狼 羊 北岸 白菜第5步：南岸 羊 北岸 农夫 狼 白菜第6步：南岸 农夫 羊 北岸 狼 白菜第7步：南岸 北岸 农夫 狼 白菜 羊与预期结果相同6.小结（1）通过这2周的程序设计使我了解到了自己在数据结构方面的不足，也坚定了我学好编程的信心。 （2）采用广度优先的算法，利用数组只能记寻前一个前驱，导致另一个路径的丢失，不是很令人满意，所以采用第二种算法，深度优先算法，利用栈来记录路径前驱。参考文献1 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版）M. 北京：人民邮电出版社，2011:54-110.附录1.广度优先算法#include#include#define MAXNUM 20using namespace std;typedef struct /顺序队列类型定义 int f, r; /f表示头，r 表示尾 int qMAXNUM;/顺序队 SqQueue ,*SqQueuePtr; SqQueuePtr createEmptySQueue()/创建空队列 SqQueuePtr squeue = new SqQueue; if(squeue = NULL) cout申请内存失败f=squeue-r=0; return squeue; bool isEmptyQueue(SqQueuePtr squeue)/判断是否空队列 return (squeue-f=squeue-r); void enQueue(SqQueuePtr squeue,int x)/向队列中插入元素x if(squeue-r+1)%MAXNUM=squeue-f) cout队列已满qsqueue-r=x; squeue-r=(squeue-r+1)%MAXNUM; void deQueue(SqQueuePtr squeue)/出对 if(isEmptyQueue(squeue) cout对列为空f=(squeue-f+1)%MAXNUM; int getHead(SqQueuePtr squeue)/对非空队列,求队列头部元素 if(squeue-f != squeue-r) return squeue-qsqueue-f; bool farmerLocation(int location) /判断农夫位置对0做与运算，还是原来的数字，用来判断位置 return 0 != (location & 0x08); bool wolfLocation(int location) /判断狼位置 return 0 != (location & 0x04); bool cabbageLocation(int location) /判断白菜位置 return 0 != (location & 0x02); bool goatLocation(int location) /判断羊的位置 return 0 !=(location & 0x01); /* 其中一共有两种状态是不安全的：狼和羊单独在一起；羊和白菜单独在一起*/ bool isSafe(int location) / 若状态安全则返回 true if (goatLocation(location) = cabbageLocation(location) /羊和白菜单独在一起& (goatLocation(location) !=farmerLocation(location) ) return 0; if (goatLocation(location) = wolfLocation(location)& (goatLocation(location) !=farmerLocation(location)/狼和羊单独在一起 return 0; return 1; /其他状态是安全的 void farmerProblem() int movers, i, location, newlocation; int route16; /记录已考虑的状态路径 int printMAXNUM; SqQueuePtr moveTo; moveTo = createEmptySQueue();/新的队列判断路径 enQueue(moveTo, 0x00); /初始状态为0 for (i = 0; i 16; i+) routei = -1; /-1表示没有记录过路径 route0=0; while (!isEmptyQueue(moveTo)&(route15= -1) /队列不为空，路径未满时循环 location = getHead(moveTo); /从队头出队，location表示位置，0为北岸，1为南岸 deQueue(moveTo);/已出队的删除 for (movers = 1; movers = 8; movers= 1) /向左移位，movers分别0001，0010，0100，1000, /也就是依次判断过河的可行性 if (0 != (location & 0x08) = (0 != (location & movers) /判断农夫和要移动的物品是否在同岸 newlocation = location(0x08|movers);/过岸 if (isSafe(newlocation) & (routenewlocation = -1) /判断是否安全，以及路径是否可用 routenewlocation = location; enQueue(moveTo, newlocation); /记录路径并入队，位置改变 /* 打印路径 */ if(route15 != -1) cout过河步骤是 : endl; couttt南岸ttt北岸= 0; location = routelocation) printi=location; i-; if (location = 0) break; for(int j=i+1;j=7;j+) cout第j步：; switch(printj) case 0: couttt农夫 狼 白菜 羊tttendl;break; case 1: couttt农夫 狼 白菜tt羊endl;break; case 2: couttt农夫 狼 羊tt白菜endl;break; case 4: couttt农夫 白菜 羊ttt狼endl;break; case 6: couttt农夫 羊tt狼 白菜endl;break; case 9: couttt狼 白菜ttt农夫 羊 endl;break; case 11: couttt狼ttt农夫 羊 白菜endl;break; case 13: couttt白菜ttt农夫 狼 羊 endl;break; case 14: couttt羊 ttt农夫 狼 白菜endl;break; case 15: coutttttt农夫 狼 羊 白菜endl;break; int main() farmerProblem(); return 0;2. 深度优先算法#include#include#define MAXNUM 20using namespace std;int solutionCout=0;typedef struct int *base;/栈底指针 int *top;/栈顶指针 int stacksize;/栈可用的最大容量SqStack;void createEmptyStack(SqStack &S)/构造一个空栈S S.base=new intMAXNUM; if(!S.base) cout申请内存失败endl; exit(0); S.top=S.base;/初始为空栈 S.stacksize = MAXNUM;void Push(SqStack &S,int x)/插入一个元素x if(S.top-S.base=S.stacksize)/栈满 cout栈满; *S.top+=x;void Pop(SqStack &S)/出栈 if(S.top=S.base)/栈空 cout栈空; -S.top;int getTop(SqStack S)/取栈顶元素 return *(S.top-1);void print(SqStack S)/打印路径 int *p=S.base; solutionCout+; int printMAXNUM; int i=0; while(!(p=S.top) printi=*p; i+;p+; cout方案solutionCout过河步骤是 : endl; couttt南岸ttt北岸endl; for(int j=0;ji;j+) cout第j步：; switch(printj) case 0: couttt农夫 狼 白菜 羊tttendl;break; case 1: couttt农夫 狼 白菜tt羊endl;break; case 2: couttt农夫 狼 羊tt白菜endl;break; case 4: couttt农夫 白菜 羊tt狼endl;break; case 6: couttt农夫 羊tt狼 白菜endl;break; case 9: couttt狼 白菜ttt农夫 羊 endl;break; case 11: couttt狼ttt农夫 羊 白菜endl;break; case 13: couttt白菜ttt农夫 狼 羊 endl;break; case 14: couttt羊 ttt农夫 狼 白菜endl;break; case 15: coutttttt农夫 狼 羊 白菜endl;break; bool farmerLocation(int location) /判断农夫位置对0做与运算，还是原来的数字，用来判断位置 return 0 != (location & 0x08); bool wolfLocation(int location) /判断狼位置 return 0 != (location & 0x04); bool cabbageLocation(int location) /判断白菜位置 return 0 != (location & 0x02); bool goatLocation(int location) /判断羊的位置 return 0 !=(location & 0x01); /* 其中一共有两种状态是不安全的：狼和羊单独在一起；羊和白菜单独在一起*/ bool isSafe(int location) / 若状态安全则返回 true if (goatLocation(location) = cabbageLocation(location) /羊和白菜单独在一起& (goatLocation(location) !=farmerLocation(location) ) return 0; if (goatLocation(location) = wolfLocation(location)& (goatLocation(location) !=farmerLocation(location)/狼和羊单独在一起 return 0; return 1; /其他状态是安全的 int isAppeared(SqStack S,int location) /判断路径是否出现过,出现返回0；没有出现返回1 int *p=S.base; while (!(p=S.top) if(*p=location) return 0; p+; return 1; void farmerProblem(SqStack S,int location) if(location = 15) print(S); return; int newlocation,movers; for (movers = 1; movers = 8; movers= 1) /向左移位，movers分别0001，0010，0100，1000, /也就是依次判断过河的可行性 if (0 != (location & 0x08) = (0 != (location & movers) /判断农夫和要移动的物品是否在同岸 newlocation = location(0x08|movers);/过岸 if (isSafe(newlocation) & isAppeared(S,newlocation) /判断是否安全，以及路径是否可用 Push(S,newlocation);/新路径入栈 farmerProblem(S,newlocation);/以新路径为当前状态递归寻找下一可行路径 Pop(S);/已找到的可行路径出战 int main() SqStack S;int location=0; createEmptyStack(S);/创建辅助空栈 Push(S,location);/首先将0000压入栈 farmerProblem(S,location); return 0;