学号： xxxxxxxxxx
姓名： xxx
专业： xxxxxx
班级： xxxxxxxxx
指导教师： xx
完成日期： 2018年6月
一、问题描述：
要求设计实现农夫过河问题（农夫带着一只狼，一只羊，一棵白菜，一次只能带一个东西）如何安全过河。
船上一次只能带一个东西，只有农夫会划船。当农夫不在时，狼如果和羊在一起，狼会把羊吃掉，羊不能和白菜在一起，羊会把白菜吃掉。但是狼不吃白菜。试求通过计算，得到能够使农夫，狼，羊，白菜一起安全过河的方法。
问题的解决方案：
可以用栈与队列、深度优先搜索算法及广度优先搜索算法相应的原理去解决问题。
实现四个过河对象（农夫、白菜、羊和狼）的状态，可以用一个四位二进制数来表示，0表示未过河，1表示已经过河了。过河的对象必须与农夫在河的同一侧，可以设计函数来判断。防止状态往复，即农夫将一个东西带过去又带回来的情况发生，需将所有可能的状态进行标定。可用深度优先搜索算法及广度优先搜索算法去解题。在基本要求达到后，可进行创新设计，如系统用户功能控制，改进算法的实现，实现友好的人机交互等等。
二、系统设计
1.功能实现概括：
在实现农夫过河中，我采用了无向图的结构来存储结点信息，用邻接矩阵存储结点的关系，用一个四位二进制数来表示过河状态，0表示河北岸，1表示从河南岸，初始状态农夫、狼、羊、白菜都在河北岸，用0000表示。完全过河后用1111表示。
图的遍历过程采用了深度优先搜素算法，将遍历的过程存入一个数组来记录过河过程，经过系统分析，农夫过河有两种解答方式，由于深度优先算法是遍历所有结点，造成数组部分被覆盖，在第二次遍历时改动了一些算法结构，使得第二种过河方式得以保存实现。
2.程序功能模块：
该系统分为三大模块
第一块：将农夫、狼、羊、白菜作为图的结点元素构建图的结点结构体，构造邻接矩阵，构造图时先判断结点的安全状态，创建只有安全结点，再判断各个结点之间的联系，将有关系的边存入邻接矩阵，构造图的结构。
第二块：利用深度优先搜索算法进行图的遍历，遍历到一个结点时，判断寻找与其有关系的下一个结点，将下一个结点的下标存入设定的ray数组，数组存放的既是过河过程。第二次遍历时，为避免深度优先搜素算法使得存入部分下标被覆盖，在可能被覆盖的结点进行算法改动，将另一种过程存入预定的ray2数组，从而实现两种过河过程。
第三块：分别循环访问ray和ray2数组， 判断数组元素对应的下标结点，打印出对应的过河过程和河两岸的对象状态，最后输出总的过河过程。
3.系统流程图
（1）图的结构：
因为从初始状态0000到1111一共有16种情况，判断其安全的情况共有十种，再判断各个结点的连接关系，运用邻接矩阵构建图的结构
（2）流程图：
略
4.系统的功能调试
本程序不需要用户输入，只需要用户按回车键即可观察下一步的操作即可。通过一定的界面友好的展示给用户正确的过程。
这是第一种过河方式
这是第二种过河方式
两种过河方式在第三步，第四步，第五步有所不同
详细代码如下：
#include <iostream> #include <windows.h> #include <stdio.h> using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 16 #define INFINTITY 65535 int visited[MAXSIZE]; int ray[MAXSIZE]; int ray2[MAXSIZE]; static int sum =0; typedef int EdgeType; /*状态顶点*/ typedef struct { int farmer; //农夫 int wolf; //狼 int sheep; //羊 int cabbage; //白菜 }status; /*邻接矩阵结点*/ typedef struct { int stanum; //顶点个数 status vexs[MAXSIZE]; //储存顶点数组 EdgeType arc[MAXSIZE][MAXSIZE]; //邻接矩阵权值 }MGraph; /*判断该状态是否安全*/ int isSafe(int farmer,int wolf,int sheep,int cabbage) { //狼羊同岸 或 羊菜同岸 if(((farmer!=wolf)&&(wolf==sheep))||((farmer!=sheep)&&(sheep==cabbage))) return FALSE; else return TRUE; } /*判断两个点是否有联系*/ int Truemove(MGraph G,int i,int j) { int change = 0; if(G.vexs[i].farmer==G.vexs[j].farmer) //判断农夫是否移动 return FALSE; else if(G.vexs[i].wolf!=G.vexs[j].wolf) //狼 change++; if(G.vexs[i].sheep!=G.vexs[j].sheep) //羊 change++; if(G.vexs[i].cabbage!=G.vexs[j].cabbage) //白菜 change++; if(change>1) return FALSE; else return TRUE; } /*创建只有安全结点的图*/ void CreateUDG(MGraph &G) { G.stanum=0; //将判断安全的状态存入数组 10种 for(int i=0;i<=1;i++) { for(int j=0;j<=1;j++) { for(int k=0;k<=1;k++) { for(int l=0;l<=1;l++) { if(isSafe(i,j,k,l)) { G.vexs[G.stanum].farmer=i; G.vexs[G.stanum].wolf=j; G.vexs[G.stanum].sheep=k; G.vexs[G.stanum].cabbage=l; G.stanum++; } } } } } //将有关系的边存入邻接矩阵 构建图的结构 for(int i = 0;i < G.stanum;i++) { for(int j = 0;j< G.stanum;j++) { if(Truemove(G,i,j)) { G.arc[i][j] = TRUE; } else { G.arc[i][j] = INFINTITY; } } } } /*邻接矩阵的深度优先递归算法*/ void DFS(MGraph G,int i,int a) { if(a==1) { visited[i] = TRUE; //cout<<i<<" "; //cout<<G.vexs[i].farmer<<G.vexs[i].wolf<<G.vexs[i].sheep<<G.vexs[i].cabbage<<endl; if(i==9) return; for(int j=0;j<G.stanum;j++) if(G.arc[i][j] != INFINTITY && !visited[j]) { ray[i] = j; //cout<<j<<" "; DFS(G,j,a); } } else if(a==2) { visited[i] = TRUE; //cout<<i<<" "; //cout<<G.vexs[i].farmer<<G.vexs[i].wolf<<G.vexs[i].sheep<<G.vexs[i].cabbage<<endl; if(i==9) return; for(int j=0;j<G.stanum;j++) if(G.arc[i][j] != INFINTITY && !visited[j]) { if(j==1||j==6){ continue; } ray2[i] = j; //cout<<j<<" "; DFS(G,j,a); } } } /*邻接矩阵的深度优先遍历算法*/ void TraverseDFS(MGraph G,int a) { if(a==1) { for(int i = 0;i<G.stanum;i++) { visited[i] = FALSE; ray[i] = -1; } for(int i=0;i<G.stanum;i++) if(!visited[i]) //对未访问过的顶点调用DFS 若是连通图的话,只会执行一次 DFS(G,i,a); } else if(a==2) { for(int i = 0;i<G.stanum;i++) { visited[i] = FALSE; ray2[i] = -1; } for(int i=0;i<G.stanum;i++) if(!visited[i]) //对未访问过的顶点调用DFS 若是连通图的话,只会执行一次 DFS(G,i,a); } } /*查找下标*/ int find(MGraph G,int farmer,int wolf,int sheep,int cabbage) { for (int i = 0; i < G.stanum; i++) { if (G.vexs[i].farmer == farmer && G.vexs[i].wolf == wolf && G.vexs[i].sheep == sheep && G.vexs[i].cabbage == cabbage ) { return i; //返回当前位置 } } return -1; } /*展示面板*/ void showTable1() //船在上 { cout<<"========================================================================================================================"<<endl; cout<<" << 船 # * - - "<<endl; cout<<" / \\ * * - "<<endl; cout<<" \\ / "<<endl; cout<<" << * - - "<<endl; cout<<" * * "<<endl; cout<<" * - - "<<endl; cout<<" << * * "<<endl; cout<<" "<<endl; cout<<" * * - "<<endl; cout<<" << * - - "<<endl; cout<<"========================================================================================================================"<<endl; } void showTable2() //船在下 { cout<<"========================================================================================================================"<<endl; cout<<" << * - - "<<endl; cout<<" * * - "<<endl; cout<<" "<<endl; cout<<" <<- - "<<endl; cout<<" * * "<<endl; cout<<" * - - "<<endl; cout<<" << # * * "<<endl; cout<<" / \\ "<<endl; cout<<" \\ / * * - "<<endl; cout<<" << 船 * * - - "<<endl; cout<<"========================================================================================================================"<<endl; } void showPeole1(MGraph G,int i)//北方的状态 { cout<<" 北方"<<" "; if(G.vexs[i].farmer==0) cout<<"\t农夫"; if(G.vexs[i].wolf==0) cout<<"\t狼"; if(G.vexs[i].sheep==0) cout<<"\t羊"; if(G.vexs[i].cabbage==0) cout<<"\t白菜"; cout<<endl; } void showPeole2(MGraph G,int i)//南方的状态 { cout<<" 南方"<<" "; if(G.vexs[i].farmer==1) cout<<"\t农夫"; if(G.vexs[i].wolf==1) cout<<"\t狼"; if(G.vexs[i].sheep==1) cout<<"\t羊"; if(G.vexs[i].cabbage==1) cout<<"\t白菜"; cout<<endl; } /*加入叙述语句*/ void saySomething(MGraph G,int i,int a) { if(a==1) { int wolf = 0, sheep = 0, cabbage = 0; if(sum!=0) { cout<<"\n\n\t第"<<sum<<"步:\t"; if(G.vexs[ray[i]].wolf != G.vexs[i].wolf) { if(G.vexs[ray[i]].farmer == 1) cout<<"农 夫 带 狼 去 了 南 边 "<<endl; else cout<<"农 夫 带 狼 去 了 北 边 "<<endl; } else if(G.vexs[ray[i]].sheep != G.vexs[i].sheep) { if(G.vexs[ray[i]].farmer == 1) cout<<"农 夫 带 羊 去 了 南 边 "<<endl; else cout<<"农 夫 带 羊 去 了 北 边 "<<endl; } else if(G.vexs[ray[i]].cabbage != G.vexs[i].cabbage) { if(G.vexs[ray[i]].farmer == 1) cout<<"农 夫 带 白 菜 去 了 南 边 "<<endl; else cout<<"农 夫 带 白 菜 去 了 北 边 "<<endl; } else { if(G.vexs[ray[i]].farmer == 1) cout<<"农 夫 独 自 去 了 南 边 "<<endl; else cout<<"农 夫 独 自 去 了 北 边 "<<endl; } } sum++; } else if(a==2) { int wolf = 0, sheep = 0, cabbage = 0; if(sum!=0) { cout<<"\n\n\t第"<<sum<<"步:\t"; if(G.vexs[ray2[i]].wolf != G.vexs[i].wolf) { if(G.vexs[ray2[i]].farmer == 1) cout<<"农 夫 带 狼 去 了 南 边 "<<endl; else cout<<"农 夫 带 狼 去 了 北 边 "<<endl; } else if(G.vexs[ray2[i]].sheep != G.vexs[i].sheep) { if(G.vexs[ray2[i]].farmer == 1) cout<<"农 夫 带 羊 去 了 南 边 "<<endl; else cout<<"农 夫 带 羊 去 了 北 边 "<<endl; } else if(G.vexs[ray2[i]].cabbage != G.vexs[i].cabbage) { if(G.vexs[ray2[i]].farmer == 1) cout<<"农 夫 带 白 菜 去 了 南 边 "<<endl; else cout<<"农 夫 带 白 菜 去 了 北 边 "<<endl; } else { if(G.vexs[ray2[i]].farmer == 1) cout<<"农 夫 独 自 去 了 南 边 "<<endl; else cout<<"农 夫 独 自 去 了 北 边 "<<endl; } } sum++; } } /*打印全部操作*/ void sayall(MGraph G,int i,int end,int a) { if(a==1) { sum = 1; cout<<"\n\n\n第一种总路程为:"<<endl; while(i!=end) { cout<<endl; saySomething(G,i,a); i = ray[i]; } getchar(); system("cls"); } else if(a==2) { sum = 1; cout<<"\n\n\n第二种总路程为:"<<endl; while(i!=end) { cout<<endl; saySomething(G,i,a); i = ray2[i]; } getchar(); system("cls"); } } /*展示总面板*/ void showAll(MGraph G,int start,int end,int a) { if(a==1) { cout<<" 农夫过河《一》"<<endl<<endl; int low = start; while(start!=end) { showPeole1(G,start); //北 if(G.vexs[start].farmer==0) showTable1(); else showTable2(); showPeole2(G,start); //南 saySomething(G,low,a); low = start; start=ray[start]; getchar(); system("cls"); } showPeole1(G,start); if(G.vexs[start].farmer==0) showTable1(); else showTable2(); showPeole2(G,low); saySomething(G,low,a); start=find(G,0,0,0,0);//重置下标 getchar(); system("cls"); } else if(a==2) { cout<<" 农夫过河《二》"<<endl<<endl; sum=0; int low = start; while(start!=end) { showPeole1(G,start); //北 if(G.vexs[start].farmer==0) showTable1(); else showTable2(); showPeole2(G,start); //南 saySomething(G,low,a); low = start; //cout<<"start="<<start<<endl;//测试遍历过程下标 start=ray2[start]; getchar(); system("cls"); } showPeole1(G,start); if(G.vexs[start].farmer==0) showTable1(); else showTable2(); showPeole2(G,start); saySomething(G,low,a); start=find(G,0,0,0,0);//重置下标 getchar(); } } int main() { MGraph G; CreateUDG(G); int start = find(G,0,0,0,0); int end = find(G,1,1,1,1); TraverseDFS(G,1); //第一种遍历答案 TraverseDFS(G,2); //第二种遍历答案 showAll(G,start,end,1);//第一种过河方式 sayall(G,start,end,1);//输出第一种过河过程 showAll(G,start,end,2);//第二种过河方式 sayall(G,start,end,2);//输出第二种过河过程 }如有错误，欢迎指出。
