定义 在已知次品比正品轻(或重)且数量较多的情况下,利用天平称量,找出最少称量次数保证找到次品的策略。
从哪来 本知识点建立在 1.3 列举策略 和 2.1 假设策略 之上。通过列举不同分组方式下的最坏情况(列举策略),并假设天平平衡或不平衡两种结果来推导最优解(假设策略)。
为什么 核心原理是“信息论”与“三分法”。天平每次称量只有三种结果:左重、右重、平衡。为了用最少的次数排除最多的可能性,必须将待测物品尽可能平均分成三份。
若分成两份,每次只能排除一半的可能性,效率低;若分成三份且尽量平均,每次称量后,无论天平如何倾斜,剩余嫌疑范围都缩小到原来的 1/3。例如 9 个物品,分 3 组(3,3,3),称一次后,无论结果如何,嫌疑范围都缩小到 3 个,再称一次即可确定。若分 2 组(4,5),称一次后,若平衡则剩 1 个(好),若不平衡则剩 4 或 5 个(坏),最坏情况需处理 5 个,效率不如三分法。因此,“尽量平均分成三份”是保证最少次数的最优策略。
讲法
实物模拟法
适合:具象思维强、动手能力强、对抽象逻辑感到困难的学生。
1. 准备 9 个外观相同的球(其中 1 个稍轻,可用乒乓球和网球模拟,或标记重量差异)。
2. 让学生尝试“二分法”:分成 4 和 5。称 4 个 vs 4 个(留 1 个)。若平衡,次品在剩下的 1 个里(1 次搞定);若不平衡,次品在重的 4 个里(还需 2 次,共 3 次)。
3. 让学生尝试“三分法”:分成 3、3、3。称 3 个 vs 3 个。若平衡,次品在剩下的 3 个里;若不平衡,次品在重的 3 个里。无论哪种情况,都剩 3 个。
4. 对剩下的 3 个,再称 1 个 vs 1 个。若平衡,剩 1 个是次品;若不平衡,重的是次品。
5. 对比两种方法的最坏情况次数(3 次 vs 2 次),得出结论:三分法更优。
讲法
决策树图解法
适合:逻辑清晰、擅长结构化思维、喜欢视觉化表达的学生。
1. 画出决策树根节点:9 个物品。
2. 分支 1(二分法):
- 称 4 vs 4。
- 结果 A:平衡 → 剩 1 个(结束)。
- 结果 B:不平衡 → 剩 4 个。
- 称 2 vs 2。
- 结果 B1:平衡 → 不可能(因为已知有次品且在天平上)。
- 结果 B2:不平衡 → 剩 2 个。
- 称 1 vs 1 → 确定。
- 最坏路径长度:3 步。
3. 分支 2(三分法):
- 称 3 vs 3。
- 结果 A:平衡 → 剩 3 个。
- 结果 B:不平衡 → 剩 3 个。
- 无论 A 或 B,都进入下一层:3 个物品。
- 称 1 vs 1。
- 结果 A1:平衡 → 剩 1 个。
- 结果 A2:不平衡 → 剩 1 个。
- 最坏路径长度:2 步。
4. 结论:树的高度(深度)代表最少称量次数,三分法树更矮。
讲法
逆向推理法
适合:抽象思维强、喜欢挑战、数学基础较好的学生。
1. 提问:1 次称量最多能找出多少个物品中的次品?
- 答:3 个。因为 3 个分 1,1,1,称 1 vs 1,平衡则剩 1 个,不平衡则重者。
2. 提问:2 次称量最多能找出多少个?
- 答:3 × 3 = 9 个。第一次称量将范围缩小到 3 个,第二次再缩小到 1 个。
3. 提问:3 次称量最多能找出多少个?
- 答:3 × 3 × 3 = 27 个。
4. 公式:n 次称量最多能处理 $3^n$ 个物品。
5. 应用:9 个物品,$3^1=3 < 9$,$3^2=9 \ge 9$,所以最少 2 次。
6. 强调:这个公式成立的前提是“每次都能平均分成三份”,即物品数在 $3^{n-1}+1$ 到 $3^n$ 之间时,最少次数为 n。