14. 水桶测量问题

描述：你有一个 5 升 和一个 6 升 的水桶，如何精确地量出 3 升 的水？

分析问题

• 基本规则：

  1. 只能使用 两个水桶（5L 和 6L）。
  2. 只能 装满、倒空、互相倒水。
  3. 目标是 精确量出 3 升的水。

• 核心思路：

  1. 这类问题属于 贝祖定理（Bézout's Identity） 应用：如果两个数 a 和 b 互质（即最大公约数 GCD(a, b) = 1），那么可以通过整数加减得到从 1 到 GCD(a, b) 的倍数 的任意值。
  2. 6 和 5 的 GCD = 1，所以可以量出任意 1-5 升的水（因为 6 - 5 = 1）。
  3. 需要通过不断倒水，让其中一个桶最终留下 3 升。

解法 1：从 6L 桶往 5L 桶倒

1. 装满 6L 桶（6 升）。
2. 把 6L 桶的水倒入 5L 桶（5L 桶满了，6L 桶还剩 1 升）。
3. 倒空 5L 桶（5L 桶 = 0L，6L 桶 = 1L）。
4. 把 6L 桶中的 1 升水倒入 5L 桶（5L 桶 = 1L，6L 桶 = 0L）。
5. 装满 6L 桶（6L 桶 = 6L，5L 桶 = 1L）。
6. 再把 6L 桶的水倒入 5L 桶（5L 桶变成 5L，6L 桶还剩 2L）。
7. 倒空 5L 桶（5L 桶 = 0L，6L 桶 = 2L）。
8. 把 6L 桶中的 2L 倒入 5L 桶（5L 桶 = 2L，6L 桶 = 0L）。
9. 装满 6L 桶（6L 桶 = 6L，5L 桶 = 2L）。
10. 再把 6L 桶的水倒入 5L 桶（5L 桶变成 5L，6L 桶还剩 3L）。

✅ 最终 6L 桶中剩下 3 升水！

解法 2：从 5L 桶往 6L 桶倒

1. 装满 5L 桶（5L）。
2. 把 5L 桶的水倒入 6L 桶（6L 桶 = 5L，5L 桶 = 0L）。
3. 再装满 5L 桶（5L 桶 = 5L，6L 桶 = 5L）。
4. 再把 5L 桶的水倒入 6L 桶（6L 桶 = 6L，5L 桶还剩 4L）。
5. 倒空 6L 桶（6L 桶 = 0L，5L 桶 = 4L）。
6. 把 5L 桶中的 4L 倒入 6L 桶（6L 桶 = 4L，5L 桶 = 0L）。
7. 再装满 5L 桶（5L 桶 = 5L，6L 桶 = 4L）。
8. 再把 5L 桶的水倒入 6L 桶（6L 桶 = 6L，5L 桶还剩 3L）。

✅ 最终 5L 桶中剩下 3 升水！

思考与扩展

• 贝祖定理的应用：如果有两个水桶，容量分别是 aL 和 bL，且它们互质，那么一定能量出从 1L 到 min(a, b) 的任意体积。
• 更大的容量如何处理？
  • 如果是 8L 和 12L，由于 GCD(8,12) = 4，那么只能量出 4L 的倍数（4L, 8L, 12L）。
  • 只有当 水桶的容量互质 时，才能测量出任意 1L 到小桶容量的水量。

相关面试题

• 如果水桶的容量是 4L 和 6L，能否量出 3L？（答案：不能，因为 GCD(4,6) = 2，无法得到 3L。）
• 如何用程序实现找出所有可测量的水量？（可用 BFS/DFS 模拟水的倒入倒出状态。）
• 如果允许有一个无限大的水源，如何优化步骤？（可以直接装满最大桶减少步骤。）

这道题考察了 逻辑推理、数学定理（GCD/贝祖定理）、模拟思维，是一道 经典的智力题！