有 8 个外观一样的球，其中一个略重，如何设计策略，用最少的称重次数找出这个球？
1️⃣ 考察意图
这道题看似是经典智力题，但面试官真正想考察的是信息论思维与工程化抽象能力。它属于“逻辑推理+数学建模”类型，刁钻点在于：候选人是否能把“称重”抽象为“每次获得3种结果（左重/右重/平衡）”，并推导出信息论下界 \log_3(8)\approx 1.89，从而证明2次是最优解。答好了能展示：① 从具体问题提炼通用模型的能力；② 对“最优解”的严格证明而非仅凭直觉；③ 将算法思想（如三进制编码）迁移到其他场景（如二分查找、故障检测）的潜力。
2️⃣ 标准答
核心策略：三分法 + 信息论下界
- 分组与首次称重
- 将8个球分成3组：A组（3个）、B组（3个）、C组（2个）。
- 称A组 vs B组。
- 情况1：平衡 → 重球在C组（2个）。第二次称C组两个球，重的即目标。
- 情况2：不平衡 → 重球在较重的那一组（3个）。第二次从该组任取2个称重：若平衡，第三个为重；否则重的即目标。
- 结果：无论哪种情况，都只需2次。
- 为什么2次是最优？——信息论证明
- 每次称重有3种结果（左重/右重/平衡），2次称重最多区分3²=9种可能性。
- 8个球中找1个重球，共有8种可能（每个球可能是重的）。
- 信息论下界：\log_3(8)\approx 1.89，向上取整为2。
- 工程取舍：若用二分法（每次分两组），2次只能区分4种可能，无法覆盖8种情况。三分法利用了天平的三态输出，是信息效率最高的策略。
- 实际落地的坑 + 解法
- 坑1：误以为“称重次数”等于“比较次数”。例如有人会先称4v4，但第一次只能知道哪边重，无法定位到具体球，仍需2次，总次数为3次（因为4v4后重的一侧有4个球，再称2次才能找出）。
- 解法：严格按信息论计算，每次称重必须最大化信息增益。三分法每次将可能性缩小到≤3个，而二分法只能缩小到≤4个。
- 坑2：扩展场景中球数不是3的幂次（如7个球）。
- 解法：分组时保证每组数量接近，且剩余组不超过3。例如7个球分3/3/1，首次称3v3：平衡则剩余1个即目标；不平衡则重侧3个再称1次。总次数仍为2次（\log_3(7)\approx 1.77，上取整2）。
- 坑3：面试官追问“如果不知道球是重还是轻，怎么办？”
- 解法：此时每个球有2种可能（重或轻），总可能性为8×2=16种。2次称重最多区分9种，不够；3次可区分27种，足够。策略需用三进制编码，例如将球编号0-7，每次称重按编码位分组。
- 推广到n个球
- 最少次数 = \lceil\log_3(n)\rceil（已知轻重）或 \lceil\log_3(2n)\rceil（未知轻重）。
- 算法本质是三进制决策树，每个节点对应一次称重，叶子节点对应目标球。
- 工程类比：类似二分查找的“三分查找”变体，但天平的三态输出比比较器的二态输出信息量更大。
3️⃣ 答题模板（30 秒电梯版）
“这个问题我从信息论、分组策略、扩展推广三个层面回答。信息论层面：每次称重有3种结果，2次可区分9种情况，而8个球只有8种可能，所以2次是下界。分组策略：将8个球分成3/3/2，首次称3v3，根据结果缩小范围到2或3个球，第二次即可找出。扩展层面：若球数n，最少次数为\lceil\log_3(n)\rceil；若不知轻重，则为\lceil\log_3(2n)\rceil。总结一句：核心是利用天平的三态输出最大化信息增益，而非直觉上的二分法。”
4️⃣ 高频追问 & 应对
追问 1：如果球数增加到12个，且不知道是重还是轻，最少需要几次？策略是什么？
最少需要3次。因为12个球×2种可能=24种情况，3次称重可区分3³=27种，足够。策略：第一次将12个球分成4/4/4，称两组4v4。若平衡，则重/轻球在第三组4个中，且已知标准球重量，后续2次可找出；若不平衡，则记录哪边重，并利用标准球（第三组）进行第二次称重（例如交换部分球，引入标准球），通过结果模式判断重/轻及具体球。具体可参考经典“12球问题”的三进制编码解法。
追问 2：这个策略和二分查找相比，时间复杂度有什么区别？
二分查找每次比较减少一半可能性，时间复杂度O(\log_2 n)；而天平称重每次减少到1/3，时间复杂度O(\log_3 n)。虽然常数因子不同，但\log_3 n \approx 0.63\times\log_2 n，实际效率提升约37%。但注意：二分查找适用于有序数组的“大于/小于”比较，而天平称重适用于“相等/不等”判断，两者应用场景不同。工程中类似场景如“三路快排”的分区思想，也是利用三态输出优化。
追问 3：如何用代码实现一个通用称重算法，输入球数n和轻重已知标志，输出最少次数和策略？
核心是构建三进制决策树。伪代码：1. 计算最少次数k=\lceil\log_3(n)\rceil（已知轻重）或k=\lceil\log_3(2n)\rceil（未知）。2. 为每个球分配一个k位的三进制编号（0,1,2）。3. 第i次称重时，将所有编号第i位为0的球放左盘，为1的放右盘，为2的不放。4. 根据天平结果（左重/右重/平衡）确定该位的值。5. 最终所有位的值组合成目标球的编号。注意：若未知轻重，需额外编码“重/轻”信息，可用正负号表示。实际实现时需处理球数不是3的幂次的情况，用虚拟球补全。
5️⃣ 避坑 · 常见错误答法
- ❌ 直接说“先称4v4，然后重的一侧再称2v2，最后称1v1，需要3次” → ✅ 正确切入：先分析信息论下界，证明2次可行，再给出3/3/2分组策略。4v4是典型的低效策略，因为第一次称重只将可能性从8缩小到4，信息增益不足。
- ❌ 认为“2次是猜出来的，没有严格证明” → ✅ 必须给出信息论推导：\log_3(8)\approx 1.89，上取整为2。同时说明二分法只能区分2^2=4种，不够用。
- ❌ 在扩展问题中，直接套用二分法公式“\log_2(n)” → ✅ 正确使用\log_3(n)，并解释天平的三态输出比比较器的二态输出信息量更大。
6️⃣ 简历呼应
- 如果你有算法竞赛/数学建模项目：从“信息论下界证明”切入，展示你如何将具体问题抽象为决策树模型，并给出严格数学推导。可提及你曾用类似思想解决“毒药测试”“故障检测”等问题。
- 如果你只做过传统后端开发：用“二分查找 vs 三分查找”类比，说明你理解不同场景下信息效率的差异。强调工程中“最大化每次操作的信息增益”是通用优化原则，例如数据库索引的B+树扇出选择。
- 如果你是校招无项目：聚焦“三进制编码”的数学原理，展示你从经典智力题中提炼出通用算法模型的能力。可提及你实现过一个小工具，输入球数自动输出称重策略，并用测试用例验证了所有n≤100的情况。
- 《信息论基础》（Thomas Cover）第2章：熵与信息论下界
- 《算法导论》第9章：中位数与顺序统计量（决策树模型）
- 论文：”The 12-Ball Problem” by J. H. Conway（经典三进制编码解法）
- 博客：”How to Solve the 8-Ball Problem with Information Theory” (Medium)
- 工具：Python实现通用称重算法库（GitHub搜索”balance-scale-solver”）