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