高中数学人教A版 (2019)选择性必修 第三册6.1 分类加法计数原理与分步乘法计数原理图片课件ppt

这是一份高中数学人教A版 (2019)选择性必修 第三册6.1 分类加法计数原理与分步乘法计数原理图片课件ppt，共26页。PPT课件主要包含了分类加法计数原理，复习回顾，N3×26，种挂法如下图所示，×26，冀A·JR005等内容，欢迎下载使用。
如果完成一件事有n类不同方案, 在第1类方案中有m1种不同的方法，在第2类方案中有m2种不同的方法，…，在第n类方案中有mn种不同的方法，那么完成这件事的方法总数为:
N＝m1＋m2＋…＋mn
2.分步乘法计数原理：
如果完成一件事需要n个步骤，做第1步有m1种不同的方法，做第2步有m2种不同的方法 ， ……，做第n步有mn种不同的方法，那么完成这件事共有多少种不同的方法？
N= m1×m2×… ×mn
例4 要从甲、乙、丙、3幅不同的画中选出2幅 , 分别挂在左、右两边墙上的指定位置，问共有多少种不同的挂法？
解: 从3幅画中选出2幅分别挂在左、右两边墙上，可以分两个步骤完成：
第1步, 从3幅画中选出1幅挂在左边墙上, 有3种选法；
第2步, 从剩下的2幅画中选1副挂在右边墙上, 有2种选法 .
根据分步乘法计数原理，不同取法的种数是：
分析: 要完成的一件事是从3幅画中选出2幅，并分别挂在左、右两边墙上，可以分步骤完成：
左边 右边 相应的挂法
分类加法计数原理和分步乘法计数原理，回答的都是有关做一件事的不同方法种数的问题. 区别在于: 分类加法计数原理针对的是“分类”问题，其中各种方法相互独立，用其中任何一种方法都可以做完这件事；分步乘法计数原理针对的是“分步”问题，各个步骤中的方法互相依存，只有每一个步骤都完成才算做完这件事.
例5 给程序模块命名，需要用3个字符，其中首字符要求用字母A~G或U~Z , 后两个字符要求用数字1~9 , 最多可以给多少个程序模块命名？
分析: 要完成的一件事是给一个程序模块命名 , 可以分三个步骤完成: 第1步，选首字符；第2步，选中间字符；第3步，选最后一个字符，而首字符又可以分为两类.
由分步乘法计数原理，不同名称的个数是13×9×9=1053,
解: 由分类加法计数原理，首字符不同选法的种数为7+6=13.
后两个字符从1~9中选，因为数字可以重复，所以不同选法的种数都为9.
即最多可以给1053个程序模块命名.
例6 电子元件很容易实现电路的通与断、电位的高与低等两种状态, 而这也是最容易控制的两种状态 . 因此计算机内部就采用了每一位只有0或1两种数字的记数法，即二进制 . 为了使计算机能够识别字符, 需要对字符进行编码 , 每个字符可以用一个或多个字节来表示 , 其中字节是计算机中数据存储的最小计量单位, 每个字节由8个二进制位构成. （1）一个字节(8位)最多可以表示多少个不同的字符？（2）计算机汉字国标码包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？
例6 字节是计算机中数据存储的最小计量单位, 每个字节由8个二进制位构成. （1）一个字节(8位)最多可以表示多少个不同的字符？（2）计算机汉字国标码包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？
分析: (1)要完成的一件事是确定1个字节各二进制位上的数字 . 由于每个字节有8个二进制位，每一位上的值都是0，1两种选择，而且不同的顺序代表不同的字符，因此可以用分步乘法计数原理来求解；(2)只要计算出多少个字节所能表示的不同字符不少于6763个即可.
例6 字节是计算机中数据存储的最小计量单位, 每个字节由8个二进制位构成. （1）一个字节(8位)最多可以表示多少个不同的字符？
解: (1)用下图表示一个字节，每一格代表一位 .
1个字节共有8位，每位上有2种选择，根据分步乘法计数原理，1个字节最多可以表示不同字符的个数是
2×2×2×2×2×2×2×2=28=256.
例6 字节是计算机中数据存储的最小计量单位, 每个字节由8个二进制位构成. （2）计算机汉字国标码包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？
解: (2)由(1)知, 1个字节所能表示的不同字符不够6763个，我们考虑2个字节能表示多少个字符.
这已经大于汉字国标码包含的汉字个数6736. 因此要对这些汉字进行编码，每个汉字要用2个字节表示.
前1个字节有256种不同的表示方法，后1个字节也有256种表示方法，根据分步乘法计数原理，2个字节可以表示不同字符的个数是
256×256=65536.
练习 1.如图, 从甲地到乙地有2条路可通, 从乙地到丙地有3条路可通; 从甲地到丁地有4条路可通, 从丁地到丙地有2条路可通。从甲地到丙地共有多少种不同的走法？
解: 从总体上看, 由甲到丙有两类不同的走法,
第一类, 由甲经乙去丙, 需分两步, 不同的走法种数为
m1 = 2×3 = 6;
第二类, 由甲经丁去丙, 需分两步,不同的走法种数为
m2 = 4×2 = 8;
所以从甲地到丙地共有 N = 6 + 8 = 14 种不同的走法.
练习2. 如图 , 从A到B共有多少条不同的线路可通电？
解: 从总体上看由A到B的通电线路可分三类,
所以, 根据分类记数原理, 从A到B共有
第一类, m1 = 3 条;
第二类, m2 = 1 条;
第三类, m3 = 2×2 = 4条.
N = 3 + 1 + 4 = 8 条不同的线路可通电。
例7 计算机编程人员在编写好程序以后需要对程序进行测试. 程序员需要知道到底有多少条执行路径(程序从开始到结束的路线), 以便知道需要提供多少个测试数据. 一般地，一个程序模块由许多子模块组成. 如图是一个具有许多执行路径的程序模块, 它有多少条执行路径？ 另外 , 为了减少测试时间 , 程序员需要设法减少测试次数, 你能帮助程序员设计一个测试方法, 以减少测试次数吗?
例7 如图是一个具有许多执行路径的程序模块, 它有多少条执行路径？
分析：整个模块的任意一条执行路径都分两步完成: 第1步是从开始执行到A点 ; 第2步是从A点执行到结束. 而第1步可由子模块1、子模块2、子模块3中任何一个来完成; 第2步可由子模块4、子模块5中任何一个来完成, 因此, 分析一条指令在整个模块的执行路径需要用到两个计数原理.
又由分步乘法计数原理，整个模块的执行路径条数共为
解：由分类加法计数原理，子模块1、子模块2、子模块3中的子路径条数共为
18+45+28=91;
子模块4、子模块5中的子路径条数共为
91×81=7371.
在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块.
这样，他可以先分别单独测试5个模块，以考察每个子模块的工作是否正常，总共需要的测试次数为
18+45+28+38+43=172.
另外 , 为了减少测试时间 , 程序员需要设法减少测试次数, 你能帮助程序员设计一个测试方法, 以减少测试次数吗?
分别单独测试5个模块，总共需要的测试次数为
再测试各个模块之间的信息交流是否正常, 只需要测试程序第1步中的各个子模块和第2步中的各个子模块之间的信息交流是否正常，需要的测试次数为
如果每个子模块都工作正常，并且各个子模块之间的信息交流也正常 , 那么整个程序模块就工作正常. 这样 , 测试整个模块的次数就变为
显然，178与7371的差距是非常大的.
例8 通常, 我国民用汽车号牌的编号由两部分组成: 第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英文字母组成的序号，如图所示. 其中，序号的编码规则为： (1)由10个阿拉伯数字和除O, I之外的24个英文字母组成； (2)最多只能有2个英文字母. 如果某地级市发牌机关采用5位序号编码，那么这个发牌机关最多能发放多少张汽车号牌？
例8 其中，序号的编码规则为： (1)由10个阿拉伯数字和除O, I之外的24个英文字母组成； (2)最多只能有2个英文字母. 如果某地级市发牌机关采用5位序号编码，那么这个发牌机关最多能发放多少张汽车号牌？
分析：由号牌编号的组成可知，序号的个数决定了这个发牌机关所能发放的最多号牌数. 按序号编码规则可知，每个序号中的数字、字母都是可重复的，并且可将序号分为三类：没有字母，有1个字母，有2个字母，以字母所在位置为分类标准，可将有1个字母的序号分为五个子类，将有2个字母的序号分为十个子类.
解：由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数.根据序号编码规则，5位序号可以分为三类： 没有字母，有1个字母，有2个字母.
(1)当没有字母时, 序号的每一位都是数字. 确定一个序号可以分5个步骤, 每一步都可以从10个数字中选1个, 各有10种选法，根据分步乘法计数原理，这类号牌张数为
10×10×10×10×10=100000.
(2)当有1个字母时，这个字母可以分别在序号的第1位、第2位、第3位、第4位或第5位，这类序号可以分为五个子类.
解：根据序号编码规则，5位序号可以分为三类：没有字母，有1个字母，有2个字母.
(1)当没有字母时, 这类号牌张数为100000.
(2)当有1个字母时, 这个字母可以分别在序号的第1、第2、第3、第4位或第5位, 这类序号可以分为五个子类.
当第1位是字母时, 分5个步骤确定一个序号中的字母和数字: 第1步, 从24个字母中选1个放在第1位, 有24种选法; 第2~5步都是从10个数字中选1个放在相应的位置, 各有10种选法, 根据分步乘法计数原理, 号牌张数为240000.
同样, 其余四个子类号牌也各有240000张.
根据分类加法计数原理，这类号牌张数一共为 240000+240000+240000+240000+240000=1200000.
(2)当有1个字母时,号牌张数一共为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个步骤确定一个序号中的字母和数字: 第1, 2步都是从24个字母中选1个分别放在第1位、第2位，各有24种选法；第3~5步都是从10个数字中选1个放在相应的位置，各有10种选法.
(3)当有2个字母时, 可以将这类序号分为十个子类.
根据分步乘法计数原理，号牌张数为
24×24×10×10×10=576000.
当第1位和第2位是字母时,号牌张数为576000.
同样, 其余九个子类号牌也各有576000张. 于是, 这类号牌张数一共为 576000×10=5760000.
综合(1)(2)(3), 根据分类加法计数原理, 这个发牌机关最多能发放的汽车号牌张数为
100000+1200000+5760000=7060000.
用两个计数原理解决计数问题时，最重要的是在开始计算之前要仔细分析两点 : (1)要完成的“一件事”是什么; (2)需要分类还是分步.
分类要做到“不重不漏”，分类后再分别对每一类进行计数，最后用分类加法计数原理求和，得到总数.
分步要做到“步骤完整”，即完成了所有步骤，恰好完成任务，分步后再计算每一步的方法数，最后根据分步乘法计数原理，把完成每一步的方法数相乘，得到总数.