Die Hard Problem（水壶问题）--算法中的数学思想

0x01.问题

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
1-装满任意一个水壶
2-清空任意一个水壶
3-从一个水壶向另外一个水壶倒水，直到装满或者倒空

C++函数形式为    bool canMeasureWater(int x, int y, int z) 

此题是著名的水壶问题

0x02.分析

对于每一种水壶，我们存在三种操作，要判断最后是否能够凑出z的水量，毫无疑问可以用搜索，深搜广搜都可以，但是对于这个数学问题来说，还是暴力了一点。

我们思考一下，每进行一次操作，对水的总量产生的影响是多少呢？

这里总共有几种可能的状态，我们穷举一下：

• 假设现在x和y均为空，那么操作对水产生的影响就是+x，或者+y。
• 假设现在x和y均为满，那么操作对水产生的影响就是-x，-y。
• 假设x是满的，y是空的，那么操作产生的影响应该是-x，或者+y。
• 假设x是空的，y是满的，那么操作产生的影响应该就是+x，或者-y。
• 假设x不空不满，y是空的，那么操作产生的是+y，为什么呢？ 难道不可能是将x倒掉，或者将x倒满，吗？其实这种操作无意义，因为将x倒掉，等于初始x就是空的情况，将x加满，等于初始状态x就是满的情况。
• 假设x不空不满，y是满的，根据上面的推论，应该是-y。
• 假设x是满的，y是不空不满的，应该是-x。
• 假设x是空的，y是不空不满的，应该+x。
• 假设x不空不满，y不空不满，这种情况是不存在的，因为根据已知的操作，必须有一个壶是空的或满的。

到这里所有可能的情况就穷举完成了，我们总结一下，操作一次，对总水量的影响应该可能是+x，+y，-x，-y。

既然就这些情况，那么进行若干次操作，如果可以凑出这么多的水量，那么肯定应该满足ax+by=z，a和b为任意常数，分别代表操作一次产生的影响，这个表达式就包含了上述所有的情况。

那么怎么求解这个表达式呢?

穷举的话，肯定费时费力，这其实是著名的 裴蜀定理 ，根据裴蜀定理，我们可以得出，当且仅当，z是a和b的最大公约数的倍数时，方程有解。

关于 裴蜀定理 ，你可以前往了解 ： 戳我前往

因为没有说明x，y，z取值的具体情况，所以我们还要考虑它们是否等于0的情况。

• 如果z=0，明显满足。
• 如果x+y<z，一定不满足。
• 如果x=0，并且y=0，肯定不满足。
• 如果x=0但y！=z，不满足。
• 如果y=0但x！=z，也不满足。

其它情况，只要正常判断就行了。

0x03.解决代码（最优代码）

class Solution {
public:
    int gcd(int x, int y) {
        return x == 0 ? y : gcd(y%x, x);
    }
    bool canMeasureWater(int x, int y, int z) {
        if(z==0) return true;      
        if(x==y&&y==0) return false;
        if(x==0&&y!=z) return false;
        if(y==0&&x!=z) return false;
        if(x+y<z) return false;
        return z%gcd(x,y)==0;
    }
};

时间复杂度取决于辗转相除法的效率，空间复杂度为O（1）

ATFWUS --Writing By 2020–03–21