农夫过河问题的求解
#includeiostream.h
站在用户的角度思考问题，与客户深入沟通，找到容城网站设计与容城网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站设计制作、成都网站制作、企业官网、英文网站、手机端网站、网站推广、主机域名、网站空间、企业邮箱。业务覆盖容城地区。
#includestdio.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"农夫自己回北岸";
}
coutendl;
}
}
else
cout"Nosolution."endl;
}
int main() /*主函数*/
{
farmerProblem();
return 0;
}
农夫过河问题，从JAVA代码看算法
好繁琐...一堆if else...你不觉得很麻烦吗? 我给你提个思路. 你每个Goods object里面都设置一个天敌的list.
Goods g = new Goods("Sheep");
g.setEnemy(Arrays.asList(new String[]{"wolf" }));
Goods g2 = new Goods("Cabbage");
g2.setEnemy(Arrays.asList(new String[]{"Sheep" }));
Goods g3 = new Goods("Wolf");
g3.setEnemy(Arrays.asList(new String[]{}));
这样你的在check isFriendly的时候, 只要检测2个物品的enemyList里面没有自己就可以了.
return !good1.getEnemyList().contains(good2.getName()) !good2.getEnemyList().contains(good1.getName());
java版农夫过河
先把羊带过去
回去
把狼带过去
把羊带回去
把白菜带过去
回去
把羊带过去
农夫过河问题(java)
这个是偶写的 你可以参考下 写的有点多 你自己优化下吧 之前还不知道农夫过河是啥意思 不过后来知道了 如果有问题的话可以马上说的 你的50分偶要定咯！！(可以直接运行)
import java.util.Iterator;
import java.util.LinkedList;
public class AcrossTheRiver {
// 定义三个String对象
public static final String rabbitName = "Rabbit";
public static final String wolfName = "Wolf";
public static final String cabbageName = "Cabbage";
// 判断两个货物之间关系是否友好 写的麻烦了一点= =..
public static boolean isFriendly(Goods goods1, Goods goods2) {
if (goods1 != null) {
if (goods1.getGoodsName().trim().equals(rabbitName)) {
if (goods2 == null) {
return true;
} else {
return false;
}
} else if (goods1.getGoodsName().trim().equals(wolfName)) {
if (goods2 == null || goods2.getGoodsName().trim().equals(cabbageName)) {
return true;
} else {
return false;
}
} else if (goods1.getGoodsName().trim().equals(cabbageName)) {
if (goods2 == null || goods2.getGoodsName().trim().equals(wolfName)) {
return true;
} else {
return false;
}
} else {
return false;
}
} else {
return true;
}
}
// 我就直接写在主方法里了
public static void main(String[] args) {
boolean isSuccess = false;
LinkedListGoods beforeCrossing = new LinkedListGoods();
LinkedListGoods afterCrossing = new LinkedListGoods();
beforeCrossing.add(new Goods(rabbitName));
beforeCrossing.add(new Goods(cabbageName));
beforeCrossing.add(new Goods(wolfName));
while (!isSuccess) {
Goods goods1 = beforeCrossing.getFirst();
System.out.println(goods1.getGoodsName() + " 被取走了");
beforeCrossing.removeFirst();
if (beforeCrossing.isEmpty()) {
afterCrossing.addLast(goods1);
isSuccess = true;
System.out.println("全部移动完毕！");
} else {
IteratorGoods it = beforeCrossing.iterator();
Goods[] beforeCro = new Goods[2];
for (int i = 0; it.hasNext(); i++) {
beforeCro[i] = it.next();
System.out.println(beforeCro[i].getGoodsName() + " 留了下来");
}
if (isFriendly(beforeCro[0], beforeCro[1])) {
if (afterCrossing.isEmpty()) {
afterCrossing.addLast(goods1);
System.out.println(goods1.getGoodsName() + " 被成功的放到了对岸");
} else {
Goods goods2 = afterCrossing.getFirst();
if (isFriendly(goods1, goods2)) {
afterCrossing.addLast(goods1);
System.out.println(goods1.getGoodsName() + " 被成功的放到了对岸");
} else {
beforeCrossing.addLast(goods2);
afterCrossing.removeFirst();
System.out.println(goods1.getGoodsName() + " 与 "
+ goods2.getGoodsName() + "并不和睦 于是把 " + goods2.getGoodsName()
+ "带了回来 并将 " + goods1.getGoodsName() + " 留了下来");
}
}
} else {
beforeCrossing.addLast(goods1);
System.out.println("很可惜 留下来的两个东西并不和睦 于是 " + goods1.getGoodsName()
+ " 又被放了回去");
}
}
}
}
}
// 货物类
class Goods {
// 货物名称
private String goodsName;
// 默认构造方法
public Goods(String goodsName) {
this.goodsName = goodsName;
}
// 获得货物名称
public String getGoodsName() {
return goodsName;
}
}
网页名称：农夫过河java代码 农夫过河问题共有几种方案
网页网址：
http://cdkjz.cn/article/ddiciec.html
