- 正确答案：最少需要称2次（在已知轻重方向的前提下），或3次（在完全未知该球是偏轻还是偏重的情况下）。 - 解答思路：首先明确问题的两种常见变体：（1）已知异常球重量不同，且明确知道它是“更轻”或“更重”——此时可用2次称量找出；（2）仅知9个球中有一个重量不同（不知轻/重），其余8个等重——这是经典天平称重问题，需3次称量保证必能定位且判明轻重。我们按最通用、面试常考的第二种情况（未知轻重）展开分析：第一次称量：将9球分为三组，每组3个：A={1,2,3,4,5,6}？不对——应均分三堆，即每堆3个：A=[1,2,3]，B=[4,5,6]，C=[7,8,9]。称A vs B（即左盘放1,2,3；右盘放4,5,6）： - 若平衡 → 异常球在C组（7,8,9）中，且不知轻重； - 若不平衡（比如A < B）→ 异常球在A∪B共6球中，且已获得方向线索：要么A中有一球偏轻，要么B中有一球偏重。第二次称量需充分利用第一次结果进行信息压缩： - 情况1（A==B）：异常在{7,8,9}。取7,8与两个已知正常球（如1,2）称：7+8 vs 1+2。 * 若平衡 → 9是异常球，再用任意一次称量（如9 vs 1）即可知轻重（但注意：我们目标是“保证找出”，而题目问“称几次”，需在最坏情况下保证，因此必须在第3次完成判定）； * 若7+8 < 1+2 → 要么7轻，要么8轻； * 若7+8 > 1+2 → 要么7重，要么8重；此时第三次称7 vs 8即可：若7<8 → 7轻；若7>8 → 8轻；若相等 → 矛盾（不可能，因已知7或8异常），故实际不会等；但注意：该分支下我们尚未确认是轻还是重，所以7 vs 8的结果还需结合前次不等号方向推断——更稳妥做法是：第二次称7 vs 8（而非vs正常球）： * 若7=8 → 9异常，第三次称9 vs 1得轻重； * 若7≠8 → 已知{7,8,9}中仅一个异常，且7≠8说明异常就在7或8中，但还不知轻重——然而此时我们没有外部参考！所以该策略信息不足。因此标准解法是第二次必须引入已知正常球。标准最优策略（三次称量完备解）：第一次：1234 vs 5678（注意：不是3 vs 3，而是4 vs 4，留1个不称？但9个球无法4-4-1平分，且4 vs 4会降低信息量）。正确分组仍是3-3-3。 ✅ 经典三次解法（信息论+决策树验证）：天平每次有3种结果：左倾（L）、右倾（R）、平衡（E）→ 每次称量提供 log₂3 ≈ 1.585 bit 信息。总可能性：9个球 × 2种异常模式（轻或重） = 18种可能状态。 3次称量最多区分 3³ = 27 种结果 ≥ 18 → 理论可行。 2次仅 3² = 9 < 18 → 不足，故下界为3次，且存在构造性算法达成。构造性三次称量方案（编号1~9）：第一次：称 [1,2,3,4] vs [5,6,7,8] - 若平衡 → 异常是9号球。第二次称9 vs 1：若9<1则9轻；若9>1则9重；→ 共2次？但等等：题目要求“找出那个不同的球”，是否包含确定轻重？通常校园题隐含“找出并确认其轻重”，故9号需1次验证，即总共2次？矛盾？ ⚠️ 关键澄清：题干“九个小球一个重量不同”未说明是否需判断轻重。但所有权威算法题（如ACM、Google面试题）默认要求**唯一确定是哪一个球，且明确它是轻还是重**。因为仅找出来不判轻重，在工程上无法修复（比如质检剔除时需知道超标方向）。因此状态空间确实是9×2=18。而[1-4] vs [5-8]第一次称： - 平衡 → 9异常，第二次9 vs 1即可知轻重 → 共2次。但这是最好情况，题目问“称几次”通常指**最坏情况下的最小次数**（即minimax策略），因此必须覆盖所有路径中最长路径。 - 不平衡：假设左盘轻（1-4 < 5-8），则异常球在1-8中，且可能是1-4中某球偏轻，或5-8中某球偏重 → 共4+4=8种可能。第二次称量需将这8种可能压缩至≤3种（因第三次最多分辨3种）。例如：称 [1,2,5] vs [3,6,9]（9是已知正常球，因第一次平衡才知9正常，但此处第一次不平衡，9未参与，故9是正常球！✅ 因第一次是1-4 vs 5-8，9没上秤，且不平衡 ⇒ 9必定正常）所以第二次：左盘=[1,2,5]，右盘=[3,6,9]（9正常）分析三种结果： (a) 平衡：说明1,2,3,5,6,9都正常 → 异常在{4,7,8}中；且由第一次1-4 < 5-8知：若4异常则必轻；若7或8异常则必重（因它们在右盘却导致右盘重，即右盘本应更重，但第一次是左盘轻 ⇒ 右盘重，故右盘中的异常球应是偏重）。所以{4(轻),7(重),8(重)}三种可能 → 第三次称7 vs 8：若7=8 → 4轻；若7>8 → 7重；若7<8 → 8重。 (b) 左盘轻（[1,2,5] < [3,6,9]）：结合第一次（1-4 < 5-8），可能原因： - 1或2轻（在左盘，导致左更轻）✅ - 6重（在右盘，使右更重，即左显轻）✅ - 注意5在左盘，但第一次5在右盘且右盘重，若5重，则第一次应右更重，符合；但第二次5在左盘，若5重会使左更重，与本次“左轻”矛盾 → 5不可能重；同理3在右盘，若3轻会使右更轻 ⇒ 左显重，与本次左轻矛盾 → 3不可能轻。故只剩：1轻、2轻、6重 → 三种可能 → 第三次称1 vs 2：若1<2→1轻；若1>2→2轻；若等→6重。 (c) 左盘重（[1,2,5] > [3,6,9]）：类似分析得可能为3轻、5重、6轻？需严格推导：第一次：1-4 < 5-8 ⇒ 右盘重 ⇒ 异常使右重或左轻。本次左盘重 ⇒ [1,2,5] 比 [3,6,9] 重。重因可能：1重？但1若重，第一次应在左盘，会使左更重，与第一次左轻矛盾 → 排除。同理2重排除。 5重：第一次5在右盘，5重→右更重，符合第一次；第二次5在左盘，5重→左更重，符合本次 → ✅ 3轻：第一次3在左盘，3轻→左更轻，符合第一次；第二次3在右盘，3轻→右更轻 ⇒ 左显重，符合本次 → ✅ 6轻：第一次6在右盘，6轻→右更轻 ⇒ 左应显重，但第一次是左轻 → 矛盾，排除。故仅剩：5重或 3轻 → 两种可能？但需检查是否遗漏：还有4？4没参与第二次，但第一次左轻，若4轻也成立，但4不在本次称量中，若4轻，本次应平衡（因4没上秤，其他都是正常球）→ 但本次不平衡，故4可排除。同理7,8未参与，但若7重，第一次右重成立，但第二次未参与，本次应平衡 → 矛盾，故7,8排除。所以(c)下只有3轻或5重 → 第三次称3 vs 9（正常球）：若3<9→3轻；若3=9→5重。综上，所有分支均可在第三次称量终结。故最坏情况为3次。 - 深度知识讲解：本题本质是**基于比较的决策树优化问题**，核心知识点包括：（1）信息论下界：每个三路比较（天平）提供 log₂3 比特信息，n个球中找1个异常（含轻/重）共2n种假设，需满足 3^k ≥ 2n ⇒ k ≥ log₃(2n)。对n=9，log₃18≈2.63 → 向上取整得3。（2）决策树构造：需设计自适应称量策略（后一次依赖前一次结果），非固定分组。关键技巧是每次称量尽可能让三种结果对应数量接近的假设数（信息熵最大化），即“三分均衡”。（3）编码视角：可将每次称量结果序列（L/R/E）视为三进制码，给18种状态分配唯一3位三进制码，并逆向设计称量方式使得每种状态触发对应码字。例如，球i若为轻，则它在某次称量中若在左盘，会导致L；在右盘导致R；不参与导致E。重球则L/R意义相反。因此需为每个球设计“轻码”和“重码”，二者互为按位取反（L↔R，E不变）。（4）扩展：若推广到n球，最大可处理球数满足 (3^k - 3)/2 ≥ n（因k次称量最多区分3^k种结果，但需排除全E、及某些无效码，标准结论是k次最多处理 (3^k - 3)/2 个球）。验证：k=3 → (27-3)/2=12，故3次实际可处理最多12球（本题9<12，可行）。 - 伪代码（策略描述，非执行代码）： function findOddBall(balls[1..9]): // 第一次：称 balls[1-3] vs balls[4-6] result1 = balance([1,2,3], [4,5,6]) if result1 == EQUAL: // 异常在 {7,8,9} result2 = balance([7], [8]) if result2 == EQUAL: return (9, UNKNOWN_WEIGHT) // 第三次称9 vs 1定轻重 else: // 假设7<8，则7轻或8重；需第三次用已知正常球验证 normal = 1 result3 = balance([7], [normal]) if result3 == LESS: return (7, LIGHT) else if result3 == GREATER: return (7, HEAVY) // 不可能，因7<8且若7重则7>normal，但7<8暗示7更轻或8更重 // 更稳健：第三次称7 vs 1 // 若7<1 → 7轻；若7>1 → 7重 → 但7重与7<8矛盾（因8正常则7<8且7>1不可能同时），故实际只需一次验证 // 标准做法：第二次改称7+1 vs 8+2（两个正常球） else if result1 == LEFT_LESS: // 异常在1-6：1-3中轻或 4-6中重 // 第二次：称 [1,4,5] vs [2,6,7] （7是正常球，因第一次7,8,9未参与且result1≠EQUAL ⇒ 7正常） result2 = balance([1,4,5], [2,6,7]) case result2: EQUAL: → 异常在 {3(轻),5(重)?} 等，按前述逻辑分支处理... // 实际编码复杂，面试中只需清晰阐述三次策略及信息论依据注：真正实现需完整决策树，但面试重点在于逻辑完整性与下界证明。综上，答案是3次（最坏情况，且需确定轻重）。若题目明确“已知异常球更轻”，则第一次3 vs 3，第二次1 vs 1，共2次；但题干未说明，故按常规默认回答3次。

赛美特中高级自动化测试笔试

全站热榜

创作者周榜