六年级第一册三单元.doc

雅博培训学校暑假五进六数学讲义 第三单元 计数原理
第一讲：枚举法（分类、树形图）
一、内容概述
1、枚举就是将要求计数的物体一一列举出来再进行总数的统计的方法。
枚举无疑是最原始、最简单的计数方法，但是它同时也是计数最可靠的方法，也是发现规律、找到技巧的最佳方法。
2、计数的关键在于既不重复、也不遗漏，枚举法也不例外。要做到这一点，关键是要在确定列举范围以后先按照一定的标准分类，再按一定的顺序进行列举。运用树形图帮助按顺序列举是解决这一问题的常用技巧。
3、借用树形图列举是解决过程的方法，不是最终目的。因此，如果能够在列举过程中及时发现规律并加以应用和推广，将更有利于问题的尽快、尽简解决。

二、枚举法的运用
1、分类枚举
例1 分子小于6而分母小于60的最简真分数共有多少个？
解：最简真分数的条件（1）分子比分母小，（2）分子与分母互质。
根据分类的原则，分的类别应该尽可能少，所以这里按分子进行分类枚举比较合理。
⑴当分子为1时，有，，，……，共计59-2+1=58（个）；
⑵当分子为2时，有，，，……，去掉可约分数共（个）；
⑶当分子为3时，有，，，……，去掉可约分数共计（个）；
⑷当分子为4时，有，，，……，去掉可约分数共（个）；
⑸当分子为5时，有……，去掉可约分数共（个）；
用加法原理可得，共有最简真分数：58+29+38+28+44=197（个）

例2 一个长方形被一条直线分为2个部分，那么8条直线最多可以将长方形分为多少个部分？如果是2002条呢？
解：枚举观察，1条直线最多可以将长方形分为：1+1=2（个）部分；
2条直线最多可以将长方形分为：1+1+2=4（个）部分；
3条直线最多可以将长方形分为：1+1+2+3=7（个）部分；
……
所以，8条直线最多可以将长方形分为：1+1+2+3+4+5+6+7+8=37（个）部分。
2002条直线最多可以将长方形分为：1+1+2+3+……+2000+2001+2002=2005004（个）部分。

2、树形图
例3 某人在A、B、C三个城市游览，他今天在这个城市，明天就要到另一个城市。那么，
他从A城出发，4天后仍然回到A城，共有多少种不同游览路线？
解：这位游客的游览路线可以用如下的树形图来表示，

所以他共有6种不同的游览路线。

例4 甲、乙两人进行象棋比赛，双方约定先胜四局者最终胜。现在三局过后，甲为二胜一负。那么要决出最后胜负为止，一共有多少种不同的可能情形？其中甲胜的不同情形共有多少种？（假设没有和局）
解：比赛要决出最后胜负，至少还要赛2场，至多还要赛5场，按进行比赛的场数分类，
再比赛2场可以决出胜负，两场都是甲胜利，1种；
再比赛3场可以决出胜负，前两场甲一负一胜或一胜一负，2种；
再比赛4场可以决出胜负，前三场甲两负一胜，3种；四场都是乙胜，1种；
再比赛5场可以决出胜负，前四场甲三负一胜，4种；前四场乙三胜一负，4种；
∴一共有不同的可能情形：1+2+3+1+4+4=15（种）
其中甲胜利的情形共有：1+2+3+4=10（种）

3、标数枚举（求最短路径）
例5 如图，要从A点走到B点，要求每一步都是向右、向上或者向斜上方，那么共有多少种不同走法？
解：根据题意，每到一个节点就会有不同的路线，
那么对每个节点的路线条数进行标数，则可得到
节点B的路线条数，如图所示，

所以，共有12种不同的走法。

例6 如下各图，由A点沿最短路线到达B点各有多少种不同走法？
解：与例题5一样，对每个节点的路线进行
标数，则可得到节点B的路线条数，
如图所示，
所以，图（1）中，到达B点有20种不同路线，
图（2）中，到达B点有34种不同路线。

第二讲：加法、乘法原理（一）
一、内容概述
1、 加法原理和乘法原理来源于枚举法中分类和有序枚举，是枚举中对于规律的一种概括。加法原理：完成一件事情，有k类不同的方法，而第一类方法中有m1种不同的做法，第二类方法中有m2种不同的做法，……那么完成这一件事情的方法总数为：m1+m2+……+mk
乘法原理：完成一件事情，有k个必经的步骤，而第一个步骤中有m1种不同的做法，第二个步骤中有m2种不同的做法，……。那么完成这一件事情的方法总数为：m1×m2×……×mk

2、可以用下图表示加法原理和乘法原理：

二、加法原理的运用
例1 长沙去广州，可乘火车，也可以乘汽车，还可以乘飞机。如果某天中，长沙去广州有5班火车、4班汽车和3班飞机，那么这一天中由长沙去广州可以有多少种不同的走法？
分析与解：目的：长沙去广州；
途径：乘坐三种不同的交通工具；
结果：乘坐任何一种交通工具都可以到达目的地，整个事件结束。
所以，利用加法原理，由长沙去广州可以有5+4+3=12（种）不同的走法。
例2 有5分币，2分币，1分币各若干，现要组成1角钱，共有多少种不同的组合方式？
分析与解：按币值较大的进行分类枚举，这样分的类别比较少，只有三种，
5分币取两张，另两种币值的没得选择，1种组合方式；
5分币取一张，再考虑2分币，可以取1张，2张，或者不取，3种组合方式；5分币不取，再考虑2分币，可以取1，2，3，4，5张，或者不取，6种组合方式。
利用加法原理，共有1+3+6=10种不同的组合方式。

例3 用10把钥匙开10把锁，但是不知道哪把钥匙开哪把锁，那么最多是多少次就能够将所有的钥匙和所有的锁一一配好？
解：第一片钥匙要找到适合它的锁，至多要试9次；
第二片钥匙要找到适合它的锁，至多要试8次；
第三片钥匙要找到适合它的锁，至多要试7次；
……
所以将所有的钥匙和所有的锁一一配好最多需要
9+8+7+6+5+4+3+2+1=45（次）

三、乘法原理的运用
例4 书架上层放着6本不同的数学书，下层放有5本不同的语文书，从中任取数学书与语文书各一本。有多少种不同的取法？
分析与解：目的：取数学书与语文书各一本
途径：上层取一本，下层取一本，分步进行。
所以，根据乘法原理，共有6×5=30种不同的取法。

例5由数字0、1、3、5、7可以组成多少个没有重复数字的四位数？能被5整除的四位数（没有重复数字）有多少个？
解：（1）没有重复数字的四位数，
先考虑特殊位置，千位数字，只有1，3，5，7四种选择；
百位数字，此时千位数字已经选定，五个数字已经用去1个，
则百位数字只能在剩下的4个数字中选择；
依次类推，十位数字有3种选择，个位数字有2种选择，
根据乘法原理，这样没有重复数字的四位数有4×4×3×2=96（个）
（2）被5整除没有重复数字的四位数，
此时个位数字更为特殊，它只能是0或者5，所以分类讨论，
当个位数字是0时，千位有4种，百位有3种，十位有2种，共计1×4×3×2=24（个）
当个位数字是5时，千位有3种，百位有3种，十位有2种，共计1×3×3×2=18（个）
所以被5整除没有重复数字的四位数有24+18=42（个）

四、加法与乘法原理的综合运用
例6 如图是连接城市A、B、C的公路网，汽车从A点出发经过B到C选择不绕远路的不同路线共有多少种？
解：利用标数枚举可知，从A到B有6种不同走法，
从B到C也有6种不同走法，
所以根据乘法原理，汽车从A点出发经过B到C
选择不绕远路的不同路线共有
6×6=36（种）

★例7 在1-500的自然数中，不含有数字“4”的数共有多少个？
解：考虑0—499，为了统一，把一位数、两位数都看作是三位数，如0看作三位数是000，12看作三位数是012，
如此，这些三位数的个位数字有0，1，2，3，5，6，7，8，9共计9种选择；
十位数字有0，1，2，3，5，6，7，8，9共计9种选择；
百位数字有0，1，2，3共计4种选择；
因此在0—499中，不含有数字“4”的数共有4×9×9=324（个）
在1-500的自然数中，不含有数字“4”的数共有324+1-1=324（个）

阅读专题：容斥原理
一、内容概述
1、容斥原理（又称包含与排除）是计数中的一个基本原理，也是一个常用的计数方法：在计数过程中，常常先将所计数的对象分为几个部分，在对所有的部分分别计数后再进行相加，然后减去重复计数的那些部分。
2、应用容斥原理进行实际计数时，为了能够清楚直观地看到计数的各个部分以及所有重复的那些部分，常常通过作出“韦恩图”——相交的圆圈集合覆盖图予以展示。（如下图）

从图示可以看出：要计数第一、二、三部分一起覆盖面的大小，一方面可以将图分为7个互不相交的部分直接相加；另一方面也可以先将一、二、三部分相加，再减去重复的部分。想一想：怎样减去？
3、容斥原理特别适用于分类不独立的计数。

二、容斥原理一的运用
，这一公式可计算出两个集合圈的有关问题。
例1 四·一班的全体同学都参加了音乐、美术这样两个课外活动小组。其中参加音乐组的有29人，参加美术组的有32人，而两个组都参加的同学有12人。那么四·一班一共有多少名同学？
解：在两个圆的韦恩图中，音乐组的那个圆有29人，美术组的那个圆有32人，
两个组都参加的同学的两圆所重叠的部分有12人，
∴四·一班一共有学生：29+32－12=49（人）

例2 在1-50的自然数中，是6的倍数或者9的倍数的数一共有多少个？
解：在1-50的自然数中是6的倍数的数有[50÷6]=8（个），
是9的倍数的数有[50÷9]=5（个），是18的倍数的数有[50÷18]=2（个）
∴是6的倍数或者9的倍数的数一共有：8+5－2=11（人）

三、容斥原理二的运用
，这一公式可计算出三个集合圈的有关问题。
例3 六年级的160名学生参加期末考试，其中：数学得满分的有58人，语文得满分的有53人，外语得满分的有59人；而语文、数学都得满分的有17人，数学、外语都得满分的有22人，语文、外语都得满分的有20人；语文、数学、外语都得满分的有10人。那么六年级学生中语、数、外一门满分都没得的有多少人？
解：首先根据容斥原理二，求出至少有一门得满分的人数，
58+53+59-17-22-20+10=121（人）
那么在全年级中，剩下的人数便是没有一门的满分的人数：
160-121=39（人）

例4 在1-500的自然数中，既不能被2整除、又不能被3整除、且不能被5整除的数一共有多少个？
解：在1-500的自然数中，能被2整除的有500÷2=250（个）；
能被3整除的有[500÷3]=166（个）；
能被5整除的有500÷5=100（个）；
能被2、3最小公倍数6整除的有[500÷6]=83（个）；
能被2、5最小公倍数10整除的有[500÷10]=50（个）；
能被3、5最小公倍数15整除的有[500÷15]=33个）；
能被2、3、5最小公倍数30整除的有[500÷30]=16（个）；
在1-500的自然数中，能被2或3或5整除的数有：
250+166+100-83-50-33+16=366（个）
所以既不能被2整除、又不能被3整除、且不能被5整除的数一共有500-366=134（个）

四、图像法
不是利用容斥原理的公式计算，而是根据题意画图，并借助图形帮助分析，逐个地计算出各个部分，从而解答问题。
例5 某班有学生48人，其中21人参加数学竞赛，13人参加作文竞赛，有7人既参加数学竞赛又参加作文竞赛，那么
（1）只参加数学竞赛的有多少人？
（2）参加竞赛的一共有多少人？
（3）没有参加竞赛的一共有多少人？
解：根据题意先作图，（如右图所示）
（1）从图上可清楚看出只参加数学竞赛的有21-7=14（人）
（2）根据容斥原理一得：参加竞赛的共有21+13-7=27（人）
（3）没有参加竞赛的一共有48-27=21（人）

例6 在不超过100的自然数中：
（1）被2、3、5三个数都能整除的数有多少个？
（2）能被2、3、5中一数整除，但不能被另两数整除的数分别有多少个？
（3）能被2、3、5中两数整除，但不能被另一个整除的数分别有多少个？不能被2、3、5中任何一个数整除的数有多少个？把以上的结果用图表表示出来。
解：准备工作，不超过100的自然数中，能被2整除的有50个；
能被3整除的有33个；
能被5整除的有20个；
能被6整除的有16个；
能被10整除的有10个；
能被15整除的有6个；
能被30整除的有3个；
（1）被2、3、5三个数都能整除的数有3个；
（2）能被2整除，但不能被3、5整除的有50-10-16+3=27（个）
能被3整除，但不能被2、5整除的有33-16-6+3=14（个）
能被5整除，但不能被2、3整除的有20-10-6+3=7（个）
（3）被2、3但不能被5整除的有16-3=13（个）；被2、5但不能被3整除的有10-3=7（个）；
被3、5但不能被2整除的有6-3=3（个）；
不能被2、3、5中任何一个数整除的数有
100-（50+33+20-16-10-6+3）=34（个）

48
- -