知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 07 - 水壶倒水 ## 题目 有两个水壶,容量分别为 **3 升**和 **5 升**。没有刻度,只能进行三种操作:装满、倒空、互相倒水。如何得到恰好 **4 升**水? ## 大白话理解 你面前有两个水壶,一个最多装 3 升,一个最多装 5 升。水壶上没有刻度,你不知道装了多少水。你可以从水龙头无限接水,也可以把水倒掉。目标是量出恰好 4 升水。 ``` 可执行的操作: 1. 装满某个壶(装满到容量上限) 2. 倒空某个壶(全部倒掉) 3. 互倒:A 壶向 B 壶倒水,直到 A 空或 B 满 ``` --- ### 解法 1:手动模拟 ``` 操作序列(5L 壶 → 3L 壶): 步骤 5L壶水量 3L壶水量 说明 ───────────────────────────────────────────────────── 初始 0 0 ① 装满 5L 壶 5 0 ② 5L → 3L 倒 2 3 3L满了 ③ 倒空 3L 壶 2 0 ④ 5L → 3L 倒 0 2 5L剩下的2L倒入3L ⑤ 装满 5L 壶 5 2 ⑥ 5L → 3L 倒 4 3 3L之前有2L,只能再装1L → 5L壶倒出1L,剩4L 得到 4 升水!✓ ``` ``` 另一条路径(3L 壶 → 5L 壶): 步骤 5L壶水量 3L壶水量 说明 ───────────────────────────────────────────────────── 初始 0 0 ① 装满 3L 壶 0 3 ② 3L → 5L 倒 3 0 ③ 装满 3L 壶 3 3 ④ 3L → 5L 倒 5 1 5L只能再装2L ⑤ 倒空 5L 壶 0 1 ⑥ 3L → 5L 倒 1 0 ⑦ 装满 3L 壶 1 3 ⑧ 3L → 5L 倒 4 0 5L装了1L,再装3L=4L 也得到 4 升水!✓ ``` --- ### 解法 2:裴蜀定理(Bézout 定理) ``` 问题抽象:用容量 a 和 b 的壶,能否得到 c 升水? 数学定理:方程 ax + by = c 有整数解的充要条件是: c % gcd(a, b) == 0 其中 gcd = 最大公约数,x 和 y 是整数(正表示装水,负表示倒水) 应用到 3L 和 5L: gcd(3, 5) = 1 4 % 1 = 0 → 有解! 解方程:3x + 5y = 4 一组解(用扩展欧几里得):x = 3, y = -1 3×3 + 5×(-1) = 9 - 5 = 4 ✓ 解读:向 3L 壶装 3 次水(3 次装满),向 5L 壶倒 1 次水(倒空) 净得水 = 3×3 - 1×5 = 9 - 5 = 4 ✓ ``` ``` 通用结论:容量为 A 和 B 的壶,能够量出的水量 = k × gcd(A, B) 其中 k 是任意非负整数,且结果不超过 max(A, B) 3 和 5:gcd=1 → 可以量出 1, 2, 3, 4, 5 任何水量 4 和 6:gcd=2 → 只能量出 2, 4(不能量出奇数水量) 6 和 9:gcd=3 → 只能量出 3, 6, 9 8 和 12:gcd=4 → 只能量出 4, 8, 12 ``` --- ### 解法 3:BFS 模拟所有状态 ``` 把每个状态定义为 (jug1, jug2),BFS 搜索从 (0,0) 到 (?,4): 状态定义:(3L壶的水量, 5L壶的水量) 初始状态:(0, 0) 目标状态:任一个壶有 4 升,即 (*, 4) 或 (4, *) (0,0) / | \ 装满3L 装满5L ... / \ (3,0) (0,5) / \ / \ 倒给5L 倒空 倒给3L 倒空 / \ / \ (0,3) (0,0) (3,2) (0,0) ... 重复 ... ``` ```java import java.util.*; /** * BFS 求水壶倒水的最短步骤 */ public class WaterJug { public List<String> solve(int jug1Cap, int jug2Cap, int target) { // BFS:状态 (j1, j2) Queue<int[]> queue = new LinkedList<>(); Map<String, String> parent = new HashMap<>(); // 记录路径 Set<String> visited = new HashSet<>(); queue.offer(new int[]{0, 0}); visited.add("0,0"); parent.put("0,0", null); String goal = null; while (!queue.isEmpty()) { int[] state = queue.poll(); int j1 = state[0], j2 = state[1]; // 检查是否到达目标 if (j1 == target || j2 == target) { goal = j1 + "," + j2; break; } // 6 种操作 List<int[]> nextStates = new ArrayList<>(); // 1. 装满壶 1 nextStates.add(new int[]{jug1Cap, j2}); // 2. 装满壶 2 nextStates.add(new int[]{j1, jug2Cap}); // 3. 倒空壶 1 nextStates.add(new int[]{0, j2}); // 4. 倒空壶 2 nextStates.add(new int[]{j1, 0}); // 5. 壶 1 → 壶 2 int pour12 = Math.min(j1, jug2Cap - j2); nextStates.add(new int[]{j1 - pour12, j2 + pour12}); // 6. 壶 2 → 壶 1 int pour21 = Math.min(j2, jug1Cap - j1); nextStates.add(new int[]{j1 + pour21, j2 - pour21}); for (int[] ns : nextStates) { String key = ns[0] + "," + ns[1]; if (!visited.contains(key)) { visited.add(key); parent.put(key, j1 + "," + j2); queue.offer(ns); } } } // 回溯路径 List<String> path = new ArrayList<>(); String cur = goal; while (cur != null) { path.add(0, cur); cur = parent.get(cur); } return path; } public static void main(String[] args) { WaterJug wj = new WaterJug(); List<String> path = wj.solve(3, 5, 4); System.out.println("步骤数: " + (path.size() - 1)); for (String p : path) { System.out.println(" → (" + p + ")"); } } } ``` --- ### 裴蜀定理详解 ``` 定理:对于整数 a, b,存在整数 x, y 使得 ax + by = gcd(a, b) 扩展到 c:ax + by = c 有整数解 ⇔ c % gcd(a, b) == 0 证明思路(不严格): 所有形如 ax + by 的数构成了 gcd(a, b) 的倍数集合 能表示的最小正整数就是 gcd(a, b) 应用到倒水问题: 操作等价于:每次改变量 = ±a 或 ±b 总水量 = a × (装满A的次数) - a × (倒空A的次数) + b × (装满B的次数) - b × (倒空B的次数) = a × x + b × y (x 和 y 是整数) 所以能得到的水量 c 必须满足:c = ax + by → c % gcd(a, b) == 0 ``` --- ## 一句话总结 两个无刻度水壶倒水问题 = 裴蜀定理:`ax + by = c` 有解 ⇔ `c % gcd(a,b) == 0`。3 和 5 的 gcd=1,所以能得到任意 0~5 的水量。可手动模拟或用 BFS 搜索最短操作序列。 --- 下一篇:[08 - 灯泡开关](./08-bulb-switch.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入