JAVA编程实现：现有三个水杯，容量分别为8L、5L、3L，但是只有容量为8L的水杯是装满水的，经过多次倒水后，使得三个杯子已装水量为4L、4L、0L
题目如上，有没有人知道其算法？
------解决思路----------------------
import java.util.ArrayList;
import java.util.List;
public class T {
private List<List<Integer>> histories = new ArrayList<List<Integer>>();
private List<Glass> glasses = new ArrayList<Glass>();
public static void main(String[] args) {
new T().test();
}
public void test() {
Glass a = new Glass(8);
a.size = 8;
Glass b = new Glass(5);
Glass c = new Glass(3);
glasses.add(a);
glasses.add(b);
glasses.add(c);
addHistory();
// 最终结果 4 4 0
while (true) {
Glass max = glasses.get(0);
Glass min = glasses.get(0);
for (int i = 1; i < glasses.size(); i++) {
Glass glass = glasses.get(i);
if (max.size < glass.size) {
max = glass;
}
if (min.size > glass.size) {
min = glass;
}
}
Glass mid = null;
for (Glass glass : glasses) {
if (glass != max && glass != min) {
mid = glass;
}
}
if (!pour(max, mid)) {
if (!pour(max, min)) {
if (!pour(mid, min)) {
if (!pour(mid, max)) {
if (!pour(min, max)) {
if (!pour(min, mid)) {
System.out.println("error");
}
}
}
}
}
}
addHistory();
System.out.println(a.size + ", " + b.size + ", " + c.size);
System.out.println("----------------");
if (a.size == 4 && b.size == 4 && c.size == 0) {
System.out.println("success");
return;
}
}
}
/**
* 增加历史记录
*/
private void addHistory() {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(glasses.get(0).size);
list.add(glasses.get(1).size);
list.add(glasses.get(2).size);
histories.add(list);
}
/**
* 是否史历史状态
*/
private boolean isHistory() {
for (List<Integer> history : histories) {
if (history.get(0) == glasses.get(0).size && history.get(1) == glasses.get(1).size && history.get(2) == glasses.get(2).size) {
return true;
}
}
return false;
}
/**
* 倒水
* @param from
* @param to
* @return
*/
public boolean pour(Glass from, Glass to) {
// 保留初始值
int temp1 = from.size;
int temp2 = to.size;
// form 中没水或 to 中已满
if (from.size == 0
------解决思路----------------------
to.capacity == to.size) {
return false;
}
int toResidual = to.capacity - to.size;
if (from.size >= toResidual) { // 对方倒满
to.size = to.capacity;
from.size -= toResidual;
} else { // 自己倒完
to.size += from.size;
from.size = 0;
}
if (isHistory()) {
// 还原
from.size = temp1;
to.size = temp2;
return false;
}
return true;
}
class Glass {
int capacity; // 容量
int size; // 拥有水量
public Glass(int capacity) {
this.capacity = capacity;
}
@Override
public String toString() {
return "Glass [capacity=" + capacity + ", size=" + size + "]";
}
}
}