智力题目
有三个容积分别为3升、5升、8升的水桶，其中容积为8升的水桶中装满了水，容积为3升和容积为5升的水桶都是空的。三个水桶都没有刻度，现在需要将大水桶中的8升水等分成两份，每份都是4升水，附加条件是只能这三个水桶，不能借助其他辅助容器。
“恩，是的，这是一个很经典的问题。”
“然而，我们并不能想全，不信请继续往下看。”
答案
”废话不多说，直接看方法吧。“
第一种（7步）
将8L的水桶中的水，倒满5L的水桶，这时：8L水桶为3L、5L水桶为5L、3L水桶为0L
将5L的水桶中的水，倒满3L的水桶，这时：8L水桶为3L、5L水桶为2L、3L水桶为3L
将3L的水桶中的水，倒入8L的水桶，这时：8L水桶为6L、5L水桶为2L、3L水桶为0L
将5L的水桶中的水，倒入3L的水桶，这时：8L水桶为6L、5L水桶为0L、3L水桶为2L
将8L的水桶中的水，倒入5L的水桶，这时：8L水桶为1L、5L水桶为5L、3L水桶为2L
将5L的水桶中的水，倒满3L的水桶，这时：8L水桶为1L、5L水桶为4L、3L水桶为3L
将3L的水桶中的水，倒入8L的水桶，这时：8L水桶为4L、5L水桶为4L、3L水桶为0L
第二种（8步）
将8L的水桶中的水，倒满3L的水桶，这时：8L水桶为5L、5L水桶为0L、3L水桶为3L
将3L的水桶中的水，倒入5L的水桶，这时：8L水桶为5L、5L水桶为3L、3L水桶为0L
将8L的水桶中的水，倒满3L的水桶，这时：8L水桶为2L、5L水桶为3L、3L水桶为3L
将3L的水桶中的水，倒满5L的水桶，这时：8L水桶为2L、5L水桶为5L、3L水桶为1L
将5L的水桶中的水，倒入8L的水桶，这时：8L水桶为7L、5L水桶为0L、3L水桶为1L
将3L的水桶中的水，倒入5L的水桶，这时：8L水桶为7L、5L水桶为1L、3L水桶为0L
将8L的水桶中的水，倒满3L的水桶，这时：8L水桶为4L、5L水桶为1L、3L水桶为3L
将3L的水桶中的水，倒入5L的水桶，这时：8L水桶为4L、5L水桶为4L、3L水桶为0L
我相信答案肯定不止两个，到底有多少种答案？
带着这个疑问，我们来设计一个算法吧。
问题分析
人的思维
解决这个问题的关键是怎么通过倒水凑出确定的1升水或能容纳1升水的空间。
例如，当8L水桶或5L水桶或3L水桶有1L水时，都能快速倒出4L水。
计算机思维
“穷举法”
水桶初始状态：8L水桶装满水，3L和5L的水桶为空。
水桶最终状态：3L水桶为空，5L和8L的水桶各4L水。
假设将每个状态下三个水桶中的水的体积作为status。
从 status = array(8,0,0) 得到 status = array(4,4,0)。
当然还会有一些限制：
- 各个水桶的都有最大值：
- 当前倒水之后各个水桶的状态，与历史倒水之后各个水桶的状态，不能相同。
- 当前水桶为空时，不能倒给其他水桶。
- 当前水桶为最大容积时，其他水桶不能再向这个水桶倒水。
BucketWater.java桶的实体类，用于包装容量和剩余的水
public class BucketWater implements Cloneable {
private int index;
private int capacity;
private int remainWater;
public BucketWater() {
}
public BucketWater(int index, int remainWater , int capacity) {
this.index = index;
this.remainWater = remainWater;
this.capacity = capacity;
}
public int getRemainWater() {
return remainWater;
}
public void setRemainWater(int remainWater) {
this.remainWater = remainWater;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public int getCapacity() {
return capacity;
}
public void setCapacity(int capacity) {
this.capacity = capacity;
}
@Override
public BucketWater clone() throws CloneNotSupportedException {
return (BucketWater)super.clone();
}
}BucketStatus.java桶状态的实体类，主要为了保存3个桶创建的对象
public class BucketStatus implements Cloneable {
private BucketWater[] bucketWaterAry = new BucketWater[3];
public BucketStatus() {
}
public BucketWater[] getBucketWaterAry() {
return bucketWaterAry;
}
public void setBucketWaterAry(BucketWater[] bucketWaterAry) {
this.bucketWaterAry = bucketWaterAry;
}
@Override
public BucketStatus clone() throws CloneNotSupportedException {
BucketStatus bucketStatus = (BucketStatus)super.clone();
BucketWater[] bucketWaterAry = new BucketWater[3];
for(int i = 0; i < this.bucketWaterAry.length ; i ++){
bucketWaterAry[i] = this.bucketWaterAry[i].clone();
}
bucketStatus.bucketWaterAry = bucketWaterAry;
return bucketStatus;
}
}Test.java 主类，包含了所有算法和流程
public class Test{
private static int index = 0;
private static Stack<BucketStatus> bucketStatusQueue = new Stack<>();
public static void main( String[] args ) throws CloneNotSupportedException {
BucketWater bucketWater1 = new BucketWater(1, 8 , 8);
BucketWater bucketWater2 = new BucketWater(2, 0 , 5);
BucketWater bucketWater3 = new BucketWater(3, 0 , 3);
BucketStatus bucketStatus = new BucketStatus();
bucketStatus.getBucketWaterAry()[0] = bucketWater1;
bucketStatus.getBucketWaterAry()[1] = bucketWater2;
bucketStatus.getBucketWaterAry()[2] = bucketWater3;
bucketStatusQueue.add(bucketStatus);
search();
}
/**
* 核心查找方法
* @throws CloneNotSupportedException
*/
public static void search() throws CloneNotSupportedException {
//从栈中获取顶端的元素
BucketStatus bucketStatus = bucketStatusQueue.peek();
//判断是否结束，若结束了打印日志
//放在上面判断因为递归必须需要进入此方法，方法退出后才会pop，在这里打印可以获取所有路径
if(isEnd(bucketStatus)){
logProcess();
}
BucketWater[] bucketWaterAry = bucketStatus.getBucketWaterAry();
for(int i = 0 ; i < bucketWaterAry.length ; i ++){
for(int j = 0 ; j < bucketWaterAry.length ; j ++){
//判断是否可以倒水 并获取可以倒水的量
int pushWater = canPush(bucketWaterAry[i] , bucketWaterAry[j]);
if(pushWater == 0 ) {
continue;
}
//这里返回的对象已经被clone了，没有指针引用的问题
//在后期处理直接压入栈
BucketStatus nextBucketStatus = push(bucketStatus , i , j , pushWater);
//判断当前的状态是否已经处理过 循环栈即可获得
//在这里不需要添加到的水量，可以想象为一个树型结构，即该节点是否处理过，以节点为一个维度
if(isAlreadyProcess(nextBucketStatus)){
continue;
}
bucketStatusQueue.add(nextBucketStatus);
search();
//pop只会pop扫描到的子节点
bucketStatusQueue.pop();
}
}
}
/**
* 倒水
*/
public static BucketStatus push(BucketStatus bucketStatus , Integer fromIndex, Integer toIndex , int pushWater) throws CloneNotSupportedException {
BucketStatus copyBucketStatus = bucketStatus.clone();
BucketWater bucketWaterFrom = copyBucketStatus.getBucketWaterAry()[fromIndex];
BucketWater bucketWaterTo = copyBucketStatus.getBucketWaterAry()[toIndex];
bucketWaterFrom.setRemainWater(bucketWaterFrom.getRemainWater() - pushWater);
bucketWaterTo.setRemainWater(bucketWaterTo.getRemainWater() + pushWater);
return copyBucketStatus;
}
/**
* 判断是否可以倒入水
* @param bucketWaterFrom
* @param bucketWaterTo
* @return
*/
public static int canPush(BucketWater bucketWaterFrom , BucketWater bucketWaterTo){
//相同的水桶号 不能倒入水
if(bucketWaterFrom.getIndex() == bucketWaterTo.getIndex()){
return 0;
}
//满的桶 不能导入水
if(bucketWaterTo.getRemainWater() == bucketWaterTo.getCapacity()){
return 0;
}
//没有水 不能倒
if(bucketWaterFrom.getRemainWater() == 0){
return 0;
}
//可以倒入的水
int canPushWater = bucketWaterTo.getCapacity() - bucketWaterTo.getRemainWater();
return bucketWaterFrom.getRemainWater() <= canPushWater ? bucketWaterFrom.getRemainWater() : canPushWater;
}
/**
* 判断当前这个流程是否之前处理过
* @return
*/
public static boolean isAlreadyProcess(BucketStatus bucketStatus){
Iterator<BucketStatus> iterator = bucketStatusQueue.iterator();
while(iterator.hasNext()){
BucketStatus bucket = iterator.next();
if(bucket.getBucketWaterAry()[0].getRemainWater() == bucketStatus.getBucketWaterAry()[0].getRemainWater() &&
bucket.getBucketWaterAry()[1].getRemainWater() == bucketStatus.getBucketWaterAry()[1].getRemainWater() &&
bucket.getBucketWaterAry()[2].getRemainWater() == bucketStatus.getBucketWaterAry()[2].getRemainWater()){
return true;
}
}
return false;
}
/**
* 判断是否查找到了解决路径
* @param bucketStatus
* @return
*/
public static boolean isEnd(BucketStatus bucketStatus){
int index = 2;
for(BucketWater bucketWater : bucketStatus.getBucketWaterAry()){
if(bucketWater.getRemainWater() == 4){
index--;
}
}
return index == 0;
}
/**
* 成功时输出
*/
public static void logProcess(){
index++;
Iterator<BucketStatus> iterator = bucketStatusQueue.iterator();
System.out.print(index + ":");
while(iterator.hasNext()) {
BucketStatus bucket = iterator.next();
System.out.print("[" + bucket.getBucketWaterAry()[0].getRemainWater() + "," + bucket.getBucketWaterAry()[1].getRemainWater() + "," + bucket.getBucketWaterAry()[2].getRemainWater() + "] ==>");
}
System.out.println();
}
}运行结果:
1:[8,0,0] ==>[3,5,0] ==>[0,5,3] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
2:[8,0,0] ==>[3,5,0] ==>[3,2,3] ==>[0,5,3] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
3:[8,0,0] ==>[3,5,0] ==>[3,2,3] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
4:[8,0,0] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[0,5,3] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
5:[8,0,0] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[0,5,3] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
6:[8,0,0] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
7:[8,0,0] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>
8:[8,0,0] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
9:[8,0,0] ==>[5,0,3] ==>[0,5,3] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>
10:[8,0,0] ==>[5,0,3] ==>[5,3,0] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>
11:[8,0,0] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[0,5,3] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>
12:[8,0,0] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[0,5,3] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>
13:[8,0,0] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>
14:[8,0,0] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[0,5,3] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>
15:[8,0,0] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[7,0,1] ==>[7,1,0] ==>[4,1,3] ==>[4,4,0] ==>
16:[8,0,0] ==>[5,0,3] ==>[5,3,0] ==>[2,3,3] ==>[2,5,1] ==>[3,5,0] ==>[3,2,3] ==>[6,2,0] ==>[6,0,2] ==>[1,5,2] ==>[1,4,3] ==>[4,4,0] ==>一共有 16 种倒水方法，方法如下：
评论区
还没有人评论