有一个3升水壶和一个5升水壶, 如何精确取出4升水?

问题背景

这个问题来自于电影Die Hard Ⅲ(虎胆龙威3) 片段, 剧中, 主人公必须在规定时间内使用3加仑水桶和5加仑水桶盛出4加仑水, 否则, 恐怖分子将引爆炸弹

为了方便以下探讨问题使用单位“升”

那么如何使用这两个水桶盛水呢?

以下是一个参考方案(用一个数对表示两个水桶的水量)假设最开始为**(0,0)**

  1. 大桶装满5升水 (0,5)
  2. 把5升水倒进3升水桶里, 留下2升 (3,2)
  3. 倒空小桶的水(不需要了) (0,2)
  4. 把2升水转移到小桶里 (2,0)
  5. 加满大桶 (2,5)
  6. 从大桶往小桶加水直至小桶正好填满, 此时大桶剩余4升 (3,4)

将这个问题一般化

假设有两个水桶容量为x和y升, 请问能否准确的到target升的水

由于没有精确测量体积的工具, 所以我们只有如下操作

  • 装满任意一个水壶
  • 清空任意一个水壶
  • 将一个水壶倒入另一个水壶, 直至水壶已满, 或者水壶已空

力扣传送门

解答思路

最开始的状态为(0,0)

然后对于最开始的状态可以进行的所有操作全部模拟一遍, 并记录操作之后的所有状态

对于产生的每一个状态, 都重复以上操作, 将所有可能的操作全部模拟一遍

如果遇到了之前已经遇到过的状态, 就不用重复模拟一遍, 直接跳过

对于每一个状态, 操作是重复的, 那么应该使用递归还是栈呢?

由于无法预估到底多少次能够找到答案, 所以使用递归方式比较危险, 容易导致栈溢出, 因此使用栈来模拟递归, 使用栈保存水桶状态, 同时, 在增减水的过程中, 会出现重复的状态, 用集合保存所有模拟过的状态, 遇到集合中存在的状态就直接跳过

返回值为布尔值, 表示是否可以达成目标

具体代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
        stack<vector<int>> state;       // 存储状态的栈
        vector<int> water = {0,0};      // 存储两个水桶的数组
        set<vector<int>> my_set;        // 保存所有已经试验过的状态的集合
        state.push(water);              // 将初始状态压入栈
        while(!state.empty()){          // 只要栈不空, 就可以继续模拟, 栈空了, 说明无法达成目标
            water = state.top();        // 获取当前准备模拟的一个状态
            state.pop();                // 获取完了弹出
            if(my_set.contains(water)){ // 如果之前已经模拟过了
                continue;               // 跳过本次循环
            }
            my_set.insert(water);       // 将本次状态加入集合
            if(water[0]==target || water[1]==target || water[0]+water[1]==target){          // 如果某一个水桶或者两个桶之和符合目标
                return true;            // 返回true
            }
            // 装满第一个桶
            vector<int> old = water;    // 保留没操作之前的状态
            water[0] = x;
            state.push(water);
            // 装满第二个桶
            water = old;                // 恢复没操作之前的状态
            water[1] = y;
            state.push(water);
            // 清空第一个桶
            water = old;
            water[0] = 0;
            state.push(water);
            // 清空第二个桶
            water = old;
            water[1] = 0;
            state.push(water);
            // 第一个桶倒入第二个桶
            water = old;
            if(water[0]+water[1]<=y){   // 如果加不满第二个桶
                water[1] += water[0];
                water[0] = 0;
                state.push(water);
            }
            else{                       // 如果加满了第二个桶, 第一个桶还有剩余
                int t = y - water[1];
                water[1] = y;
                water[0] -= t;
                state.push(water);
            }
            // 第二个桶倒入第一个桶
            water = old;
            if(water[0]+water[1]<=x){   // 如果加不满第一个桶
                water[0] += water[1];
                water[1] = 0;
                state.push(water);
            }
            else{                       // 如果加满了第一个桶, 第二个桶还有剩余
                int t = x - water[0];
                water[0] = x;
                water[1] -= t;
                state.push(water);
            }
        }
        return false;                   // 栈空了也没找到符合要求的操作, 就返回false
    }
};

几个小问题

1. set判断的是vector 对象的地址还是值

C++中, set会判断vector 的值, 自动比对是否一致, 但是在Java中会比较对象的地址, 此时想使用的set中的contains()方法的话, 可以使用如下方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
calss Water{
    int a;
    int b;
    public Water(int a, int b){
        this.a = a;
        this.b = b;
    } 
    // 重写eauals()
    public boolean equals(Object o){
        if(this==o)         // 本来就是这个对象, 直接返回
            return true;
        if(!(o.instanceof(Water)))  // 不是这个类的对象
            return false;
        Water w = (Water)o;
        retuan w.a==this.a && w.b==this.b;
    }
    // 重写hashCode(), 原因见下文
    public int hashCode(){
        return Objects.hash(this.a,this.b);
    }
}

2. 为什么重写equals()方法时一定要重写hashCode()方法呢?

在Java中, HashMap和HashSet类需要使用hashCode值确定对象在内存中的位置, 如果要在HashMap和HashSet对象中寻找是否存在一个对象, 那么首先会检查对象的hashCode值存不存在, 然后再调用equals()方法来比较和已经存在的对象是否相等

如果重写了equals()方法时没有重写hashCode()方法, 那么在比较时压根找不到集合中已经存在的相同的对象, 导致程序认为集合中不存在要找的对象

Objects.hash()方法的参数是若干个Object对象
它的定义是public static int hash(Object... values)
参考链接

3. 递归多少层会栈溢出呢?

递归的层数导致栈溢出的具体限制因系统而异, 但通常在几千到几百万层之间这取决于计算机的内存大小、操作系统和编程语言的实现方式

为了避免栈溢出, 可以考虑以下方法

  1. 优化递归算法：使用尾递归, 以减少栈帧的累积
  2. 增加栈大小：某些编程语言和环境允许你手动设置栈的大小如果递归算法需要更深的栈, 可以尝试增加栈的大小
  3. 使用循环：修改算法的具体实现方法, 改成使用循环迭代思考具体的循环条件, 或者使用直接用栈模拟递归过程

4. 什么是尾递归

在递归时, 通常会发生, a函数在自己内部调用了2次或者多次a函数本身, 此时递归使用的系统栈空间称指数增加, 容易发生栈溢出, 所以如果只调用一次的话, 可以减少一定的系统栈的占用, 此时如果调用语句时return语句, 那么a函数调用自己之后就无需保留自己的状态, 系统也不需要为程序保留旧的a函数, 只需要管理新的a函数即可, 大大减少了系统栈的开销

给尾递归下一个定义, 指一个函数在调用自身之后不再执行任何其他操作，而是将返回值直接传递给函数调用的上级

参考链接

下面演示一下如何将一个不是尾递归的函数改造成尾递归

改造前

1
2
3
4
5
6
// 求斐波那契数列 0,1,1,2....
int fibonacci(n){
    if(n==0 || n==1)
        return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

改造后

1
2
3
4
5
6
7
8
9
10
11
// 求斐波那契数列 0,1,1,2....
int fibonacci(n, k=2, prev=0, next=1){
    if(n==0 || n==1)
        return n;
    if(n==k){   // k表示目前累积到了第几项
        return prev+next;
    }
    return fibonacci(n, k+1, next, prev+next);
    // 到n==k的时候, 就无需向下递归, 直接返回前两项之和
    // 如果没到n==k, 那么继续向下累计
}
技术笔记
#算法 #数据结构 #C++ #力扣刷题 #Java转C++
有一个3升水壶和一个5升水壶, 如何精确取出4升水?
http://example.com/水壶问题/
作者
李小基
许可协议