分类加法计数原理与分步乘法计数原理(同名840)课件.ppt

1、 问题问题1 1、用用A AZ Z或或0 09 9给教室的座位编号有多少给教室的座位编号有多少不同的号码不同的号码?你能说出这两个问你能说出这两个问题的共同特征吗题的共同特征吗?1、分类加法计数原理完成一件事有两类不同方案,在第1类方案中有m种不同的方法,在第2类方案中有n种不同的方法.那么完成这件事共有 N=m+n种不同的方法注意：两类中的方法不相同例1、在填写高考志愿表时,一名高中毕业生了解到,A,B两所大学各有一些自己感兴趣的强项专业,具体如下:A大学生物学化学医学物理学工程学B大学数学会计学信息技术学法学分 析分 析:两两大学只能大学只能选一所一选一所一专业专业,且且没有共同没有共同的

2、强项专的强项专业业54+=9这名同学可能的专业选择共有这名同学可能的专业选择共有9种种这名同学可能的专业选择共有多少种这名同学可能的专业选择共有多少种?做一件事情，完成它可以做一件事情，完成它可以有有n n类办法类办法,在第一类办在第一类办法中有法中有m m1 1种不同的方法，在第二类办法中有种不同的方法，在第二类办法中有m m2 2种不种不同的方法，同的方法，在第，在第n n类办法中有类办法中有m mn n种不同的方种不同的方法。那么完成这件事共有种法。那么完成这件事共有种不同的方法不同的方法用前用前6 6个大写英文字母和个大写英文字母和1919个阿拉伯数字个阿拉伯数字,以以A A1 1,A

3、 A2 2,B B1 1,B B2 2的方式给教室的座位编号的方式给教室的座位编号.总共能总共能编出多少个不同的号码编出多少个不同的号码?A123456789A1A2A3A4A5A6A7A8A99种B1234567899种6 9=54B1B2B3B4B5B6B7B8B9分析：分析：你能说出这个问题的特征吗你能说出这个问题的特征吗?无论第无论第1 1步采用哪种方法，都不影响第步采用哪种方法，都不影响第2 2步方法的选取步方法的选取2 2、分步乘法计数原理、分步乘法计数原理 完成一件事需要两个步骤完成一件事需要两个步骤,做第做第1 1步有步有m m种不同种不同的方法的方法,做第做第2 2步有步有n

4、 n种不同的方法种不同的方法,那么完成这件那么完成这件事共有事共有N=mN=mn n种不同的方法种不同的方法.例例2、设某班有男生设某班有男生30名名,女生女生24名名.现要从中选出现要从中选出男、女各一名代表班级参加比赛男、女各一名代表班级参加比赛,共有多少种不同共有多少种不同的选法的选法?分析：分析：分两步进行选取分两步进行选取男女3024=720再根据分步乘法原理再根据分步乘法原理若再要从语若再要从语,数数,英三英三科科任老师中选出一科科任老师中选出一名代表参加比赛名代表参加比赛,那又那又共 有 多 少 种 选 法共 有 多 少 种 选 法?老师3=2160 如果完成一件事需要如果完成一

5、件事需要三个步骤三个步骤,做第做第1步有步有m1种不同的方法种不同的方法,做第做第2步有步有m2种不同的方法种不同的方法,做做第第3步有步有m3种不同的方法种不同的方法,那么完成这件事共有那么完成这件事共有_种不同的方法种不同的方法.N=m1m2m3做一件事情，完成它需要分成做一件事情，完成它需要分成n个步骤个步骤，做第一，做第一步有步有m1种不同的方法，做第二步有种不同的方法，做第二步有m2种不同的种不同的方法，方法，做第，做第n步有步有mn种不同的方法，那种不同的方法，那么完成这件事有么完成这件事有_种不同的方法种不同的方法.N=m1m2mn 例例3 3、书架第书架第1 1层放有层放有4

6、4本不同的计算机书本不同的计算机书,第第2 2层层放有放有3 3本不同的文艺书本不同的文艺书,第第3 3层放有层放有2 2本不同的体育本不同的体育书书.(1)从书架中取1本书,有多少种不同取法?有3类方法,根据分类加法计数原理N=4+3+2=9(2)从书架第1,2,3层各取1本书,有多少种不同取法?分3步完成,根据分步乘法计数原理N=432=24例例4 4、要从甲、乙、丙要从甲、乙、丙3 3幅不同的画中选出幅不同的画中选出2 2幅幅,分分别挂在左、右两边墙上的指定位置别挂在左、右两边墙上的指定位置,问共有多少种问共有多少种不同的挂法不同的挂法?分两步完成左边右边甲乙丙乙丙甲丙甲乙32第一步第二

7、步=6分析：分析：根据分步计数原理，最多可以有根据分步计数原理，最多可以有13139 99 910531053种不同的选法种不同的选法例例5 5、给程序模块命名，需要用给程序模块命名，需要用3 3个字符，其中首个字符，其中首个字符要求用字母个字符要求用字母A AG G或或U UZ Z，后两个要求用数，后两个要求用数字字1 19 9，问最多可以给多少个程序命名？，问最多可以给多少个程序命名？分析：分析：要给一个程序模块命名，可以分三个步骤：要给一个程序模块命名，可以分三个步骤：第一步，选首字符；第二步，选中间字符；第三第一步，选首字符；第二步，选中间字符；第三步，选末位字符。步，选末位字符。解：

8、解：首字符共有首字符共有7+67+61313种不同的选法，种不同的选法，答：最多可以给答：最多可以给10531053个程序命名。个程序命名。中间字符和末位字符各有中间字符和末位字符各有9 9种不同的选法种不同的选法例例6 6、核糖核酸（核糖核酸（RNARNA）分子是在生物细胞中发现）分子是在生物细胞中发现的化学成分，一个的化学成分，一个RNARNA分子是一个有着数百个甚分子是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都至数千个位置的长链，长链中每一个位置上都由一种称为碱基的化学成分所占据，总共有由一种称为碱基的化学成分所占据，总共有个不同的碱基，分别用个不同的碱基，分别用A A，C

9、 C，G G，U U表示，在一表示，在一个个RNARNA分子中，各种碱基能够以任意次序出现，分子中，各种碱基能够以任意次序出现，所以在任意一个位置上的碱基与其他位置上的所以在任意一个位置上的碱基与其他位置上的碱基无关。假设有一类碱基无关。假设有一类RNARNA分子由分子由100100个碱基组个碱基组成，那么能有多少种不同的成，那么能有多少种不同的RNARNA分子？分子？UUUAAACCCGGG解：解：100个碱基组成的个碱基组成的长链共有长链共有100个位置，个位置，在每个位置中，从在每个位置中，从A、C、G、U中任选一个来填中任选一个来填入，每个位置有入，每个位置有4种填充方法。根据分步计数

10、原种填充方法。根据分步计数原理，共有理，共有分析分析:用用100个位置表示由个位置表示由100个碱基组成的长链，个碱基组成的长链，每个位置都可以从每个位置都可以从A、C、G、U中任选一个来中任选一个来占据。占据。100410044444个 种不同的种不同的RNA分子分子.第1位第2位 第3位第100位 4种 4种 4种 4种 例例7、电子元件很容易实现电路的通与断、电位的高与电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有算机内部就采用了每一位只有0或或1两种数字的计数法，即

11、两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进计算机中数据存储的最小计量单位，每个字节由个二进制位构成，制位构成，问：问：（1）一个字节（一个字节（8位）最多可以表示多少个不同的字符？位）最多可以表示多少个不同的字符？（2）计算机汉字国标码（计算机汉字国标码（GB码）包含了码）包含了6763个汉字，一个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至个汉字为一个字符

12、，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？少要用多少个字节表示？第1位第2位第3位第8位2种种2种种2种种2种种解：解：（1 1）8=2562共（2 2）由（由（1 1）可知，用一个字节所能表示的不同）可知，用一个字节所能表示的不同字符不够字符不够67636763个，个，所以要表示这些汉字，每个汉字至少要所以要表示这些汉字，每个汉字至少要用用2个字节表示。个字节表示。我们就考虑用我们就考虑用2个字节能够表示个字节能够表示多少个字符。多少个字符。前一个字节有前一个字节有256256种不同的表示方法，种不同的表示方法，后一个字节也有后一个字节也有256256种表示方法。种表示方法。根

13、据分步乘法计根据分步乘法计数原理，两个字节可以表示数原理，两个字节可以表示 256256256=65536256=65536个不同的字符，个不同的字符，这已经大于汉字国标码包含的汉字这已经大于汉字国标码包含的汉字个数个数6763，例例8、计算机编程人员在编写好程序以后要对程序计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条执行路进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的路线），以便知道需要（即程序从开始到结束的路线），以便知道需要提供多少个测试数据。一般地，一个程序模块由提供多少个测试数据。一般地，一个程序模块由许多子模块组成，它是一个具有许多执

14、行路径的许多子模块组成，它是一个具有许多执行路径的程序模块。程序模块。问：问：这个程序模块有多少条执行路径？这个程序模块有多少条执行路径？另外为了减少测试时间，程序员需要设法减少测另外为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式，以试次数，你能帮助程序员设计一个测试方式，以减少测试次数吗？减少测试次数吗？开始开始子模块子模块118条执行路径条执行路径子模块子模块328条执行路径条执行路径子模块子模块245条执行路径条执行路径子模块子模块543条执行路径条执行路径子模块子模块438条执行路径条执行路径结束结束A开始开始子模块子模块118条执行路径条执行路径子模块子

15、模块328条执行路径条执行路径子模块子模块245条执行路径条执行路径子模块子模块543条执行路径条执行路径子模块子模块438条执行路径条执行路径结束结束A分析：分析：整个模块的任整个模块的任意一条路径都分两步意一条路径都分两步完成：完成：第第1 1步是从开始步是从开始执行到执行到A A点；第点；第2 2步是步是从从A A点执行到结束。而点执行到结束。而第一步可由子模块第一步可由子模块1 1或或子模块子模块2 2或子模块或子模块3 3来来完成；第二步可由子完成；第二步可由子模块模块4 4或子模块或子模块5 5来完来完成。因此，分析一条成。因此，分析一条指令在整个模块的执指令在整个模块的执行路径需

16、要用到两个行路径需要用到两个计数原理。计数原理。(184528)(3843)91 817371()条开始开始子模块子模块118条执行路径条执行路径子模块子模块328条执行路径条执行路径子模块子模块245条执行路径条执行路径子模块子模块543条执行路径条执行路径子模块子模块438条执行路径条执行路径结束结束A这样，测试整个模块的次数就变为这样，测试整个模块的次数就变为 172+6=178（次）（次）2）在实际测试中在实际测试中，程序，程序员总是把每一个子模块看员总是把每一个子模块看成一个黑箱，即通过只考成一个黑箱，即通过只考察是否执行了正确的子模察是否执行了正确的子模块的方式来测试整个模块。块的

17、方式来测试整个模块。这样，他可以先分别单独这样，他可以先分别单独测试测试5个模块，以考察每个模块，以考察每个子模块的工作是否正常。个子模块的工作是否正常。总共需要的测试次数为：总共需要的测试次数为：18+45+28+38+43=172。再测试各个模块之间的信再测试各个模块之间的信息交流是否正常，需要测息交流是否正常，需要测试的次数为：试的次数为：。如果每个子模块都正常工如果每个子模块都正常工作，并且各个子模块之间作，并且各个子模块之间的信息交流也正常，那么的信息交流也正常，那么整个程序模块就正常。整个程序模块就正常。3 26 例例9 9、随着人们生活水平的提高，某城市家庭随着人们生活水平的提高

18、，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容。汽车拥有量迅速增长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌照组成办法，交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有个不重复的英文字每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字，并且个字母母和个不重复的阿拉伯数字，并且个字母必须合成一组出现，个数字也必须合成一组必须合成一组出现，个数字也必须合成一组出现，那么这种办法共能给多少辆汽车上牌照出现，那么这种办法共能给多少辆汽车上牌照?同理同理,字母组合在字母组合在右右的牌照也有的牌照也有1123200011232000个个.于是于是,根据分类加法计数

19、原理，得共能给根据分类加法计数原理，得共能给11232000+11232000=2246400011232000+11232000=22464000（辆）汽车上牌照（辆）汽车上牌照.字母组合在字母组合在左左时，分时，分6 6个个步骤确定一个牌照的字母和数字：步骤确定一个牌照的字母和数字：第一步第一步,从从2626个字母中选一个个字母中选一个,放在首位放在首位,有有26 26 种选法；种选法；第二步第二步,从剩下的从剩下的2525个字母中选个字母中选1 1个个,放在第放在第2 2位位,有有2525种选法种选法第三步第三步,从剩下的从剩下的2424个字母中选个字母中选1 1个个,放在第放在第3 3

20、位位,有有2424种选法种选法第四步第四步,从从1010个数字中选个数字中选1 1个个,放在第放在第4 4位位,有有1010种选法；种选法；第五步第五步,从剩下的从剩下的9 9个数字中选个数字中选1 1个个,放在第放在第5 5位位,有有9 9种选法；种选法；第六步第六步,从剩下的从剩下的8 8个数字中选个数字中选1 1个个,放在第放在第6 6位位,有有8 8种选法种选法.根据分步乘法计数原理，字母组合在左的牌照共有根据分步乘法计数原理，字母组合在左的牌照共有26262525242410109 98=112320008=11232000（个）（个）.解：解：将汽车牌照分为将汽车牌照分为2 2类，

21、一类的字母组合在左，另类，一类的字母组合在左，另一类的字母组合在右一类的字母组合在右.在所有的两位数中在所有的两位数中,个位数字大于十位数字个位数字大于十位数字的两位数共有多少个？的两位数共有多少个？练习 一个三位密码锁一个三位密码锁,各位上数字由各位上数字由0,1,2,3,4,5,6,7,8,9十个数字组成十个数字组成,可以设置多少种三位数的可以设置多少种三位数的密码密码(各位上的数字允许重复各位上的数字允许重复)?首位数字不为首位数字不为0的的密码数是多少密码数是多少?首位数字是首位数字是0的密码数又是多少的密码数又是多少?分析分析:按密码位数按密码位数,从左到右从左到右依次设置第一位、第

22、二位、第三依次设置第一位、第二位、第三位位,需分为三步完成需分为三步完成;第一步第一步,m1=10;第二步第二步,m2=10;第三步第三步,m3=10.根据乘法原理根据乘法原理,共可以设置共可以设置 N=101010=103 种三位数的密码。种三位数的密码。练习 答答:首位数字不为首位数字不为0的密码数是的密码数是 N=91010=9102 种种,首位数字是首位数字是0的密码数是的密码数是 N=11010=102 种。种。由此可以看出由此可以看出,首位数字不为首位数字不为0的密码数与首的密码数与首位数字是位数字是0的密码数之和等于密码总数。的密码数之和等于密码总数。问问:若设置四位、五位、六位

23、、若设置四位、五位、六位、等密码、等密码,密码数分别有多少种？密码数分别有多少种？答答:它们的密码种数依次是它们的密码种数依次是 104,105,106,种。种。分类计数原理分类计数原理 分步计数原理分步计数原理完成一件事，共有完成一件事，共有n类类办法，关键词办法，关键词“分类分类”区别区别1完成一件事，共分完成一件事，共分n个个步骤，关键词步骤，关键词“分步分步”区别区别2区别区别3每类办法都能独立地完成每类办法都能独立地完成这件事情，它是独立的、这件事情，它是独立的、一次的、且每次得到的是一次的、且每次得到的是最后结果，最后结果，只须一种方法只须一种方法就可完成这件事就可完成这件事。每一

24、步得到的只是中间结果，每一步得到的只是中间结果，任何一步都不能独立完成这件任何一步都不能独立完成这件事，缺少任何一步也不能完成事，缺少任何一步也不能完成这件事，这件事，只有各个步骤都完成只有各个步骤都完成了，才能完成这件事了，才能完成这件事。各类办法是互相独立的。各类办法是互相独立的。各步之间是互相关联的。各步之间是互相关联的。即：即：类类独立，步步关联。类类独立，步步关联。1、分类计数原理和分步计数原理的、分类计数原理和分步计数原理的内容；内容；2、在解决实际问题时应如何正确选、在解决实际问题时应如何正确选择分类计数原理和分步计数原理择分类计数原理和分步计数原理.小结小结:作业作业:P12 习题习题1.1 A组组 1 B组组 1