1、6.1 分类加法计数原理与分步乘法计数原理2分类加法计数原理分步乘法计数原理相同点不同点注意点复习引入用来计算“完成一件事”的方法种数 每类方案中的每一种方法都能_完成这件事每步_才算完成这件事情（每步中的每一种方法不能独立完成这件事）类类独立，不重不漏步步相依，步骤完整独立依次完成分类完成，类类相加分步完成，步步相乘例4要从甲、乙、丙 3 幅不同的画中选出 2 幅，分别挂在左、右两边墙上的指定位置，共有多少种不同的挂法？左边右边得到的挂法甲乙丙甲丙甲乙丙乙左甲右乙左甲右丙左乙右甲左乙右丙左丙右甲左丙右乙典例分析分析：要完成的一件事是“从 3 幅画中选出 2 幅，并分别挂在左、右两边墙上”，可
2、以分步完成解:从3幅画中选出2幅分别挂在左、右两边墙上，可以分两个步骤完成:第1步，从3幅画中选1幅挂在左边墙上，有3种选法；第2步，从剩下的2幅画中选1幅挂在右边墙上，有2种选法，根据分步乘法计数原理，不同挂法的种数为N=32=6.例5 给程序模块命名，需要用 3 个字符，其中首字符要求用字母 AG 或 UZ，后两个字符要求用数字 19，最多可以给多少个程序模块命名？典例分析解:由分类加法计数原理，首字符不同选法的种数为7+6=13.后两个字符从19中选，因为数字可以重复，所以不同选法的种数都为9.由分步乘法计数原理，不同名称的个数是1399=1053,即最多可以给1053个程序模块命名.分
3、析：要完成的一件事是“给一个程序模块命名”，可以分三个步骤完成：第 1 步，选首字符；第 2 步，选中间字符；第 3 步，选最后一个字符而首字符又可以分为两类例6 电子元件很容易实现电路的通与断、电位的高与低等两种状态，而这也是最容易控制的两种状态因此计算机内部就采用了每一位只有 0 或 1 两种数字的记数法，即二进制为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用 1 个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由 8 个二进制位构成（1）1 个字节（8 位）最多可以表示多少个不同的字符？（2）计算机汉字国标码包含了 6 763 个汉字，一个汉字为一个字
4、符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？典例分析第 1 位第 2 位第 3 位第 8 位2 种2 种2 种2 种第 1 位第 2 位第 3 位第 8 位2 种2 种2 种2 种解:(1)用右图表示1个字节.1个字节共有8位，每位上有2种选择，根据分步乘法计数原理，1个字节最多可以表示不同字符的个数是22222222=28=256.(2)由(1)知，1个字节所能表示的不同字符不够6763个，我们考虑2个字节能够表示多少个字符.前1个字节有256种不同的表示方法，后1个字节也有256种表示方法.根据分步乘法计数原理，2个字节可以表示不同字符的个数是256256=65536这已经大
5、于汉字国标码包含的汉字个数6763.因此要对这些汉字进行编码，每个汉字至少要用2个字节表示.例7 计算机编程人员在编写好程序以后需要对程序进行测试.程序员需要知道到底有多少条执行路径(程序从开始到结束的路线),以便知道需要提供多少个测试数据.一般地,一个程序模块由许多子模块组成.右图是一个具有许多执行路径的程序模块,它有多少条执行路径？另外,为了减少测试时间,程序员需要设法减少测试次数.你能帮助程序员设计一个测试方法,以减少测试次数吗？典例分析开始结束子模块 118 条执行路径子模块 245 条执行路径子模块 328 条执行路径子模块 438 条执行路径子模块 543 条执行路径A解：由分类加
6、法计数原理，子模块1、子模块2、子模块3中的子路径条数共为18+45+28=91子模块4、子模块5中的子路径条数共38+43=81又由分步乘法计数原理，整个模块的执行路径条数共为9181=7371 再测试各个模块之间的信息交流是否正常，只需要测试程序第1步中的各个子模块和第2步中的各个子模块之间的信息交流是否正常，需要的测试次数为32=6.如果每个子模块都工作正常，并且各个子模块之间的信息交流也正常，那么整个程序模块就工作正常，这样，测试整个模块的次数就变为172+6=178.显然，178与7371的差距是非常大的.在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确
7、的子模块的方式来测试整个模块，这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常，总共需要的测试次数为18+45+28+38+43=172.你看出了程序员是如何实现减少测试次数的吗？例8 通常，我国民用汽车号牌的编号由两部分组成：第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英文字母组成的序号，如下图所示0冀 A JR005省、自治区、直辖市简称发牌机关代号序号典例分析其中，序号的编码规则为：（1）由 10 个阿拉伯数字和除 O，I 之外的 24 个英文字母组成；（2）最多只能有 2 个英文字母如果某地级市发牌机关采用 5
8、位序号编码，那么这个发牌机关最多能发放多少张汽车号牌？解:由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数.根据序号编码规则，5位序号可以分为三类：没有字母，有1个字母，有2个字母.(1)当没有字母时，序号的每一位都是数字，确定一个序号可以分5个步骤，每一步都可以从10个数字中选1个，各有10种选法，根据分步乘法计数原理，这类号牌张数为1010101010=100000(2)当有1个字母时，这个字母可以分别在序号的第1位、第2位、第3位、第4位或第5位，这类序号可以分为五个子类.当第1位是字母时,分5个步骤确定一个序号中的字母和数字:第1步,从24个字母中选1个放在第1位,
9、有24种选法;第25步都是从10个数字中选1个放在相应的位置,各有10种选法,根据分步乘法计数原理,号牌张数为2410101010=240000 同样，其余四个子类号牌也各有240000张.根据分类加法计数原理，这类号牌张数一共为 240000+240000+240000+240000+240000=1200000(3)当有2个字母时，根据这2个字母在序号中的位置，可以将这类序号分为十个子类：第1位和第2位，第1位和第3位，第1位和第4位，第1位和第5位，第2位和第3位，第2位和第4位，第2位和第5位，第3位和第4位，第3位和第5位，第4位和第5位.当第1位和第2位是字母时，分5个步骤确定一个
10、序号中的字母和数字：第1,2步都是从24个字母中选1个分别放在第1位、第2位，各有24种选法；第35步都是从10个数字中选1个放在相应的位置，各有10种选法，根据分步乘法计数原理，号牌张数为2424101010=576000.同样，其余九个子类号牌也各有576000张.于是，这类号牌张数一共为57600010=5760000.综合(1)(2)(3),根据分类加法计数原理，这个发牌机关最多能发放的汽车号牌张数为100000+1200000+5760000=7060000.用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点：（1）要完成的“一件事”是什么；（2）需要分类还是需要分
11、步分类要做到“不重不漏”分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数归纳乘法运算是特定条件下加法运算的简化，分步乘法计数原理和分类加法计数原理也有这种类似的关系吗？思考 (1)有些计数问题既需要进行“分类”，又需要进行“分步”，此时就要注意综合运用两个计数原理来解决问题解决这类问题时，首先要明确是先“分类”后“分步”，还是先“分步”后“分类”；其次，在“分类”和“分步”的过程中，均要有明确的分类标准和分步程序 (2)在既需要分类又需
12、要分步的题目中，可以先根据对题意的理解，合理地画出示意图（如树形图）或列出表格，使问题的实质能直观地表示出来.1某电话局管辖范围内的电话号码由 8 位数字组成，其中前 4 位的数字是不变的，后 4 位数字都是 09 之间的一个数字，这个电话局不同的电话号码最多有多少个？2从 5 名同学中选出正、副组长各 1 名，有多少种不同的选法？课堂练习10 000 个20 种3乘积(a1a2a3)(b1b2b3)(c1c2c3c4c5)展开后共有多少项？4在所有的两位数中，个位数字小于十位数字的有多少个？45 项45 个5由数字1,2,3,4,5可以组成多少个三位数（各位上的数字可以重复）？125 个错解
13、1 第一步，第1位同学去夺这3项冠军，有可能1项都不夺或夺1项、2项、3项，因此有4种不同的情况；第二步，第2位同学去夺这3项冠军也有4种不同的情况；同理第3位、第4位同学也各有4种不同的情况由分步乘法计数原理，共有444444256种不同的情况1.4名同学去争夺3项冠军，不允许并列，共有多少种不同的情况？易错疑难辨析：易错疑难辨析：错解2第一步，第1位同学去争冠军，有3种不同的情况；第二步，第2位同学去争冠军，也有3种不同的情况；同理第3位、第4位同学也各有3种不同的情况由分步乘法计算原理，共有33333481种不同的情况1.4名同学去争夺3项冠军，不允许并列，共有多少种不同的情况？易错疑难
14、辨析：易错疑难辨析：辨析 完成夺取冠军这件事，即每项冠军都有人夺取错解1中可能有4位同学都不得冠军以及1项冠军不止1人获得这种情况，与题意不符；错解2中可能有1项冠军不止1人获得这种情况，也不符合题意正解 可分三步完成，第一项冠军被4名同学争夺，一定是其中1名而且只能是其中一名同学获得，共有4种不同的情况；同理其余2项冠军分被4名同学中的1名获得，各有4种不同的情况由分步乘法计算原理，共有4444364种不同的夺得冠军的情况1.现有高一四个班学生34个，其中一、二、三、四班各7人、8人、9人、10人，他们自愿组成数学课外小组(1)选其中一人为负责人，有多少种不同的选法？(2)每班选一名组长，有
15、多少种不同的选法？(3)推选二人作中心发言，这二人需来自不同的班级，有多少种不同的选法？巩固练习分类求解分步求解先分类后分步解：(1)分四类，第一类，从一班学生中选1人，有7种选法；第二类，从二班学生中选1人，有8种选法；第三类，从三班学生中选1人，有9种选法；第四类，从四班学生中选1人，有10种选法，所以，共有不同的选法N7891034种(2)分四步，第一、二、三、四步分别从一、二、三、四班学生中选一人任组长，所以共有不同的选法N789105 040种(3)分六类，每类又分两步：从一班、二班学生中各选1人，有78种不同的选法；从一、三班学生中各选1人，有79种不同的选法；从一、四班学生中各选
16、1人，有710种不同的选法；从二、三班学生中各选1人，有89种不同的选法；从二、四班学生中各选1人，有810种不同的选法；从三、四班学生中各选1人，有910种不同的选法，所以共有不同的选法N787971089810910431种方法总结对于复杂问题，不能只用分类加法计数原理或分步乘法计数原理解决时，可以综合应用两个原理，可以先分类，在某一类中再分步，也可先分步，在某一步中再分类课堂小结 用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点：（1）要完成的“一件事”是什么；（2）需要分类还是需要分步分类要做到“不重不漏”分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数归纳两大原理妙无穷,茫茫数理此中求;万万千千说不尽,运用解题任驰骋。
