古老的題目：2個水壺， 一個5升，一個6升。問如何用這2個測量出3升水
一個面向對象的算法程序如下：
/*
* 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;
}
}
結果如下
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個解，這算法就是廣度遍歷，壓棧。
還有一個思路，可用逆推
有用的事實：
1 如果一個壺是非空非滿，則另外一個壺必是空或滿。
2 空和滿之間轉換沒難度，思考時可以理解空就是滿
3 記住3是目的。所以3不能參與運算。
設5升壺為a,6升壺為b
則最后的可能
一 a 有3升
1. b 0升 則說明前一步是 b->a,之前的水是 1/2 或 2/1 對照上述事實，可見此選擇不可能。
2. b 6 升 則說明前一步是 a->b,之前是 5/4 ，ok, 4 只可能為5－1，6－2，加法全部不可能。得到1則很容易。
二 b 有3升
1. a 0 升 則說明前一步是 a->b
2. a 5 升 則說明前一步是 b->a
從純數學的角度來說這個問題是如何用有限的數字組合出最后的數字。這樣會大大簡化程序。
如果按照逆推的思路，相信也可以寫出算法（感覺可以用遞歸），而且應該速度會快很多。
其實猜出來很容易，但是要找出統一規律則有些難度。我本來以為會有很多解，但我的算法只算出來4個，應該是準確的。