用JAVA解答： 有一位厨师要从12斤油（A桶）倒出6斤油但现在手里只有8斤和5斤的桶,怎么取出6斤
import java.util.ArrayList;
public class DaoYou {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<State> stateList = new ArrayList<State>();
Tong t1 = new Tong("5斤桶",5,0);
Tong t2 = new Tong("8斤桶",8,0);
Tong t3 = new Tong("12斤桶",12,12);
DaoYou dy = new DaoYou();
State st = new State(t1,t2,t3,0,0);
stateList.add(st);
try {
dy.dao(st, stateList);
} catch (CloneNotSupportedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
for(int i=0; i< stateList.size(); i++){
System.out.println(stateList.get(i));
}
}
public boolean dao(State s,ArrayList<State> states) throws CloneNotSupportedException{
Tong tempT1 = (Tong)s.getT1().clone();
Tong tempT2 = (Tong)s.getT2().clone();
Tong tempT3 = (Tong)s.getT3().clone();
//t1 向 t2 里边倒油
//还可以对倒油的方法单独拿出来，减少代码的冗余
if(tempT1.getNow() > 0 && tempT2.getNow()<tempT2.getMax()){
Tong t1 = (Tong)tempT1.clone();
Tong t2 = (Tong)tempT2.clone();
Tong t3 = (Tong)tempT3.clone();
int temp = (tempT1.getNow() > tempT2.getMax() - tempT2.getNow()) ?
tempT2.getMax() - tempT2.getNow() : tempT1.getNow();
t1.setNow(t1.getNow() - temp);
t2.setNow(t2.getNow() + temp);
State.NEWID = State.NEWID + 1;
State st = new State(t1,t2,t3,State.NEWID,s.getId());
if (states.contains(st)){
State.NEWID = State.NEWID - 1;
State tempState = states.get(states.indexOf(st));
if (s.getId() < tempState.getId()){
System.out.println("======向前的捷径倒油方法======"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}else {
System.out.println("============"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}
}else {
states.add(st);
// 如果倒油成功，返回
// if(t1.getNow() == 6 || t2.getNow() == 6 || t3.getNow() == 6){
// return true;
// }
dao(st,states);
}
}
//t2向t1里倒油
if(tempT2.getNow() > 0 && tempT1.getNow()<tempT1.getMax()){
Tong t1 = (Tong)tempT1.clone();
Tong t2 = (Tong)tempT2.clone();
Tong t3 = (Tong)tempT3.clone();
int temp = (tempT2.getNow() > tempT1.getMax() - tempT1.getNow()) ?
tempT1.getMax() - tempT1.getNow() : tempT2.getNow();
t2.setNow(t2.getNow() - temp);
t1.setNow(t1.getNow() + temp);
State.NEWID = State.NEWID + 1;
State st = new State(t1,t2,t3,State.NEWID,s.getId());
if (states.contains(st)){
State.NEWID = State.NEWID - 1;
State tempState = states.get(states.indexOf(st));
if (s.getId() < tempState.getId()){
System.out.println("======向前的捷径倒油方法======"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}else {
System.out.println("============"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}
}else {
states.add(st);
// 如果倒油成功，返回
// if(t1.getNow() == 6 || t2.getNow() == 6 || t3.getNow() == 6){
// return true;
// }
dao(st,states);
}
}
//t1 向 t3 里边倒油
if(tempT1.getNow() > 0 && tempT3.getNow()<tempT3.getMax()){
Tong t1 = (Tong)tempT1.clone();
Tong t2 = (Tong)tempT2.clone();
Tong t3 = (Tong)tempT3.clone();
int temp = (tempT1.getNow() > tempT3.getMax() - tempT3.getNow()) ?
tempT3.getMax() - tempT3.getNow() : tempT1.getNow();
t1.setNow(t1.getNow() - temp);
t3.setNow(t3.getNow() + temp);
State.NEWID = State.NEWID + 1;
State st = new State(t1,t2,t3,State.NEWID,s.getId());
if (states.contains(st)){
State.NEWID = State.NEWID - 1;
State tempState = states.get(states.indexOf(st));
if (s.getId() < tempState.getId()){
System.out.println("======向前的捷径倒油方法======"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}else {
System.out.println("============"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}
}else {
states.add(st);
// 如果倒油成功，返回
// if(t1.getNow() == 6 || t2.getNow() == 6 || t3.getNow() == 6){
// return true;
// }
dao(st,states);
}
}
//t3向t1里倒油
if(tempT3.getNow() > 0 && tempT1.getNow()<tempT1.getMax()){
Tong t1 = (Tong)tempT1.clone();
Tong t2 = (Tong)tempT2.clone();
Tong t3 = (Tong)tempT3.clone();
int temp = (tempT3.getNow() > tempT1.getMax() - tempT1.getNow()) ?
tempT1.getMax() - tempT1.getNow() : tempT3.getNow();
t3.setNow(t3.getNow() - temp);
t1.setNow(t1.getNow() + temp);
State.NEWID = State.NEWID + 1;
State st = new State(t1,t2,t3,State.NEWID,s.getId());
if (states.contains(st)){
State.NEWID = State.NEWID - 1;
State tempState = states.get(states.indexOf(st));
if (s.getId() < tempState.getId()){
System.out.println("======向前的捷径倒油方法======"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}else {
System.out.println("============"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}
}else {
states.add(st);
// 如果倒油成功，返回
// if(t1.getNow() == 6 || t2.getNow() == 6 || t3.getNow() == 6){
// return true;
// }
dao(st,states);
}
}
//t2向t3里倒油
if(tempT2.getNow() > 0 && tempT3.getNow()<tempT3.getMax()){
Tong t1 = (Tong)tempT1.clone();
Tong t2 = (Tong)tempT2.clone();
Tong t3 = (Tong)tempT3.clone();
int temp = (tempT2.getNow() > tempT3.getMax() - tempT3.getNow()) ?
tempT3.getMax() - tempT3.getNow() : tempT2.getNow();
t2.setNow(t2.getNow() - temp);
t3.setNow(t3.getNow() + temp);
State.NEWID = State.NEWID + 1;
State st = new State(t1,t2,t3,State.NEWID,s.getId());
if (states.contains(st)){
State.NEWID = State.NEWID - 1;
State tempState = states.get(states.indexOf(st));
if (s.getId() < tempState.getId()){
System.out.println("======向前的捷径倒油方法======"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}else {
System.out.println("============"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}
}else {
states.add(st);
// 如果倒油成功，返回
// if(t1.getNow() == 6 || t2.getNow() == 6 || t3.getNow() == 6){
// return true;
// }
dao(st,states);
}
}
//t3向t2里倒油
if(tempT3.getNow() > 0 && tempT2.getNow()<tempT2.getMax()){
Tong t1 = (Tong)tempT1.clone();
Tong t2 = (Tong)tempT2.clone();
Tong t3 = (Tong)tempT3.clone();
// 测试 12斤向8斤油 到的 时候，为什么没成功，因为已经包含了该状态
// if (t1.getNow() == 0 && t2.getNow() == 0 && t3.getNow() == 12 ){
// System.out.println("有执行到此");
// for(int i=0; i< states.size(); i++){
// System.out.println(states.get(i));
// }
// System.out.println("=================");
//
// }
int temp = (tempT3.getNow() > tempT2.getMax() - tempT2.getNow()) ?
tempT2.getMax() - tempT2.getNow() : tempT3.getNow();
t3.setNow(t3.getNow() - temp);
t2.setNow(t2.getNow() + temp);
State.NEWID = State.NEWID + 1;
State st = new State(t1,t2,t3,State.NEWID,s.getId());
if (states.contains(st)){
State.NEWID = State.NEWID - 1;
State tempState = states.get(states.indexOf(st));
if (s.getId() < tempState.getId()){
System.out.println("======向前的捷径倒油方法======"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}else {
System.out.println("============"+ states.indexOf(st) + "\t" + s + "\t" + states.get(states.indexOf(st)));
}
}else {
states.add(st);
// 如果倒油成功，返回
// if(t1.getNow() == 6 || t2.getNow() == 6 || t3.getNow() == 6){
// return true;
// }
dao(st,states);
}
}
return false;
}
}
class State implements Cloneable{
public static int NEWID = 0;
private Tong t1;
private Tong t2;
private Tong t3;
private int id;
private int pid;
public State(Tong t1, Tong t2, Tong t3, int id, int pid) {
super();
this.t1 = t1;
this.t2 = t2;
this.t3 = t3;
this.id = id;
this.pid = pid;
}
public Tong getT1() {
return t1;
}
public void setT1(Tong t1) {
this.t1 = t1;
}
public Tong getT2() {
return t2;
}
public void setT2(Tong t2) {
this.t2 = t2;
}
@Override
public boolean equals(Object arg0) {
if(this == arg0){
return true;
}
if (!(arg0 instanceof State)){
return false;
}
State t = (State)arg0;
if ((this.t1.equals(t.t1) && this.t2.equals(t.t2)) && this.t3.equals(t.t3) ){
return true;
}else {
return false;
}
}
@Override
public String toString() {
// TODO Auto-generated method stub
return this.id + "\t" + this.pid + "\t" + t1.getName() + "当前有" + t1.getNow() + "斤油" + "\t" + t2.getName() + "当前有" + t2.getNow() + "斤油"+ "\t" + t3.getName() + "当前有" + t3.getNow() + "斤油";
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public int getPid() {
return pid;
}
public void setPid(int pid) {
this.pid = pid;
}
public Tong getT3() {
return t3;
}
public void setT3(Tong t3) {
this.t3 = t3;
}
}
class Tong implements Cloneable{
@Override
public Object clone() throws CloneNotSupportedException {
// TODO Auto-generated method stub
return super.clone();
}
private String name;
private int max;
private int now;
@Override
public boolean equals(Object arg0) {
// TODO Auto-generated method stub
if(this == arg0){
return true;
}
if (!(arg0 instanceof Tong)){
return false;
}
Tong t = (Tong)arg0;
if (this.max == t.max && this.now == t.now){
return true;
}else {
return false;
}
}
public int getMax() {
return max;
}
public void setMax(int max) {
this.max = max;
}
public int getNow() {
return now;
}
public void setNow(int now) {
this.now = now;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Tong(String name, int max, int now) {
super();
this.name = name;
this.max = max;
this.now = now;
}
public Tong() {
super();
}
}
