两个水桶

说明

给定两个容量不同的桶，以及先装满哪个桶，通过有策略地在两个桶之间倒水，确定量出精确升数需要多少次操作。

你的解答必须遵守以下规则：

• 一次只能执行一个操作。
• 总共只有 3 种可能的操作：
  1. 把一个桶倒入另一个桶，直到满足以下任一条件： a) 第一个桶为空 b) 第二个桶已满
  2. 清空一个桶，另一个桶不变。
  3. 装满一个桶，另一个桶不变。
• 执行一次操作后，不能出现起始桶为空而另一个桶已满的状态。

你的程序接收以下输入：

• 一号桶的容量
• 二号桶的容量
• 需要量出的目标升数
• 先装满哪个桶，一号桶还是二号桶

你的程序应确定：

• 达到目标升数所需的总操作次数，包括第一次装满起始桶
• 最终哪个桶里是目标升数，一号桶还是二号桶
• 另一个桶里还剩多少升

注意：只要任意一个桶发生变化，都算作 1 次操作。

示例： 一号桶最多能装 7 升，二号桶最多能装 11 升。 假设在某一时刻，一号桶里有 7 升，二号桶里有 8 升（7,8）。 如果你清空一号桶，二号桶不变，两个桶分别剩下 0 升和 8 升（0,8），这算作一次操作。 相反，如果你把一号桶倒入二号桶，直到二号桶装满，结果一号桶里有 4 升，二号桶里有 11 升（4,11），同样只算作一次操作。

另一个例子： 一号桶能装 3 升，二号桶最多能装 5 升。 题目要求你必须从一号桶开始。 所以你的第一个操作是装满一号桶。 第二个操作你选择清空一号桶。 对于第三个操作，你不能装满二号桶，因为这会违反第三条规则：任何操作之后，都不能出现起始桶为空而另一个桶已满的状态。

由 Lindsay Levine 在 Fullstack Academy 用 <3 写成。

---

来源

倒水问题