数据结构实训——农夫过河.doc

农夫过河问题项目实训一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他只有一条船，船小到只能容下他和一件物品，当然，船只有农夫能撑。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和狼或者羊和白菜单独在河的一边，自己离开。好在狼属于食肉动物，它不吃白菜。请问农夫该采取什么方案，才能将所有的东西安全运过河呢？一、算法与数据结构的设计：要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫和或者某种东西在河的南岸，1表示在河的北岸。则问题的初始状态是整数（其二进制表示为0000）；而问题的终结状态是整数15（其二进制表示为1111）。用整数location表示用上述方法描述的状态，函数返回值为真（1）表示所考察的人或物在河的北岸，否则在南岸。二、算法的精化： 用一个整数队列moveTo，把搜索过程中每一步所有可能达到的状态都保存起来。队列中每一个元素表示一个可以安全到达的中间状态。另外，用一个整数数组route，用于记录已被访问过的各个状态，以及已被发现的能够到达这些状态的前驱状态。route数组只需要使用16个元素。Route的每一个元素初始化值均设置为-1，每当在队列加入一个新状态时，就把route中以该状态坐下标的元素的值改为达到这个状态的前一状态的下标值。所以，数组的第i个元素，不仅记录状态i是否已被访问过，同时对已被访问过的状态，还保存了这个状态的前驱状态下标。算法结束后，可以利用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 = (PSeqQueue)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) 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 ); else paqu-f = (paqu-f + 1) % MAXNUM;DataType frontQueue_seq( PSeqQueue paqu ) /* 对非空队列,求队列头部元素 */ return (paqu-qpaqu-f);int farmer(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(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; moveTo = 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,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结果分析：从初始状态0到最后状态15的动作序列为：1.初始全部在南岸（0000），2农夫把羊带到北岸（1001），3.农夫独自回到南岸（0001），4.农夫把白菜带到北岸（1011），5.农夫带着羊回到南岸（0010）, 6.农夫把狼带到北岸（1110），7.农夫独自回到南岸（0110），8.农夫把羊带到北岸（1111）程序运行最后location结果为15（二进制为1111），即农夫和其他东西都安全运过了北岸。解决了农夫过河问题.五、收获与体会：通过本次的上机实验，把书本的知识运用于实践