NOIP 提高 2017 第一轮 第 12 题：在n（n≥3）枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），

题目

在 $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 中硬币不合格

正确的填空顺序是（   ）。

选项

• A. b, c, a
• B. c, b, a
• C. c, a, b
• D. a, b, c

答案

D

题解

考点定位

本题考「三堆称币策略」,对应大纲 4.2.1 算法策略（难度【5】）。

解题过程

三分法：每次把硬币分三堆（A、B、C），称 A vs B：平则坏币在 C（对照 A 排大小）；不平则坏币在轻/重侧结合标记排除。三行代码的正确顺序使三分逻辑闭环：

按官方答案 a, b, c。

选 D。

易错提醒

① 每称一次把候选缩到 1/3，n 枚硬币 ⌈log₃(2n)⌉ 次；② 「过轻或过重」双向不确定是本题难点——需带正反两组对照。