古老的题目：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个，应该是准确的。