6.1分类加法计数原理与分步乘法计数原理（2） 课件（共29张PPT）

(共29张PPT)
6.1分类加法计数原理与分步乘法计数原理
第2课时
1.分类加法计数原理：
完成一件事有两类不同方案，在第1类方案中有m种不同的方法，在第2类方案中有n 种不同的方法，那么完成这件事共有N＝m＋n种不同的方法.
推广：如果完成一件事有n类不同方案,在第1类方案中有m1种不同的方法,在第2类方案中有m2种不同的方法，…，在第n类方案中有 mn种不同的方法，那么完成这件事的方法总数为 N＝m1＋m2＋…＋mn.
复习引入
2.分步乘法计数原理：
完成一件事需要两个步骤,做第1步有 m种不同的方法，做第2步有n 种不同的方法,那么完成这件事共有N＝m×n种不同的方法.
推广：如果完成一件事需要n个步骤,做第1步有m1种不同的方法，做第2步有m2种不同的方法，…，做第n步有mn种不同的方法,那么完成这件事的方法总数为N＝m1×m2×…×mn
复习引入
例4.要从甲、乙、丙3幅不同的画中选出2幅,分别挂在左右两边墙上的指定位置,问共有多少种不同的挂法？
分析:要完成的一件事情是“3幅不同的画中选出2幅,并分别挂在左右两边墙上”,可以分步完成.
解:从3幅画中选出2幅，分别挂在左右两边墙上,可以分两个步骤完成:第1步,从3幅画中选1幅挂在左边墙上，有3种选法:第2步,从剩下的2幅画中选1幅挂在右边墙上，有2种选法.根据分步乘法计数原理,不同挂法的种数N=3×2=6.
6种挂法如图6.1-2所示
左边 右边 得到的挂法
甲
乙
丙
图6.1-2
左甲右乙
左甲右丙
左乙右甲
左乙右丙
左丙右甲
左丙右乙
乙
丙
甲
丙
甲
乙
新知探究
例5.给程序模块命名，需要用3个字符，其中首字符要求用字母A～G或U～Z，后两个要求用数字1～9，问最多可以给多少个程序命名？
分析:要完成的一件事情是“给一个程序模块命名”,可以分三个步骤完成:第1步，选首字符：第2步，选中间字符:第3步，选最后一个字符.而首字符又可以分为两类.
解:由分类加法计数原理,首字符不同选法的种数为7+6=13.后两个字符从1~9中选,因数字可以重复,所以不同选法的种数都为9由分步乘法计数原理，不同名称的个数是 N=13×9×9=1053
即最多可以给1053个程序模块命名.
在解题时有时既要分类又要分步
新知探究
例6. 电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的记数法，即二进制.为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由8个二进制位构成.问：
（1）一个字节（8位）最多可以表示多少个不同的字符？
（2）计算机汉字国际码（GB码）包含了6 763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？
=256个
(2).2个字节 (65536个）
分析:要完成的一件事情是“确定1个字节各二进制位上的数字”,由于每个字节有8个二进制，每一位上的值有0,1两种选择，而且不同的顺序代表不同的字符因此可以用分步乘法计数原理求解.如图6.1-3.
第1位 第2位 第3位 第8位
　 　 　 ··· 　
2种 2种 2种 2种
图6.1-3
新知探究
例7. 计算机编程人员在编写好程序以后需要对程序进行测试，程序员需要知道到底有多少条执行路径（即程序从开始到结束的路线），以便知道需要提供多少个测试数据.一般地，一个程序模块由许多子模块组成.如图所示是一个具有许多执行路径的程序模块.
（1）这个程序模块有多少条执行路径；
（2）为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方法，以减少测试次数吗？
新知探究
开始
子模块1
18条执行路径
子模块5
43条执行路径
子模块4
38条执行路径
子模块3
28条执行路径
子模块2
45条执行路径
结束
A
91×81=7371条
172+6=178次
图6.1-4
新知探究
例8. 通常，我国民用汽车牌的编号由两部分组成:第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分由阿拉伯数字和英文字母组成的序号(如图6.1-5).
最多能给 7 060 000 辆汽车上牌照.
冀A·JR005
图6.1-5
其中，序号的编码规则为:
(1)由10个阿拉伯数字和O,I之外24个英文字母组成;
(2)最多只能有2个英文字母.如果某地级市发牌机关采用5位序号编码，那么这个发牌机关最多能发放多少张汽车号牌
分析:由号牌编号的组成可知，序号的个数决定了这个发牌机关所能发放的号牌数，按序号编码规则可知，每个序号中的数字、字母都是可重复的，并且可将序号分为三类:没有字母、有一个字母、有两个字母.以字母所在的位置为分类标准，可将有1个字母的序号分为五个子类，将有两个字母的序号分为十个子类.
新知探究
1．分类计数是指将完成这件事的所有方式进行分类，每一类都能独立完成该
事件． ( )
2.分步计数是指将完成这件事分解成若干步骤，当完成所有的步骤时，这个事件才算完成． ( )
3．当一个事件既需要分步又需要分类时，分步和分类没有先后之分． ( )
提示　当一个事件既需要分步又需要分类时，通常要明确是先分类后分步还是先分步后分类，并且要明确分类的标准和分步的程序问题．
×
√
√
小练
1．有A，B两种类型的车床各一台，现有甲、乙、丙三名工人，其中甲、乙都会操作两种车床，丙只会操作A种车床，要从这三名工人中选两名分别去操作这两种车床，则不同的选派方法有(　　)
A．6种 B．5种
C．4种 D．3种
解析　不同的选派情况可分为3类：若选甲、乙，有2种方法；若选甲、丙，有1种方法；若选乙、丙，有1种方法．根据分类加法计数原理知，不同的选派方法有2＋1＋1＝4(种)．
答案　C
新知探索
2．某班有3名学生准备参加校运会的100米、200米、跳高、跳远四项比赛，如果每班每项限报1人，则这3名学生的参赛的不同方法有(　　)
A．24种 B．48种
C．64种 D．81种
解析　由于每班每项限报1人，故当前面的学生选了某项之后，后面的学生不能再报，由分步乘法计数原理，共有4×3×2＝24(种)不同的参赛方法．
答案　A
新知探索
用前6个大写英文字母和1～9九个阿拉伯数字，以A1，A2，…，B1，B2，…的方式给教室里的座位编号，总共能编出多少个不同的号码？
由于前6个英文字母中的任意一个都能与9个数字中的任何一个组成一个号码，而且它们各不相同，因此共有6×9＝54(个)不同的号码.
提示　编写一个号码要先确定一个英文字母，后确定一个阿拉伯数字，我们可以用树形图列出所有可能的号码．如图：
新知探索
题型一　两个计数原理在排数中的应用
【例1】　用0，1，2，3，4五个数字，
(1)可以排成多少个三位数字的电话号码？
(2)可以排成多少个三位数？
(3)可以排成多少个能被2整除的无重复数字的三位数？
解　(1)三位数字的电话号码，首位可以是0，数字也可以重复，每个位置都有5种排法，共有5×5×5＝53＝125(种)，即可以排成125个三位数字的电话号码．
练习巩固
(2)三位数的首位不能为0，但可以有重复数字，首先考虑首位的排法，除0外共有4种方法，第二、三位可以排0，因此，共有4×5×5＝100(种)，即可以排成100个三位数．
(3)被2整除的数即偶数，末位数字可取0，2，4，因此，可以分两类，一类是末位数字是0，则有4×3＝12(种)排法；一类是末位数字不是0，则末位有2种排法，即2或4，再排首位，因0不能在首位，所以有3种排法，十位有3种排法，因此有2×3×3＝18(种)排法．因而有12＋18＝30(种)排法，即可以排成30个能被2整除的无重复数字的三位数．
练习巩固
【迁移】　(变设问)由本例中的五个数字可组成多少个无重复数字的四位奇数？
解　完成“组成无重复数字的四位奇数”这件事，可以分四步：第一步定个位，只能从1，3中任取一个，有2种方法；第二步定首位，把1，2，3，4中除去用过的一个剩下的3个中任取一个，有3种方法；第三步，第四步把剩下的包括0在内的3个数字先排百位有3种方法，再排十位有2种方法．由分步乘法计数原理知共有2×3×3×2＝36(个)．
练习巩固
规律方法　对于组数问题，应掌握以下原则：
(1)明确特殊位置或特殊数字，是我们采用“分类”还是“分步”的关键．一般按特殊位置(末位或首位)分类，分类中再按特殊位置(或特殊元素)优先的策略分步完成；如果正面分类较多，可采用间接法求解．
(2)要注意数字“0”不能排在两位数字或两位数字以上的数的最高位．
练习巩固
变1 从0，2中选一个数字，从1，3，5中选两个数字，组成无重复数字的三位数，其中奇数的个数为(　　)
A．24 B．18
C．12 D．6
解析　由于题目要求是奇数，那么对于此三位数可以分成两种情况；奇偶奇，偶奇奇．如果是第一种奇偶奇的情况，可以从个位开始分析(3种情况)，之后十位(2种情况)，最后百位(2种情况)，共12种；如果是第二种情况偶奇奇：个位(3种情况)，十位(2种情况)，百位(不能是0，一种情况)，共6种，因此总共有12＋6＝18(种)情况．故选B.
答案　B
练习巩固
题型二　分配问题
【例2】　高三年级的四个班到甲、乙、丙、丁、戊五个工厂进行社会实践，其中工厂甲必须有班级去，每班去何工厂可自由选择，则不同的分配方案有(　　)
A．360种 B．420种
C．369种 D．396种
解析　法一　(直接法)
以甲工厂分配班级情况进行分类，共分为四类：
第一类，四个班级都去甲工厂，此时分配方案只有1种情况；
第二类，有三个班级去甲工厂，剩下的班级去另外四个工厂，其分配方案共有4×4＝16(种)；
练习巩固
第三类，有两个班级去甲工厂，另外两个班级去其他四个工厂，其分配方案共有6×4×4＝96(种)；
第四类，有一个班级去甲工厂，其他班级去另外四个工厂，其分配方案有4×4×4×4＝256(种)．
综上所述，不同的分配方案有1＋16＋96＋256＝369(种)．
法二　(间接法)
先计算四个班自由选择去何工厂的总数，再扣除甲工厂无人去的情况，即：5×5×5×5－4×4×4×4＝369(种)方案．
答案　C
练习巩固
规律方法　选(抽)取与分配问题的常见类型及其解法
(1)当涉及对象数目不大时，一般选用枚举法、树形图法、框图法或者图表法．
(2)当涉及对象数目很大时，一般有两种方法：
①直接使用分类加法计数原理或分步乘法计数原理．一般地，若抽取是有顺序的就按分步进行；若按对象特征抽取的，则按分类进行．
②间接法：去掉限制条件计算所有的抽取方法数，然后减去所有不符合条件的抽取方法数即可．
练习巩固
变2 　(1)有4位老师在同一年级的4个班级中各教一个班的数学，在数学考试时，要求每位老师均不在本班监考，则安排监考的方法种数是(　　)
A．11 B．10
C．9 D．8
(2)从6名志愿者中选4人分别从事翻译、导游、导购、保洁四项不同的工作，若其中甲、乙两名志愿者不能从事翻译工作，则选派方案共有(　　)
A．280种 B．240种
C．180种 D．96种
练习巩固
解析　(1)法一　设四个班级分别是A，B，C，D，它们的老师分别是a，b，c，d，并设a监考的是B，则剩下的三个老师分别监考剩下的三个班级，共有3种不同的方法；同理当a监考C，D时，剩下的三个老师分别监考剩下的三个班级也各有3种不同的方法．这样，由分类加法计数原理知共有3＋3＋3＝9(种)不同的安排方法．
法二　让a先选，可从B，C，D中选一个，即有3种选法．若选的是B，则b从剩下的3个班级中任选一个，也有3种选法，剩下的两个老师都只有一种选法，根据分步乘法计数原理知，共有3×3×1×1＝9(种)不同安排方法．
(2)由于甲、乙不能从事翻译工作，因此翻译工作从余下的4名志愿者中选1人，有4种选法．后面三项工作的选法有5×4×3种，因此共有4×5×4×3＝240(种)选派方案．
答案　(1)C　(2)B
练习巩固
题型三　涂色问题
【例3】　如图所示，要给“创”、“新”、“设”、“计”四个区域分别涂上3种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，有多少种不同的涂色方法？
练习巩固
解　创、新、设、计四个区域依次涂色，分四步．
第1步，涂“创”区域，有3种选择．
第2步，涂“新”区域，有2种选择．
第3步，涂“设”区域，由于它与“创”、“新”区域颜色不同，有1种选择．
第4步，涂“计”区域，由于它与“创”“设”区域颜色不同，有1种选择．
所以根据分步乘法计数原理，得不同的涂色方法共有3×2×1×1＝6(种)．
练习巩固
规律方法　求解涂色(种植)问题一般是直接利用两个计数原理求解，常用方法有：
(1)按区域的不同以区域为主分步计数，用分步乘法计数原理分析；
(2)以颜色(种植作物)为主分类讨论，适用于“区域、点、线段”问题，用分类加法计数原理分析；
(3)对于涂色(立方体)问题将空间问题平面化，转化为平面区域涂色问题.
练习巩固
变3　如图所示，一环形花坛分成A，B，C，D四块，现有四种不同的花供选种，要求在每块里种一种花，且相邻的两块种不同的花，则不同的种法种数为(　　)
A．96 B．84 C．60 D．48
练习巩固
解析　依次种A，B，C，D 4块，当C与A种同一种花时，有4×3×1×3＝36(种)种法；当C与A所种的花不同时，有4×3×2×2＝48(种)种法．由分类加法计数原理知，不同的种法种数为36＋48＝84.
答案　B
练习巩固
用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点:一、要完成的“一件事”是什么;二、需要分类还是分步.
分类要做到“不重不漏”，分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数.
分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务，分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数.
课堂小结