6.1分类加法计数原理与分布乘法计数原理（第2课时）课件-2024-2025学年高二数学下学期人教A版（2019）选择性必修第三册

第六章 计数原理 6.1 分类加法计数原理与 分步乘法计数原理 第 二课时 一 二 三 学习目标 进一步理解和掌握分类加法计数原理和分步乘法计数原理； 能正确理解“完成一件事”的正确含义，能根据事件完成的特征，正确选择“分类”加法、分步乘法进行计算 能利用分类加法、分步乘法计数原理解决相关问题 分类加法计数原理 分步乘法计数原理 相同点 区别 注意 都是用来计算“完成一件事”的不同方法种数的问题 类类独立，不重不漏 步步相依，步骤完整 复习回顾 两个原理的异同点： 分类完成，类类相加 分步完成，步步相乘 任何一类中的任何一种方法都能独立完成这件事 只有依次完成每一个步骤，才能完成这件事（每步中的每一种方法不能独立完成这件事） “类类独立，不重不漏” “步步关联，缺一不可” 新知探究 例4 要从甲、乙、丙、3幅不同的画中选出2幅,分别挂在左、右两边墙上的指定位置，问共有多少种不同的挂法？ 3 2 × 新知探究 例4 要从甲、乙、丙、3幅不同的画中选出2幅,分别挂在左、右两边墙上的指定位置，问共有多少种不同的挂法？ 解:从3幅画中选出2幅分别挂在左、右两边墙上，可以分两个步骤完成： 第1步, 从3幅画中选出1幅挂在左边墙上,有3种选法； 第2步, 从剩下的2幅画中选1副挂在右边墙上,有2种选法 . 根据分步乘法计数原理，不同取法的种数是： 请大家验证一下，是否为6种不同的的取法呢？ 典例解析 左边 右边 相应的挂法 甲 乙 丙 乙 丙 左甲右乙 左甲右丙 左乙右甲 左乙右丙 左丙右甲 左丙右乙 甲 乙 甲 丙 我们可以采用树状图的方式 分类加法计数原理和分步乘法计数原理，回答的都是有关做一件事的不同方法种数的问题. 区别在于: 分类加法计数原理针对的是“分类”问题，其中各种方法相互独立，用其中任何一种方法都可以做完这件事； 分步乘法计数原理针对的是“分步”问题，各个步骤中的方法互相依存，只有每一个步骤都完成才算做完这件事. 典例解析 例5 给程序模块命名，需要用3个字符，其中首字符要求用字母A~G或U~Z，后两个要求用数字1 ~9，最多可以给多少个程序命名？ 分析：要完成的一件事是“给一个程序模块命名”. 可以分三个步骤完成： 第 1 步，选首字符； 第 2 步，选中间字符； 第 3 步，选最后一个字符． 而首字符又可以分为两类． 解: 由分类加法计数原理，首字符不同选法的种数为 7＋6＝13. 后两个字符从1~9中选，因为数字可以重复，所以不同选法的种数都为9. 由分步乘法计数原理，不同名称的个数是 13×9×9＝1053， 即最多可以给1053个程序模块命名. 典例解析 例5 给程序模块命名，需要用3个字符，其中首字符要求用字母A~G或U~Z，后两个要求用数字1 ~9，最多可以给多少个程序命名？ 思考 你还能给出不同的解法吗? 解2:首字符用A~G给程序命名的个数为 7×9×9＝567. 首字符用U~Z给程序命名的个数为 6×9×9＝486. ∴总的不同名称的个数是 567＋486＝1053. 典例解析 例6 电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有0或1两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由８个二进制位构成，问 （1）一个字节（8位）最多可以表示多少个不同的字符？ （2）计算机汉字国标码（GB码）包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？ 第1位 第2位 第3位 第8位 2种 2种 2种 2种 …… 如 00000000， 10000000， 11111111. … 第 1 位 第 2 位 第 3 位 第 8 位 2 种 2 种 2 种 2 种 解:(1)用上图表示1个字节. 1个字节共有8位，每位上有2种选择，根据分步乘法计数原理，1个字节最多可以表示不同字符的个数是 2×2×2×2×2×2×2×2=28=256. (2)由(1)知，1个字节所能表示的不同字符不够6763个，我们考虑2个字节能够表示多少个字符. 前1个字节有256种不同的表示方法，后1个字节也有256种表示方法. 根据分步乘法计数原理，2个字节可以表示不同字符的个数是 256×256=65536 这已经大于汉字国标码包含的汉字个数6763. 因此要对这些汉字进行编码，每个汉字至少要用2个字节表示. 巩固练习 课本P7 1. 某电话局管辖范围内的电话号码由8位数字组成，其中前4位的数字是不变的，后4位数字都是0~9中的一个数字，这个电话局不同的电话号码最多有多少个? 解：104＝10000 (个). 2. 从5名同学中选出正、副组长各1名，有多少种不同的选法? 解：5×4＝20 (种). 3. 从1, 2, ‧‧‧, 19, 20中任选一个数作被减数，再从1, 2, ‧‧‧, 10中任选一个数作减数，然后写成一个减法算式，共可得到多少个不同的算式? 解：20×10＝200 (个). 巩固练习 课本P7 解1：被5除余2的正整数的个位是2或7. 当满足条件的数是一位数时，满足条件的个数有2个 ； 当满足条件的数是两位数时，满足条件的个数有9×2＝18个 ； 当满足条件的数是三位数时，满足条件的个数有4×10×2＝ 80个 . 所以满足条件的数共有100个. 解2：被5除余2的数可以表示为5k＋2 (k为整数). 由1≤5k＋2≤500，解得0≤k≤99， 满足条件的k值有100个， 所以满足条件的数共有100个. 解：满足条件的三位数有5×5×5＝ 125 个 . 5. 由数字1, 2, 3, 4, 5可以组成多少个三位数(各位上的数字可以重复)? 4. 在1, 2, ‧‧‧, 500中，被5除余2的数共有多少个? 新知探究 例7 计算机编程人员在编写好程序以后需要对程序进行测试.程序员需要知道到底有多少条执行路径(程序从开始到结束的路线),以便知道需要提供多少个测试数据. 一般地，一个程序模块由许多子模块组成. 如图是一个具有许多执行路径的程序模块, 它有多少条执行路径？ 另外,为了减少测试时间,程序员需要设法减少测试次数,你能帮助程序员设计一个测试方法,以减少测试次数吗? 分析：整个模块的任意一条执行路径都分两步完成: 第1步是从开始执行到A点;第2步是从A点执行到结束. 而第1步可由子模块1、子模块2、子模块3中任何一个来完成; 第2步可由子模块4、子模块5中任何一个来完成 因此,分析一条指令在整个模块的执行路径需要用到两个计数原理. 典例解析 解：由分类加法计数原理，子模块1、子模块2、子模块3中的子路径条数共为 18+45+28=91 子模块4、子模块5中的子路径条数共 38+43=81 又由分步乘法计数原理，整个模块的执行路径条数共为 91×81=7371 在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块，这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常，总共需要的测试次数为：18+45+28+38+43=172. 再测试各个模块之间的信息交流是否正常，只需要测试程序第1步中的各个子模块和第2步中的各个子模块之间的信息交流是否正常，需要的测试次数为：3×2=6. 如果每个子模块都工作正常，并且各个子模块之间的信息交流也正常，那么整个程序模块就工作正常，这样，测试整个模块的次数就变为：172+6=178. 显然，178与7371的差距是非常大的. 　　你看出了程序员是如何实现减少测试次数的吗？ ？ 典例解析 典例解析 例8 通常，我国民用汽车号牌的编号由两部分组成：第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英文字母组成的序号，如下图所示． 0 冀 A JR005 省、自治区、直辖市简称 发牌机关代号 序号 其中，序号的编码规则为： （1）由 10 个阿拉伯数字和除 O，I 之外的 24 个英文字母组成； （2）最多只能有 2 个英文字母． 　　 如果某地级市发牌机关采用 5 位序号编码，那么这个发牌机关最多能发放多少张汽车号牌？ 分析：由号牌编号的组成可知，序号的个数决定了这个发牌机关所能发放的最多号牌数. 按序号编码规则可知，每个序号中的数字、字母都是可重复的，并且可将序号分为三类：没有字母，有1个字母，有2个字母. 典例解析 解:由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数.根据序号编码规则，5位序号可以分为三类：没有字母，有1个字母，有2个字母. (1)第1类：当序号中没有字母时，序号的每一位都是数字， 确定一个序号可以分5个步骤，每一步都可以从10个数字中选1个，各有10种选法，根据分步乘法计数原理，这类号牌张数为 10×10×10×10×10=100000 典例解析 (2)第2类：当序号中有1个字母时，这个字母可以分别在序号的第1位、第2位、第3位、第4位或第5位，这类序号可以分为五个子类. 当第1位是字母时,分5个步骤确定一个序号中的字母和数字:第1步,从24个字母中选1个放在第1位,有24种选法; 第2～5步都是从10个数字中选1个放在相应的位置,各有10种选法,根据分步乘法计数原理,号牌张数为 24×10×10×10×10=240000 同样，其余四个子类号牌也各有240000张. 根据分类加法计数原理，这类号牌张数一共为 240000+240000+240000+240000+240000=1200000 24×5×104＝1200000 典例解析 (3)第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个步骤确定一个序号中的字母和数字：第1~2步都是从24个字母中选1个分别放在第1位、第2位，各有24种选法；第3~5步都是从10个数字中选1个放在相应的位置，各有10种选法，根据分步乘法计数原理，号牌张数为24x24x10x10x10=576000. 同样，其余九个子类号牌也各有576000张.则这类号牌张数一共为576000x10=5760000张. 综合（1）（2）（3），根据分类加法计数原理，这个发牌机关最多 能发放的汽车号牌张数为100000 + 1200000 + 5760000 = 7060000 归纳： 用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点: (1) 要完成的“一件事”是什么; (2) 需要分类还是需要分步. 分类要做到“不重不漏”. 分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数. 分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务. 分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数. 典例解析 例(补）五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？又他们争夺这四项比赛的冠军，获得冠军的可能性有多少种？ 解:（1）5名学生中任一名均可报其中的任一项，因此每个学生都有4种报名方法，5名学生都报了项目才能算完成这一事件故报名方法种数为 4×4×4×4×4=45种 . （2）每个项目只有一个冠军，每一名学生都可能获得其中的一项获军，因此每个项目获冠军的可能性有5种故有n=5×5×5×5=54种 . 巩固练习 解：展开后共有3×3×5＝45项. 1. 乘积(a1+a2+a3)(b1+b2+b3)(c1+c2+c3+c4+c5) 展开后共有多少项? 解：9＋8＋7＋6＋5＋4＋3＋2＋1＝45 (个). 2. 在所有的两位数中，个位数字小于十位数字的有多少个? 3. 某商场有6个门，如果某人从其中的任意一个门进人商场，并且要求从其他的门出去，那么共有多少种不同的进出商场的方式? 解：进出商场的不同方式有6×5＝30(种). 4.任意画一条直线，在直线上任取n个分点. (1) 从这n个分点中任取2个点形成一条线段，可得到多少条线段? (2) 从这n个分点中任取2个点形成一个向量，可得到多少个向量? 解： 课本P11 作业布置 2.《小本》P3~P4 1.《大本》P5~P7 $$