農夫運送貓狗魚過河問題（面向對象）
來源：程序員人生 發布時間：2014-09-08 14:28:20 閱讀次數：3387次
題設：農夫欲用船將左岸的貓、狗、魚運送到右岸。在運送的過程中，每次只能運送一只動物，農夫也可以空船過河。其中當人不在此岸時，狗會咬貓；貓會吃魚。當人在此岸時，則不會發生沖突。請用面向對象的設計思想解決此類問題。
分析：通過題設條件可以得出以下結論：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.java
package 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;
}
}
友情提示：（面向對象的思想大致認為是正確的；由于時間倉促，如有修改代碼，請您附上源碼與大家共享，謝謝！）
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
