《简单的枚举法》PPT课件

《《简单的枚举法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章简单的枚举法小三春节奥数班在研究问题时，把所有可能发生的情况一一列举加以研究的方法叫做枚举法。枚举法特点：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。例如：找出1到100之间的质数。需要将1到100之间的所有整数进行判断。用枚举法解题时，常常需要把讨论的对象进行恰当的分类，否则就无法枚举，或解答过程变得冗长、繁琐、当讨论的对象很多，甚至是无穷多个时，更是必须如此。枚举时不能有遗漏。当然分类也就不能有遗漏，也就是说，要使研究的每一个对象都在某一类中。分类时，一般最好不重复，但有时重复没有引起错误，没有使解法变复杂，就不必苛求。缩小枚举范围的方

2、法叫做筛选法，筛选法遵循的原则是：确定范围，逐个试验，淘汰非解，寻求解答。枚举法缺点：用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大，在时间上就难以承受。但枚举算法的思路简单，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。例1小明和小红玩掷骰子的游戏，共有两枚骰子，一起掷出。若两枚骰子的点数和为7，则小明胜；若点数和为8，则小红胜。试判断他们两人谁获胜的可能性大。分析与解：将两

3、枚骰子的点数和分别为7与8的各种情况都列举出来，就可得到问题的结论。出现7的情况共有6种，它们是：1＋6，2＋5，3＋4，4＋3，5＋2，6＋1。出现8的情况共有5种，它们是：2＋6，3＋5，4＋4，5＋3，6＋2。所以，小明获胜的可能性大。例2数一数，下图中有多少个三角形。分析与解：图中的三角形形状、大小都不相同，位置也很凌乱，不好数清楚。为了避免数数过程中的遗漏或重复，我们将图形的各部分编上号（见右图），然后按照图形的组成规律，把三角形分成单个的、由两部分组成的、由3部分组成的……再一类一类地列举出来。单个的三角形有：1，2，3，5，6，8。由两部分组成的三角形有：（1，2），（2，6）

4、，（4，6），（5，7）由三部分组成的三角形有：（5，7，8）由四部分组成的三角形有：（1，3，4，5），（2，6，7，8）由八部分组成的三角形有：（1，2，3，4，5，6，7，8）总共有6＋4＋1＋2＋1=14（个）对于这类图形的计数问题，分类型数是常用的方法。例3已知甲、乙、丙三个数的乘积是10，试问甲、乙、丙三数分别可能是几？分析与解：在寻找问题的答案时，应该严格遵循不重不漏的枚举原则，由于10的因子有1、2、5、10，因此甲、乙、丙仅可取这四个自然数，先令甲数=1、2、5、10，做到不重不漏，再考虑乙、丙的取法。B、甲=2乙=1丙=5乙=5丙=2A、甲=1乙=1丙=10乙=2丙=5乙

5、=5丙=2乙=10丙=1解：因为10的因子有：1、2、5、10，故甲、乙、丙三数的取法可列下表：C、甲=5乙=1丙=2乙=2丙=1总共得到问题的九组解答。甲=1、1、1、1、2、2、5、5、10乙=1、2、5、10、1、5、1、2、1丙=10、5、2、1、5、1、2、1、1D、甲=10乙=1丙=1由例1～3看出，当可能的结果较少时，可以直接枚举，即将所有结果一一列举出来；当可能的结果较多时，就需要分类枚举，分类枚举是我们需重点学习掌握的内容。分类一定要包括所有可能的结果，这样才能不遗漏，并且类与类之间不重叠，这样才能不重复。例4有一只无盖立方体纸箱，将它沿棱剪开成平面展开图。那么，共有多少种

6、不同的展开图？分析与解：我们将展开图按最长一行有多少个正方形（纸箱的面）来分类，可以分为三类：最长一行有4个正方形的有2种：最长一行有3个正方形的有5种：最长一行有2个正方形的有1种：解：不同的展开图共有2＋5＋1＝8（种）。例5小明的暑假作业有语文、算术、外语三门，他准备每天做一门，且相邻两天不做同一门。如果小明第一天做语文，第五天也做语文，那么，这五天作业他共有多少种不同的安排？分析与解：本题是分步进行一项工作，每步有若干种选择，求不同安排的种数（有一步差异即为不同的安排）。这类问题简单一些的可用乘法原理与加法原理来计算，而本题中由于限定条件较多，很难列出算式计算。但是，我们可以根据实际

7、的安排，对每一步可能的选择画出一个树枝状的图，非常直观地得到结果。这样的图不妨称为“枚举树”。由右图可知，共有6种不同的安排。例6甲、乙两人打乒乓球，谁先胜两局谁赢；如果没有人连胜两局，则谁先胜三局谁赢，打到决出输赢为止。那么一共有多少种可能的情况？解：设甲胜为A，甲负为B。若最终甲赢，有7种可能的情况。如图。同理，乙赢也有7种可能的情况。7+7＝14再见