NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 12 题

在 $n(n \geq 3)$ 枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重）,如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c 三行代码补全到算法中。 a. A ← X ∪ Y b. A ← Z c. n ← |A| 算法 Coin(A, n)

1. k ← ⌊n/3⌋   
2. 将 A 中硬币分成 X，Y，Z 三个集合，使得 |X| = |Y| = k,|Z| = n - 2k  
3. if W(X) ≠ W(Y)       //W(X), W(Y) 分别为 X 或 Y 的重量   
4. then __________   
5. else __________   
6.   ___  
7. if n>2 then goto 1   
8. if n=2 then 任取 A 中 1 枚硬币与拿走硬币比较，若不等，则它不合格； 若相等，则 A 中剩下的硬币不合格.    
9.  if n=1 then A 中硬币不合格   

正确的填空顺序是（ ）。

这题核心就是三分法找次品，拿到题先想：天平称 X 和 Y，结果只有两种可能，不等说明坏蛋在 X 或 Y 里，相等说明坏蛋在剩下的 Z 里。顺着这个逻辑，先把集合 A 更新到嫌疑范围，再更新规模 n，就能把问题规模缩小，直到 n 很小直接处理。填空顺序就是先更新 A（a），再更新 n（c），最后处理剩余情况（b），选 D。

最容易掉进的坑是把 a 和 b 的顺序搞反，误以为先排除 Z 再合并 X、Y，或者以为不等时只保留 X 或只保留 Y。其实不等时坏硬币可能在 X 也可能在 Y，必须把 X 和 Y 都放进 A 里，所以 a 行必须是 A ← X ∪ Y。另外，有些同学会忘记在更新 A 之后立刻更新 n，导致循环里 n 还是原来的大数，永远进不去 n>2 的递归，或者在 n=2 时逻辑混乱。还有一种是看到 else 分支就以为可以直接结束，忘了 else 里其实也要把 Z 放进 A，只是这时候 A 直接等于 Z，不需要再 union。

考点概念：三分法找次品

这道题考的是经典的“三分法”策略：每次把硬币分成三堆 X、Y、Z，让 X 和 Y 数量相等，然后称一次天平。

• 如果 W(X) ≠ W(Y)，说明坏硬币一定在 X 或 Y 里（因为如果坏硬币在 Z，X 和 Y 重量就必相等）。此时我们要把嫌疑范围缩小到 X∪Y。
• 如果 W(X) = W(Y)，说明 X 和 Y 都是好的，坏硬币只能在剩下的 Z 里。此时嫌疑范围就是 Z。

无论哪种情况，我们都要把新的嫌疑集合赋值给 A，然后重新计算 A 的大小作为新的 n，继续递归。只有当 n 足够小（≤2）时，才能直接通过“拿一枚和已知好币比较”或“只剩一枚”来判定。

逐空推演：逻辑与代码对应

看代码骨架： 1. 初始化 k = ⌊n/3⌋，把 A 分成 X、Y、Z，满足 |X| = |Y| = k，|Z| = n - 2k。 2. if W(X) ≠ W(Y) then __________ 3. else __________ 4. ___ 5. if n>2 then goto 1 6. if n=2 then … 7. if n=1 then …

我们按顺序填空。

第一空（第 4 行）：这是 if 分支成立的情况，即 W(X) ≠ W(Y)。根据刚才的分析，坏硬币在 X 或 Y 里，所以新的 A 应该是 X 和 Y 的并集。代码里 a 行正好是 A ← X ∪ Y，所以第一空填 a。

第二空（第 5 行）：这是 else 分支，即 W(X) = W(Y)。此时坏硬币在 Z 里，新的 A 就是 Z。代码里 b 行是 A ← Z，所以第二空填 b。

第三空（第 6 行）：无论走了 if 还是 else，我们都已经把 A 更新为新的嫌疑集合了，接下来必须更新 n 为 |A|，否则循环里 n 还是原来的大数，永远满足 n>2，陷入死循环。代码里 c 行是 n ← |A|，所以第三空填 c。

这样三个空依次是 a、b、c，对应选项 D。

为什么不能换顺序？

假设你把 a 和 b 换一下，先填 b（A ← Z）再填 a（A ← X ∪ Y），那 if 分支里 A 就被错误地设成了 Z，完全违背“不等时在 X∪Y”的逻辑，算法就错了。

假设你把 c 提前到第二行，即先更新 n 再更新 A，那在 if 分支里 n 还是原来的大数，while 条件 n>2 永远为真，程序会一直递归下去，甚至可能因为 A 还没更新导致后续 n=2 或 n=1 的判断出错。

所以顺序必须是：先根据称量结果更新 A（a），再根据 else 分支更新 A（b），最后统一更新规模 n（c）。这就是 a, b, c。

易错点再强调一遍

1. 不等时只保留 X 或只保留 Y：很多同学看到“不等”就以为坏硬币要么在 X 要么在 Y，然后随便选一边，忘了并集。其实天平只告诉我们“X 和 Y 重量不同”，没告诉我们哪边重，所以两边都可能藏着坏硬币，必须都保留。 2. 忘记更新 n：更新 A 后如果不立刻更新 n，循环条件永远为真，程序会无限递归，这是典型的死循环陷阱。 3. else 分支直接结束：else 里虽然 A 直接等于 Z，但别忘了还要更新 n，否则下一轮 n 还是大数，逻辑会乱。

考频与趋势

从题库数据看，“分支结构”这个考点总共考过 181 题，覆盖 10 个考试级别（2008-2026）。逐年分布是：2008 年 7 题、2010 年 1 题、2011 年 4 题、2012 年 5 题、2013 年 5 题、2014 年 5 题、2015 年 4 题、2016 年 12 题、2017 年 12 题、2018 年 10 题、2023 年 4 题、2024 年 8 题、2025 年 3 题、2026 年 100 题、null 年 1 题。

分赛事来看，NOIP 普及组初赛考了 48 题，GESP 二级 45 题，GESP 一级 25 题，NOIP 提高组初赛 17 题，GESP 三级 13 题，GESP 五级 11 题，GESP 四级 10 题，GESP 六级 9 题，GESP 八级 2 题，GESP 七级 1 题。

这道题本身是 2017 年 NOIP 提高组初赛第 12 题，属于分支结构里的“算法流程填空”子类。从历年数据看，2016 年、2017 年、2018 年连续三年在 NOIP 提高组初赛里出现了大量分支结构题（12 题、12 题、10 题），说明这类题型在提高组初赛里非常稳定。

预测

结合“分支结构”在 NOIP 提高组初赛的考频（17 题）以及近年来的趋势（2016-2018 连续高题量），可以合理预测：未来几年 NOIP 提高组初赛仍会保持对分支结构、递归算法、三分法等逻辑题的高频考查，尤其是需要学生根据条件判断选择不同分支并更新状态的题目。这类题往往以“填空”或“改错”形式出现，考察对算法流程的精确理解。

如果数据不足以支撑更细的预测（比如具体到某一年是否会出现类似题目），那就诚实说“暂无足够依据预测”。这里我们有足够的历年数据，所以可以给出上述预测。

小结

这道题的正确答案是 D：a, b, c。解题关键是抓住“三分法”的核心逻辑——不等时在 X∪Y，相等时在 Z，然后按顺序更新集合和规模。记住别把 a 和 b 顺序搞反，也别忘记更新 n，就能稳稳拿分。