Question

农夫过河问题(java)

(1)确定农夫、狼、羊和白菜位置的功能模块。
(2)确定安全状态的功能模块。
(3)将各个安全状态还原成友好的提示信息的功能模块。

求源代码！非诚勿扰！

Answer 1

这个是偶写的 你可以参考下 写的有点多 你自己优化下吧 之前还不知道农夫过河是啥意思 不过后来知道了 如果有问题的话可以马上说的 你的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;
LinkedList<Goods> beforeCrossing = new LinkedList<Goods>();
LinkedList<Goods> afterCrossing = new LinkedList<Goods>();
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 {
Iterator<Goods> 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;
}

}

Answer 2

java的深度优先搜索不会啊
用C++的，这么详细的解释你应该看得懂的
// 本程序采用广度优先搜索算法求解农夫过河问题
#include<iostream>
#include<queue>
#include<vector>
#include<bitset>
#include<deque>

using namespace std;

// 过河者，共4种对象
enum Wader
{
cabbage, // 默认为0
goat, // 默认为1
wolf, // 默认为2
farmer // 默认为3
};

// 过河状态类型，4bit分别对应4种过河对象
typedef bitset<4> bitvec;

// 判断状态是否安全
bool is_safe( const bitvec&);
// 判断待过河的对象是否与农夫在河的同一侧
bool withFarmer(int, bitvec& );

// 求解得到可行性路径
void findRoute(vector<int> & path)
{
// 待发现的各个状态
queue<int> discovering;
// 过河的初始状态为 0000
discovering.push(0x00);
// 初始状态路径初始化
path[0]=0;
// 只要还有下一个状态可以到达，并且尚未到达最终状态
while (!discovering.empty() && (path[15] == -1))
{
// 获取当前待发现状态
// 隐式类型转换：int -> bitset<4>
bitvec curState = discovering.front();
// 队首元素弹出
discovering.pop();
// 农夫到河对岸，伴随农夫的对象
// 依次尝试狼、白菜、羊
for (int companion = 0; companion <= 3; ++companion)
{
// 随农夫过河的只能是与农夫在同一河边的
if (withFarmer(companion,curState))
{
// 农夫过河后的新状态
bitvec nextState = curState;
// 农夫必定过河
nextState.flip(farmer);
// 如果不是农夫单独过河的情形
if(companion != farmer)
nextState.flip(companion);
// 将状态矢量转换为整型以作为队列元素和路径下标
int nextIndex = nextState.to_ulong();
// 如果新状态是安全的，并且尚未被发现，
// 则新状态进入下一状态队列
if (is_safe(nextState) && ( path[nextIndex] == -1) )
{
// 建立当前状态与下一状态的联系
path[nextIndex] = curState.to_ulong();
// 将新状态入对列
discovering.push(nextIndex);
}//end if
}// end if
}//end for
}// end while
// 状态起点，没有前驱，设为-1；
//path[0] = -1;
}

// 显示实际方案
// 从抽象状态变量转换为具体表达
void displayRoute(const vector<int>& path)
{
// 如果“1111”状态没有前驱
// 则没能够成功到达目的状态
if (path[15] == -1)
{
cout << "该过河问题无解" << endl;
return;
}
// 将整数表示的路径转换为布尔矢量表示的状态路径
// 存储状态路径的容器
deque<bitvec> statePath;
for(int i=15; i >0; i=path[i])
statePath.push_front(i);
// 反向插入，完成路径从初始状态到目的状态的转换
// 隐式类型转换：int -> bitset<4>
// 将初始状态插入
statePath.push_front(0);
// 当前状态变量、下一状态变量与转换变量
bitvec current,next,trans;
bool crossed = true;
int step =1;
for(unsigned int i=1; i < statePath.size(); ++i)
{
current = statePath[i-1];
next = statePath[i];
// 状态变量中的变化位
trans = current ^ next;
// 获取状态发生变化的对象
int wader = -1;
for(int i=0;i<=2;++i)
{
if( trans.test(i))
{
wader = i;
break;
}
}
cout << "步骤" << step++ << "： ";
switch (wader)
{
case goat:
cout << "农夫把羊带" << (crossed ? "到河彼岸" : "回河此岸") << endl;
break;
case cabbage:
cout << "农夫把白菜带" << (crossed ? "到河彼岸" : "回河此岸")<< endl;
break;
case wolf:
cout << "农夫把狼带" << (crossed ? "到河彼岸" : "回河此岸") << endl;
break;
case -1:
cout << "农夫独自" << (crossed ? "到河彼岸" : "回河此岸")<< endl;
break;

}
crossed = !crossed;
}
cout << "Congratulations！过河问题求解成功！" << endl;
}

// 判断状态是否安全
bool is_safe( const bitvec & state)
{
// 羊吃白菜
if ((state[cabbage] == state[goat]) && (state[farmer] != state[goat]) )
return false;
// 狼吃羊
if ((state[goat] == state[wolf]) && (state[farmer] != state[wolf]))
return false;
// 其它状态为安全状态
return true;
}

// 判断待过河的对象是否与农夫在河的同一侧
// state为当前状态
inline bool withFarmer(int wader,bitvec& state)
{
return ( state[farmer] == state[wader] );
}

// 主函数
int main()
{
// 记录已经探测状态及转移路径，初始化为-1
vector<int> path(16, -1);
findRoute(path);
displayRoute(path);
system("pause");
return 0;
}

Answer 3

楼上

LinkedList<Goods> beforeCrossing = new LinkedList<Goods>();
LinkedList<Goods> afterCrossing = new LinkedList<Goods>();
这2句不能通过编译的呀. <> 是什么表示方法? 还是你搞错了?

Answer 4

又是要代码的。。。 都真懒