1.1分类加法计数原理与分步乘法计数原理

1.1分类计数原理与分步计数原理用A~Z或0~9给教室的座位编号分析:给座位编号有2类方法,第一类方法,用英文字母，有26种号码;第二类方法,用阿拉伯数字，有10种号码;所以有26+10=36种不同号码.思考1从甲地到乙地，可以乘火车，也可以乘汽车。一天中，火车有4班，汽车有2班。那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法?分析:从甲地到乙地有2类方法,第一类方法,乘火车，有4种方法;第二类方法,乘汽车，有2种方法;所以从甲地到乙地共有4+2=6种方法.思考2你能否发现这两个问题有什么共同特征？1、都是要完成一件事2、用任何一类方法都能直接完成这件事3、都是采用加法运算完成一件事有两类不同的方案，在第1类方案中有m种不同的方法，在第2类方案中有n种不同的方法，那么完成这件事共有N=m+n种不同的方法。两类中的方法不相同例1在填写高考志愿表时,一名高中毕业生了解到,A,B两所大学各有一些自己感兴趣的强项专业,具体如下:A大学生物学化学医学物理学工程学B大学数学会计学信息技术学法学分析:两大学只能选一所一专业,且没有共同的强项专业54+=9如果这名同学只能选一个专业,那么他共有多少种选择呢?变式：在填写高考志愿表时,一名高中毕业生了解到,A,B两所大学各有一些自己感兴趣的强项专业,具体如下:A大学生物学化学医学物理学工程学B大学数学会计学信息技术学法学54+=14如果这名同学只能选一个专业,那么他共有多少种选择呢?C大学机械制造建筑学广告学汉语言文学韩语+5如果完成一件事情有3类不同方案，在第1类方案中有m1种不同的方法，在第2类方案中有m2种不同的方法，在第3类方案中有m3种不同的方法，那么完成这件事情有种不同的方法N=m1+m2+m3探究1完成一件事有n类不同的方案，在第1类方案中有m1种不同的方法，在第2类方案中有m2种不同的方法，那么完成这件事共有种不同的方法。……在第n类方案中有mn种不同的方法，nmmmN21用前6个大写英文字母和1~9个阿拉伯数字,以A1,A2,,B1,B2的方式给教室的座位编号.A123456789A1A2A3A4A5A6A7A8A99种B1234567899种6×9=54思考3分析：这件事分两步完成：第1步，确定一个英文字母，有6种不同方法第2步，确定一个阿拉伯数字，有9种不同方法如图,由A村去B村的道路有3条，由B村去C村的道路有2条。从A村经B村去C村，共有多少种不同的走法?A村B村C村北南中北南分析:从A村经B村去C村有2步,第一步,由A村去B村有3种方法,第二步,由B村去C村有2种方法,所以从A村经B村去C村共有3×2=6种不同的方法思考4完成一件事有两类不同方案,在第1类方案中有m种不同的方法,在第2类方案中有n种不同的方法.那么完成这件事共有种不同的方法.N=m+n分类加法计数原理：完成一件事需要两个步骤,做第1步有m种不同的方法,做第2步有n种不同的方法.那么完成这件事共有N=m×n分步乘法计数原理：种不同的方法.例2设某班有男生30名,女生24名.现要从中选出男、女各一名代表班级参加比赛,共有多少种不同的选法?分两步进行选取男女3024×=720再根据分步乘法原理若再要从语,数,英三科科任老师中选出一名代表参加比赛,那又共有多少种选法?老师3×=2160如果完成一件事情需要3个步骤，第1步有m1种不同的方法，第2步有m2种不同的方法，第3步有m3种不同的方法，那么完成这件事情有种不同的方法N=m1×m2×m3探究2完成一件事需要n个步骤，第1步有m1种不同的方法，第2步有m2种不同的方法，那么完成这件事共有种不同的方法。……第n步有mn种不同的方法，nmmmN21例3书架第1层放有4本不同的计算机书,第2层放有3本不同的文艺书,第3层放有2本不同的体育书.(1)从书架中取1本书,有多少种不同取法?有3类方法,根据分类加法计数原理N=4+3+2=9(2)从书架第1,2,3层各取1本书,有多少种不同取法?分3步完成,根据分步乘法计数原理N=4×3×2=24解题关键：从总体上看做这件事情是“分类完成”,还是“分步完成”.再根据其对应的计数原理计算.要从甲、乙、丙3幅不同的画中选出2幅,分别挂在左、右两边墙上的指定位置,问共有多少种不同的挂法?分两步完成左边右边甲乙丙乙丙甲丙甲乙32第一步第二步×例4两个计数原理分类加法计数原理分步乘法计数原理相同点不同点注意点用来计算“完成一件事”的方法种数每类方案中的每一种方法都能______完成这件事每步_________才算完成这件事情（每步中的每一种方法不能独立完成这件事）类类相加步步相乘类类独立步步相依独立依次完成不重不漏步骤完整分类完成分步完成解答计数问题的一般思维过程：完成一件什么事如何完成这件事利用加法原理进行计数方法的分类过程的分步利用乘法原理进行计数?.9~1,Z~UG~A,3,5序命名问最多可以给多少个程后两个要求用数字或要求用字母其中首字符个字符需要用给程序模块命名例..3;,2;,1:,类而首字符又可以分为两符步选最后一个字第选中间字符步第选首字符步第可以分三个步骤要给一个程序模块命名分析.1367,.种选法首字符共有由分类加法计数原理先计算首字符的选法解.1053,10539913,.个程序命名即最多可以给个不同的名称最多可以有理由分步乘法计数原名称再计算可能的不同程序?吗你还能给出不同的解法例5?RNA,100RNA.,,RNA.U,G,C,A,4.,RNA.RNA6分子少种不同的那么能有多个碱基组成分子由有一类假设位置上的碱基无关个位置上的碱基与其他所以在任意一序出现各种碱基能够以任意次中分子在一个表示分别用同的碱基种不总共有分所占据一种称为碱基的化学成由长链中每一个位置上都至数千个位置的长链甚分子是一个有着数百个一个的化学成分现分子是在生物细胞中发核糖核酸例ＡＵＣＣＵＵＡＡＡＧＧ例6.U,G,C,A,100,100任选一个来占据中每个位置都可以从个位置这时我们有个碱基组成的长链用下面的图来表示由分析位第1位第2位第3位第100种4种4种4种4.4,U,G,C,A,.,100100充方法种填每个位置有中任选一个填入从置中从左到右依次在每个位如上图所示个位置个碱基组成的长链共有解长度为根据分步乘法计数原理,分子数目有的所有可能的不同RNA100.4444100个4100个.NAR.,106.1460100资料的有关阅一下以自己查的同学可有兴趣数非常大的这是一个?,,,6763GB2?81:.8,,,,.,10.,7表示字至少要用多少个字节每个汉要对这些汉字进行编码个汉字为一个字符一个汉字包含了码计算机汉字国标码同的字符最多可以表示多少个不位一个字节问个二进制位构成每个字节由最小计量单位据存储的其中字节是计算机中数多个字节来表示每个字符可以用一个或需要对字符进行编码字符为了使计算机能够识别即二进制种数字的记数法两或了每一位只有因此计算机内部就采用状态两种而这也是最容易控制的的高与低等两种状态的通与断、电位易实现电路容电子元件很例例7.,,1,0,8数原理求解本题因此可以用分步乘法计字符同的而且不同的顺序代表不两种选择值都有每一位上的个二进制位由于每个字节有分析;256222222222,.2,88个不同的字符一个字节最多可以表示法计数原理根据分步乘种选择每位上有位一个字节有来表示一个字节用图解31.1位第1位第2位第3位第8种2种2种2种231.1图.256,256.2,6763,12种表示方法后一个字节也有种不同的表示方法前一个字节有能够表示多少个字符个字节我们就考虑用个字符不够不同用一个字节所能表示的知由.2,.6763,536652562562,个字节表示每个汉字至少要用所以要表示这些汉字的汉字个数经大于汉字国标码包含这已个不同字符示个字节可以表根据分步乘法计数原理?,,,?:.,41.1.,.),(.8以减少测试次数吗法序员设计一个测试方少测试次数你能帮助程程序员需要设法减时间为了减少测试另外执行路径这个程序模块有多少条问路径的程序模块它是一个具有许多执行如图模块组成一个程序模块由许多子的一般个测试数据以便知道需要提供多少线路即程序从开始到结束的径多少条执行路到底有程序员需要知道要对程序进行测试好程序以后需计算机编程人员在编写例例8条执行路径子模块181条执行路径子模块452条执行路径子模块283条执行路径子模块435条执行路径子模块384结束开始A.A2;A1:到结束点执行步是从第点步是从开始执行到第成行路径都分两步完整个模块的任意一条执分析来或子模块或子模块步可由子模块而第3211;完成.542来完成或子模块步可由子模块第.原理计数执行路径需要用到两个一条指令在整个模块的分析因此,);(91284518321,条的子路径共有子模块或或子模块子模块由分类加法计数原理解);(81433854条的子路径共有或子模块子模块).(73718191,条有整个模块的执行路径共又由分步乘法计数原理.1724338284518.,5,.,,试次数为总共需要测作是否一正常以考察每个子模块的工块个模它可以先分别单独测试这样来测试整个模块了正确的子模块的方式即通过只考察是否执行黑箱模块看成一个程序员总是把每一个子在实际测试中.632,21,需要测试次数为常之间的信息交流是否正步中的各子模块步中的各个子模块和第试程序第只需要测信息交流是否正常再测试各个模块之间的.1786172,.,,次为试整个模块的次数就变测这样作正常那么整个程序模块就工息交流也正常并且各子模块之间的信工作如果每个子模块都正常.7371178,的差距是非常大的与显然?实现减少测试次数的吗你看出了程序员是如何?.3,3,33,.,,9少辆汽车上牌照那么这种办法共能给多必须合成一组出现个数字也现个字母必须合成一组出并且字个不重复的阿拉伯数复的英文字母和个不重有每一个汽车牌照都必须成办法种汽车牌照组交通管理部门出台了一扩容汽车牌照号码需要庭汽车拥有量迅速增长某城市家高着人们生活水平的提随例.6.,2,个步骤的字母和数字可以分确定一个牌照在右母组合在左和字母组合即字类牌照可以分为按照新规定分析例9.,,2类的字母组合在右另一一类字母组合在左类将汽车牌照分为解:6,字母和数字照的个步骤确定一个汽车牌分字母组合在左时;26,,126,1种选法有放在首位个个字母中选从步第;25,2,125,2种选法有位放在第个个字母中选从剩下的步第;24,3,124,3种选法有位放在第个个字母中选从剩下的步第;10,4,110,4种选法有位放在第个个数字中选从步第;9,5,19,5种选法有位放在第个个数字中选从剩下的步第.8,6,18,6种选法有位放在第个个数字中选从剩下的步第.000232118910242526,个有字母组合在左的牌照共根据分步乘法计数原理.00023211,个有字母组合在右的牌照也同理.224640001123200011232000,辆汽车上牌照共能给所以在所有的两位数中,个位数字大于十位数字的两位数共有多少个？分析1:按个位数字是2,3,4,5,6,7,8,9分成8类,在每一类中满足条件的两位数分别是:1个,2个,3个,4个,5个,6个,7个,8个.根据加法原理共有1+2+3+4+5+6+7+8=36(个).分析2:按十位数字是1,2,3,4,5,6,7,8分成8类,在每一类中满足条件的两位数分别是:8个,7个,6个,5个,4个,3个,2个,1个.根据加法原理共有8+7+6+5+4+3+2+1=36(个)练习一个三位密码锁,各位上数字由0,1,2,3,4,5,6,7,8,9十个数字组成,可以设置多少种三位数的密码(各位上的数字允许重复)?首位数字不为0的密码数是多少?首位数字是0的密码数又是多少?分析:按密码位数,从左到右依次设置第一位、第二位、第三