1. 面试中的“12枚硬币”问题一道经典的逻辑思维试金石如果你在技术面试尤其是算法或逻辑思维考察环节遇到过“12枚硬币称重”这道题那你一定印象深刻。它不像LeetCode上的动态规划那样有明确的套路也不像系统设计那样可以侃侃而谈。它更像一个精巧的谜题安静地躺在那里考验着你将复杂问题拆解、抽象、并系统化解决的能力。很多面试官青睐这道题不是因为它能筛选出“最聪明”的人而是因为它能清晰地暴露一个候选人的问题解决框架你是慌乱地开始穷举还是冷静地定义约束你是满足于找到一个答案还是追求最优的解决方案这道题背后是信息论、决策树和严谨逻辑推理的完美结合。今天我们就来彻底拆解这个经典问题不仅告诉你“怎么做”更要讲清楚“为什么可以这么做”以及在实际面试中如何优雅地展示你的思考过程。2. 问题定义与约束条件一切推理的起点面对任何问题第一步永远是精确理解题意。模糊的需求是bug的温床也是面试中失分的开始。“12枚硬币称重”问题通常有以下几种常见变体我们必须先锁定我们讨论的是哪一种。2.1 标准问题描述最经典的版本是这样的你有12枚外观完全相同的硬币其中11枚重量相同真币1枚是假币其重量可能略轻也可能略重。你有一架天平不是电子秤天平只能比较左右两边的重量告诉你左边重、右边重或两边相等这三种结果。请问最少需要称几次才能保证找出那枚假币并确定它是轻了还是重了这个描述包含了几个至关重要的约束条件它们是整个解题逻辑的基石硬币总数12枚。这个数字不是随便选的它与称量次数有直接数学关系。假币数量1枚。问题复杂度是线性的不是多枚假币。假币特性重量与真币不同但不知是轻是重。这是关键如果已知假币是轻是重问题会简单很多。未知轻重使得每次称量获得的信息量最大化也最考验策略。工具限制一架天平。这意味着我们无法获得绝对值比如克数只能获得相对比较结果左重、右重、平衡。每一次称量都是一次“三态输出”的实验左倾、右倾、平衡。目标保证找出假币并知其轻重。“保证”意味着你的策略必须覆盖所有可能性无论假币是轻是重也无论它在哪一个位置你的方案都能在限定步骤内解决。不是平均次数而是最坏情况下的次数。2.2 为什么是“最少称几次”理解信息论边界面试官问“最少需要几次”其实是在问这个问题的理论下界。我们可以从信息论的角度做一个快速估算这能体现你的理论素养。每次称量天平有3种可能的结果左重、右轻、平衡。称量k次理论上最多可以区分 3^k 种不同的“状态”或“可能性”。我们的问题有多少种可能性呢假币可能是12枚中的任何一枚并且对于每一枚它都有“轻”或“重”两种可能。所以总共有 12 * 2 24 种可能的初始状态注意所有硬币都是真币的状态不存在因为已知有一枚假币。因此我们需要通过称量结果序列来唯一确定这24种可能性中的一种。这就要求 3^k 24。计算一下3^2 9 24 3^3 27 24。所以从理论上讲3次称量是可能完成任务的。如果 k2最多区分9种情况小于24所以2次称量绝对不可能保证解决。这个简单的计算立刻告诉我们答案至少是3次并且3次是理论上可行的。这就把问题从“要多少次”聚焦到了“如何用3次实现”。在面试中直接说出这个信息论下界的分析是非常加分的。3. 核心策略与决策树构建如何设计三次称量知道至少要3次和真正设计出3次的方案中间隔着一道巨大的鸿沟。这里最核心的策略是分组与信息最大化利用。你不能第一次称量就指望运气好找到假币必须设计一个无论第一次结果如何都能为后续称量留下清晰、可控路径的方案。3.1 第一次称量的设计哲学第一次称量是基石。一个糟糕的第一次称量会导致后续情况分支混乱无法在剩余两次称量内解决。我们的目标是让第一次称量的三种结果左重、右重、平衡所对应的剩余可能性尽可能平均地分配到三个分支上并且每个分支剩余的可能性数量不能超过后续称量能解决的上限。根据信息论第一次称量后每个分支最多有 3^(k-1) 3^2 9 种可能性需要区分。所以我们第一次称量要确保无论出现哪种结果剩下的“嫌疑”可能性不超过9种。一个经典且正确的第一次称量方案是将12枚硬币分成三组每组4枚记为A组、B组、C组。 第一次称量A组4枚 vs B组4枚。我们来分析这次称量产生的三个结果分支分支一天平平衡。这意味着A组和B组的8枚硬币都是真币。假币一定在未参与称量的C组4枚中。同时我们获得了至关重要的标准重量参考——A组和B组的任何一枚硬币都是真币。这个分支下剩余可能性是假币在C组的4枚中且不知轻重。共4 * 2 8种可能性。8 9符合要求。分支二天平左重A B。这意味着假币要么在A组且为重币要么在B组且为轻币。C组的4枚可以暂时标记为真币作为参考。这个分支下剩余可能性是A组4枚中的一枚是重的假币或B组4枚中的一枚是轻的假币。共4 4 8种可能性。注意这里“轻重”是绑定的A组嫌疑则必重B组嫌疑则必轻所以不是4*2而是44。8 9符合要求。分支三天平右重A B。这与分支二对称。假币要么在A组且为轻币要么在B组且为重币。C组为真。剩余可能性也是8种。可以看到这个分组策略完美地将24种初始可能性均匀地分配到了三个分支每个分支承接8种可能性都没有超过后续2次称量能处理的9种上限。这就是最优设计的体现。3.2 第二次称量的分治策略第一次称量后我们进入了三个不同的分支。每个分支都是一个子问题但子问题的“已知信息”不同。我们必须针对每个分支设计第二次称量。这里以最复杂的“天平不平衡”分支例如左重AB为例来详解因为“平衡”分支相对简单。分支第一次称量 A B已知嫌疑硬币在A1, A2, A3, A4 (可能为重) 或 B1, B2, B3, B4 (可能为轻)。C1~C4为标准真币。现在我们有8个嫌疑对象需要设计第二次称量使得无论结果如何第三次称量都能一锤定音。关键在于混入已知的真币C组并打破原有的分组以获取新的信息维度。一个经典的第二次称量方案是 左边托盘A1, A2, B1, B2, C1 即2枚可能重的A 2枚可能轻的B 1枚已知真币C 右边托盘A3, A4, B3, C2, C3 即2枚可能重的A 1枚可能轻的B 2枚已知真币C 注意这里A4和B4没有参与第二次称量。这个配置非常精妙它混合了不同类型的嫌疑币和真币。我们来推演第二次称量的三种结果第二次称量平衡这意味着左右托盘上的所有硬币都是真币。那么假币一定在未参与第二次称量的两枚硬币中A4可能重和B4可能轻。第三次称量就非常简单了拿A4与一枚已知真币比如C1比较。如果A4重则它是假币重如果平衡则B4是假币轻如果A4轻这不可能因为A4只可能是重。第二次称量左重天平方向改变了第一次是A组重现在是左边重。这意味着什么左边托盘重了。观察左右托盘的组成左边有(A1,A2,B1,B2,C1)。其中C1是真币B1,B2是可能轻的币它们如果导致左边重那只能是它们其实是真币轻币不会导致左重。所以B1,B2嫌疑下降。右边有(A3,A4,B3,C2,C3)。其中C2,C3是真币。导致左重的可能性集中在左边托盘中的A1或A2是重假币使得左边更重或者右边托盘中的B3是轻假币使得右边更轻相对左边就重了。所以嫌疑范围缩小到{A1(重), A2(重), B3(轻)}共3种可能性。第三次称量足以解决例如比较A1和A2平衡则B3为轻假币否则重的那枚是假币。第二次称量右重分析与“左重”对称。嫌疑范围会缩小到{A3(重), A4(重), B1(轻), B2(轻)}不这里需要仔细分析。右重意味着右边重了。可能的情况是右边托盘中的A3或A4是重假币或者左边托盘中的B1或B2是轻假币。所以嫌疑范围是{A3(重), A4(重), B1(轻), B2(轻)}共4种可能性。这仍然在第三次称量可解决的范围内例如比较A3和A4再结合与真币的比较。通过这样设计第二次称量成功地将8种可能性分散到三个更小的子集中2个3个4个每个子集都能在最后一次称量中被唯一确定。3.3 第三次称量的收官之战第三次称量通常是最简单的因为经过前两次嫌疑范围已经缩小到2-4枚硬币并且我们拥有充足的真币作为参考。此时的目标是一次比较直接锁定唯一假币并判断轻重。策略通常是如果嫌疑对象只剩2枚且已知它们一个可能重、一个可能轻如上面的A4和B4只需取其中一枚与真币比较。如果嫌疑对象是2-3枚同类型都可能重或都可能轻只需将它们互相比较或与真币比较一次。如果嫌疑对象是3-4枚混合类型需要设计一个比较使得三种结果能映射到不同的硬币上。这通常需要利用已知的真币来构造比较组。分支第一次称量平衡这个分支最简单。假币在C组4枚中不知轻重。第二次称量可以C1, C2, C3 vs 三枚真币来自A或B组。如果平衡则C4是假币第三次称C4与真币即知轻重。如果不平衡假设左重C1,C2,C3 真币则假币在C1,C2,C3中且为重。第三次只需比较其中两枚如C1 vs C2平衡则C3重否则重的那个是假币。整个决策树就像一棵三叉树每一次称量都是一个三路分支最终所有叶子节点24种可能性都在深度为3的地方被唯一标识。4. 面试实战如何展示你的思考而不仅仅是答案在面试中直接背诵答案价值有限。面试官想看到的是你解决陌生逻辑难题的过程。以下是我建议的答题框架澄清问题首先复述问题并确认所有约束。“请允许我确认一下我们有12枚硬币一架天平一枚假币不知轻重目标是保证找出并知轻重对吗”这显示你的严谨。理论分析关键加分项不要急于说方案。先分析理论下限。“这是一个信息论问题。每次称量有3种结果称k次最多区分3^k种状态。我们有12枚硬币*2种轻重可能24种状态。所以需要3^k 24k最小为3。因此理论上3次是可能的2次不可能。我们的目标是找到一个3次的策略。”这立刻将你与只会蛮干的候选人区分开。阐述核心策略“核心策略是分组和利用信息最大化。第一次称量必须设计成无论什么结果剩余的可能性不超过9种因为3^29以便后续两次能解决。”逐步推演边画边说这是最重要的部分。向面试官要一张纸或白板。画决策树在顶部写下“12硬币24种状态”。第一次称量画出第一次称量方案如A组4 vs B组4。画出三个分支平衡、左重、右重。在每个分支下写出剩余的嫌疑集如平衡C组4枚8种状态左重A组可能重或B组可能轻8种状态。强调这个分组的均衡性。第二次称量选择一个分支通常是左重进行详细推演。画出你设计的第二次称量方案如混合A、B、C组硬币。再次画出三个子分支平、左重、右重并分析每个子分支下嫌疑如何缩小到2-4个。第三次称量展示对于第二次称量后的每个小嫌疑集如何用一次比较收官。可以只详细演示一个路径。总结与验证“通过这样一棵三层的决策树我们确保了24种初始状态的每一种都有一条唯一的、长度为3的称量结果路径与之对应。因此3次称量可以保证解决。”如果你时间充裕或面试官追问可以补充变体讨论“如果硬币数量是13枚呢3^327 26理论上3次也可能但第一次分组需要更精巧因为13无法被3整除。这是一个更难的挑战。”通用化思考“这本质上是利用三进制编码给硬币贴标签。每次称量结果左重、右重、平可以看作三进制的0,1,2。我们需要为24种状态分配一个唯一的三进制编码长度为3。称量设计就是在解码这个编码。”5. 常见误区与避坑指南在实际思考和面试表述中有几个高频误区需要避免盲目二分这是最大的陷阱。很多人下意识想到“二分法”但天平不是二分是三分左、右、平。二分法思维会导致你总想分成两堆忽略了“平衡”结果所蕴含的“全部是真币”这一巨大信息量。正确思路是“三进制”思维。第一次称量随意分组比如分成6 vs 6。如果天平不平衡你只知道假币在这12枚中但不知道轻重倾向剩余可能性是12*224种第二次称量根本无法处理。必须确保第一次称量后每个分支的剩余可能性≤9。忽略“标准真币”的价值在第一次称量后无论是平衡还是不平衡我们都能获得一批确定无疑的真币。后续称量中巧妙地混入这些真币是缩小嫌疑范围的关键手段。很多错误的方案就是因为后续称量只在嫌疑币内部比较没有引入真币这个“参照物”。只讲方案不讲证明给出了一个3次称量的步骤但无法向面试官证明这个方案能“保证”覆盖所有情况。面试官可能会追问“如果假币是A1且重你的方案一定能找到吗如果假币是B2且轻呢”你需要能沿着决策树走通所有路径。在讲解时主动选择一条路径走到底并提及其他路径类似能体现你思维的完整性。混淆“找出假币”和“找出并知轻重”如果目标只是找出假币而无需知道它是轻是重那么3次称量可以处理更多硬币最多13枚。但标准问题是要求知道轻重的这增加了难度因为你需要区分“轻”和“重”这两种状态。务必在开始时明确目标。这道“12枚硬币”问题就像一把尺子能量出思考的深度与广度。它告诉我们解决复杂问题不是靠灵光一现而是靠扎实的步骤定义问题、理论分析、设计策略、系统推演、验证完备性。掌握它不仅是为了通过某一场面试更是为了锻炼那种面对模糊挑战时能一步步理清头绪、构建解决方案的底层能力。