Question

农夫过河问题的求解

[问题描述]
一个农夫带着—只狼、一只羊和—棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和—件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。
[数据结构设计]

要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用4位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。
现在问题变成：从初的状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111（全部到达河的北岸）为最终目标，并且在序列中的每一个状态都可以从前一状态到达。实现上述求解的搜索过程可以采用两种不同的策略：一种广度优先搜索，另一种深度优先搜索。这里介绍在广度优先搜索方法中采用的数据结构设计。
[功能(函数)设计]
(1)确定农夫、狼、羊和白菜位置的功能模块。
用整数locate表示上—述4位二进制描述的状态，由于采用4位二进制的形式表示农夫、狼、白菜和羊，所以要使用位操作的“与”操作来考察每个角色所在位置的代码是0还是1。函数返回值为真表示所考察的角色在河的北岸，否则在北岸。例如某个状态和1000做“与”操作后所得结果为0，则说明农夫的位置上的二进制数为0，即农夫在南岸，如果所得结果为1，则说明农夫的位置上的二进制数为1，即农夫在北岸。狼、羊和白菜的处理办法以此类推。
(2)确定安全状态的功能模块。
此功能模块通过位置分布的代码来判断当前状态是否安全。若状态安全返回1，状态不安全返回0。
(3)将各个安全状态还原成友好的提示信息的功能模块。
由于程序中route表中最终存放的是整型的数据，如果原样输出不利于最终用户理解问题的解决方案，所以要把各个整数按照4位二进制的各个位置上的0、1代码所表示的含义输出成容易理解的文字。
[界面设计]
如果能力和时间允许，可以使用动画设计将运送的过程演示出来。 —般情况下可以使用最终的状态表描述出来就可以了。
[运行与测试]
使用状态表，程序应在屏幕上得到如表10-3所示的结果。
表10-3 测试结果
步骤 状态
南岸 北岸
0 农夫 狼 羊 白菜
1 狼 白菜 农夫 羊
2 狼 农夫 白菜 羊
3 农夫 狼 羊 白菜
4 羊 农夫 狼 白菜
5 农夫 羊 狼 白菜
6 农夫 狼 羊 白菜
广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步所有可能的状态都列举出来，放在队列中，再顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……，由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各种情况的处理。这样，具体算法中就需要用一个整数队列moveTo，它的每个元素表示—个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及己被发现的能够到达当前这个状态的路径。由于在这个问题的解决过程中需要列举的所有状态(二进制0000到1111)一共16种，所以可以构造一个包含16个元素的整数顺序表来实现。顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，把这个顺序表叫做route。route的每个分量初始值为-1。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后可以利用route顺序表元素的值建立起正确的状态路径。于是得到农夫过河问题的广度优先算法。

谁写个这C++源程序给我吧，急用！！

Answer 1

#include<iostream.h>
#include<stdio.h>
#defineMAXNUM 20
typedefstruct //顺序队列类型定义
{
int f, r; //f表示头，r 表示尾
int q[MAXNUM];//顺序队
}SeqQueue,*PSeqQueue;

PSeqQueuecreateEmptyQueue_seq( ) //创建队列
{
PSeqQueue paqu = new SeqQueue;
if(paqu == NULL)
cout<<"Out of space!"<<endl;
else
paqu->f=paqu->r=0;
return (paqu);
}
intisEmptyQueue_seq( PSeqQueue paqu ) //判断paqu 所指是否是空队列
{
return paqu->f==paqu->r;
}
voidenQueue_seq(PSeqQueue paqu,int x) //在队列中插入一元素 x
{
if ((paqu->r+1)%MAXNUM==paqu->f)
cout<<"队列已满."<<endl;
else
{
paqu->q[paqu->r]=x;
paqu->r=(paqu->r+1)%MAXNUM;
}
}
void deQueue_seq(PSeqQueue paqu) //删除队列头部元素
{
if( paqu->f==paqu->r)
cout<<"队列为空"<<endl;
else
paqu->f=(paqu->f+1)%MAXNUM;
}
intfrontQueue_seq( PSeqQueue paqu ) //对非空队列,求队列头部元素
{
return (paqu->q[paqu->f]);
}
intfarmer(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置
{
return 0 != (location & 0x08);
}
intwolf(int location) //判断狼位置
{
return 0 != (location & 0x04);
}
intcabbage(int location) //判断白菜位置
{
return 0 != (location & 0x02);
}
intgoat(int location) //判断羊的位置
{
return 0 !=(location & 0x01);
}
intsafe(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 route[16]; //记录已考虑的状态路径
int print[MAXNUM];
PSeqQueue moveTo;
moveTo = createEmptyQueue_seq( );//新的队列判断路径
enQueue_seq(moveTo, 0x00); //初始状态为0
for (i = 0; i < 16; i++)
route[i] = -1; //-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)
{
cout<<"过河步骤是 : "<<endl;
i=0;
for(location = 15; location >= 0; location= route[location])
{
print[i]=location;
i++;
if (location == 0)
break;
}
int num=i-1;
int temp[20][4];
int j;
for(i=num;i>=0;i--)
{
for(j=3;j>=0;j--)
{
temp[num-i][j]=print[i]%2;
print[i]/=2;
temp[0][j]=0;
temp[num+1][j]=1;
}
}
for(i=1;i<=num;i++)
{
cout<<"\t\t\tNO ."<<i<<"\t";
if(i%2==1)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"农夫带羊过南岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"农夫带白菜过南岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"农夫带狼过南岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"农夫自己过南岸";
}
else if(i%2==0)
{
if(temp[i][3]!=temp[i-1][3])
cout<<"农夫带羊回北岸";
if(temp[i][2]!=temp[i-1][2])
cout<<"农夫带白菜回北岸";
if(temp[i][1]!=temp[i-1][1])
cout<<"农夫带狼回北岸";
if(temp[i][3]==temp[i-1][3]&&temp[i][2]==temp[i-1][2]&&temp[i][1]==temp[i-1][1])
cout<<"农夫自己回北岸";
}
cout<<endl;
}
}

else
cout<<"Nosolution."<<endl;
}
int main() /*主函数*/
{
farmerProblem();

return 0;
}

Answer 2

njkjknjknjknjknjknkjnkjnj

Answer 3

看的我一头雾水 搞不懂