知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 称硬币找假币 ## 题目 12 枚硬币中有 1 枚假币(重量与真币不同,但**不知是轻还是重**)。用一个天平,称 **3 次**找出假币,并判断它是轻了还是重了。 ## 大白话理解 想象你在超市买了 12 个苹果,有人告诉你其中一个是烂的(可能更轻也可能更重),你有一个天平可以比较两堆苹果的重量。你的任务是用 3 次称量找出烂苹果。 ``` 信息论角度: 12 枚硬币 × (轻 或 重) = 12 × 2 = 24 种可能 天平每次有 3 种结果:左重、右重、平衡 3 次称量 → 3^3 = 27 种结果组合 27 > 24,所以理论上 3 次一定够! ``` ### 三分法思想 ``` 二分:每次把可能范围减半 三分:每次把可能范围分成三份——左边、右边、剩下的 天平天然就是三分工具: ┌─────────┐ │ 天平 │ │ ═══════ │ │ 左 右 │ └─────────┘ 结果分三种:左重 / 右重 / 平衡 ``` --- ### 推导全过程 #### 第一次称量:12 枚 → 分成 3 组 ``` 将 12 枚硬币编号:1~12 分成三组: A 组:{1, 2, 3, 4} B 组:{5, 6, 7, 8} C 组:{9, 10, 11, 12} 第一次:A 组 vs B 组 ╔═══════╗ {1,2,3,4} {5,6,7,8} ═══════════╤═══════════ │ ┌─────┼─────┐ │ │ │ 左边重 平衡 右边重 ``` #### 情况 1:第一次平衡 ``` 平衡 → 假币在 C 组 {9,10,11,12} 中 A 组和 B 组 8 枚都是真币(可以作为参考) 现在知道假币是 9~12 中的一个,还剩 2 次称量。 第二次:拿 3 个真币 vs {9,10,11} ┌───────────────────────┐ │ 真币 ×3 │ 9,10,11 │ ├─────────┼──────────────┤ │ 平衡 │ → 假币 = 12 │ 第三次:12 vs 真币 → 判断轻重 │ 左边重 │ → 假币在{9,10,11}且假币轻 │ │ 右边重 │ → 假币在{9,10,11}且假币重 │ └─────────┴──────────────┘ 第三次(假设假币轻,以 9,10,11 为例): 9 vs 10: 平衡 → 11 是假币(轻) 9 重 → 10 是假币(轻) 10 重 → 9 是假币(轻) 完美解决!3 次称出 ✓ ``` #### 情况 2:第一次 A 组重(或 B 组重) ``` 假设第一次:A 组 > B 组(左边重) 这意味着: ┌─────────────────────────────────────────┐ │ 如果假币在 A 组 → 假币重 │ │ 如果假币在 B 组 → 假币轻 │ │ 假币绝不在 C 组(因为 C 组没上天平) │ └─────────────────────────────────────────┘ C 组 {9,10,11,12} 都是真币!这是重要信息。 现在还剩 8 个嫌疑币:A 组 4 个(可能重),B 组 4 个(可能轻) 需要 2 次称量区分 8 种可能性。 第二次称量(关键操作——重新分组): 左边放:{1, 2, 5}(A 组 2 个 + B 组 1 个) 右边放:{3, 6, 真币}(A 组 1 个 + B 组 1 个 + 1 个真币) 剩下 {4, 7, 8} 不称(A 组 1 个 + B 组 2 个) ╔═════════════╗ {1,2,5} {3,6,真} ═══════════════════════ 三种结果分析: ┌─────────┬──────────────────────────────────────┐ │ 结果 │ 推理 │ ├─────────┼──────────────────────────────────────┤ │ 左边重 │ 1 或 2 重(A组嫌疑),或 6 轻 │ │ │ (B组嫌疑 但 6 在右边所以如果 6 轻 │ │ │ 右边轻=左边重) │ │ │ → 嫌疑:{1重, 2重, 6轻} │ ├─────────┼──────────────────────────────────────┤ │ 右边重 │ 3 重(A组在右边),或 5 轻(B组) │ │ │ → 嫌疑:{3重, 5轻} │ ├─────────┼──────────────────────────────────────┤ │ 平衡 │ 天平上的都是真币 │ │ │ → 假币在没上天平的 {4, 7, 8} 中 │ │ │ → {4重, 7轻, 8轻} │ └─────────┴──────────────────────────────────────┘ 第三次称量: 情况 A(嫌疑 {1重, 2重, 6轻}): 1 vs 2 平衡 → 6 是假币(轻) 1 重 → 1 是假币(重) 2 重 → 2 是假币(重) 情况 B(嫌疑 {3重, 5轻}): 3 vs 真币 平衡 → 5 是假币(轻) 不均衡 → 3 是假币(重) 情况 C(嫌疑 {4重, 7轻, 8轻}): 7 vs 8 平衡 → 4 是假币(重) 7 轻 → 7 是假币(轻) 8 轻 → 8 是假币(轻) 全部情况 3 次搞定 ✓ ``` --- ### 信息论解释 ``` 为什么恰好 3 次够用? 初始信息量:12 × 2 = 24 种可能(12个硬币 × 轻或重) 每次称量提供 3 种结果 → 信息量 = log₂(3) ≈ 1.585 bit 3 次称量能区分:3³ = 27 种情况 24 < 27 → 刚好够! 推广:N 个硬币最少需要 ⌈log₃(2N)⌉ 次 3 个硬币 → ⌈log₃(6)⌉ = ⌈1.63⌉ = 2 次 12 个硬币 → ⌈log₃(24)⌉ = ⌈2.89⌉ = 3 次 13 个硬币 → ⌈log₃(26)⌉ = ⌈2.97⌉ = 3 次(也够) 39 个硬币 → ⌈log₃(78)⌉ = ⌈3.97⌉ = 4 次 ``` --- ## 变体:已知假币是轻(或重) 如果明确知道假币更轻(或者更重),问题大幅简化。**三分法更高效,二分法也能做,但次数更多:** ``` 12 枚硬币,已知假币更轻 三分法(3 次): 第1次:4 vs 4 → 锁定 4 枚(轻的那边 / 平衡时未上称那组) 第2次:2 vs 2 → 锁定 2 枚 第3次:1 vs 1 → 找出假币 二分法(3 次): 第1次:6 vs 6 → 轻的那边 6 枚 第2次:3 vs 3 → 轻的那边 3 枚 第3次:1 vs 1 → 找出假币(平衡则第 3 枚是假币) ``` ### 二分法 vs 三分法 对比 | 对比维度 | 二分法 | 三分法 | |---------|--------|--------| | 每次减半/减至 1/3 | 6→3→2 | 4→2→1 | | 12 枚称量次数 | 3 次 | 3 次 | | 理论最大处理量(3次) | 2³ = 8 枚 | 3³ = 27 枚 | | 每次称量利用率 | 只用 2/3 的信息 | 用满 3 种结果 | | 适用场景 | 简单直观 | 最优解 | ### 结论 ``` 已知轻重时,三分法理论最优(每次称量利用全部 3 种结果): N 枚硬币需要 ⌈log₃(N)⌉ 次 ⌈log₃(8)⌉ = 2 次 二分也能 2 次 ⌈log₃(12)⌉ = 3 次 二分也是 3 次 ← 12 枚时打平 ⌈log₃(27)⌉ = 3 次 二分需要 5 次 ← 三分优势明显! ⌈log₃(81)⌉ = 4 次 二分需要 7 次 N > 8 时三分法开始显著优于二分法。 这也是为什么 12 枚硬币需要 3 次: - 二分:每次剩 6 个 → 3¹ 个 → 最多 8 枚用 3 次,而 12 > 8,不够! - 实际上二分法的"6 vs 6"虽然也是 1 次,但天平有 3 个结果, 你用二分只利用了其中 2 个(左重/右重),浪费了"平衡"这个信息 ``` --- ## 一句话总结 天平天然是三分工具(左重/右重/平衡),每次称量拿到 3 种结果中的一个,3 次称量能区分 3³=27 种情况。 - **已知轻重**:三分法 `⌈log₃(N)⌉` 次,12 枚只需 3 次 - **不知道轻重**:需 `⌈log₃(2N)⌉` 次,12 枚仍需 3 次(但策略复杂得多) 二分法浪费了天平"平衡"这一结果,所以效率不如三分法。关键在于每次称量后,利用已知真币作为参考重新分组。 --- 下一篇:[03 - 小白鼠试毒](./03-poisoned-wine.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入