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