1、水壶问题

有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。

你允许：

1、装满任意一个水壶

2、清空任意一个水壶

3、从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1:

输入: x = 3, y = 5, z = 4
输出: True

示例 2:

输入: x = 2, y = 6, z = 5
输出: False

1.1、解题思路

装满任意一个水壶，定义为「操作一」，分为：

（1）装满 A，包括 A 为空和 A 非空的时候把 A 倒满的情况；

（2）装满 B，包括 B 为空和 B 非空的时候把 B 倒满的情况。

清空任意一个水壶，定义为「操作二」，分为（1）清空 A；（2）清空 B。

从一个水壶向另外一个水壶倒水，直到装满或者倒空，定义为「操作三」，其实根据描述「装满」或者「倒空」就知道可以分为 4 种情况：

（1）从 A 到 B，使得 B 满，A 还有剩；（2）从 A 到 B，此时 A 的水太少，A 倒尽，B 没有满；（3）从 B 到 A，使得 A 满，B 还有剩余；（4）从 B 到 A，此时 B 的水太少，B 倒尽，A 没有满。

因此，从当前「状态」最多可以进行 8 种操作，得到 8 个新「状态」，对这 8 个新「状态」，依然可以扩展，一直做下去，直到某一个状态满足题目要求。

ContactAuthor