- 浏览: 351139 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
无红墙:
另一种修改,请参考:https://github.com/ta ...
Dubbo不能优雅停机,导致停止服务的时候,业务掉单 -
fish_no7:
if (handler instanceof WrappedC ...
Dubbo不能优雅停机,导致停止服务的时候,业务掉单 -
frankfan915:
lizhou828 写道怎么解决?设置NetTimeoutFo ...
Communications link failure错误分析 -
lizhou828:
怎么解决?
Communications link failure错误分析 -
frankfan915:
ileson 写道 解决办法sh设置NetTimeoutFo ...
Communications link failure错误分析
面试的时候,被问到过河算法,所以写了一下,
此算法的特点:将类型安装二进制存储,如狼 1,人 2,羊 4,草 8.
比较的时候按位操作,在算法2中可以扩展一辆船容量N个人
算法1:
import java.util.ArrayList;
public class PassRiver {
private enum Type {
wolf(1, "wolf"), human(1 << 1, "human"), sheep(1 << 2, "sheep"), grass(
1 << 3, "grass");
private long typeid;
public long getTypeid() {
return typeid;
}
public void setTypeid(long typeid) {
this.typeid = typeid;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
private String name;
Type(long typeid, String name) {
this.typeid = typeid;
this.name = name;
}
public static String getNameById(long id) {
for (int i = 0; i < types.length; i++) {
if (types[i].getTypeid() == id)
return types[i].getName();
}
return null;
}
}
private enum Side {
left, right;
}
private class State {
private long rightSideState;
public long getRightSideState() {
return rightSideState;
}
public long getLeftSideState() {
return leftSideState;
}
public Side getSide() {
return side;
}
private long leftSideState;
private Side side;
public State(long leftSideState, long rightSideState, Side side) {
this.rightSideState = rightSideState;
this.leftSideState = leftSideState;
this.side = side;
}
public int compare(State state) {
if (this.rightSideState > state.rightSideState) {
return 1;
} else if (this.rightSideState < state.rightSideState) {
return -1;
} else if (this.leftSideState > state.leftSideState) {
return 1;
} else if (this.leftSideState < state.leftSideState) {
return -1;
} else
return this.side.compareTo(state.getSide());
}
}
private Type[] driver;
private Long[] animalCanNotExists;
private Long[] animalCanExists;
private long successState;
private static final Type[] types = Type.values();;
ArrayList<State> happendedStates; // used the save the state have happen
private StringBuilder steps;
public StringBuilder getSteps() {
return steps;
}
private final static String MOVE_FROM_LEFT_TO_BOAT = "Move animal from left side to boat: ";
private final static String MOVE_FROM_RIGHT_TO_BOAT = "Move animal from right side to boat: ";
private final static String DRIVER_TO_ANOTHER_SIDE = "Driver to another side: ";
private final static String REMOVE_ALL_BOAT_ANIMALS_TO_LEFT = "Remove all boat animals to left side: ";
private final static String REMOVE_ALL_BOAT_ANIMALS_TO_RIGHT = "Remove all boat animals to right side: ";
private final static String REMOVE_ANIMALS_TO_LEFT = "Remove animal from boat to left side: ";
private final static String REMOVE_ANIMALS_TO_RIGHT = "Remove animal from boat to right side: ";
private final static String LEFT_SIDE_ANIMAL = "Left side animal: ";
private final static String RIGHT_SIDE_ANIMAL = "Right side animal: ";
private final static String BOAT_ANIMAL = "Boat animal: ";
PassRiver(long successState) {
driver = new Type[] { Type.human };
animalCanNotExists = new Long[] {
Type.wolf.getTypeid() | Type.sheep.getTypeid(),
Type.sheep.getTypeid() | Type.grass.getTypeid() };
animalCanExists = new Long[] { Type.human.getTypeid() };
this.successState = successState;
happendedStates = new ArrayList<State>(); // used the save the state
// have happen
steps = new StringBuilder();
}
public boolean pass(long leftSideState, long boatSideState,
long rightSideState, Side side, int sizeOfBoatAnimals) {
if (rightSideState == successState)
return true;
addHappenedState(new State(leftSideState, rightSideState, side));
long leftState = leftSideState;
long rightState = rightSideState;
String step;
// have no animal in the boat
if (sizeOfBoatAnimals == 0) {
return moveToBoat(leftSideState, boatSideState, rightSideState,
side, sizeOfBoatAnimals);
} else if (sizeOfBoatAnimals == 1) {
if (driveBoatToAnotherSide(leftSideState, boatSideState,
rightSideState, side, sizeOfBoatAnimals)) {
return true;
}
return moveToBoat(leftSideState, boatSideState, rightSideState,
side, sizeOfBoatAnimals);
} else if (sizeOfBoatAnimals == 2) {
if (driveBoatToAnotherSide(leftSideState, boatSideState,
rightSideState, side, sizeOfBoatAnimals)) {
return true;
}
// remove all animals
if (side == Side.left) {
leftState = leftSideState | boatSideState;
step = REMOVE_ALL_BOAT_ANIMALS_TO_LEFT;
} else {
rightState = rightSideState | boatSideState;
step = REMOVE_ALL_BOAT_ANIMALS_TO_RIGHT;
}
if (passWithCheck(leftState, 0, rightState, side, 0)) {
logSteps(step + "\n");
return true;
}
// remove not driver
long animalNotDriver = boatSideState;
for (int i = 0; i < driver.length; i++) {
animalNotDriver = animalNotDriver & (~driver[i].getTypeid());
}
boatSideState = removeAnimal(boatSideState, animalNotDriver);
if (side == Side.left) {
leftState = leftSideState | animalNotDriver;
step = REMOVE_ANIMALS_TO_LEFT;
} else {
rightState = rightSideState | animalNotDriver;
step = REMOVE_ANIMALS_TO_RIGHT;
}
if (passWithCheck(leftState, boatSideState, rightState, side, 1)) {
logSteps(step + Type.getNameById(animalNotDriver) + "\n");
return true;
}
}
return false;
}
private boolean driveBoatToAnotherSide(long leftSideState,
long boatSideState, long rightSideState, Side side,
int sizeOfBoatAnimals) {
if (haveDriver(boatSideState)) {
if (passWithCheck(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left),
sizeOfBoatAnimals)) {
logSteps(DRIVER_TO_ANOTHER_SIDE + "\n");
return true;
}
}
return false;
}
private boolean moveToBoat(long leftSideState, long boatSideState,
long rightSideState, Side side, int sizeOfBoatAnimals) {
long leftState = leftSideState;
long rightState = rightSideState;
String step;
for (int i = 0; i < types.length; i++) {
if (side == Side.left) {
if ((types[i].getTypeid() & leftSideState) != 0) {
leftState = removeAnimal(leftSideState, types[i]
.getTypeid());
step = MOVE_FROM_LEFT_TO_BOAT;
} else {
continue;
}
} else {
if ((types[i].getTypeid() & rightSideState) != 0) {
rightState = removeAnimal(rightSideState, types[i]
.getTypeid());
step = MOVE_FROM_RIGHT_TO_BOAT;
} else {
continue;
}
}
if (passWithCheck(leftState, boatSideState | types[i].getTypeid(),
rightState, side, sizeOfBoatAnimals + 1)) {
logSteps(step + Type.getNameById(types[i].getTypeid()) + "\n");
return true;
}
}
return false;
}
private boolean haveDriver(long state) {
for (int i = 0; i < driver.length; i++) {
if ((driver[i].getTypeid() & state) != 0)
return true;
}
return false;
}
private boolean passWithCheck(long leftState, long boatState,
long rightState, Side side, int sizeOfBoatAnimals) {
if (checkCanExist(leftState) == false
|| checkCanExist(rightState) == false
|| checkCanExist(boatState) == false)
return false;
if (isHappenedState(new State(leftState, rightState, side)) == true)
return false;
if (pass(leftState, boatState, rightState, side, sizeOfBoatAnimals)) {
StringBuilder sbTemp = new StringBuilder();
// sbTemp.append("***************************************************\n");
sbTemp
.append(LEFT_SIDE_ANIMAL)
.append(getAnimalNameList(leftState))
.append(RIGHT_SIDE_ANIMAL)
.append(getAnimalNameList(rightState))
.append(BOAT_ANIMAL)
.append(getAnimalNameList(boatState))
.append("Side:")
.append((side == Side.left ? "left" : "right"))
.append("\n")
.append("***************************************************\n");
logSteps(sbTemp.toString());
return true;
}
return false;
}
private boolean isHappenedState(State state) {
int index = findIndex(state);
if (index != -1 && happendedStates.get(index).compare(state) == 0)
return true;
return false;
}
private void addHappenedState(State state) {
int index = findIndex(state);
happendedStates.add(index + 1, state);
}
private StringBuilder getAnimalNameList(long state) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < types.length; i++) {
if ((types[i].getTypeid() & state) != 0) {
s.append(types[i].getName()).append(",");
}
}
s.append("\n");
return s;
}
private int findIndex(State state) {
// user binary search
int left = 0;
int right = happendedStates.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int temp = happendedStates.get(mid).compare(state);
if (temp < 0) {
left = mid + 1;
} else if (temp > 0) {
right = mid - 1;
} else {
return mid;
}
}
return right;
}
private boolean checkCanExist(long state) {
for (int i = 0; i < animalCanExists.length; i++) {
if ((state & animalCanExists[i]) != 0)
return true;
}
for (int i = 0; i < animalCanNotExists.length; i++) {
if ((state & animalCanNotExists[i]) == animalCanNotExists[i])
return false;
}
return true;
}
private long removeAnimal(long animalList, long animalNeedRemove) {
return (~animalNeedRemove) & animalList;
}
private void logSteps(String s) {
this.steps.insert(0, s);
}
public static void main(String[] args) {
long startState = Type.wolf.getTypeid() | Type.sheep.getTypeid()
| Type.human.getTypeid() | Type.grass.getTypeid();
PassRiver pr = new PassRiver(startState);
pr.pass(startState, 0, 0, Side.left, 0);
System.out.print(pr.getSteps());
}
}
算法2:
import java.util.ArrayList;
import java.util.List;
public class PassRiver2 {
private enum Type {
wolf(1, "wolf"), human(1 << 1, "human"), sheep(1 << 2, "sheep"), grass(
1 << 3, "grass");
private long typeid;
public long getTypeid() {
return typeid;
}
public void setTypeid(long typeid) {
this.typeid = typeid;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
private String name;
Type(long typeid, String name) {
this.typeid = typeid;
this.name = name;
}
public static String getNameById(long id) {
for (int i = 0; i < types.length; i++) {
if (types[i].getTypeid() == id)
return types[i].getName();
}
return null;
}
}
private enum Side {
left, right;
}
private class State {
private long rightSideState;
public long getRightSideState() {
return rightSideState;
}
public long getLeftSideState() {
return leftSideState;
}
public Side getSide() {
return side;
}
private long leftSideState;
private Side side;
public State(long leftSideState, long rightSideState, Side side) {
this.rightSideState = rightSideState;
this.leftSideState = leftSideState;
this.side = side;
}
public int compare(State state) {
if (this.rightSideState > state.rightSideState) {
return 1;
} else if (this.rightSideState < state.rightSideState) {
return -1;
} else if (this.leftSideState > state.leftSideState) {
return 1;
} else if (this.leftSideState < state.leftSideState) {
return -1;
} else
return this.side.compareTo(state.getSide());
}
}
private Type[] driver;
private Long[] animalCanNotExists;
private Long[] animalCanExists;
private long successState;
private long maxSizeOfBoatAnimal = 2;
private static final Type[] types = Type.values();;
ArrayList<State> happendedStates; // used the save the state have happen
private StringBuilder steps;
public StringBuilder getSteps() {
return steps;
}
private final static String MOVE_FROM_LEFT_TO_BOAT = "Move animal from left side to boat: ";
private final static String MOVE_FROM_RIGHT_TO_BOAT = "Move animal from right side to boat: ";
private final static String DRIVER_TO_ANOTHER_SIDE = "Driver to another side: ";
private final static String REMOVE_ANIMALS_TO_LEFT = "Remove animal from boat to left side: ";
private final static String REMOVE_ANIMALS_TO_RIGHT = "Remove animal from boat to right side: ";
private final static String LEFT_SIDE_ANIMAL = "Left side animal: ";
private final static String RIGHT_SIDE_ANIMAL = "Right side animal: ";
private final static String BOAT_ANIMAL = "Boat animal: ";
PassRiver2(long successState) {
driver = new Type[] { Type.human };
animalCanNotExists = new Long[] {
Type.wolf.getTypeid() | Type.sheep.getTypeid(),
Type.sheep.getTypeid() | Type.grass.getTypeid() };
animalCanExists = new Long[] { Type.human.getTypeid() };
this.successState = successState;
happendedStates = new ArrayList<State>(); // used the save the state
// have happen
steps = new StringBuilder();
}
public boolean pass(long leftSideState, long boatSideState,
long rightSideState, Side side) {
if (rightSideState == successState)
return true;
if (checkCanExist(leftSideState) == false
|| checkCanExist(boatSideState) == false
|| checkCanExist(rightSideState) == false)
return false;
if (isHappenedState(new State(leftSideState, rightSideState, side)) == true)
return false;
addHappenedState(new State(leftSideState, rightSideState, side));
List<Type> boatAnimals = getAnimalList(boatSideState);
//boat is on the left side
if(side == Side.left){
//move animal from left side to boat
if(boatAnimals.size() < maxSizeOfBoatAnimal){
List<Type> list = getAnimalList(leftSideState);
for(int i= 0 ; i < list.size() ; i++){
if (pass(removeAnimal(leftSideState, list.get(i).getTypeid()), boatSideState |list.get(i).getTypeid(),
rightSideState, side)) {
logSteps(removeAnimal(leftSideState, list.get(i).getTypeid()), boatSideState |list.get(i).getTypeid(),
rightSideState, side, MOVE_FROM_LEFT_TO_BOAT + Type.getNameById(list.get(i).getTypeid()) + "\n");
return true;
}
}
}
//move animal from boat to left side
for(int i= 0 ; i < boatAnimals.size() ; i++){
if (pass(leftSideState |boatAnimals.get(i).getTypeid(),removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState, side)) {
logSteps(leftSideState |boatAnimals.get(i).getTypeid(),removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState, side, REMOVE_ANIMALS_TO_LEFT + Type.getNameById(boatAnimals.get(i).getTypeid()) + "\n");
return true;
}
}
//boat is on the right side
}else{
//move animal from right side to boat
if(boatAnimals.size() < maxSizeOfBoatAnimal){
List<Type> list = getAnimalList(rightSideState);
for(int i= 0 ; i < list.size() ; i++){
if (pass(leftSideState , boatSideState |list.get(i).getTypeid(),
removeAnimal(rightSideState, list.get(i).getTypeid()), side)) {
logSteps(leftSideState , boatSideState |list.get(i).getTypeid(),
removeAnimal(rightSideState, list.get(i).getTypeid()), side, MOVE_FROM_RIGHT_TO_BOAT + Type.getNameById(list.get(i).getTypeid()) + "\n");
return true;
}
}
}
//move animal from boat to right side
for(int i= 0 ; i < boatAnimals.size() ; i++){
if (pass(leftSideState ,removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState |boatAnimals.get(i).getTypeid(), side)) {
logSteps(leftSideState ,removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState |boatAnimals.get(i).getTypeid(), side, REMOVE_ANIMALS_TO_RIGHT + Type.getNameById(boatAnimals.get(i).getTypeid()) + "\n");
return true;
}
}
}
//drive to another side
if (haveDriver(boatSideState)) {
if (pass(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left) )) {
logSteps(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left),DRIVER_TO_ANOTHER_SIDE + "\n");
return true;
}
}
return false;
}
private boolean haveDriver(long state) {
for (int i = 0; i < driver.length; i++) {
if ((driver[i].getTypeid() & state) != 0)
return true;
}
return false;
}
private boolean isHappenedState(State state) {
int index = findIndex(state);
if (index != -1 && happendedStates.get(index).compare(state) == 0)
return true;
return false;
}
private void addHappenedState(State state) {
int index = findIndex(state);
happendedStates.add(index + 1, state);
}
private StringBuilder getAnimalNameList(long state) {
StringBuilder s = new StringBuilder();
List<Type> list = getAnimalList(state);
for (int i = 0; i < list.size(); i++) {
s.append(list.get(i).getName()).append(",");
}
s.append("\n");
return s;
}
public List<Type> getAnimalList(long state){
ArrayList<Type> list = new ArrayList<Type>();
for (int i = 0; i < types.length; i++) {
if ((types[i].getTypeid() & state) != 0) {
list.add(types[i]);
}
}
return list;
}
private int findIndex(State state) {
// user binary search
int left = 0;
int right = happendedStates.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int temp = happendedStates.get(mid).compare(state);
if (temp < 0) {
left = mid + 1;
} else if (temp > 0) {
right = mid - 1;
} else {
return mid;
}
}
return right;
}
private boolean checkCanExist(long state) {
for (int i = 0; i < animalCanExists.length; i++) {
if ((state & animalCanExists[i]) != 0)
return true;
}
for (int i = 0; i < animalCanNotExists.length; i++) {
if ((state & animalCanNotExists[i]) == animalCanNotExists[i])
return false;
}
return true;
}
private long removeAnimal(long animalList, long animalNeedRemove) {
return (~animalNeedRemove) & animalList;
}
private void logSteps(long leftState , long boatState,long rightState,Side side, String msg) {
StringBuilder sbTemp = new StringBuilder();
// sbTemp.append("***************************************************\n");
sbTemp.append(msg)
.append(LEFT_SIDE_ANIMAL)
.append(getAnimalNameList(leftState))
.append(RIGHT_SIDE_ANIMAL)
.append(getAnimalNameList(rightState))
.append(BOAT_ANIMAL)
.append(getAnimalNameList(boatState))
.append("Side:")
.append((side == Side.left ? "left" : "right"))
.append("\n")
.append("***************************************************\n");
this.steps.insert(0, sbTemp);
}
public static void main(String[] args) {
long startState = Type.wolf.getTypeid() | Type.sheep.getTypeid()
| Type.human.getTypeid() | Type.grass.getTypeid();
PassRiver2 pr = new PassRiver2(startState);
pr.pass(startState, 0, 0, Side.left );
System.out.print(pr.getSteps());
}
}
此算法的特点:将类型安装二进制存储,如狼 1,人 2,羊 4,草 8.
比较的时候按位操作,在算法2中可以扩展一辆船容量N个人
算法1:
import java.util.ArrayList;
public class PassRiver {
private enum Type {
wolf(1, "wolf"), human(1 << 1, "human"), sheep(1 << 2, "sheep"), grass(
1 << 3, "grass");
private long typeid;
public long getTypeid() {
return typeid;
}
public void setTypeid(long typeid) {
this.typeid = typeid;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
private String name;
Type(long typeid, String name) {
this.typeid = typeid;
this.name = name;
}
public static String getNameById(long id) {
for (int i = 0; i < types.length; i++) {
if (types[i].getTypeid() == id)
return types[i].getName();
}
return null;
}
}
private enum Side {
left, right;
}
private class State {
private long rightSideState;
public long getRightSideState() {
return rightSideState;
}
public long getLeftSideState() {
return leftSideState;
}
public Side getSide() {
return side;
}
private long leftSideState;
private Side side;
public State(long leftSideState, long rightSideState, Side side) {
this.rightSideState = rightSideState;
this.leftSideState = leftSideState;
this.side = side;
}
public int compare(State state) {
if (this.rightSideState > state.rightSideState) {
return 1;
} else if (this.rightSideState < state.rightSideState) {
return -1;
} else if (this.leftSideState > state.leftSideState) {
return 1;
} else if (this.leftSideState < state.leftSideState) {
return -1;
} else
return this.side.compareTo(state.getSide());
}
}
private Type[] driver;
private Long[] animalCanNotExists;
private Long[] animalCanExists;
private long successState;
private static final Type[] types = Type.values();;
ArrayList<State> happendedStates; // used the save the state have happen
private StringBuilder steps;
public StringBuilder getSteps() {
return steps;
}
private final static String MOVE_FROM_LEFT_TO_BOAT = "Move animal from left side to boat: ";
private final static String MOVE_FROM_RIGHT_TO_BOAT = "Move animal from right side to boat: ";
private final static String DRIVER_TO_ANOTHER_SIDE = "Driver to another side: ";
private final static String REMOVE_ALL_BOAT_ANIMALS_TO_LEFT = "Remove all boat animals to left side: ";
private final static String REMOVE_ALL_BOAT_ANIMALS_TO_RIGHT = "Remove all boat animals to right side: ";
private final static String REMOVE_ANIMALS_TO_LEFT = "Remove animal from boat to left side: ";
private final static String REMOVE_ANIMALS_TO_RIGHT = "Remove animal from boat to right side: ";
private final static String LEFT_SIDE_ANIMAL = "Left side animal: ";
private final static String RIGHT_SIDE_ANIMAL = "Right side animal: ";
private final static String BOAT_ANIMAL = "Boat animal: ";
PassRiver(long successState) {
driver = new Type[] { Type.human };
animalCanNotExists = new Long[] {
Type.wolf.getTypeid() | Type.sheep.getTypeid(),
Type.sheep.getTypeid() | Type.grass.getTypeid() };
animalCanExists = new Long[] { Type.human.getTypeid() };
this.successState = successState;
happendedStates = new ArrayList<State>(); // used the save the state
// have happen
steps = new StringBuilder();
}
public boolean pass(long leftSideState, long boatSideState,
long rightSideState, Side side, int sizeOfBoatAnimals) {
if (rightSideState == successState)
return true;
addHappenedState(new State(leftSideState, rightSideState, side));
long leftState = leftSideState;
long rightState = rightSideState;
String step;
// have no animal in the boat
if (sizeOfBoatAnimals == 0) {
return moveToBoat(leftSideState, boatSideState, rightSideState,
side, sizeOfBoatAnimals);
} else if (sizeOfBoatAnimals == 1) {
if (driveBoatToAnotherSide(leftSideState, boatSideState,
rightSideState, side, sizeOfBoatAnimals)) {
return true;
}
return moveToBoat(leftSideState, boatSideState, rightSideState,
side, sizeOfBoatAnimals);
} else if (sizeOfBoatAnimals == 2) {
if (driveBoatToAnotherSide(leftSideState, boatSideState,
rightSideState, side, sizeOfBoatAnimals)) {
return true;
}
// remove all animals
if (side == Side.left) {
leftState = leftSideState | boatSideState;
step = REMOVE_ALL_BOAT_ANIMALS_TO_LEFT;
} else {
rightState = rightSideState | boatSideState;
step = REMOVE_ALL_BOAT_ANIMALS_TO_RIGHT;
}
if (passWithCheck(leftState, 0, rightState, side, 0)) {
logSteps(step + "\n");
return true;
}
// remove not driver
long animalNotDriver = boatSideState;
for (int i = 0; i < driver.length; i++) {
animalNotDriver = animalNotDriver & (~driver[i].getTypeid());
}
boatSideState = removeAnimal(boatSideState, animalNotDriver);
if (side == Side.left) {
leftState = leftSideState | animalNotDriver;
step = REMOVE_ANIMALS_TO_LEFT;
} else {
rightState = rightSideState | animalNotDriver;
step = REMOVE_ANIMALS_TO_RIGHT;
}
if (passWithCheck(leftState, boatSideState, rightState, side, 1)) {
logSteps(step + Type.getNameById(animalNotDriver) + "\n");
return true;
}
}
return false;
}
private boolean driveBoatToAnotherSide(long leftSideState,
long boatSideState, long rightSideState, Side side,
int sizeOfBoatAnimals) {
if (haveDriver(boatSideState)) {
if (passWithCheck(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left),
sizeOfBoatAnimals)) {
logSteps(DRIVER_TO_ANOTHER_SIDE + "\n");
return true;
}
}
return false;
}
private boolean moveToBoat(long leftSideState, long boatSideState,
long rightSideState, Side side, int sizeOfBoatAnimals) {
long leftState = leftSideState;
long rightState = rightSideState;
String step;
for (int i = 0; i < types.length; i++) {
if (side == Side.left) {
if ((types[i].getTypeid() & leftSideState) != 0) {
leftState = removeAnimal(leftSideState, types[i]
.getTypeid());
step = MOVE_FROM_LEFT_TO_BOAT;
} else {
continue;
}
} else {
if ((types[i].getTypeid() & rightSideState) != 0) {
rightState = removeAnimal(rightSideState, types[i]
.getTypeid());
step = MOVE_FROM_RIGHT_TO_BOAT;
} else {
continue;
}
}
if (passWithCheck(leftState, boatSideState | types[i].getTypeid(),
rightState, side, sizeOfBoatAnimals + 1)) {
logSteps(step + Type.getNameById(types[i].getTypeid()) + "\n");
return true;
}
}
return false;
}
private boolean haveDriver(long state) {
for (int i = 0; i < driver.length; i++) {
if ((driver[i].getTypeid() & state) != 0)
return true;
}
return false;
}
private boolean passWithCheck(long leftState, long boatState,
long rightState, Side side, int sizeOfBoatAnimals) {
if (checkCanExist(leftState) == false
|| checkCanExist(rightState) == false
|| checkCanExist(boatState) == false)
return false;
if (isHappenedState(new State(leftState, rightState, side)) == true)
return false;
if (pass(leftState, boatState, rightState, side, sizeOfBoatAnimals)) {
StringBuilder sbTemp = new StringBuilder();
// sbTemp.append("***************************************************\n");
sbTemp
.append(LEFT_SIDE_ANIMAL)
.append(getAnimalNameList(leftState))
.append(RIGHT_SIDE_ANIMAL)
.append(getAnimalNameList(rightState))
.append(BOAT_ANIMAL)
.append(getAnimalNameList(boatState))
.append("Side:")
.append((side == Side.left ? "left" : "right"))
.append("\n")
.append("***************************************************\n");
logSteps(sbTemp.toString());
return true;
}
return false;
}
private boolean isHappenedState(State state) {
int index = findIndex(state);
if (index != -1 && happendedStates.get(index).compare(state) == 0)
return true;
return false;
}
private void addHappenedState(State state) {
int index = findIndex(state);
happendedStates.add(index + 1, state);
}
private StringBuilder getAnimalNameList(long state) {
StringBuilder s = new StringBuilder();
for (int i = 0; i < types.length; i++) {
if ((types[i].getTypeid() & state) != 0) {
s.append(types[i].getName()).append(",");
}
}
s.append("\n");
return s;
}
private int findIndex(State state) {
// user binary search
int left = 0;
int right = happendedStates.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int temp = happendedStates.get(mid).compare(state);
if (temp < 0) {
left = mid + 1;
} else if (temp > 0) {
right = mid - 1;
} else {
return mid;
}
}
return right;
}
private boolean checkCanExist(long state) {
for (int i = 0; i < animalCanExists.length; i++) {
if ((state & animalCanExists[i]) != 0)
return true;
}
for (int i = 0; i < animalCanNotExists.length; i++) {
if ((state & animalCanNotExists[i]) == animalCanNotExists[i])
return false;
}
return true;
}
private long removeAnimal(long animalList, long animalNeedRemove) {
return (~animalNeedRemove) & animalList;
}
private void logSteps(String s) {
this.steps.insert(0, s);
}
public static void main(String[] args) {
long startState = Type.wolf.getTypeid() | Type.sheep.getTypeid()
| Type.human.getTypeid() | Type.grass.getTypeid();
PassRiver pr = new PassRiver(startState);
pr.pass(startState, 0, 0, Side.left, 0);
System.out.print(pr.getSteps());
}
}
算法2:
import java.util.ArrayList;
import java.util.List;
public class PassRiver2 {
private enum Type {
wolf(1, "wolf"), human(1 << 1, "human"), sheep(1 << 2, "sheep"), grass(
1 << 3, "grass");
private long typeid;
public long getTypeid() {
return typeid;
}
public void setTypeid(long typeid) {
this.typeid = typeid;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
private String name;
Type(long typeid, String name) {
this.typeid = typeid;
this.name = name;
}
public static String getNameById(long id) {
for (int i = 0; i < types.length; i++) {
if (types[i].getTypeid() == id)
return types[i].getName();
}
return null;
}
}
private enum Side {
left, right;
}
private class State {
private long rightSideState;
public long getRightSideState() {
return rightSideState;
}
public long getLeftSideState() {
return leftSideState;
}
public Side getSide() {
return side;
}
private long leftSideState;
private Side side;
public State(long leftSideState, long rightSideState, Side side) {
this.rightSideState = rightSideState;
this.leftSideState = leftSideState;
this.side = side;
}
public int compare(State state) {
if (this.rightSideState > state.rightSideState) {
return 1;
} else if (this.rightSideState < state.rightSideState) {
return -1;
} else if (this.leftSideState > state.leftSideState) {
return 1;
} else if (this.leftSideState < state.leftSideState) {
return -1;
} else
return this.side.compareTo(state.getSide());
}
}
private Type[] driver;
private Long[] animalCanNotExists;
private Long[] animalCanExists;
private long successState;
private long maxSizeOfBoatAnimal = 2;
private static final Type[] types = Type.values();;
ArrayList<State> happendedStates; // used the save the state have happen
private StringBuilder steps;
public StringBuilder getSteps() {
return steps;
}
private final static String MOVE_FROM_LEFT_TO_BOAT = "Move animal from left side to boat: ";
private final static String MOVE_FROM_RIGHT_TO_BOAT = "Move animal from right side to boat: ";
private final static String DRIVER_TO_ANOTHER_SIDE = "Driver to another side: ";
private final static String REMOVE_ANIMALS_TO_LEFT = "Remove animal from boat to left side: ";
private final static String REMOVE_ANIMALS_TO_RIGHT = "Remove animal from boat to right side: ";
private final static String LEFT_SIDE_ANIMAL = "Left side animal: ";
private final static String RIGHT_SIDE_ANIMAL = "Right side animal: ";
private final static String BOAT_ANIMAL = "Boat animal: ";
PassRiver2(long successState) {
driver = new Type[] { Type.human };
animalCanNotExists = new Long[] {
Type.wolf.getTypeid() | Type.sheep.getTypeid(),
Type.sheep.getTypeid() | Type.grass.getTypeid() };
animalCanExists = new Long[] { Type.human.getTypeid() };
this.successState = successState;
happendedStates = new ArrayList<State>(); // used the save the state
// have happen
steps = new StringBuilder();
}
public boolean pass(long leftSideState, long boatSideState,
long rightSideState, Side side) {
if (rightSideState == successState)
return true;
if (checkCanExist(leftSideState) == false
|| checkCanExist(boatSideState) == false
|| checkCanExist(rightSideState) == false)
return false;
if (isHappenedState(new State(leftSideState, rightSideState, side)) == true)
return false;
addHappenedState(new State(leftSideState, rightSideState, side));
List<Type> boatAnimals = getAnimalList(boatSideState);
//boat is on the left side
if(side == Side.left){
//move animal from left side to boat
if(boatAnimals.size() < maxSizeOfBoatAnimal){
List<Type> list = getAnimalList(leftSideState);
for(int i= 0 ; i < list.size() ; i++){
if (pass(removeAnimal(leftSideState, list.get(i).getTypeid()), boatSideState |list.get(i).getTypeid(),
rightSideState, side)) {
logSteps(removeAnimal(leftSideState, list.get(i).getTypeid()), boatSideState |list.get(i).getTypeid(),
rightSideState, side, MOVE_FROM_LEFT_TO_BOAT + Type.getNameById(list.get(i).getTypeid()) + "\n");
return true;
}
}
}
//move animal from boat to left side
for(int i= 0 ; i < boatAnimals.size() ; i++){
if (pass(leftSideState |boatAnimals.get(i).getTypeid(),removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState, side)) {
logSteps(leftSideState |boatAnimals.get(i).getTypeid(),removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState, side, REMOVE_ANIMALS_TO_LEFT + Type.getNameById(boatAnimals.get(i).getTypeid()) + "\n");
return true;
}
}
//boat is on the right side
}else{
//move animal from right side to boat
if(boatAnimals.size() < maxSizeOfBoatAnimal){
List<Type> list = getAnimalList(rightSideState);
for(int i= 0 ; i < list.size() ; i++){
if (pass(leftSideState , boatSideState |list.get(i).getTypeid(),
removeAnimal(rightSideState, list.get(i).getTypeid()), side)) {
logSteps(leftSideState , boatSideState |list.get(i).getTypeid(),
removeAnimal(rightSideState, list.get(i).getTypeid()), side, MOVE_FROM_RIGHT_TO_BOAT + Type.getNameById(list.get(i).getTypeid()) + "\n");
return true;
}
}
}
//move animal from boat to right side
for(int i= 0 ; i < boatAnimals.size() ; i++){
if (pass(leftSideState ,removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState |boatAnimals.get(i).getTypeid(), side)) {
logSteps(leftSideState ,removeAnimal(boatSideState, boatAnimals.get(i).getTypeid()),
rightSideState |boatAnimals.get(i).getTypeid(), side, REMOVE_ANIMALS_TO_RIGHT + Type.getNameById(boatAnimals.get(i).getTypeid()) + "\n");
return true;
}
}
}
//drive to another side
if (haveDriver(boatSideState)) {
if (pass(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left) )) {
logSteps(leftSideState, boatSideState, rightSideState,
(side == Side.left ? Side.right : Side.left),DRIVER_TO_ANOTHER_SIDE + "\n");
return true;
}
}
return false;
}
private boolean haveDriver(long state) {
for (int i = 0; i < driver.length; i++) {
if ((driver[i].getTypeid() & state) != 0)
return true;
}
return false;
}
private boolean isHappenedState(State state) {
int index = findIndex(state);
if (index != -1 && happendedStates.get(index).compare(state) == 0)
return true;
return false;
}
private void addHappenedState(State state) {
int index = findIndex(state);
happendedStates.add(index + 1, state);
}
private StringBuilder getAnimalNameList(long state) {
StringBuilder s = new StringBuilder();
List<Type> list = getAnimalList(state);
for (int i = 0; i < list.size(); i++) {
s.append(list.get(i).getName()).append(",");
}
s.append("\n");
return s;
}
public List<Type> getAnimalList(long state){
ArrayList<Type> list = new ArrayList<Type>();
for (int i = 0; i < types.length; i++) {
if ((types[i].getTypeid() & state) != 0) {
list.add(types[i]);
}
}
return list;
}
private int findIndex(State state) {
// user binary search
int left = 0;
int right = happendedStates.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int temp = happendedStates.get(mid).compare(state);
if (temp < 0) {
left = mid + 1;
} else if (temp > 0) {
right = mid - 1;
} else {
return mid;
}
}
return right;
}
private boolean checkCanExist(long state) {
for (int i = 0; i < animalCanExists.length; i++) {
if ((state & animalCanExists[i]) != 0)
return true;
}
for (int i = 0; i < animalCanNotExists.length; i++) {
if ((state & animalCanNotExists[i]) == animalCanNotExists[i])
return false;
}
return true;
}
private long removeAnimal(long animalList, long animalNeedRemove) {
return (~animalNeedRemove) & animalList;
}
private void logSteps(long leftState , long boatState,long rightState,Side side, String msg) {
StringBuilder sbTemp = new StringBuilder();
// sbTemp.append("***************************************************\n");
sbTemp.append(msg)
.append(LEFT_SIDE_ANIMAL)
.append(getAnimalNameList(leftState))
.append(RIGHT_SIDE_ANIMAL)
.append(getAnimalNameList(rightState))
.append(BOAT_ANIMAL)
.append(getAnimalNameList(boatState))
.append("Side:")
.append((side == Side.left ? "left" : "right"))
.append("\n")
.append("***************************************************\n");
this.steps.insert(0, sbTemp);
}
public static void main(String[] args) {
long startState = Type.wolf.getTypeid() | Type.sheep.getTypeid()
| Type.human.getTypeid() | Type.grass.getTypeid();
PassRiver2 pr = new PassRiver2(startState);
pr.pass(startState, 0, 0, Side.left );
System.out.print(pr.getSteps());
}
}
相关推荐
农夫过河问题讲述的是一位农夫带着一只狼,一只羊和一颗白菜要渡过一条河,只有农夫能开船,且每次农夫只能带最多一样东西,并且农夫不在的时候,狼和羊,羊和白菜不能共存,我们需要在这个前提下找到渡河的最短路径...
A*算法解决传教士与野人过河问题 * 程 序 说 明 * * 功能: 用A*算法求解传教士与野人问题。M=C=5, K=3 * * 说明: * * 本程序按照《人工智能导论》一书所介绍的A*算法求解传教士与野人问题。 * * * * 注意:...
DFS算法
野人过河问题,本实验研究了用人工智能的理论求解传教士(Missionaries)与野人(Cannibals)过河问题(M-C问题)。实验设计采用产生式系统的概念,将问题用状态空间表示,搜索技术采用状态空间启发式搜索的A算法,规则...
野人过河 高中信息技术程序设计 训练 算法描术 野人过河 高中信息技术程序设计 训练 算法描术
内容索引:VC/C++源码,界面编程,过河,算法 VC++ 过河算法游戏与源码解析,用VC++遍历所有可能走的路及可能发生的情况,可以算出从任一上节点到另一节点可能发生状况的步骤。警察小偷爸爸妈妈儿子女儿过河,这个游戏...
摸石头过河算法是以一个解为起点,向该起点附近邻域随机搜索若干个解,找出这些解中的最好的一个解,以此解为下次迭代的结果,然后以此点为起点,再向附近邻域随机搜索若干个解,以此类推. 解连续性优化问题时改进的方法...
农夫过河问题的算法与实现.doc
采用深度优先遍历图的方法,解决农夫过河的问题,有代码,有可执行文件和流程图
主要介绍了基于C++的农夫过河问题算法设计与实现方法,简单描述了农夫过河问题,并结合实例形式详细分析了基于C++实现农夫过河问题的相关算法实现步骤与操作技巧,需要的朋友可以参考下
智力过河算法总结 源码介绍 vc6.0 判断条件 你要防止一下三件事情发生: 1) 当警员与犯人分开时,犯人会伤害一家六口; 2) 当爸爸看见妈妈离开女儿时,爸爸便会教训女儿; 3) 当妈妈看见爸爸离开女儿时,妈妈便会...
一个农夫带着一只狼,一只羊和一筐菜,欲从河的左岸坐船到右岸,由于船太小,农夫每次只能带一样东西过河,并且没有农夫看管的话,狼会吃掉羊,羊会吃菜。设计一个方案,使农夫可以无损失的过河。 代码请用VS2010...
以下这个问题的演示 (附工程文件) 一个人带了一只狼、一只羊和一棵白菜想要过河,河上只有一只独木舟,每次除了人以外只能带一样东西,另外,如果人不在旁时,狼会吃羊,羊会吃菜。应该怎么安排能安全渡河
自己写的java版本的 人狼羊草问题 关于图的dfs搜索算法
10.11.1 青蛙过河算法 331 10.11.2 青蛙过河求解 333 10.12 三色旗 335 10.12.1 三色旗算法 335 10.12.2 三色旗求解 337 10.13 渔夫捕鱼 339 10.13.1 渔夫捕鱼算法 339 10.13.2 渔夫捕魚求解 340 10.14 ...
有3个美女和3个野人要过河,只有1条船,没有船夫,这6个人都会划船。但这条船1次只能载两个人,任何情况下,只要野人的数量大于美女的数量,美女就会被野人吃掉。也就是说,在河的两岸,即河的左岸上和右岸上,野人...
使用Javascript编写的人工智能课程中野人传教士过河问题解决方案脚本,只需使用浏览器打开ai.html即可使用
人工智能过河问题算法深度优先算法.doc
过河问题是操作系统中进程同步和互斥的一个重要问题,传统的解决方法...问题,但当一面的过河者源源不断的到来时,另一面要求过河者会发生“饿死”现象,本文对原有算法进行改 进,给出了一种新的算法,避免了“饿死”现象.
这里分析的是采用C语言描述的著名的人工智能算法之一的野人与牧师过河算法,其中的C源代码在VisualC++上运行测试过都能运行,生成的文件可以转载到其他机器上运行。还带有FLASH模拟运行器,