1、第四讲 枚举法 1.1.计数问题分为两个大类计数问题分为两个大类，一类是“计次序”的问题，一类是“不计次序”的问题。 2.2.枚举需要按照一定的顺序和一定的规律来进行分类，这样可以做到不重复和不遗漏。 3.3.枚举法的根本思想在于分类， 通过分类可以将原本复杂的问题拆分成若干个比较简单的问 题，然后再逐一进行分析。分类的思想可以化繁为简，化复杂为简单。 4.4.可以利用“树形图”来方便的记录枚举的过程，有几类问题就分出几个分枝，逐层按照 顺序不断分叉再一一筛选，留下符合条件的，去掉不符合条件的。注意在枚举“不计次序” 的问题时，只需考虑从小到大（或从大到小）排列的分枝，而不用理会其他情况。 5
2、.5.计次序：计次序：不但要挑选出来，而且还需要排列顺序，不同的排列顺序认为是不同的情况或 方法。这类问题通常是“排列”的题目。 6.6.不计次序：不计次序：只要挑选出来即可，不需要排列顺序，不同的排列顺序认为是相同的情况或方 法。这类问题通常是“选取”的题目。 1.理解“枚举法”的含义。 2.能在题目中熟练运用枚举法解题。 例例 1 1：小明和小红玩掷骰子的游戏，共有两枚骰子，一起掷出。若两枚骰子的点数和为小明和小红玩掷骰子的游戏，共有两枚骰子，一起掷出。若两枚骰子的点数和为 7 7， 则小明胜；若点数和为则小明胜；若点数和为 8 8，则小红胜。试判断他们两人谁获胜的可能性大。，则小红胜。试
3、判断他们两人谁获胜的可能性大。 分析与解：分析与解： 将两枚骰子的点数和分别为7与8的各种情况都列举出来， 就可得到问题的结论。 用 ab 表示第一枚骰子的点数为 a，第二枚骰子的点数是 b 的情况。 出现 7 的情况共有 6 种，它们是： 16，25，34，43，52，61。 出现 8 的情况共有 5 种，它们是： 26，35，44，53，62。 所以，小明获胜的可能性大。 注意， 本题中若认为出现 7 的情况有 16， 25， 34 三种， 出现 8 的情况有 26， 35， 44 也是三种，从而得“两人获胜的可能性一样大”，那就错了。 例例 2 2：数一数，右图中有多少个三角形。数一数，
4、右图中有多少个三角形。 分析与解：分析与解：图中的三角形形状、大小都不相同，位置也很凌乱，不好数清楚。为了避免数数 过程中的遗漏或重复，我们将图形的各部分编上号（见右图） ，然后按照图形的组成规律， 把三角形分成单个的、由两部分组成的、由 3 部分组成的再一类一类地列举出来。 单个的三角形有 6 个：1 ，2，3，5，6，8。 由两部分组成的三角形有 4 个： （1，2） ， （2，6） ， （4，6） ， （5，7） 。 由三部分组成的三角形有 1 个： （5，7，8） 。 由四部分组成的三角形有 2 个： （1，3，4，5） ， （2，6，7，8） 。 由八部分组成的三角形有 1 个： （
5、1，2，3，4，5，6，7，8） 。 总共有 64121=14（个） 。 对于这类图形的计数问题，分类型数是常用的方法。 例例 3:3:在算盘上，用两颗珠子可以表示多少个不同的四位数？在算盘上，用两颗珠子可以表示多少个不同的四位数？ 分析与解：分析与解：上珠一个表示 5，下珠一个表示 1。分三类枚举： （1）两颗珠都是上珠时，可表示 5005，5050，5500 三个数； （2）两颗珠都是下珠时，可表示 1001，1010，1100，2000 四个数； （3）一颗上珠、一颗下珠时，可表示 5001，5010，5100，1005，1050，1500，6000 七个数。 一共可以表示 347=14
6、（个）四位数。 由例由例 1 13 3 看出，当可能的结果较少时，可以直接枚举，即将所有结果一一列举出来；当可看出，当可能的结果较少时，可以直接枚举，即将所有结果一一列举出来；当可 能的结果较多时，就需要分类枚举，分类枚举是我们需重点学习掌握的内容。分能的结果较多时，就需要分类枚举，分类枚举是我们需重点学习掌握的内容。分类一定要类一定要 包括所有可能的结果，这样才能不遗漏，并且类与类之间不重叠，这样才能不重复。包括所有可能的结果，这样才能不遗漏，并且类与类之间不重叠，这样才能不重复。 例例 4 4 有一只无盖立方体纸箱，将它沿棱剪开成平面展开图。那么，共有多少种不同的展开有一只无盖立方体纸箱，
7、将它沿棱剪开成平面展开图。那么，共有多少种不同的展开 图？图？ 分析与解：分析与解：我们将展开图按最长一行有多少个正方形（纸箱的面）来分类，可以分为三类： 最长一行有 4 个正方形的有 2 种，见图（1） （2） ； 最长一行有 3 个正方形的有 5 种，见图（3）（7） ； 最长一行有 2 个正方形的有 1 种，见图（8） 。 不同的展开图共有 2518（种） 。 例例 5 5：小明的暑假作业有语文、算术、外语三门，他准备每天做一门，且相邻两天不做同一小明的暑假作业有语文、算术、外语三门，他准备每天做一门，且相邻两天不做同一 门。如果小明第一天做语文，第五天也做语文，那么，这五天作业他共有多
8、少种不同的安门。如果小明第一天做语文，第五天也做语文，那么，这五天作业他共有多少种不同的安 排？排？ 分析与解：分析与解：本题是分步进行一项工作，每步有若干种选择，求不同安排的种数（有一步差异 即为不同的安排） 。这类问题简单一些的可用乘法原理与加法原理来计算，而本题中由于限 定条件较多，很难列出算式计算。但是，我们可以根据实际的安排，对每一步可能的选择画 出一个树枝状的图，非常直观地得到结果。这样的图不妨称为“枚举树” 。 由上图可知，共有 6 种不同的安排。 例例 6 6：一次数学课堂练习有一次数学课堂练习有 3 3 道题，老师先写出一个，然后每隔道题，老师先写出一个，然后每隔 5 5 分
9、钟又写出一个。规定：分钟又写出一个。规定： （1 1）每个学生在老师写出一个新题时，如果原有题还没有做完，那么必须立即停下来转做）每个学生在老师写出一个新题时，如果原有题还没有做完，那么必须立即停下来转做 新题； （新题； （2 2）做完一道题时，如果老师没有写出新题，那么就转做前面相邻未解出的题。解）做完一道题时，如果老师没有写出新题，那么就转做前面相邻未解出的题。解 完各题的不同顺序共有多少种可能？完各题的不同顺序共有多少种可能？ 分析与解：分析与解：与例 5 类似，也是分步完成一项工作，每步有若干种可能，因此可以通过画枚举 树的方法来求解。但必须考虑到所有可能的情形。 由上图可知，共有
10、5 种不同的顺序。 说明：必须正确理解图示顺序的实际过程。如左上图的下一个过程，表示在第一个 5 分钟内做完了第 1 题，在第二个 5 分钟内没做完第 2 题，这时老师写出第 3 题，只好转做第 3 题，做完后再转做第 2 题。 例例 7 7：是否存在自然数是否存在自然数 n n，使得，使得 n n 2 2 n n2 2 能被能被 3 3 整除？整除？ 分析与解：分析与解：枚举法通常是对有限种情况进行枚举，但是本题讨论的对象是所有自然数，自然 数有无限多个，那么能否用枚举法呢？我们将自然数按照除以 3 的余数分类，有整除、余 1 和余 2 三类，这样只要按类一一枚举就可以了。 当 n 能被 3
11、 整除时，因为 n 2，n 都能被 3 整除，所以（n2n2）3 余 2； 当 n 除以 3 余 1 时，因为 n 2，n 除以 3 都余 1，所以（n2n2）3 余 1； 当 n 除以 3 余 2 时，因为 n 23 余 1，n3 余 2，所以（n2n2）3 余 2。 因为所有的自然数都在这三类之中，所以对所有的自然数 n， （n 2n2）都不能被 3 整除。 A A 1.A、B、C、D、E、F 六支球队进行单循环赛，当比赛进行到某一天时，统计出 A、B、C、D、 E 五队已分别比赛了 5、4、3、2、1 场，由此可知，还没有与 B 队比赛的球队是（ ） A. C 队 B. D 队 C. E
12、 队 D. F 队 答案：答案：C 由于是单循环赛， 所以每个队至多赛 5 场。 A 队已经完成了 5 场， 则每个队均与 A 队比赛过。 E 队仅赛一场（即与 A 赛过） ，所以 E 队没有与 B 队赛过。 2写自然数 1、2、3、1000，一共写了个 0（ ） A. 90 B. 171 C. 189 D. 192 答案：答案：D 分类如下：仅各位是 0 的数共含 90 个 0，仅十位是 0 的数共含 81 个 0，个位、十位同时是 0 的共含 18 个 0， 个、 十、 百位同时是 0 的 （仅 1000） 共含 3 个 0， 所以一共有 90+81+18+3=192 个 0 3.已知 x
13、，y 都有整数，且 xy=6，那么适合等式的解共有8组 答案：答案：8 4.将 6 拆成两个或两个以上的自然数之和，共有多少种不同拆法？ 答案：答案：10 种。 解：6=15=24=33=114=123=2+2+2=1+1+1+3 1+1+2+21+1+1+1+2=1+1+1+1+1+1。 5.小明有 10 块糖，如果每天至少吃 3 块，吃完为止，那么共有多少种不同的吃法？ 答案：答案：9 种。 解：一天吃完有 1 种： （10） ；两天吃完有 5 种： （3，7） ， （4，6） ， （5，5） ， （6，4） ， （7，3） ； 三天吃完有 3 种： （3，3，4） ， （3，4，3） ，
14、 （4，3，3） 。共 1+5+3=9（种） 。 B B 6.用五个 12 的小矩形纸片覆盖右图的 25 的大矩形，共有多少种不同盖法？ 答案：答案：8 种。 解：如下图所示，只有 1 个小矩形竖放的有 3 种，有 3 个小矩形竖放的有 4 种，5 个小矩形 都竖放的有 1 种。共 341=8（种） 。 7.15 个球分成数量不同的四堆，数量最多的一堆至少有多少个球？ 答案：答案：6 个。 解：15 个球分成数量不同的四堆的所有分法有下面 6 种： （1，2，3，9） ， （1，2，4，8， ） （1， 2，5，7） ， （1，3，4，7） ， （1，3，5，6） ， （2，3，4，6） 。
15、可以看出，分成的四堆中最多的那一堆至少有 6 个球。 8.数数右图中共有多少个三角形？ 答案：答案：10 个。 提示：由一块、两块、三块、四块组成的三角形依次有 4，3，2，1 个，共有 4321 10（个） 。 9.甲、乙比赛乒乓球，五局三胜。已知甲胜了第一盘，并最终获胜。问：各盘的胜负情况有 多少种可能？ 答案：答案：6 种。 提示：将各盘获胜者写出来，可画出枚举树如下： 10.经理有 4 封信先后交给打字员，要求打字员总是先打最近接到的信，比如打完第 3 封信 时第4封信还未到， 此时如果第2封信还未打完， 那么就应先打第2封信而不能打第1封信。 打字员打完这 4 封信的先后顺序有多少种
16、可能？ 答案：答案：14 种。 提示：按四封信的完成顺序可画出枚举树如下： C C 11.从 150 这 50 个自然数中选取两个数字， 使它们的和大于 50， 共有多少种不同的取法？ 答案；答案；取法有很多，找到规律使数法简单且不重复不遗漏是解题的关键 解 若两数中较大的是 50，则另一个可以取 1,2,3，49，共 49 种取法； 若两数中较大的是 49，则另一个可以取 1,2,3，48，共 47 种取法； 若两数中较大的是 48，则另一个可以取 1,2,3，47，共 45 种取法； 若两数中较大的是 26，则另一个只能取 25，共 1 种取法。 因此共有 1+3+5+47+49=625
17、种取法。 说明 在运用枚举法时，一定要找出问题的本质，按照一定的规律去设计枚举的形式。 12.从 150 这 50 个自然数中选取两个数字，使它们的和不大于 50，共有多少种不同的取 法 答案；答案；600 种。 取法共有 2+4+6+46+48=600. 13.求证：若整数 n 不是 5 的倍数，则 n 2也不是 5 的倍数。 答案；答案；不是 5 的倍数的数可以除以 5 的余数分为 4 类，按 4 类来讨论。 证明：不是 5 的倍数的数可以除以 5 的余数分为 4 类，设为 5k+1、5k+2、5k+3、5k+4（k 为整数） ， n=5k+1 时，n 2=5（5k2+2k）+1，不是 5
18、 的倍数； n=5k+2 时，n 2=5（5k2+4k）+4，不是 5 的倍数； n=5k+3 时，n 2=5（5k2+6k+1）+4，不是 5 的倍数； n=5k+4 时，n 2=5（5k2+8k+3）+1，不是 5 的倍数。 若整数 n 不是 5 的倍数，则 n 2不是 5 的倍数。 说明 本题体现了在枚举法里常见的思路：分类考查，要注意分类的科学性。 14.除以 4 余 1 的两位数共有几个？ 答案；答案；22 个 令这样的数为 4k+1 （k 为整数） ， 只要令其值在 10 到 99 之间就可以了。 则 k=3,4,523,24。 共 22 个。 15.今有一角币 1 张、贰角币 1
19、 张、伍角币 1 张、一元币 4 张、五元币 2 张。这些纸币任意 付款，可以付出多少种不同数额的款？ 答案；答案；本题如直接枚举，情况复杂，很难求出正确答案。我们可以先考虑付款的数额范围， 在此范围内，再考虑那些不能构成的付款数额，将其剔除。 由题意， 付款的最小数额为 1 角， 最大数额为 14.8 元。 其间 1 角的整数倍共有 148 种款额。 另一方面，4 角、9 角，这两种数额是这些钱币无法付出的，所以 1.4 元、1.9 元、2.4 元、 2.9 元、3.4 元、3.9 元、14.4 元，这些数额也无法付出。上述这些付不出的数额共 29 种，应剔除。所以能付出的数额应是 148-
20、29=119（种） 。 说明 本题采用逆向思维，把本来比较复杂的正面枚举改为较简单的反面枚举。这是我们做 题时的常见的策略。 1.由若干个小正方体堆成大正方体,其表面涂成红色,在所有小正方体中,三面被涂红的有 a 个,两面被涂红的有 b 个,一面被涂红的有 c 个。那么啊 a，b，c 三个数中（ ） A. a 最大 B. b 最大 C. c 最大 D.哪个最大与小正方体的个数有关 答案：答案：D 2.10 块蛋糕分给甲、乙两人，每人至少 1 块，求一共有多少种不同的分法？ 答案：答案：同第 2 题类似共 8 种。 3.10 块蛋糕分成两堆，求一共有多少种不同的分法？ 答案：答案：1+9，2+8
21、，3+7，4+6 四种 4.1，2，3，4 四个数字组成一个没有重复数字的四位数 abcd，若 ac，cd，求一共有 多少种方法？ 答案：答案：1324，1423，2314，2413，3412 5.把4位数x先四舍五入到十位， 所得之数再四舍五入到百位， 所得之数再四舍五入到千位， 恰好得到 2000，则 x 的最小值和最大值是多少？ 答案；答案； 最小值是 1445， 最大值是 2444. 可以倒过来想， 要是 x 最小， 千位必为 1， 百位为 4， 十位为 4，各位最小为 5 即可。同理可以退出最大值。 1.从 1，2，3，4 四个数中选取 3 个数组成一个没有重复数字的 3 位数，求一
22、共有多少种方 法？ 答案：答案：123，124，134，.共有 24 种 2.有甲、乙、丙三个工厂一共要定 300 份报纸，每个工厂最少定 99 份，最多定 101 份，求 一共有多少种订报纸的方法？ 答案：答案： （1）99；100；101；共六种； （2）100；100；100 共一种。合计 7 种。 3.从 1，2，3，4 四个数中选取 3 个不同的数字组成一组，求一共有多少种方法？ 答案：答案：4 种。 4.将 300 拆成三个整数的和， 并且每个整数不小于 99， 不大于 101， 求一共有多少种方法？ 答案：答案：和例题 2 向类似，所以一共有 2 种方法。 5.从 18 中取出
23、3 个不同的数字使得 3 个数字的和等于 11，一共有多少种取法？ 答案：答案：11=8+2+1=7+3+1=6+4+1=6+3+2=5+4+2 共5 种。 6.一共有 6 件相同的礼物分给甲、乙、丙、丁四个小朋友，每个人至少分一件，求一共有 多少种分法？ 答案：答案：6=1+1+1+3=1+1+2+2 四个人分到的数不一样结果也有所不同。合计：10 种 7.一共有 6 件相同的礼物分成 4 份，求一共有多少种分法？ 答案：答案：6=1+1+1+3=1+1+2+2 共两种 8.妈妈买来 7 个鸡蛋，每天至少吃 2 个，吃完为止，一共有多少种不同的吃法？ 答案：答案：8 种 9.妈妈买来 7 个鸡蛋，将它们分成若干份，一共有多少种不同的分法？ 答案：答案：将 7 拆分为几个整数和的形式 7=1+1+1+1+1+1+1=1+1+1+1+1+2 =1+1+1+1+3 =1+1+1+2+2 =1+1+5 =1+1+2+3 =1+3+3 10.从两个 1，两个 2，1 个 3 中选出 3 个数字组成 3 位数，那么一共可以组成多少个不同的 3 位数？ 答案：答案：树型图分析， 百位为 1，共 7 种。 百位为 2，共 7 种。 百位为 3，共 4 种。 合计：18 种
