古老的題目：2個(gè)水壺， 一個(gè)5升，一個(gè)6升。問(wèn)如何用這2個(gè)測(cè)量出3升水
一個(gè)面向?qū)ο蟮乃惴ǔ绦蛉缦拢?br />
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package desktopapplication1;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author shen
*/
public class Actioner {
Bottle a;
Bottle b;
String log = "";
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Actioner)) {
return false;
}
Actioner actioner2 = (Actioner) obj;
if ((a.water == actioner2.a.water) && (b.water == actioner2.b.water)) {
return true;
}
return false;
}
public void action() {
Bottle copyA;
Bottle copyB;
//a ->b
copyA = a.copy();
copyB = b.copy();
if (copyA.fill(copyB)) {
System.out.println("succeeded:" + log + "a->b ("+copyA.water+"/"+copyB.water+"), ");
}
Stack.actions.add(new Actioner(copyA, copyB, log + "a->b ("+copyA.water+"/"+copyB.water+"), "));
//b->a
copyA = a.copy();
copyB = b.copy();
if (copyB.fill(copyA)) {
System.out.println("succeeded:" + log + "b->a ("+copyA.water+"/"+copyB.water+"), ");
}
Stack.actions.add(new Actioner(
copyA,
copyB, log + "b->a ("+copyA.water+"/"+copyB.water+"), "));
//drop a
copyA = a.copy();
copyB = b.copy();
copyA.drop();
Stack.actions.add(
new Actioner(copyA, copyB, log + "drop a, "));
//drop b
copyA = a.copy();
copyB = b.copy();
copyB.drop();
Stack.actions.add(new Actioner(copyA, copyB, log + "drop b, "));
// fill a
copyA = a.copy();
copyB = b.copy();
copyA.fill();
Stack.actions.add(new Actioner(
copyA,
copyB, log + " fill a, "));
// fill b
copyA = a.copy();
copyB = b.copy();
copyB.fill();
Stack.actions.add(new Actioner(copyA, copyB, log + "fill b, "));
//then continue;
}
public Actioner(Bottle a, Bottle b, String log) {
this.a = a;
this.b = b;
this.log = log;
}
public static void main(String[] args) {
Bottle a = new Bottle(5, 0);
Bottle b = new Bottle(6, 0);
Stack.actions.add(new Actioner(a, b, ""));
Stack.action();
}
}
class Stack {
public static int level;
public static List<Actioner> actions = new ArrayList<Actioner>();
public static List<Actioner> done = new ArrayList<Actioner>();
public static void action() {
List<Actioner> list = new ArrayList();
list.addAll(actions);
for (Actioner actioner : list) {
actioner.action();
done.add(actioner);
}
actions.removeAll(done);
level++;
if (actions.size() > 0) {
//System.out.println("----------------level" + level + ",size:" + actions.size() + "-------------------");
action();
}
}
}
class Bottle {
int capable;
int water;
boolean fill(Bottle b) {
//System.out.println("bottle[" + capable + "] -> bottle[" + b.capable + "]");
int available = b.capable - b.water;
int transfer = Math.min(water, available);
water = water - transfer;
b.water = b.water + transfer;
return checkSucceeded();
}
void fill() {
//System.out.println("bottle[" + capable + "] -> fill");
water = capable;
}
void drop() {
//System.out.println("bottle[" + capable + "] -> drop");
water = 0;
}
boolean checkSucceeded() {
//System.out.println("the water is " + water);
if (water == 3) {
//System.out.println("it's done");
return true;
}
return false;
}
Bottle copy() {
return new Bottle(capable, water);
}
public Bottle(int capable, int water) {
this.capable = capable;
this.water = water;
}
}
結(jié)果如下
succeeded: fill a, a->b (0/5), fill a, a->b (4/6), drop b, a->b (0/4), fill a, a->b (3/6),
succeeded: fill a, a->b (0/5), fill a, a->b (4/6), drop b, a->b (0/4), fill a, a->b (3/6), a->b (3/6),
succeeded:fill b, b->a (5/1), drop a, b->a (1/0), fill b, b->a (5/2), drop a, b->a (2/0), fill b, b->a (5/3),
succeeded:fill b, b->a (5/1), drop a, b->a (1/0), fill b, b->a (5/2), drop a, b->a (2/0), fill b, b->a (5/3), b->a (5/3),
所以是4個(gè)解，這算法就是廣度遍歷，壓棧。
還有一個(gè)思路，可用逆推
有用的事實(shí)：
1 如果一個(gè)壺是非空非滿，則另外一個(gè)壺必是空或滿。
2 空和滿之間轉(zhuǎn)換沒(méi)難度，思考時(shí)可以理解空就是滿
3 記住3是目的。所以3不能參與運(yùn)算。
設(shè)5升壺為a,6升壺為b
則最后的可能
一 a 有3升
1. b 0升 則說(shuō)明前一步是 b->a,之前的水是 1/2 或 2/1 對(duì)照上述事實(shí)，可見(jiàn)此選擇不可能。
2. b 6 升 則說(shuō)明前一步是 a->b,之前是 5/4 ，ok, 4 只可能為5－1，6－2，加法全部不可能。得到1則很容易。
二 b 有3升
1. a 0 升 則說(shuō)明前一步是 a->b
2. a 5 升 則說(shuō)明前一步是 b->a
從純數(shù)學(xué)的角度來(lái)說(shuō)這個(gè)問(wèn)題是如何用有限的數(shù)字組合出最后的數(shù)字。這樣會(huì)大大簡(jiǎn)化程序。
如果按照逆推的思路，相信也可以寫出算法（感覺(jué)可以用遞歸），而且應(yīng)該速度會(huì)快很多。
其實(shí)猜出來(lái)很容易，但是要找出統(tǒng)一規(guī)律則有些難度。我本來(lái)以為會(huì)有很多解，但我的算法只算出來(lái)4個(gè)，應(yīng)該是準(zhǔn)確的。