《数据结构实训——农夫过河.doc》由会员分享，可在线阅读，更多相关《数据结构实训——农夫过河.doc（5页珍藏版）》请在金锄头文库上搜索。
1、农夫过河问题项目实训一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他只有一条船，船小到只能容下他和一件物品，当然，船只有农夫能撑。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河的一边，自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案，才能将所有的东西安全运过河呢？一、算法与数据结构的设计：要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫和或者某种东西在河的南岸，1表示在河的北岸。则问题的初始状态是整数（其二进制表示为0000）；而问题的终结状态是整数15（其二进制表示为1
2、111）。用整数location表示用上述方法描述的状态，函数返回值为真（1）表示所考察的人或物在河的北岸，否则在南岸。二、算法的精化： 用一个整数队列moveTo，把搜索过程中每一步所有可能达到的状态都保存起来。队列中每一个元素表示一个可以安全到达的中间状态。另外，用一个整数数组route，用于记录已被访问过的各个状态，以及已被发现的能够到达这些状态的前驱状态。route数组只需要使用16个元素。Route的每一个元素初始化值均设置为-1，每当在队列加入一个新状态时，就把route中以该状态坐下标的元素的值改为达到这个状态的前一状态的下标值。所以，数组的第i个元素，不仅记录状态i是否已被访问
3、过，同时对已被访问过的状态，还保存了这个状态的前驱状态下标。算法结束后，可以利用route数组元素的值生成一个正确的状态路径。三、程序的实现：程序代码如下:#include#include#define MAXNUM 20typedef int DataType;struct SeqQueue /* 顺序队列类型定义 */ int f, r; DataType qMAXNUM;typedef struct SeqQueue *PSeqQueue; /* 顺序队列类型的指针类型 */PSeqQueue createEmptyQueue_seq(void) PSeqQueue paqu = (PS
4、eqQueue)malloc(sizeof(struct SeqQueue); if (paqu = NULL) printf(Out of space!n); else paqu-f = paqu-r = 0; return (paqu);int isEmptyQueue_seq( PSeqQueue paqu ) /*判断paqu所指是否是空队列*/ return paqu-f = paqu-r;void enQueue_seq(PSeqQueue paqu, DataType x) /* 在队列中插入一元素x */ if (paqu-r + 1) % MAXNUM = paqu-f) p
5、rintf(Full queue.n); else paqu-qpaqu-r = x; paqu-r = (paqu-r + 1) % MAXNUM; void deQueue_seq(PSeqQueue paqu) /* 删除队列头部元素 */ if( paqu-f = paqu-r ) printf( Empty Queue.n ); else paqu-f = (paqu-f + 1) % MAXNUM;DataType frontQueue_seq( PSeqQueue paqu ) /* 对非空队列,求队列头部元素 */ return (paqu-qpaqu-f);int farme
6、r(int location) /*判断农夫位置*/ return 0 != (location & 0x08);int wolf(int location) /*判断狼位置*/ return 0 != (location & 0x04);int cabbage(int location) /*判断白菜位置*/ return 0 != (location & 0x02);int goat(int location) /*判断羊的位置*/ return 0 !=(location & 0x01);int safe(int location) /* 若状态安全则返回true */ if (goat
7、(location) = cabbage(location) & (goat(location) != farmer(location) ) return 0; if (goat(location) = wolf(location) & (goat(location) != farmer(location) return 0; return 1; /* 其他状态是安全的 */void farmerProblem( ) int movers, i, location, newlocation; int route16; /*记录已考虑的状态路径*/ PSeqQueue moveTo; moveT
8、o = createEmptyQueue_seq( ); enQueue_seq(moveTo, 0x00); for (i = 0; i 16; i+) routei = -1; route0=0; while (!isEmptyQueue_seq(moveTo)&(route15 = -1) location = frontQueue_seq(moveTo); deQueue_seq(moveTo); for (movers = 1; movers = 8; movers = 0; location = routelocation) printf(The location is : %dn
9、,location); if (location = 0) return; else printf(No solution.n);int main() /*主函数*/ farmerProblem(); return 0;四、程序运行结果如下：The reverse path is ：The location is ： 15The location is ： 6The location is ： 14 The location is ： 2The location is ： 11The location is ： 1The location is ： 9The location is ： 0结果
10、分析：从初始状态0到最后状态15的动作序列为：1.初始全部在南岸（0000），2农夫把羊带到北岸（1001），3.农夫独自回到南岸（0001），4.农夫把白菜带到北岸（1011），5.农夫带着羊回到南岸（0010）, 6.农夫把狼带到北岸（1110），7.农夫独自回到南岸（0110），8.农夫把羊带到北岸（1111）程序运行最后location结果为15（二进制为1111），即农夫和其他东西都安全运过了北岸。解决了农夫过河问题.五、收获与体会：通过本次的上机实验，把书本的知识运用于实践，使我对书本上知识的理解更为生动，透彻。在本次的上机实验中，由于之前有去预习并试着去编写程序，所以在上机过程中比较顺利，但是还是免不了出些差错。经过多次调试才改正过来。而且还做不到脱离课本自身来编程。这也说明c语言能力不强。希望经过多次的上机实验可以使我的c语言有进一步的提高。对算法与数据结构的知识更为理解。
