分类讨论:把复杂问题分开
约 10 分钟
一个问题若包含几种性质不同的情况,混在一起容易乱。把所有可能按清楚标准分成若干类,分别处理,再合并结果,叫分类讨论。它的关键不是“分得多”,而是各类之间不重叠、合起来不遗漏。
先选分类标准
把 1 到 20 分类,可以按奇偶、是否为 3 的倍数、位数多少。没有唯一的“正确分类”,要看问题在问什么。研究能否两两配成整数和时,奇偶分类有用;研究十位数字时,按位数更合适。
分支要互斥且完整
判断一场户外活动方案,可分为“下雨”和“不下雨”,两类不会同时发生且覆盖全部天气判断。若分成“大雨”和“晴天”,就漏了小雨、阴天。画树状分支并在末端核对,是检查完整性的办法。
边界属于哪一类
规定身高“低于 120 厘米”和“高于 120 厘米”会漏掉刚好 120。数学语言中的小于、小于等于必须精确。写规则时给每个边界安排归属,再用边界值测试。
分别求解后不要忘记合并
问共有多少方案,通常要把互斥类别的数量相加;问是否都满足,则每一类都要检查。合并方式由问题决定,不是分类结束就完成。
同一对象可有多个标签
数字 6 既是偶数又是 3 的倍数。如果分类要求互斥,就应改成“只被2整除、只被3整除、同时被2和3整除、都不是”等类别。先明确集合关系,避免重复计数。
练一练:统计 1 到 30 中能被 2 或 3 整除的数,设计互不重叠的分类,并解释如何避免把 6 的倍数算两次。
小纸条
好的分类讨论要满足哪两个覆盖条件?