农夫过河问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
一. 问题描述
设一个农夫过河带着一条狼、一只羊和一棵白菜，身处河的南岸。现在他要把这些西全部运到北岸,现在问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃白菜。根据原题的描述我们知道，单独留下白菜和羊，或单独留下狼和羊在某一岸的状态是不安全的。白菜和狼相处没事,把它看作个重要关系的,通过位置分布的代码来判断状态是否安全。然后设计一个
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
, 模拟农夫能安全地将这三样东西带过河。
二．基本要求
以队列解决农夫过河问题，用广度优先搜索实现求解的过程。用这个方法来搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。为了实现广度优先搜索，算法中需要使用了一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制0000 ~ 1111)一共16种，所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。
三．测试数据
要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。确定每个角色位置的函数,用整数location表示上述四位二进制描述的状态，用下面的四个函数从上述状态中得到每个角色所在位置的代码。函数返回值为真表示所考察的人或物在河的北岸，否则在南岸。从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。
四．
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
代码如下：/* 用队列解决农夫过河问题的算法*/
#include
#include
#define MAXNUM 20
typedef int DataType;
struct SeqQueue { /* 顺序队列类型定义 */
int f, r;
DataType q[MAXNUM];
};
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 ) {
return paqu->f == paqu->r;
}
/* 在队列中插入一元素x */
void enQueue_seq( PSeqQueue paqu, DataType x ) {
if ( (paqu->r + 1) % MAXNUM == paqu->f )
printf( "Full queue.\n" );
else {
paqu->q[paqu->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->q[paqu->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);
}
/* 若状态安全则返回true */
int safe(int location) {
/* 羊吃白菜 */
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 route[16]; /*记录已考虑的状态路径*/
PSeqQueue moveTo;
/*准备初值*/
moveTo = createEmptyQueue_seq( );
enQueue_seq(moveTo, 0x00);
for (i = 0; i < 16; i++) route[i] = -1;
route[0]=0;
/*开始移动*/
while (!isEmptyQueue_seq(moveTo)&&(route[15] == -1)) {
/*得到现在的状态*/
location = frontQueue_seq(moveTo);
deQueue_seq(moveTo);
for (movers = 1; movers <= 8; movers <<= 1) {
/* 农夫总是在移动，随农夫移动的也只能是在农夫同侧的东西 */
if ((0 != (location & 0x08)) == (0 != (location & movers))) {
newlocation = location^(0x08|movers);
if (safe(newlocation) && (route[newlocation] == -1)) {
route[newlocation] = location;
enQueue_seq(moveTo, newlocation);
}
}
}
}
/* 打印出路径 */
if(route[15] != -1) {
printf("The reverse path is : \n");
for(location = 15; location >= 0; location = route[location]) {
printf("The location is : %d\n",location);
if (location == 0) return;
}
}
else
printf("No solution.\n");
}
int main() {
farmerProblem( );
return 0;
}
截图：
}
浙公网安备 33021202002483