关于农民带猫狗鱼过河的问题 - 黑马程序员技术交流社区

package com.itheima;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* 10、一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，
* 则不会发生这种问题。编程解决猫狗鱼过河问题。
*
* 分析：
* 假设动物和老农都在左岸，要到达右岸
* 第一步：老农带着猫到达右岸
* 第二步：老农一个返回左岸
* 第三步：老农带着狗或者鱼到达右岸
* 第四步：老农带着猫返回左岸
* 第五步：老农带着非猫的动物到达右岸
* 第六步：老农一个人返回左岸
* 第七步：老农带着猫到达右岸
* 过河完成！
*
* 把整个过河问题分为从左岸到右岸，从右岸到左岸这两个动作问题。
* 老农从左岸到右岸，必须带着动物，否则没有任何意义，并且该动物不能为上次从右岸返回到左岸的动物。老农从右岸到左岸，
* 如果可以不带动物，则不带，效率高，否则必须带一个动物返回左岸，并且该动物不能为上次从左岸到达右岸的动物。
*
* 采用过程追溯法来是实现过河问题，不满足条件追溯回原状态，知道满足条件为止。
*
* @author liuxiangyun
*
*/
public class Test10 {
List<String> leftBank = new ArrayList<String>();// 左岸
List<String> rightBank = new ArrayList<String>();// 右岸
public static void main(String args[]) {
new Test10().crossRiver();
}
public Test10() {
// 初始化数据
leftBank.add("person");
leftBank.add("fish");
leftBank.add("cat");
leftBank.add("dog");
}
// 过河
public void crossRiver() {
boolean isAtLeftBank = true;// 老农是否在左边
String lastToLeftAnl = "";// 上一个到左边去的动物，默认没有，用""表示
String lastToRightAnl = "";// 上一个到右边去的动物，默认没有，用""表示
while (leftBank.size() > 0) {
//从左岸到右岸
if (isAtLeftBank) {
lastToRightAnl = toRight(lastToLeftAnl);
System.out.println("老农带着{" + lastToRightAnl + "}到达右岸");
isAtLeftBank = false;
//从右岸到左岸
} else {
lastToLeftAnl = toLeft(lastToRightAnl);
if (lastToLeftAnl == "")
System.out.println("老农一个人回到左岸");
else
System.out.println("老农带着{" + lastToLeftAnl + "}到达左岸");
isAtLeftBank = true;
}
}
System.out.println("老农和动物全部过河！");
}
/**
* 从左岸到右岸，老农必须携带一个动物，否则没有任何意义，并且要保证左右岸不出现安全问题
*
* @param lastToLeftAniaml
* 上一个到左岸去的动物，没有则用""表示
* @return 返回要携带的动物
*/
public String toRight(String lastToLeftAniaml) {
boolean flag = true;
String animal = null;
while (flag) {
leftBank.remove("person");
animal = leftBank.get(new Random().nextInt(leftBank.size()));// 随机获取一个动物
leftBank.remove(animal);
rightBank.add("person");
rightBank.add(animal);
if (isSafe() && (animal != lastToLeftAniaml)) {// 不是上一个去左边的动物，并且不产生和谐问题
flag = false;
} else {
rightBank.remove("person");
rightBank.remove(animal);
leftBank.add("person");
leftBank.add(animal);
}
}
return animal;
}
/**
* 从左岸到右岸，老农独自返回，如果没有产生安全问题，他就独自返回，否则必须携带一个动物返回左岸，并且也要保证不产生安全问题。
*
* @param lastToRightAniaml
* 上一个到达右岸的动物
* @return 返回要携带的动物，没有则返回""
*/
public String toLeft(String lastToRightAniaml) {
String animal = null;
rightBank.remove("person");
leftBank.add("person");
if (isSafe()) {
return animal = "";
} else {
leftBank.remove("person");
rightBank.add("person");
boolean flag = true;
while (flag) {
rightBank.remove("person");
animal = rightBank.get(new Random().nextInt(rightBank.size()));// 随机获取一个动物
rightBank.remove(animal);
leftBank.add("person");
leftBank.add(animal);
if (isSafe() && (animal != lastToRightAniaml)) {// 不是上一个去右边的动物，并且不产生和谐问题
flag = false;
} else {
leftBank.remove("person");
leftBank.remove(animal);
rightBank.add("person");
rightBank.add(animal);
}
}
}
return animal;
}
// 判断左右岸是否存在安全问题
public boolean isSafe() {
boolean leftBankIsSafe = true;
boolean rightBankIsSafe = true;
// 岸上没有老农，有猫且有狗或者鱼就存在安全问题
if (!leftBank.contains("person") && leftBank.contains("cat")
&& leftBank.size() > 1)
leftBankIsSafe = false;
if (!rightBank.contains("person") && rightBank.contains("cat")
&& rightBank.size() > 1)
rightBankIsSafe = false;
return leftBankIsSafe && rightBankIsSafe;
}
}

复制代码

import java.util.LinkedList;
public class Ferry {
public static void main(String[] args) {
LinkedList<String> here = new LinkedList<String>();
LinkedList<String> there = new LinkedList<String>();
String cat = "猫";
String dog = "狗";
String fish = "鱼";
int count = 0;
here.add(cat);
here.add(dog);
here.add(fish);
while(there.size()<3){
System.out.println("----第"+(++count)+"次摆渡开始----");
String boat = null;
while(true){
boat = here.removeFirst();
if(isNice(here)){
there.addLast(boat);
System.out.println("老农正把("+boat+")送往河对面....");
break;
}
here.addLast(boat);
}
if(!isNice(there)&&there.size()<3){
boat = there.removeFirst();
System.out.println("并把("+boat+")往回送....");
here.addLast(boat);
}
System.out.println("河这面："+here);
System.out.println("河对面："+there);
}
}
public static boolean isNice(LinkedList<String> li){
if(li.contains("猫")&&li.contains("鱼"))
return false;
else if(li.contains("狗")&&li.contains("猫"))
return false;
else
return true;
}
}

复制代码