第十四讲 枚举法及其运用

第十四讲枚举法及其运用学法探讨我们在平常的数学学习过程中，遇到的数学问题，一般都可以列出算式，然后求出结果。但在数学竞赛或日常生活中却经常会遇到一些有趣的问题，由于找不到计算的算式，似乎无从下手。但是，如果问题所述的情况或满足问题要求的结果能够被一一列举出来，或者能够被分类列举出来，那么我们就应该运用枚举法来解决这类问题。一般地，根据问题要求，将符合已知信息的结果不重复、不遗漏地一一列举出来；或者把问题分为有限种情况，然后将各种情况中符合已知信息的的结果不重复、不遗漏地一一列举出来，以达到解决整个问题的目的。这种分析、解决问题的方法，称之瞰举法，我们也可以通俗地称“枚举法”为举例子。枚举法是一种常见的数学方法。如果遇到要枚举的情况太多，容易导致重复或遗漏掉一些情况时，我们要注意合理分类、有序思考。枚举法是加法原理和乘法原理的基础。关于“枚举法及其运用”你还有什么需要补充？请你写在下面：例题选讲【例1】A、B、C、D四个同学进行乒乓球单打比赛，每两人之间都要赛一场，四个人一共要比赛多少场？【分析】人不多，我们可以将每场比赛——列举出来，如图14-1所示；我们也可以用四个点代表四位同学，如果某两个同学之间进行了一场比赛，我们就在代表这两个同学的两点之间连一条线段，最后计算有多少条线段，就表示进行了多少场比赛，如图14-2所示。DCDC由图易知，四个人一共要比赛6场。你能将6场比赛都列出来吗?【解答】【体会】在解决这个问题的过程中，你有什么体会？有什么需要补充？请你写在下面:【练习14—1】A、B、C、D、E五个同学进行乒乓球单打比赛，每两人之间都要赛一场,五个人一共要比赛多少场？【例2】小明和小红玩掷骰子的游戏，共有两枚骰子，一起掷出。若两枚骰子的点数和为7,则小明胜；若两枚骰子的点数和为8,则小红胜。试判断他们两人谁获胜的可能性大。【分析】将两枚骰子的点数和分别为7与8的各种情况都列举出来，就可得到问题的结论。用a表示第一枚骰子的点数；用b表示第二枚骰子的点数。a+b=7的情况共有6种，它们是：+6,2+5,3+4,4+3,5+2,6+1。a+b=8的情况共有5种，它们是：+6,3+5,4+4,5+3,6+2。所以，小明获胜的可能性大。也有人这样认为，因为出现7的情况有：1+6,2+5,3+4三种，出现8的情况有：2+6,3+5,4+4三种，所以两人获胜的可能性一样大。你认为呢？【解答】【体会】在解决这个问题的过程中，你有什么体会？有什么需要补充？请你写在下面:【练习14—2】现有10块糖，如果要求每天至少吃3块，吃完为止，那么一共有多少种不同的吃法？【例3】现有面值为5角、8角的邮票各两枚。用这些邮票能付多少种不同的邮资?【分析】我们可根据使用邮票的数量，分成四类（一枚、二枚、三枚、四枚）进行枚举：一枚:5角、8角；二枚：10角、13角、16角；三枚：18角、21角；四枚：26角。一共可以付多少种不同的邮资就一目了然了。【解答】【体会】在解决这个问题的过程中，你有什么体会？有什么需要补充？请你写在下面:【练习14-3］现有三张数字卡片1、2、3,用这些卡片可以组成多少个不同的数？分别是哪些个数？【例4】请你数一数，右图中一共有多少个三角形。【分析】状、大小都不相同，位置也很凌乱，不好数清楚。为了避免数数过程中的遗漏或重复，我们将图形的各部分编上号（见下图），然后按照图形的组成规律，把三角形分成单个的、由两部分组成的、地枚举出来。单个的三角形有6个：1,2,3,5，【例4】请你数一数，右图中一共有多少个三角形。【分析】状、大小都不相同，位置也很凌乱，不好数清楚。为了避免数数过程中的遗漏或重复，我们将图形的各部分编上号（见下图），然后按照图形的组成规律，把三角形分成单个的、由两部分组成的、地枚举出来。单个的三角形有6个：1,2,3,5，6，8。由两部分组成的三角形有4个：（1，2）、（2,5）、（4,5）、（6,7）。由三部分组成的三角形有1个：（6,7,8）。由四部分组成的三角形有2个：（1,3,4,6）、（2,5,7,8）。由八部分组成的三角形有1个：（1,2,3,4,5,6,7,8）。那么，图中一共有多少个三角形呢？【解答】、再一类一类【体会】对于这类图形的计数问题，按由一部分组成、由两部分组成、由三部分组成进行分类型计数是最常用的方法。在解决这个问题的过程中，你还有什么体会？还有什么需要补充？请你写在下面:【练习14一4】请你数一数，下图中一共有多少三角形?请问一共有【例5】甲、乙两人比赛乒乓球，先胜三局的人算赢，多少种可能发生的情况？【分析】如果遇到要枚举的情况太多，容易导致重复或遗漏掉一些情况时，我们除了要合理分类、有序思考以外，最好引用一种工具一一树枝图。先考虑甲胜第一局的情况，列树枝图如下：甲乙甲乙甲」乙容易看出，甲胜第一局的情况一共有10种情况。同理，乙胜第一局也有10种情况，合计一共有20种情况。【解答】【体会】在解决这个问题的过程中，你有什么体会？有什么需要补充？请你写在下面:【练习14—5】甲、乙两人比赛乒乓球，采取五局三胜制。已知甲胜了第一盘，并最终获胜。请问一共有多少种可能发生的情况？【例6】在算盘上，用两颗珠子可以表示多少个不同的四位数？【分析】算盘是我国优秀的文化遗产，我们先回忆一下相关的知识。算盘上，上面的珠子一个表示5,下面的珠子一个表示1。我们分三类来进行枚举：两颗珠都是上珠时，可表示5005，5050，5500三个数；两颗珠都是下珠时，可表示1001，1010，1100，2000四个数；一颗上珠、一颗下珠时，可表示5001，5010，5100，1005，1050，1500，6000七个数。一共可以表示可以表示多少个不同的四位数呢？【解答】【体会】由上述各例可知，当可能的情况较少时，可以直接枚举，即将所有结果——列举出来；当可能的情况较多时，就需要分类枚举。分类枚举是我们需重点学习掌握的内容。分类一定要包括所有可能的结果，这样才能不遗漏，并且类与类之间不重叠，这样才能不重复。在解决这个问题的过程中，你还有什么体会？还有什么需要补充？请你写在下面：同的盖法?【练习14—6】用五个1X2的小矩形纸片覆盖右图的2X5的大矩形，一共有多少种不同的盖法?自我检测1.用0、6、7、8这四个数字组成各个数位上数字互不相同的两位数共有多少个?2•有6位老朋友聚会，他们见面时每两人都要握一次手，照这样计算，这次聚会他们一共握了多少次手？将三个相同的小球放入A、B、C三个盒子中，一共有多少种放法?三个人各自都戴着一顶帽子，现在要求每个人都换成戴别人的帽子，一共有多少种换法?有0、1、4、7、9共5张数字卡片，从中取出4张排成四位数，把其中只能被3整除的数从小到大的顺序排列起来，第三个数是几？6•有红、黄、蓝色的小旗各1面，从中选出1面、2面或3面升上旗杆，作出各种不同的信号，一共可以作几种不同的信号？7•小明的暑假作业有语文、算术、外语三门，他准备每天做一门，且相邻两天不做同一门。如果小明第一天做语文，第五天也做语文，那么，这五天作业他共有多少种不同的安排？&数数右图中一共有多少个三角形?9•现有15个球，要求分成数量不同的四堆，数量最多的一堆至少有多少个球?10.一个人在三个城市A、B、C中游览。他今天在这个城市，明天就必须到另一个城市。这个人从A城出发，4天后还回到A城，那么这个人有多少种旅游路线？你知道吗？《孙子算经》《孙子算经》约成书于四、五世纪，作者生平和编写年代都不清楚。现在流传的《孙子算经》共三卷。上卷叙述算筹记数的纵横相间制度和筹算乘除法则。中卷举例说明筹算分数算法和筹算开平方算法。下卷对后世的影响最为深远，比如下卷第31题，可谓是后世“鸡兔同笼”问题的始祖，后来流传到日本，变成“鹤龟算”书中是这样叙述的：“今有雉、兔同笼，上有三十五头，下有九十四足。问：雉、兔各几何？”这四句话的意思是：有若干只鸡、兔同在一个笼子里，从上面数，有35个头；从下面数，有94只脚。求笼中各有多少只鸡和兔？书中不但提供了答案，而且还给出了解法。术曰：上置三十五头，下置九十四足。半其足，得四十七，以少减多，再命之，上三除下三，上五除下五，下有一除上一，下有二除上二，即得。又术曰：上置头，下置足，半其足，以头除足，以足除头，即得：雉二十三，兔一十二。具有重大意义的是下卷第26题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?”《孙子算经》不但提供了答案，而且还给出了解法。显然，这相当于求不定方程组N=3x+2、N=5y+3与N=7z+2的正整数解N,或用现代数论符号表示，等价于解下列的一次同余组：N=2(mod3)；N=3(mod5)；N=2(mod7)。《孙子算经》所给答案是N=23。由于孙子问题数据比较简单，这个得数通过试算也可以得到。但是《孙子算经》并不是这样做的。“物不知数”问题术文提出的解法是：三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。将诸乘积相加，然后减去一百零五的倍数。列成算式就是：N=70X2+21X3+15X2—2X105=23。这里105是模数3、5、7的最小公倍数，容易看出，《孙子算经》给出的是符合条件的最小正整数。对于一般余数的情形，《孙子算经》术文指出，只要把上述算法中的余数2、3、2分别换成新的余数就行了。以R1、R2、R3表示这些余数，那么《孙子算经》相当于给出公式：N=70XR1+21XR2+15XR3—PX105(p是整数)。孙子算法的关键在于70、21和15这三个数的确定。后来流传的《孙子歌》中所说“七十稀”、“廿一技”和“正半月”，就是暗指这三个关键的数字。《孙子算经》没有说明这三个数的来历。实际上，它们具有如下特性：这三个数可以从最小公倍数M=3X5X7=105中各约去模数3、5、7后，再分别乘以整数2、1、1而得到。假令kl=2,K2=l,K3=l,那么整数Ki(i=l,2,3)的选取使所得到的三数70、21、15被相应模数相除的时候余数都是1。由此出发，立即可以推出余数是R1、R2、R3的情况下的情况。南宋大数学家秦九韶则进一步开创了对一次同余式理论的研究工作，推广“物不知数”的问题。德国数学家高斯［K.F.Gauss.公元1777T855年］于公元1801年出版的《算术探究》中明确地写出了上述定理。公元1852年，英国基督教士伟烈亚士［AlexanderWylie公元1815-1887年］将《孙子算经》“物不知数”问题的解法传到欧洲，公元1874年马蒂生［L.Malhiesen］指出孙子的解法符合高斯的定理，从而在西方的数学史里将这一个定理称为“中国的剩余定理”［Chinese,remaindertheorem］0第十四讲枚举法及其运用例题及练习解答:【例1】解答：因为参加比赛的人不多，我们可以将每场比赛一一列举出来，如图14-1所示；我们也可以用四个点代表四位同学，如果某两个同学之间进行了一场比赛，我们就在代表这两个同学的两点之间连一条线段，最后计算有多少条线段,就表示进行了多少场比赛,如图14-2所示。DC图14-2DC图14-2由图易知，四个人一共要比赛6场。它们分别是：AB、AC、AD、BC、BD、CD。【练习14-1】解答：如例题画出示意图，由图易知五个人一共要比赛10场。它们分别是：AB、AC、AD、AE、BC、BD、BE、CD、CE、DE。【例2】解答：将两枚骰子的点数和分别为7与8的各种情况都列举出来，就可得到问题的结论。用a表示第一枚骰子的点数；用b表示第二枚骰子的点数。a+b=7的情况共有6种，它们是：+6，2+5，3+4，4+3，5+2，6+1。a+b=8的情况共有5种，它们是：+6，3+5，4+4，5+3，6+2。所以，小明获胜的可能性大。也有人这样认为，因为出现7的情况有：1+6,2+5，3+4三种，出现8的情况有：2+6，3+5，4+4三种，所以两人获胜的可能性一样大。这种解法是错误的。【练习14-2】解答：9种。一天吃完有1种:(10)；两天吃完有5种:(3,7),(4,6),(5,5),(6,4),(7，3);三天吃完有3种：(3,3,4),(3,4,3),(4,3,3)。共1+5+3=9(种)。【例3】解答：我们可根据使用邮票的数量，分成四类(一枚、二枚、三枚、四枚)进行枚举：一枚:5角、8角；二枚:10角、13角、16角；三枚：18角、21角；四枚：26角。所以一共可付8种不同的邮资。【练习14-3】解答：根据组成的数的位数进行分类:一位数：有1、2、3共三个数；两位数：有12、13、21、23、31、32共六个；

三位数：对于三位数，我们又可以根据百位上数字的不同，把它们分为三类：第1类百位上的数字为1的有：123、132;第2类百位上的数字为2的有：213、231;第3类百位上的数字为3的有：312、321。所以可以组成1、2、3、12、13、21、23、31、32、123、132、213、231、312、321共15个数。【例4】解答：图中的三角形形状、大小都不相同，位置也很凌乱，不好数清楚。为了避免数数过程中的遗漏或重复，我们将图形的各部分编上号（见下图），然后按照图形的组成规律，把三角形分成单个的、由两部分组成的、由3部分组成的、、再一类一类地枚举出来。由两部分组成的三角形有4个：（1，2）、（2，5）、（4，5）、（6,8)4由两部分组成的三角形有4个：（1，2）、（2，5）、（4，5）、（6,8)4,6)、(2,5,7,8)3,4,5,6,7,8)。由三部分组成的三角形有1个：（6,7,由四部分组成的三角形有2个：（1,3,由八部分组成的三角形有1个:（1,2,总共有6+4+1+2+1=14（个）【练习14-4】解答：为了避免数数过程中的遗漏或重复，我们将图形的各部分编上号（如右图），然后按照图形的组成规律，把三角形分成单个的、由两部分组成的、由3部分组成的、、再一类一类地枚举出来。单个三角形有10个：1,2,3,4,6,7,8,9,10,11。由两部分组成的三角形有10个：（1,2）、（2,3）、（1,4）、（4,7）、（3,6）、（6,10）、(7,8)、(8,11)、(9,11)、(9,10)由三部分组成的三角形有10个：（1,2,3）、（1,4,7）、（3,6,10）、（7,8,11）、(9,10,11)、(2,5,8)、(2,5,9)、(4,5,6)、(4,5,9)、(6,5,8)由五部分组成的三角形有5个：（1,2,4,5,9）、（2,3,5,6,8）、（4,5,6,9,10)、(2,5,8,9,11)(4,5,6,7,8)图形中一共有：10+10+10+5=35（个）三角形。【例5】解答：如果遇到要枚举的情况太多，容易导致重复或遗漏掉一些情况时，我们除了要合理分类、有序思考以外，最好引用一种工具一一树枝图。先考虑甲胜第一局的情况，列树枝图如下：容易看出，甲胜第一局的情况一共有10种情况。同理，乙胜第一局也有10种情况，合计一共有20种情况。【练习14-5】解答：画出树枝图如下，各种可能发生的情况一共有6种。1212345【例6】解答：算盘是我国优秀的文化遗产，我们先回忆一下相关的知识。算盘上，上面有两个珠子，一个表示5;下面有四个珠子珠子，一个表示1。我们分三类来进行枚举：两颗珠都是上珠时，可表示5005，5050，5500三个数；两颗珠都是下珠时，可表示1001，1010，1100，2000四个数；一颗上珠、一颗下珠时，可表示5001，5010，5100，1005，1050，1500，6000七个数。一共可以表示3+4+7=14（个）四位数。【练习14-6】解答：我们根据竖放的1x2的小矩形有多少个来分类：只有1个小矩形竖放的有3种，如下图所示：有3个小矩形竖放的有4种，如下图所示:5个小矩形全部竖放的有1种，如下图所示:综上所述，一共有：3+4+1=8（种）。自我检测题解答:1.解答：以两位数十位上的数字为标准进行分类:十位上是6的有：60、67、68共3个；十位上是7的有：70、76、78共3个；十位上是8的有：80、86、87共3个。一共有9个不同的两位数。

解答：可以画出示意图，易知，这次聚会他们一共握手：5+4+3+2+1=15（次）。解答：三个球相同，所以就考虑盒子，分别有下面这样的放法：（0，0，