农夫过河问题状态图及程序Word文档下载推荐.docx

1、算法的精化要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5（其二进制表示为0101） 表示农夫和白菜在河的南岸，而狼和羊在北岸。四、算法的实现完成了上面的准备工作，现在的问题变成：从初始状态二进制0000（全部在河的南岸） 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111（全部到达河的北岸） 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。为避免不必要的瞎费功夫，要求在序

2、列中不应该出现重复的状态。为了实现广度优先搜索，算法中需要使用了一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态（二进制0000 1111）一共16种，所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，算法中把这个顺序表叫做route。route的每个分量初始化值均为-1，每当我们在队列中加入一个新状态时，就把顺序表中以该状态作下标的元素

3、的值改为达到这个状态的路径上前一状态的下标值。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后我们可以利用route顺序表元素的值建立起正确的状态路径。五、程序代码/ farmerProblem.c/ 用队列解决农夫过河问题#include stdlib.htypedef int DataType;/顺序队列：类型和界面函数声明struct SeqQueue/ 顺序队列类型定义int MAXNUM; / 队列中最大元素个数int f, r;DataType *q;typedef struct SeqQueue *PSeqQueue; / 顺序队列类型的指针类型PSeqQu

4、eue createEmptyQueue_seq（int m）/创建一个空队列PSeqQueue queue = （PSeqQueue）malloc（sizeof（struct SeqQueue）;if （queue != NULL）queue-q = （DataType*）malloc（sizeof（DataType） *m）;if （queue-q）MAXNUM = m;f = 0;r = 0;return （queue）;elsefree（queue）;printf（Out of space!n）; / 存储分配失败return NULL;int isEmptyQueue_seq（PSe

5、qQueue queue）/判断队列是否为空return （queue-f = queue-r）;void enQueue_seq（PSeqQueue queue, DataType x）/ 在队尾插入元素xif （queue-r + 1） % queue-MAXNUM = queue-f）Full queue.nqqueue-r = x;r = （queue-MAXNUM;void deQueue_seq（PSeqQueue queue）/ 删除队列头部元素r）Empty Queue.nf = （queue-f + 1） % queue-DataType frontQueue_seq（PSe

6、qQueue queue）f）;/个体状态判断函数int farmer（int location）/判断农夫的位置return （0 != （location &0x08）;int wolf（int location）/判断狼的位置0x04）;int cabbage（int location）/判断白菜的位置0x02）;int goat（int location）/判断羊的位置0x01）;/安全状态的判断函数int safe（int location）/ 若状态安全则返回trueif （goat（location） = cabbage（location） & （goat（location） !

7、= farmer（location）return （0）;/ 羊吃白菜if （goat（location） = wolf（location） &/ 狼吃羊return （1）; / 其他状态是安全的main（）int i, movers, location, newlocation;int route16; /用于记录已考虑的状态路径PSeqQueue moveTo; /用于记录可以安全到达的中间状态moveTo = createEmptyQueue_seq（20）; /创建空队列enQueue_seq（moveTo, 0x00）; /初始状态进队列for （i = 0; i 16; i+）r

8、outei =- 1;/准备数组route初值route0 = 0;while （!isEmptyQueue_seq（moveTo） & （route15 =- 1）location = frontQueue_seq（moveTo）; /取队头状态为当前状态deQueue_seq（moveTo）;for （movers = 1; movers = 8;= 0; location = routelocation）The location is : %dn, location）;if （location = 0）exit（0）;No solution.n/问题无解六、测试结果程序输出按相反的变化方

9、向输出的，真实的情况应该是从0、9、15变化的。七、总结和体会这个程序还有很大的改进空间，首先是人性化方面的设计，这个程序最终的输出结果是用10进制的，而我们需要知道的应该是二进制的结果，所以应该直接把结果输出为二进制，还要按开始到最终状态的排序输出。还有一种更为人性化的设计，就是把对应的每个二进制代码代表的含义直接用中文表示出来，这样的结果更直观，方便用户使用。例如：0000时，程序输出：所有的物品都在南岸。后面的一个状态是9（1001），程序输出：农夫和羊到了北岸。通过这个程序的学习，很受启发，明白了如何用计算机解决实际生活中的问题。刚开始接到这个题目时，感觉到相当困难，因为这种题以前是考验我们的IQ用的，现在没想到要用计算机来解决，而且计算机又没有思想，怎样让它想问题，实现我们需要的功能。原来，可以把实际的问题转变为数学模型，通过计算机超强悍的循环功能和强大的数据处理能力，把所有可能的结果都算出来，然后用约束项来对这些结果进行筛选，然后把结果用数学格式来输出，让问题得以求解。这个程序的设计方法比较巧妙的地方是数学建模，即每个角色的位置进行描述的方法：用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。这个方法令人拍案叫绝，不得不佩服人类的智慧。