农夫携物过河问题-数据结构与算法课程设计报告

1、精选优质文档-倾情为你奉上合肥学院计算机科学与技术系课程设计报告2009 2010 学年第二学期课程 数据结构与算法课程设计名称农夫携物过河问题学生姓名程梦云学号专业班级08计科(2)指导教师王昆仑 张贯虹2010年5月题目：农夫携物过河问题内容：有一农夫要将自己的兔子、蔬菜和狐狸等3件物品运过河。但农夫过河时所用的船每次最多只能装其中的一件物品，而这3件物品之间又存在一定的制约关系：兔子不能单独和狐狸以及不能和蔬菜在一起，因为狐狸要吃兔子，兔子也能吃蔬菜。试构造出问题模式以编程实现这一问题的求解。一、问题分析和任务定义根据对象的状态分为过河（1）和不过河（0），此对象集合就构成了一个状态空间

2、。问题就是在这个状态空间内搜索一条从开始状态到结束状态的安全路径。显然，其初始状态为四对象都不过河，结束状态为四对象全部过河。这里利用图的广度优先算法思想处理，并采用队列存储，灵活运用二进制的特点完美解决问题。对于农夫，狐狸，兔子，蔬菜组成一个4位二进制代码，即4位二进制数分别代表了农夫、狐狸、白菜和兔子，状态空间为16，初始状态为（0000），目标为（1111）。解决问题的方法是，首先将初始状态（0000）入队(第一层)，再将由初始状态（0000）可达到的所有安全状态入队（第二层），能由已有的安全状态到达的安全且不重复的所有状态入队（第三层），依次如此直到状态（1111）为止。对当前对象是否

3、安全的判断，若当农夫与兔子不在一起时，狐狸与兔子或兔子与蔬菜在一起是不安全的，其他情况是安全的。二、概要设计和数据结构的选择求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。此处采用广度优先算法。广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，

4、放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。表1 物品的所有位置状态农夫、狐狸、白菜、兔子Location农夫、狐狸、白菜、兔子Location00000100080

5、001110019001021010100011310111101004110012010151101130110611101401117111115数据结构的选择：本程序采用队列处理。typedef struct node/ 顺序队列类型定义 int f, r;/定义头尾指针 int datamaxlen; SeqQueue;为了实现上述程序的功能，需要：队列的创建、判空、入队、出队、取队首元素；判断农夫、狐狸、白菜和兔子的位子，并以此来判断该状态是否安全；按位子输出农夫、狐狸、；主函数，一个广度优先的过程；各函数关系如下：mainCreateQenQueuesafeDFS_pathprin

6、tflocationclick图1 各函数关系图三、详细设计和编码完成了上面的准备工作，现在的问题变成：从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。并且要求在序列中不应该出现重复的状态。算法分析如图2。为了实现广度优先搜索，算法中需要使用了一个整数队列Q，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需

7、要列举的所有状态(二进制0000 1111)一共16种，所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，算法中把这个顺序表叫做visited。visited的每个分量初始化值均为-1，每当我们在队列中加入一个新状态时，就把顺序表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。visited的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后我们可以利用visited顺序表元素的值建立起正确的状态路径。实现概要设计中定义的所有数据类型，对每个操作作出伪码算法。1、

8、定义一个队列的结构体，包含头尾指针和组data。2、子函数：置空队列Q->r=Q->f=03、子函数：判断队列是否为空return (Q->f = Q->r)4、子函数：入队5、子函数：出队6、子函数：取队头元素return (Q->dataQ->f)7、四个子函数，分别判断农夫、狐狸、白菜、兔子的位置。具体利用二进制数的按位取与法来完成，其中农夫ox08对应的二进制为0000 1000，狐狸ox04对应的二进制为0000 0100，白菜ox02对应的二进制为0000 0010，兔子ox01对应的二进制为0000 0001。不难看出，1所在的位置即要判断的物

9、品所在的位置。例如状态1011，1011&&1000=1000，即判断出农夫的位置为1，1011&&0100=0000，即判断狐狸的位置为0。8、子函数：判断状态是否安全。通过调用上述7的四个子函数可分别判断四个物品的位置，由此可知当兔子和白菜在一起且农夫不在以及狐狸和兔子在一起且农夫不在的时候为不安全状态，返回0，其他状态均是安全的，返回1。初始状态 00001001安全1010不安全1000不安全1100不安全0000重复0001安全1011安全1101安全1001安全0010安全0001重复0011不安全0100安全0001重复0101不安全0000重复0

10、001重复1011重复1110安全1010不安全1101重复1110安全1100不安全1111过河成功0110安全0110安全图2 算法分析9、点击函数：先将visited全部赋值为-1，创建队列，将初值0000入队，location为每次取的队头元素，从第一位兔子开始循环至农夫，利用的是<<左移符号，然后将所有与农夫在同一侧的物品（包括农夫自己，即不带物品移动）均带到河的另一侧，实现语句为newlocation = location (0x08 | movers);其中括号里的ox08|movers意思是带着物品或农夫独自移动，按位取异或所得的结果正好能达到此效果。newloca

11、tion即为新状态，判断其状态是否安全或是否重复，如果是则入队，且将visited里下标为newlocation的位置赋值为location。确定完location的数值后，判断鼠标点击是什么按钮，如果点的是开始键，则把location和newlocation赋值为15作为初始状态，并显示点击下一步开始过河，如果开始点的就是下一步，且点下一步前未点开始即没有赋值，则提示点开始。若已赋值，则在各个物品相应的位置输出。10、输出函数：根据location的值分别输出四个物体的位置。由表1可知，当location得值小于8时，农夫均为0，则在左岸输出农夫，否则在右岸输出。当location的值小于4

12、或在712之间，狐狸均为0，则在左岸输出狐狸，否则在右岸输出。当location的值对4求模的值为0或1时，白菜均为0，则在左岸输出白菜，否则在右岸输出。当location的值为偶数时，兔子均为0，则在左岸输出兔子，否则在右岸输出。（注：在每次输出前进行一次清屏处理。）11、释放函数，释放由此句柄控制的所有控件。YYNNYYNNNY开始创建队列Ox00入队队空？访问结束？取队头赋给locationfor (1 8; movers 左移)movers与农夫同侧带着movers移位Safe？未访问？newlocation入队visitednewlocation= locationID=开始newl

13、ocation=location=15ID=下一步已点开始？根据location的值按位置分别输出四物Location=0?过河成功location = visitedlocation结束图3 流程图四、上机调试经分析可知，该问题总共有2种路径可行，分别是：带兔子到对岸 ，空手回本岸 ，带狐狸到对岸 ，带兔子回本岸 ，带菜到对岸 ，空手回本岸 ，带兔子到对岸；带兔子到对岸，空手回本岸，带菜到对岸 ，带兔子回本岸 ，带狐狸到对岸 ，空手回本岸 ，带兔子到对岸。本程序输出的路径是前一种方案，具体见测试结果截图部分。本来应该把2种方案都输出的，要想第二种方法能够输出，比较是否重复的时候必须和除本层外

14、的层次比较，此处还未解决这一问题。另外本程序在搜索路径是采用的是BFS即广度优先搜索，还可用DFS即深度优先搜索。深度优先: 每个时刻探索一条路径，并记录访问过的合法状态，一直向前探视，直到走不通时回溯。显然，应该用堆栈来保存访问过的状态，以便回溯。广度优先：在所有可能的路径上齐头并进，同时探索可能性。这样，在某个位置会有多个分支，他们都要进行处理，因此需要一个缓冲队列，把他们进对保存，在依次出对处理。这样才能应付所有的状态。五、用户使用说明在vc+6.0下运行程序即可得到解决问题的方案，不需要其他操作六、测试结果图4 初始状态图5 如果第一步未按开始键图6 点击下一步过河图7 过河步骤图8

15、过河步骤图9 过河步骤图10 过河步骤图11 过河步骤图12 过河步骤图13 过河步骤图14 过河成功图15 为location赋初值5图16 程序错误七、参考文献1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2007年6月。2 严蔚敏，吴伟民. 数据结构（C语言版）. 清华大学出版社。3 网站CSDN 八、 附录#include "stdafx.h"#include <windows.h>#include <windowsx.h>#include "resource.h"#include "MainDlg

16、.h"#include <stdio.h>#include <stdlib.h>BOOL WINAPI Main_Proc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam) switch(uMsg) HANDLE_MSG(hWnd, WM_INITDIALOG, Main_OnInitDialog); HANDLE_MSG(hWnd, WM_COMMAND, Main_OnCommand);HANDLE_MSG(hWnd,WM_CLOSE, Main_OnClose); return FALSE;BOOL

17、Main_OnInitDialog(HWND hwnd, HWND hwndFocus, LPARAM lParam) return TRUE;const int maxlen=20;/定义maxlen的长度typedef struct node/ 顺序队列类型定义 int f, r;/定义头尾指针 int datamaxlen;SeqQueue;void InitQueue(SeqQueue *Q)/置空队列Q->r=0;Q->f=0;int isEmptyQueue_seq(SeqQueue *Q)/判断队列是否为空 return (Q->f = Q->r);voi

18、d enQueue_seq(HWND hwnd,SeqQueue *Q, int x) / 入队 if (Q->r + 1) % maxlen = Q->f)MessageBox(hwnd,TEXT("队列已满!"),TEXT("警告"),MB_OK); else Q->dataQ->r = x; Q->r = (Q->r + 1) % maxlen; void deQueue_seq(HWND hwnd,SeqQueue *Q)/出队 if (Q->f = Q->r)MessageBox(hwnd,TEX

19、T("队列已空!"),TEXT("警告"),MB_OK); else Q->f = (Q->f + 1) % maxlen;int frontQueue_seq(HWND hwnd,SeqQueue *Q)/取队头元素 if (Q->f = Q->r)MessageBox(hwnd,TEXT("队列已空!"),TEXT("警告"),MB_OK);return 0;else return (Q->dataQ->f);/ox01: 0000 0001 rabbit/ox02: 000

20、0 0010 cabbage/ox04: 0000 0100 fox/ox08: 0000 1000 farmerint farmer(int location)/判断农夫的位置 return (0 != (location &0x08);int fox(int location)/判断狐狸的位置 return (0 != (location &0x04);int cabbage(int location)/判断白菜的位置 return (0 != (location &0x02);int rabbit(int location)/判断兔子的位置 return (0 !

21、= (location &0x01);int safe(int location)/安全状态的判断函数 if (rabbit(location) = cabbage(location) && (rabbit(location) != farmer(location) return (0);/ 兔子吃白菜 if (rabbit(location) = fox(location) && (rabbit(location) != farmer(location) return (0);/ 狐狸吃兔子 return (1);/ 其他状态是安全的void prin

22、tfarmer(HWND hwnd,int location)/输出农夫的位置if(location<8)SetDlgItemText(hwnd,IDC_ETA2,TEXT("农夫");/在hwnd控制下的窗口的IDC_ETA2控件中输出农夫elseSetDlgItemText(hwnd,IDC_ETA1,TEXT("农夫");/在hwnd控制下的窗口的IDC_ETA1控件中输出农夫void printfox(HWND hwnd,int location)/输出狐狸的位置if(location<12)&&(location&g

23、t;7)|(location<4)SetDlgItemText(hwnd,IDC_ETB2,TEXT("狐狸");/在hwnd控制下的窗口的IDC_ETB2控件中输出狐狸elseSetDlgItemText(hwnd,IDC_ETB1,TEXT("狐狸");/在hwnd控制下的窗口的IDC_ETB1控件中输出狐狸void printcabbage(HWND hwnd,int location)/输出白菜的位置if(location%4=0|location%4=1)SetDlgItemText(hwnd,IDC_ETC2,TEXT("白菜

24、");/在hwnd控制下的窗口的IDC_ETC2控件中输出白菜elseSetDlgItemText(hwnd,IDC_ETC1,TEXT("白菜");/在hwnd控制下的窗口的IDC_ETC1控件中输出白菜void printrabbit(HWND hwnd,int location)/输出兔子的位置if(location%2=0)SetDlgItemText(hwnd,IDC_ETD2,TEXT("兔子");/在hwnd控制下的窗口的IDC_ETD2控件中输出兔子elseSetDlgItemText(hwnd,IDC_ETD1,TEXT(&q

25、uot;兔子");/在hwnd控制下的窗口的IDC_ETD1控件中输出兔子void empty(HWND hwnd)/清屏SetDlgItemText(hwnd,IDC_ETA1,TEXT("");SetDlgItemText(hwnd,IDC_ETA2,TEXT("");SetDlgItemText(hwnd,IDC_ETB1,TEXT("");SetDlgItemText(hwnd,IDC_ETB2,TEXT("");SetDlgItemText(hwnd,IDC_ETC1,TEXT("&q

26、uot;);SetDlgItemText(hwnd,IDC_ETC2,TEXT("");SetDlgItemText(hwnd,IDC_ETD1,TEXT("");SetDlgItemText(hwnd,IDC_ETD2,TEXT("");void Main_OnCommand(HWND hwnd, int id, HWND hwndCtl, UINT codeNotify)/点击函数int i, movers, newlocation,location,visited20;/movers:正在移动的物品;visited:用于记录已考

27、虑的状态路径TCHAR strlo256;/用于存放location转换的字符 SeqQueue *Q;/用于记录可以安全到达的中间状态SeqQueue movet; Q = &movet;/取movet的地址InitQueue(Q);/建空队 enQueue_seq(hwnd,Q, 0x00);/初始状态0000进队列 for (i = 1; i < 16; i+)/定义数组visited初值 visitedi = -1; visited0 = 0;/初始化visited0while (!isEmptyQueue_seq(Q) && (visited15 = -

28、1)/Q非空或已全部被访问过 location = frontQueue_seq(hwnd,Q);/取队头状态为当前状态 deQueue_seq(hwnd,Q);/队头元素出队 for (movers = 1; movers <= 8; movers <<= 1)/考虑各种物品移动,<<为左移运算符 if (0 != (location &0x08) = (0 != (location & movers)/农夫与移动的物品在同一侧newlocation = location (0x08 | movers); /计算新状态，为按位异或，|为按位或if (safe(newlocation) && (visitednewlocation = -1)/新状态安全且未处理visitednewlocation = location;/记录新状态的前驱enQueue_seq(hwnd,Q, newlocation);/新状态入队static int k1=0;/静态变量 switch(id) case IDC_begin:/如果点击开始键k1=1;SetDlgItemText(hwnd,IDC_LO,"15");/在IDC_LO中显示15SetDlgItemText(hwnd,IDC_NL