农夫运送猫狗鱼过河问题（面向对象）
栏目：互联网时间：2014-09-08 14:28:20
题设：农夫欲用船将左岸的猫、狗、鱼运送到右岸。在运送的过程中，每次只能运送一只动物，农夫也可以空船过河。其中当人不在此岸时，狗会咬猫；猫会吃鱼。当人在此岸时，则不会发生冲突。请用面向对象的设计思想解决此类问题。
分析：通过题设条件可以得出以下结论：1、左到右，不存在从左岸到右岸的空船（也就是从左岸到右岸必须运送一只动物）；2、右到左，有且只有两种情况：①空船过河、②带一只动物过河。
程序设计：5个类：MyCrossRiver.java、CrossProcess.java、CrossStep.java、Status.java、Animal.java。其中，MyCrossRiver是程序运行的主类，也包含了过河逻辑；CrossProsess是记录整个过程已经走过的正确的步骤序列；CrossStep表示的是所走过的每一步；Status表示的是对当前步骤的状态的封装（对于左岸和右岸的数据是深度拷贝）；Animal是动物的抽象。
主要代码如下：
MyCrossRiver.java：
package com.others;
import java.util.ArrayList;
import java.util.List;
/**
* 猫狗鱼过河问题
* @author xuefeihu
*
*/
public class MyCrossRiver {
/** 河左岸 **/
private List<Animal> left = new ArrayList<Animal>();
/** 河右岸 **/
private List<Animal> right = new ArrayList<Animal>();
/** 人的位置：左边是true,右边是false **/
private boolean flag = true;
/** 过河步骤 **/
private CrossProcess process = new CrossProcess();
public static void main(String[] args) {
new MyCrossRiver().crossRiver();
}
/**
* 初始化条件
*/
public void initAnimal(){
Animal dog = new Animal("狗", 1, -1, 2);
Animal cat = new Animal("猫", 2, 1, 3);
Animal fish = new Animal("鱼", 3, 2, -1);
left.add(dog);
left.add(cat);
left.add(fish);
}
/**
* 过河操作
*/
public void crossRiver(){
initAnimal();
while(right.size() != 3){
Status preStatus = new Status(this.left, this.right, this.flag);//记录步骤前状态
CrossStep step = new CrossStep(process.getStepCount()+1, this.flag, null, preStatus);//创建步骤
if(this.flag){//从左到右过河（不存在空船过河）
int leftIndex = step.getNextLeftIndex();
int leftSize = this.left.size();
if(leftIndex >= leftSize){//回退数据
this.process.removeLastStep();
CrossStep step2 = this.process.getLastStep();
this.back2Step(step2);
continue;
}else{//带动物过河
step.setAnimal(this.left.get(leftIndex));
}
}else{//从右往左过河
Animal animal = null;
boolean rightSecurity = this.check(right);
if(rightSecurity){
animal = this.getTargetAnimal(this.right);
if(animal == null){//冲突无法解决时，回退数据
this.process.removeLastStep();
CrossStep step2 = this.process.getLastStep();
this.back2Step(step2);
continue;
}else{
step.setAnimal(animal);
}
}else{//无冲突时，不运送动物
step.setAnimal(null);
}
}
boolean result = moveByOneStep(step);
if(!result){//如果执行失败，则恢复上一步骤
this.process.removeLastStep();
CrossStep step2 = this.process.getLastStep();
this.back2Step(step2);
}
}
this.process.printStepMessage();
}
/**
* 移动操作
* @param step
* @return 返回true表示转移成功，false表示转移失败（失败时需要回退到上一步进行转移）
*/
public boolean moveByOneStep(CrossStep step){
/** 返回的结果：true表示移动成功、false表示失败 **/
boolean result = false;
/** 循环标志位 **/
boolean cricleFlag = false;
while(!cricleFlag){
int leftIndex = step.getNextLeftIndex();
int leftSize = step.getStatus().getLeft().size();
int rightIndex = step.getNextRightIndex();
if(this.flag){//当可以找到下一个索引时，进行转移
if(leftIndex < leftSize){//带动物过河
Animal animal = left.remove(leftIndex);
right.add(animal);
flag = !flag;
step.setAnimal(animal);
}else if(leftIndex >= leftSize){
return false;//返回失败信息，并交给上一层程序处理
}
}else if(!this.flag){
if(step.getAnimal() == null){//此时可以单人过河
flag = !flag;
this.process.addStep(step);
return true;
}else{//带动物过河
Animal animal = right.remove(rightIndex);
left.add(animal);
flag = !flag;
}
}
//检查冲突情况（转移后回退）
if(!this.flag && check(this.left)){
step.addNextLeftIndex();
this.back2Step(step);
}else if(this.flag && check(this.right)){
step.addNextRightIndex();
this.back2Step(step);
}else {
this.process.addStep(step);
result = true;
cricleFlag = true;
}
}
return result;
}
/**
* 将当前状态恢复到step步骤
* @param step
*/
private void back2Step(CrossStep step){
Status status = step.getStatus();
this.left = status.getLeft();
this.right = status.getRight();
this.flag = status.getFlag();
}
/**
* 从冲突的数据中获取不冲突的动物：不存在时返回null
*/
public Animal getTargetAnimal(List<Animal> array){
Animal result = null;
//克隆对象
List<Animal> lists = new ArrayList<Animal>();
Animal target = null;
Animal source = null;
for(int i = 0; i < array.size(); i++){
source = array.get(i);
target = new Animal(source.type, source.id, source.afraid, source.control);
lists.add(target);
}
//查找对象
for(int i = 0; i < lists.size(); i++){
result = lists.remove(i);
if(!check(lists)){
break;
}
lists.add(i, result);
}
return result;
}
/**
* 检查是否有冲突
*/
private boolean check(List<Animal> array){
boolean result = true;
if(array.size() > 1){
for(int i = 0; i < array.size(); i++){
for(int j = i+1; j < array.size(); j++){
result = array.get(i).check(array.get(j));
if(result) return result;
}
}
}else{
result = false;
}
return result;
}
}
CrossProcess.javapackage com.others;
import java.util.ArrayList;
import java.util.List;
/**
* 过河的过程
* @author xuefeihu
*
*/
public class CrossProcess {
/** 所有步骤 **/
private List<CrossStep> steps = new ArrayList<CrossStep>();
/**
* 添加步骤
* @param step 步骤
*/
public void addStep(CrossStep step){
if(step.getDirection()){
step.addNextLeftIndex();
}else{
step.addNextRightIndex();
}
this.steps.add(step);
}
/**
* 删除最后一步
*/
public CrossStep removeLastStep(){
return this.steps.remove(this.steps.size()-1);
}
/**
* 获取最后一个步骤
* @return
*/
public CrossStep getLastStep(){
return this.steps.get(this.steps.size()-1);
}
/**
* 打印步骤信息
*/
public void printStepMessage(){
for(CrossStep step : steps){
System.out.println(step.getMessage());
}
}
/**
* 获得当前步骤数
* @return
*/
public int getStepCount(){
return this.steps.size();
}
}
CrossStep.java
package com.sunrise.others;
/**
* 过河步骤
* @author xuefeihu
*
*/
public class CrossStep {
/** 步骤数 **/
private int stepCount;
/** 方向:true是左到右，false是右到左 **/
private boolean direction;
/** 此步骤运送的动物 **/
private Animal animal;
/** 该步骤之前状态 **/
private Status status;
/** 打印语句 **/
private String message;
/** 下一个左侧需要移动的索引 **/
private int nextLeftIndex = 0;
/** 下一个右侧需要移动的索引 **/
private int nextRightIndex = 0;
/**
* 构造器
* @param stepCount 步骤数
* @param direction 方向:true是左到右，false是右到左
* @param animal 此步骤运送的动物
* @param status 当前状态
*/
public CrossStep(int stepCount, boolean direction, Animal animal, Status status) {
this.stepCount = stepCount;
this.direction = direction;
this.animal = animal;
this.status = status;
this.message = "第"+stepCount+"步：农夫将" + (this.animal==null?" 自己 ":this.animal.type) + (this.direction ? "从左岸运到右岸" : "从右岸运到左岸");
}
public int getStepCount() {
return stepCount;
}
public boolean getDirection() {
return direction;
}
public Animal getAnimal() {
return animal;
}
public Status getStatus() {
return status;
}
public String getMessage() {
return message;
}
public int getNextLeftIndex() {
return nextLeftIndex;
}
public void addNextLeftIndex() {
this.nextLeftIndex++;
}
public int getNextRightIndex() {
return nextRightIndex;
}
public void addNextRightIndex() {
this.nextRightIndex++;
}
public void setAnimal(Animal animal) {
this.animal = animal;
this.message = "第"+stepCount+"步：农夫将" + (this.animal==null?" 自己 ":this.animal.type) + (this.direction ? "从左岸运到右岸" : "从右岸运到左岸");
}
}
Status.java
package com.sunrise.others;
import java.util.ArrayList;
import java.util.List;
/**
* 当前状态
* @author xuefeihu
*
*/
public class Status {
/** 左侧 **/
private List<Animal> left = new ArrayList<Animal>();
/** 右侧 **/
private List<Animal> right = new ArrayList<Animal>();
/** 人的位置 **/
private boolean flag;
/**
* 构造状态对象--克隆相应数据
* @param left 左侧状态
* @param right 右侧状态
* @param flag 人的位置
* @param preSelf 前一个动作是否是人单独过河
*/
public Status(List<Animal> left, List<Animal> right, boolean flag) {
this.left = newList(left);
this.right = newList(right);
this.flag = flag;
}
/**
* 克隆List对象
*/
private List<Animal> newList(List<Animal> array){
List<Animal> result = new ArrayList<Animal>();
for(Animal animal : array){
result.add(animal);
}
return result;
}
public List<Animal> getLeft() {
return left;
}
public List<Animal> getRight() {
return right;
}
public boolean getFlag() {
return flag;
}
}
Animal.java
package com.sunrise.others;
/**
* 动物实体
* @author xuefeihu
*
*/
public class Animal {
public String type = null;
public int id = -1;
public int afraid = -1;
public int control = -1;
public Animal(String type, int id, int afraid, int control) {
this.type = type;
this.id = id;
this.afraid = afraid;
this.control = control;
}
/**
* 设计一个制约关系：检查动物是否可以并存
* @param animal
* @return
*/
boolean check(Animal animal){
return this.afraid == animal.id || this.control == animal.id
|| animal.afraid == this.id || animal.control == this.id;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Animal other = (Animal) obj;
if (id != other.id)
return false;
return true;
}
}
友情提示：（面向对象的思想大致认为是正确的；由于时间仓促，如有修改代码，请您附上源码与大家共享，谢谢！）
------分隔线----------------------------
------分隔线----------------------------