水桶取水：3L + 5L 桶如何取 4L？
一句话结论（30s）
结论先行：3L 和 5L 桶能取出 4L，因为 gcd(3,5)=1 而 4 是 1 的倍数，贝祖定理保证 ax+by 能凑出 gcd 的所有倍数。本质是”是否可解”交给数论（贝祖定理/扩展欧几里得），“最少步数”交给图搜索（BFS 最短路径）。
核心原理（2min）
经典解法反复互倒：5L 满倒入 3L 剩 2L，清空 3L，把 2L 倒入 3L，再灌满 5L，倒入 3L 至满即剩 4L，共 5 步。数学上 4 = 3×(-2) + 5×2 正是贝祖等式的一组解。通用判断：目标必须是 gcd(a,b) 的倍数（如 4L/6L 桶 gcd=2，只能取偶数）。扩展欧几里得算法可编程求出 ax+by=gcd(a,b) 的整数解再缩放；而最小步数则把每个 (桶1水量, 桶2水量) 状态视为图节点、倒水操作为边，用 BFS 求最短路径。
底层深入（5-10min）
经典解法
1. 5L桶满 → 倒入3L桶 → 5L桶剩2L
2. 倒空3L桶
3. 5L桶的2L倒入3L桶（3L桶中2L，还剩1L空）
4. 再次灌满5L桶
5. 5L桶倒入3L桶直到满（加1L） → 5L桶剩4L步数：5 步。操作：反复互倒凑出余数。
💭 思考：为什么反复互倒就能凑出 4L？——因为每次倒水的本质是让两桶水量产生”差/余数”变化：5-3=2、3-2=1，这些余数正是 gcd(3,5)=1 的线性组合，反复操作其实是在手工执行贝祖等式 3×(-2)+5×2=4。
数学本质：贝祖定理（Bézout’s Identity）
对于整数 a 和 b，存在整数 x 和 y 使得 ax + by = gcd(a, b)。
这里 a=3, b=5, gcd(3,5)=1，所以可以取到 1 的整数倍的所有值——包括 4。
4 = 3×(-2) + 5×2 = -6 + 10 = 4。数学上”取 4L”可行，因为 gcd(3,5)=1 且 4 是 1 的倍数。
如果 a=4, b=6, gcd=2 → 只能取到 2 的整数倍（0/2/4/6/8…），取不到 1/3/5/7。
💭 思考：为什么 4L/6L 桶取不出 1L、3L、5L？——因为无论怎么倒，水量变化量永远是 gcd=2 的倍数，两桶水量之差、之和都只能是偶数，奇数目标永远无法到达。
通用解法：扩展欧几里得算法
// 找 ax + by = gcd(a,b) 的整数解
int[] extendedGcd(int a, int b) {
if (b == 0) return new int[]{a, 1, 0}; // gcd=a, x=1, y=0
int[] rec = extendedGcd(b, a % b);
int gcd = rec[0], x1 = rec[1], y1 = rec[2];
return new int[]{gcd, y1, x1 - (a / b) * y1};
}得到 gcd(a,b) 以及一组整数解 (x, y)。然后判断目标是否 gcd 的倍数 → 是则缩放。
倒水过程与算法解的对应
贝祖定理告诉我们”是否可解”。倒水的”最小步数”问题则对应最短路径搜索——每个倒水状态（桶1水量, 桶2水量）是图中的节点，倒水操作是边，BFS 求最短路径。
💭 思考：为什么”是否可解”和”最少步数”要用两套工具？——因为贝祖定理只回答存在性、给不出最少操作数；而每一步倒水都是状态转移、天然构成图，最少步数就是最短路径，BFS 按层扩散正好求最短路。
总结
水桶取水 = 贝祖定理（判断可解性）+ BFS（最小步数）。用数学判断可行性，用算法求最优解。通用方法——扩展欧几里得——可编程求解任意容量、任意目标的水桶问题。
章末提问
追问 1：为什么 gcd(a,b) 不为 1 时就取不出任意水量？
回答思路：结论是只能取出 gcd 的整数倍，因为每次倒水操作引起的水量变化都是 gcd(a,b) 的倍数，所有可达状态都被 gcd 整除，目标不是 gcd 倍数就永远到不了。
追问 2：贝祖等式的系数出现负数（如 3×(-2)）怎么理解？
回答思路：结论是负系数对应”倒掉”的方向性操作，数学解只证明存在性、不直接给出物理步数；真正的最少步数要用 BFS 在状态图上求最短路径。
追问 3：如何用 BFS 求最少步数？
回答思路：结论是把 (桶1水量, 桶2水量) 当作状态节点，六种操作（装满/倒空/互相倒）当作边，从 (0,0) 开始 BFS 按层扩展，第一次到达目标状态的层数就是最少步数。