1、6.1 6.1 分类加法计数原理分类加法计数原理与分步乘法计数原理分步乘法计数原理 问题导学：问题导学：2022 2022年年3 3月月4 4日政协十三届五日政协十三届五次会议在北京人民大会堂举行，次会议在北京人民大会堂举行，某政协委员某政协委员3 3月月2 2日要从湖北前往日要从湖北前往北京参加会议他有两类快捷途北京参加会议他有两类快捷途径可供选择：一是乘飞机，二是径可供选择：一是乘飞机，二是乘坐动车组假如这天飞机有乘坐动车组假如这天飞机有3 3个航班可乘，动车组有个航班可乘，动车组有4 4个班次个班次可乘可乘问：此委员这一天从湖北到问：此委员这一天从湖北到北京共有多少种快捷途径可选？北京共
2、有多少种快捷途径可选？用一个大写的的英文字母或一个阿拉伯数用一个大写的的英文字母或一个阿拉伯数字给教室里的座位编号，总共能够编出多少种字给教室里的座位编号，总共能够编出多少种不同的号码？不同的号码？思考：思考：因为英文字母共有因为英文字母共有2626个，阿拉伯数字共有个，阿拉伯数字共有1010个，所以总共可以编出个，所以总共可以编出 262610103636种不同的号码种不同的号码探究：探究：你能说一说这个问题的特征吗你能说一说这个问题的特征吗?首先，这里要完成的事情是首先，这里要完成的事情是“给一个座位编号给一个座位编号”；其；其次是次是“或或”字的出现：一个座位编号用一个英文字母或一字的出
3、现：一个座位编号用一个英文字母或一个阿拉伯数字表示因为英文字母与阿拉伯数字互不相同，个阿拉伯数字表示因为英文字母与阿拉伯数字互不相同，所以用英文字母编出的号码与用阿拉伯数字编出的号码也所以用英文字母编出的号码与用阿拉伯数字编出的号码也互不相同这两类号码数相加就得到号码的总数互不相同这两类号码数相加就得到号码的总数上述计数过程的基本环节是：上述计数过程的基本环节是：（1 1）确定分类标准，根据问题条件分为字母号码和数字）确定分类标准，根据问题条件分为字母号码和数字号码两类；号码两类；（2 2）分别计算各类号码的个数；）分别计算各类号码的个数；（3 3）各类号码的个数相加，得出所有号码的个数）各类
4、号码的个数相加，得出所有号码的个数一般地，有如下分类加法计数原理：一般地，有如下分类加法计数原理：问题问题1 1：从甲地到乙地，可以乘火车，也可以从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。一天中，火车有乘汽车，还可以乘轮船。一天中，火车有4 4 班班,汽车有汽车有2 2班，轮船有班，轮船有3 3班。那么一天中乘坐这些班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法交通工具从甲地到乙地共有多少种不同的走法?分析：分析：从甲地到乙地有从甲地到乙地有3 3类方法类方法,第一类方法：乘火车，有第一类方法：乘火车，有4 4种方法种方法;第二类方法：乘汽车，有第二类方法：乘汽车，
5、有2 2种方法种方法;第三类方法：乘轮船，有第三类方法：乘轮船，有3 3种方法种方法;所以从甲地到乙地共有所以从甲地到乙地共有 4+2+3=94+2+3=9 种方法。种方法。完成一件事，有完成一件事，有n n类办法类办法.在第在第1 1类办法中有类办法中有m m1 1种不种不同的方法，在第同的方法，在第2 2类方法中有类方法中有m m2 2种不同的方法，种不同的方法，在第在第n n类方法中有类方法中有m mn n种不同的方法，则完成这件事共有种不同的方法，则完成这件事共有 各类办法之间相互独立各类办法之间相互独立,都能独立的完成这件事，都能独立的完成这件事，要计算方法种数要计算方法种数,只需将
6、各类方法数相加。只需将各类方法数相加。N=m N=m1 1+m+m2 2+m+mn n 种不同的方法种不同的方法 完成一件事有两类不同方案，在第完成一件事有两类不同方案，在第1 1类方案中有类方案中有m m种不同的方法，在第种不同的方法，在第2 2类方案中有类方案中有n n种不同的方法，那种不同的方法，那么完成这件事共有么完成这件事共有 N Nm mn n种不同的方法种不同的方法例例1 1：在填写高考志愿表时，一名高中毕业生了解到：在填写高考志愿表时，一名高中毕业生了解到A A、B B两所两所大学各有一些自己感兴趣的强项专业，具体情况如下：大学各有一些自己感兴趣的强项专业，具体情况如下：A A
7、大学大学B B大学大学生物学生物学化学化学医学医学物理学物理学工程学工程学数学数学会计学会计学信息技术学信息技术学法学法学如果这名同学只能选一个专业，那么他共有多少种选择呢？如果这名同学只能选一个专业，那么他共有多少种选择呢？解：解：这名同学在这名同学在A A大学中有大学中有5 5种专业选择，在种专业选择，在B B大学中有大学中有4 4种专业选择。种专业选择。根据分类加法计数原理：这名同学可能的专业选择共有根据分类加法计数原理：这名同学可能的专业选择共有5+45+49 9种。种。用前用前6 6个大写英文字母和个大写英文字母和1 19 9九个阿拉伯数字，九个阿拉伯数字，以以A A1 1，A A2
8、 2，B B1 1，B B2 2，的方式给教室里的方式给教室里的座位编号，总共能编出多少个不同的号码？的座位编号，总共能编出多少个不同的号码？思考？思考？分析：分析：由于前由于前6 6个英文字母中的任意一个个英文字母中的任意一个都能与都能与9 9个数字中的任何一个组成一个号码，而个数字中的任何一个组成一个号码，而且它们各个不同，因此共有且它们各个不同，因此共有6 69 95454个不同的个不同的号码。号码。字母字母数字数字得到的号码得到的号码A A1 12 23 34 45 56 67 78 89 9A A1 1A A2 2A A3 3A A4 4A A5 5A A6 6A A7 7A A8
9、8A A9 9树形图树形图问题问题2 2：如图，由如图，由A A村去村去B B村的道路有村的道路有3 3条，由条，由B B村去村去C C村的道路有村的道路有2 2条。从条。从A A村经村经B B村去村去C C村，共村，共有多少种不同的走法有多少种不同的走法?A村村B村村C村村北北南南中中北北南南分析：分析：从从A A村经村经B B村去村去C C村有村有2 2步，步，第一步，由第一步，由A A村去村去B B村有村有3 3种方法，种方法，第二步，由第二步，由B B村去村去C C村有村有3 3种方法，种方法，所以，从所以，从A A村经村经B B村去村去C C村共有村共有 3 3 2=62=6种不种不
10、同的方法。同的方法。完成一件事，需要分成完成一件事，需要分成n n个步骤。做第个步骤。做第1 1步有步有m m1 1种种不同的方法，做第不同的方法，做第2 2步有步有m m2 2种不同的方法，种不同的方法，做，做第第n n步有步有m mn n种不同的方法，则完成这件事共有种不同的方法，则完成这件事共有 各个步骤相互依存各个步骤相互依存,只有各个步骤都完成了只有各个步骤都完成了,这件事才算完成这件事才算完成,将各个步骤的方法数相乘得到完成这件事的方法总数。将各个步骤的方法数相乘得到完成这件事的方法总数。N=mN=m1 1m m2 2 m mn n种不同的方法种不同的方法例例2 2：设某班有男生设
11、某班有男生3030名，女生名，女生2424名。现要从中选名。现要从中选出男、女生各一名代表班级参加比赛，共有多少出男、女生各一名代表班级参加比赛，共有多少种不同的选法？种不同的选法？例例3 3：书架的第书架的第1 1层放有层放有4 4本不同的计算机书，第本不同的计算机书，第2 2层放有层放有3 3本不同的文艺书，第本不同的文艺书，第3 3层放有层放有2 2本不同的体育书，本不同的体育书，（1 1）从书架上任取）从书架上任取1 1本书，有多少种不同的取法？本书，有多少种不同的取法？（2 2）从书架的第）从书架的第1 1，2 2，3 3层各取层各取1 1本书，有多少种不同本书，有多少种不同的取法？
12、的取法？解：解：（1 1）从书架上任取一本书，有三类办法：）从书架上任取一本书，有三类办法：第第1 1类办法是：从第类办法是：从第1 1层取层取1 1本计算机书，有本计算机书，有4 4种方法；种方法；第第2 2类办法是：从第类办法是：从第2 2层取层取1 1本文艺书，有本文艺书，有3 3种方法；种方法；第第3 3类办法是：从第类办法是：从第3 3层取层取1 1本体育书，有本体育书，有2 2种方法；种方法；根据分类加法计数原理，不同取法的种数是：根据分类加法计数原理，不同取法的种数是：4329N 答：从书架上任取答：从书架上任取1 1本书，有本书，有9 9种不同的取法。种不同的取法。解：解：（2
13、 2）从书架的）从书架的1 1、2 2、3 3层各取层各取1 1本书，可以分本书，可以分3 3步来完成：步来完成：第第1 1步：从第步：从第1 1层取层取1 1本计算机书，有本计算机书，有4 4种方法；种方法；第第2 2步：从第步：从第2 2层取层取1 1本文艺书，有本文艺书，有3 3种方法；种方法；根据分步乘法计数原理，从书架的根据分步乘法计数原理，从书架的1 1、2 2、3 3层各取层各取1 1本书，本书，不同取法的种数是：不同取法的种数是：124 3 224nNmmm 答：从书架的答：从书架的1 1、2 2、3 3层各取层各取1 1本书，有本书，有2424种不同的取法。种不同的取法。例例
14、3 3：书架的第书架的第1 1层放有层放有4 4本不同的计算机书，第本不同的计算机书，第2 2层放有层放有3 3本不同的文艺书，第本不同的文艺书，第3 3层放有层放有2 2本不同的体育书，本不同的体育书，（1 1）从书架上任取）从书架上任取1 1本书，有多少种不同的取法？本书，有多少种不同的取法？（2 2）从书架的第）从书架的第1 1，2 2，3 3层各取层各取1 1本书，有多少种不同本书，有多少种不同的取法？的取法？请看课本请看课本P5P5：练习：练习练习练习1 1：某县的部分电话号码是某县的部分电话号码是057764057764,后面每个数字来自后面每个数字来自0 09 9这这1010个数
15、个数,问可以产生多少个不问可以产生多少个不同的电话号码同的电话号码?变式变式:若要求最后若要求最后6个数字不重复个数字不重复,则又有多少则又有多少种不同的电话号码种不同的电话号码?057764=15120010 101010 10 10=106分析分析:分析分析:1098765练习练习2 2：一个三位密码锁一个三位密码锁,各位上数字由各位上数字由0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8，9 9十个数字组成十个数字组成,可以设置多少种三位可以设置多少种三位数的密码数的密码(各位上的数字允许重复各位上的数字允许重复)？首位数字不为？首位数字不为0 0的的密码数是多少？
16、首位数字是密码数是多少？首位数字是0 0的密码数又是多少？的密码数又是多少？分析：分析：按密码位数按密码位数,从左到右依次设置第一位、第二位、第从左到右依次设置第一位、第二位、第三位三位,需分为三步完成需分为三步完成;第一步：第一步：m m1 1=10;=10;第二步：第二步：m m2 2=10;=10;第三步：第三步：m m2 2=10.=10.根据分步乘法计数原理根据分步乘法计数原理,共可以设置共可以设置N=10N=10101010=1010=103 3种种三位数的密码。三位数的密码。答答:首位数字不为首位数字不为0 0的密码数是的密码数是N=9N=9101010=910=910102 2
17、种种,首位数字是首位数字是0 0的密码数是的密码数是N=1N=1101010=1010=102 2 种。由此可种。由此可以看出以看出,首位数字不为首位数字不为0 0的密码数与首位数字是的密码数与首位数字是0 0的密的密码数之和等于密码总数。码数之和等于密码总数。.不不重重不不漏漏分分类类要要做做到到分分类类后后再再分分别别.,得得到到总总数数数数原原理理求求和和最最后后用用分分类类加加法法计计对对每每一一类类进进行行计计数数完完成成了了所所有有.步步骤骤完完整整分分步步要要做做到到.,.,得得到到总总数数每每一一步步方方法法数数相相乘乘把把完完成成原原理理最最后后根根据据分分步步乘乘法法计计数
18、数数数方方法法分分步步后后再再计计算算每每一一步步的的立立相相互互独独当当然然步步与与步步之之间间要要恰恰好好完完成成任任务务步步骤骤.,需需要要分分步步是是要要分分类类还还需需细细分分析析行行仔仔前前要要进进之之计计算算开开始始在在重重要要的的是是最最数数问问题题时时原原理理解解决决计计用用两两个个计计数数,3,A GU Z,15 9.?:给给程程序序模模块块命命名名 需需要要用用 个个字字符符 其其中中首首字字符符要要求求用用字字母母或或后后两两个个要要求求用用数数字字问问最最多多可可以以给给多多少少个个程程序序命命名名例例,:1,;2,;3.:要要给给一一个个程程序序模模块块命命名名 可
19、可以以分分三三个个步步骤骤 第第步步 选选首首字字符符 第第 步步 选选分分中中间间字字符符 第第步步选选最最后后一一个个字字符符 而而首首字字符符又又可可以以分分为为两两类类析析.,7613.:先先计计算算首首字字符符的的选选法法 由由分分类类加加法法计计数数原原理理首首字字符符共共有有种种选选法法解解.,13991053,1053.再再计计算算可可能能的的不不同同程程序序名名称称 由由分分步步乘乘法法计计数数原原理理 最最多多可可以以有有个个不不同同的的名名称称 即即最最多多可可以以给给个个程程序序命命名名 ,.01,.,8.:18?2GB6763:6电电子子元元件件很很 容容 易易实实现
20、现电电路路 的的通通与与断断、电电位位的的高高与与低低等等两两种种状状态态 而而这这也也是是最最容容易易控控制制的的两两种种状状态态 因因此此计计算算机机内内部部就就采采用用了了每每一一位位只只有有 或或两两种种数数字字的的记记数数法法 即即二二进进制制 为为了了使使计计算算机机能能够够识识别别字字符符 需需要要对对字字符符进进行行编编码码 每每个个字字符符可可以以用用一一个个或或多多个个字字节节来来表表示示 其其中中字字节节是是计计算算机机中中数数据据存存储储的的最最小小计计量量单单位位 每每个个字字节节由由 个个二二进进制制位位构构成成 问问一一个个字字节节位位 最最多多可可以以表表示示多
21、多少少个个不不同同的的字字符符计计算算机机汉汉字字国国标标码码码码 包包含含了了例例个个汉汉,?字字 一一个个汉汉字字为为一一个个字字符符 要要对对这这些些汉汉字字进进行行编编码码 每每个个汉汉字字至至少少要要用用多多少少个个字字节节表表示示:8,0,1,.分分析析 由由于于每每个个字字节节有有 个个二二进进制制位位 每每一一位位上上的的值值都都有有两两种种选选择择 而而且且不不同同的的顺顺序序代代表表不不同同的的字字符符 因因此此可可以以用用分分步步乘乘法法计计数数原原理理求求解解本本题题88,2.,222222222256;一一个个字字节节有有位位 每每位位上上有有 种种选选择择 根根据据
22、分分步步乘乘法法计计数数原原理理 一一个个字字节节最最多多可可以以表表示示个个不不同同的的字字符符来表示一个字节用图解31.1位位第第1位位第第2位位第第3位位第第8种种2种种2种种2种种2 31.1图图 21,6763,2.256,256.由由知知用用 一一 个个 字字 节节 所所 能能 表表 示示 的的 不不 同同字字 符符 不不 够够个个 我我 们们 就就 考考 虑虑 用用个个 字字 节节能能 够够 表表 示示 多多 少少 个个 字字 符符 前前 一一 个个 字字 节节 有有种种 不不 同同 的的 表表 示示 方方 法法 后后 一一 个个 字字 节节 也也 有有种种 表表 示示 方方 法
23、法,225625665 536,6763.,2.根根 据据 分分 步步 乘乘 法法 计计 数数 原原 理理个个 字字 节节 可可 以以 表表示示个个 不不 同同 字字 符符 这这 已已经经 大大 于于 汉汉 字字 国国 标标 码码 包包 含含 的的 汉汉 字字 个个 数数所所 以以 要要 表表 示示 这这 些些 汉汉 字字 每每 个个 汉汉 字字 至至 少少 要要 用用个个 字字 节节 表表 示示 请看课本请看课本P7P7：练习：练习7:.(),.,.1.14,.:?,?例例计计算算机机编编程程人人员员在在编编写写好好程程序序以以后后需需要要对对程程序序进进行行测测试试 程程序序员员需需要要知
24、知道道 到到底底有有多多少少条条执执行行路路 径径 即即程程序序从从开开始始到到结结束束的的路路线线以以便便知知道道需需要要提提供供多多少少个个测测试试数数据据 一一般般的的 一一个个程程序序模模块块由由许许多多子子模模块块组组成成 如如图图它它是是一一个个具具有有许许多多执执行行路路径径的的程程序序模模块块问问这这个个程程序序模模块块有有多多少少条条 执执行行路路径径另另外外 为为了了减减少少测测试试 时时间间 程程序序员员需需要要设设法法减减少少测测试试次次数数你你能能帮帮助助程程序序员员设设计计一一个个测测试试方方法法 以以减减少少测测试试次次数数吗吗条执行路径条执行路径子模块子模块18
25、1条执行路径条执行路径子模块子模块452条执行路径条执行路径子模块子模块283条执行路径条执行路径子模块子模块435条执行路径条执行路径子模块子模块384结束结束开始开始A:1A;2A.分分析析整整个个模模块块的的任任意意一一条条执执行行路路径径都都分分两两步步完完成成 第第 步步是是从从开开始始执执行行到到点点 第第 步步是是从从点点执执行行到到结结束束来来或子模块或子模块或子模块或子模块步可由子模块步可由子模块而第而第3211;完成完成.542来完成来完成或子模块或子模块步可由子模块步可由子模块第第.原理原理计数计数执行路径需要用到两个执行路径需要用到两个一条指令在整个模块的一条指令在整个
26、模块的分析分析因此因此,:,12318452891();解解 由由分分类类加加法法计计数数原原理理 子子模模块块 或或子子模模块块 或或子子模模块块 的的子子路路径径共共有有条条45384381();子子模模块块 或或子子模模块块 的的子子路路径径共共有有条条,91817371().又又由由分分步步乘乘法法计计数数原原理理 整整个个模模块块的的执执行行路路径径共共有有条条,.,5,.1845283843172.在在实实际际测测试试中中 程程序序员员总总是是把把每每一一个个子子模模块块看看成成一一个个黑黑箱箱 即即通通过过只只考考察察是是否否执执行行了了正正确确的的子子模模块块的的方方式式来来测
27、测试试整整个个模模块块 这这样样 它它可可以以先先分分别别单单独独测测试试个个模模块块 以以考考察察每每个个子子模模块块的的工工作作是是否否一一正正常常总总共共需需要要测测试试次次数数为为,12,2 36.再再测测试试各各个个模模块块之之间间的的信信息息交交流流是是否否正正常常 只只需需要要测测试试程程序序第第 步步中中的的各各个个子子模模块块和和第第 步步中中的的各各子子模模块块之之间间的的信信息息交交流流是是否否正正常常 需需要要测测试试次次数数为为 ,.,1726178.如如果果每每个个子子模模块块都都正正常常工工作作 并并且且各各子子模模块块之之间间的的信信息息交交流流也也正正常常 那
28、那么么整整个个程程序序模模块块就就工工作作正正常常 这这样样 测测试试整整个个模模块块的的次次数数就就变变为为次次,1787371.显显然然与与的的差差距距是是非非常常大大的的1、乘积、乘积 展开后共有几项？展开后共有几项？)()(54321321321cccccbbbaaa3、某商场有、某商场有6个门，如果某人从其中的任意一个个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，共有多门进入商场，并且要求从其他的门出去，共有多少种不同的进出商场的方式？少种不同的进出商场的方式？请看课本请看课本P11P11：练习：练习 2.2.如图如图,从甲地到乙地有从甲地到乙地有2 2条路可通条
29、路可通,从乙地到丁地有从乙地到丁地有3 3条路可通条路可通;从甲地到丙地有从甲地到丙地有4 4条路可通条路可通,从丙地到丁地从丙地到丁地有有2 2条路可通。从甲地到丁地共有多少种不同的走法？条路可通。从甲地到丁地共有多少种不同的走法？甲地甲地乙地乙地丁地丁地丙地丙地 解解:从总体上看从总体上看,由甲到丙有两由甲到丙有两类不同的走法类不同的走法,第一类第一类,由甲经乙去丁由甲经乙去丁,又又需分两步需分两步,所以所以m1=23=6 种不同的走法种不同的走法;第二类第二类,由甲经丙去丁由甲经丙去丁,也也需分两步需分两步,所以所以 m2=42=8 种不同的走法种不同的走法;所以从甲地到丁地共有所以从甲地到丁地共有N=6+8=14 种不同的走法。种不同的走法。请看课本请看课本P11P11：习题：习题6.16.1 3.如图如图,该电该电路路,从从A到到B共共有多少条不有多少条不同的线路可同的线路可通电？通电？AB请看课本请看课本P11P11：习题：习题6.16.1所以所以,根据分类原理根据分类原理,从从A到到B共有共有 N=3+1+4=8 条不同的线路可通电。条不同的线路可通电。解解:从总体上看由从总体上看由A到到B的通电线路可分三类的通电线路可分三类,第一类第一类,m1=3 条条第二类第二类,m2=1 条条第三类第三类,m3=22=4,条条
