農(nóng)夫運送貓狗魚過河問題（面向?qū)ο螅?/h1>

來源：程序員人生   發(fā)布時間：2014-09-08 14:28:20 閱讀次數(shù)：3383次

題設(shè)：農(nóng)夫欲用船將左岸的貓、狗、魚運送到右岸。在運送的過程中，每次只能運送一只動物，農(nóng)夫也可以空船過河。其中當(dāng)人不在此岸時，狗會咬貓；貓會吃魚。當(dāng)人在此岸時，則不會發(fā)生沖突。請用面向?qū)ο蟮脑O(shè)計思想解決此類問題。

分析：通過題設(shè)條件可以得出以下結(jié)論：1、左到右，不存在從左岸到右岸的空船（也就是從左岸到右岸必須運送一只動物）；2、右到左，有且只有兩種情況：①空船過河、②帶一只動物過河。

程序設(shè)計：5個類：MyCrossRiver.java、CrossProcess.java、CrossStep.java、Status.java、Animal.java。其中，MyCrossRiver是程序運行的主類，也包含了過河邏輯；CrossProsess是記錄整個過程已經(jīng)走過的正確的步驟序列；CrossStep表示的是所走過的每一步；Status表示的是對當(dāng)前步驟的狀態(tài)的封裝（對于左岸和右岸的數(shù)據(jù)是深度拷貝）；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);//記錄步驟前狀態(tài) CrossStep step = new CrossStep(process.getStepCount()+1, this.flag, null, preStatus);//創(chuàng)建步驟 if(this.flag){//從左到右過河（不存在空船過河） int leftIndex = step.getNextLeftIndex(); int leftSize = this.left.size(); if(leftIndex >= leftSize){//回退數(shù)據(jù) 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){//沖突無法解決時，回退數(shù)據(jù) 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){//如果執(zhí)行失敗，則恢復(fù)上一步驟 this.process.removeLastStep(); CrossStep step2 = this.process.getLastStep(); this.back2Step(step2); } } this.process.printStepMessage(); } /** * 移動操作 * @param step * @return 返回true表示轉(zhuǎn)移成功，false表示轉(zhuǎn)移失敗（失敗時需要回退到上一步進行轉(zhuǎn)移） */ public boolean moveByOneStep(CrossStep step){ /** 返回的結(jié)果：true表示移動成功、false表示失敗 **/ boolean result = false; /** 循環(huán)標志位 **/ boolean cricleFlag = false; while(!cricleFlag){ int leftIndex = step.getNextLeftIndex(); int leftSize = step.getStatus().getLeft().size(); int rightIndex = step.getNextRightIndex(); if(this.flag){//當(dāng)可以找到下一個索引時，進行轉(zhuǎn)移 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; } } //檢查沖突情況（轉(zhuǎn)移后回退） 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; } /** * 將當(dāng)前狀態(tài)恢復(fù)到step步驟 * @param step */ private void back2Step(CrossStep step){ Status status = step.getStatus(); this.left = status.getLeft(); this.right = status.getRight(); this.flag = status.getFlag(); } /** * 從沖突的數(shù)據(jù)中獲取不沖突的動物：不存在時返回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()); } } /** * 獲得當(dāng)前步驟數(shù) * @return */ public int getStepCount(){ return this.steps.size(); } }

CrossStep.java

package com.sunrise.others; /** * 過河步驟 * @author xuefeihu * */ public class CrossStep { /** 步驟數(shù) **/ private int stepCount; /** 方向:true是左到右，false是右到左 **/ private boolean direction; /** 此步驟運送的動物 **/ private Animal animal; /** 該步驟之前狀態(tài) **/ private Status status; /** 打印語句 **/ private String message; /** 下一個左側(cè)需要移動的索引 **/ private int nextLeftIndex = 0; /** 下一個右側(cè)需要移動的索引 **/ private int nextRightIndex = 0; /** * 構(gòu)造器 * @param stepCount 步驟數(shù) * @param direction 方向:true是左到右，false是右到左 * @param animal 此步驟運送的動物 * @param status 當(dāng)前狀態(tài) */ 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+"步：農(nóng)夫?qū)?quot; + (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+"步：農(nóng)夫?qū)?quot; + (this.animal==null?" 自己 ":this.animal.type) + (this.direction ? "從左岸運到右岸" : "從右岸運到左岸"); } }

Status.java

package com.sunrise.others; import java.util.ArrayList; import java.util.List; /** * 當(dāng)前狀態(tài) * @author xuefeihu * */ public class Status { /** 左側(cè) **/ private List<Animal> left = new ArrayList<Animal>(); /** 右側(cè) **/ private List<Animal> right = new ArrayList<Animal>(); /** 人的位置 **/ private boolean flag; /** * 構(gòu)造狀態(tài)對象--克隆相應(yīng)數(shù)據(jù) * @param left 左側(cè)狀態(tài) * @param right 右側(cè)狀態(tài) * @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; } /** * 設(shè)計一個制約關(guān)系：檢查動物是否可以并存 * @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; } }

友情提示：（面向?qū)ο蟮乃枷氪笾抡J為是正確的；由于時間倉促，如有修改代碼，請您附上源碼與大家共享，謝謝！）

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈