《分类加法计数原理和分步乘法计数原理.ppt》由会员分享,可在线阅读,更多相关《分类加法计数原理和分步乘法计数原理.ppt(78页珍藏版)》请在金锄头文库上搜索。
1、1.1分类计数原理分类计数原理与分步计数原理分步计数原理 2008年年29届夏季奥运会在北京举行奥运届夏季奥运会在北京举行奥运会足球赛共有个队参赛它们先分成个会足球赛共有个队参赛它们先分成个小组进行循环赛,决出强,这个队按确定小组进行循环赛,决出强,这个队按确定的程序进行淘汰赛后,最后决出冠亚军,此外的程序进行淘汰赛后,最后决出冠亚军,此外还决出了第三、第四名问一共安排了多少场还决出了第三、第四名问一共安排了多少场比赛?比赛?实际问题实际问题 要回答这个问题,就要用到排列、组合的知要回答这个问题,就要用到排列、组合的知识识在运用排列、组合方法时,经常要用到在运用排列、组合方法时,经常要用到分类
2、分类分类分类计数原理与分步计数原理计数原理与分步计数原理计数原理与分步计数原理计数原理与分步计数原理 用一个大写的的英文字母用一个大写的的英文字母或或一个阿拉伯一个阿拉伯数字给教室里的座位编号,总共能够编出多数字给教室里的座位编号,总共能够编出多少种不同的号码?少种不同的号码?问题问题 1问题问题 2. 从甲地到乙地,可以乘火车,也从甲地到乙地,可以乘火车,也可以乘汽车,还可以乘轮船。一天中,火可以乘汽车,还可以乘轮船。一天中,火车有车有4 班班, 汽车有汽车有2班,轮船有班,轮船有3班。那么一班。那么一天中乘坐这些交通工具从甲地到乙地共有天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法多
3、少种不同的走法?分析分析: 从甲地到乙地有从甲地到乙地有3类方法类方法, 第一类方法第一类方法, 乘火车,有乘火车,有4种方法种方法; 第二类方法第二类方法, 乘汽车,有乘汽车,有2种方法种方法; 第三类方法第三类方法, 乘轮船乘轮船, 有有3种方法种方法; 所以所以 从甲地到乙地共有从甲地到乙地共有 4 + 2 + 3 = 9 种方法。种方法。 一、分类计数原理一、分类计数原理一、分类计数原理一、分类计数原理 完成一件事,有两类办法完成一件事,有两类办法. 在第在第1类办法中有类办法中有m种不同的方法,在第种不同的方法,在第2类方法中有类方法中有n种不同的方种不同的方法,则完成这件事共有法,
4、则完成这件事共有 2)首先要根据具体的问题确定一个分类标准,在分)首先要根据具体的问题确定一个分类标准,在分类标准下进行分类,然后对每类方法计数类标准下进行分类,然后对每类方法计数.1)各类办法之间相互独立)各类办法之间相互独立,都能独立的完成这件事,都能独立的完成这件事,要计算方法种数要计算方法种数,只需将各类方法数相加只需将各类方法数相加,因此分类计因此分类计数原理又称数原理又称加法原理加法原理说明说明说明说明N= m+n种不同的方法种不同的方法问题问题3 3、用前用前6 6个大写英文字母和个大写英文字母和1 19 9九个阿拉九个阿拉伯数字,以伯数字,以A A1 1,A A2 2,B B1
5、 1,B B2 2,的方式给教室里的座位编号,总共能编出多的方式给教室里的座位编号,总共能编出多少个不同的号码?少个不同的号码?字母字母数字数字得到的号码得到的号码A A123456789A1A2A3A4A5A6A7A8A9树形图树形图二、分步计数原理二、分步计数原理二、分步计数原理二、分步计数原理 完成一件事,需要两个步骤。做第完成一件事,需要两个步骤。做第1步有步有m种不种不同的方法,做第同的方法,做第2步有步有n种不同的方法,则完成这件事种不同的方法,则完成这件事共有共有 2)首先要根据具体问题的特点确定一个分步的标准,)首先要根据具体问题的特点确定一个分步的标准,然后对每步方法计数然后
6、对每步方法计数.1)各个步骤相互依存)各个步骤相互依存,只有各个步骤都完成了只有各个步骤都完成了,这件事这件事才算完成才算完成,将各个步骤的方法数相乘得到完成这件事的将各个步骤的方法数相乘得到完成这件事的方法总数方法总数,又称又称乘法原理乘法原理说明说明说明说明N= mn种不同的方法种不同的方法 加法原理加法原理 乘法原理乘法原理联系联系区别一区别一完成一件事情共有完成一件事情共有n类类办法,关键词是办法,关键词是“分类分类”完成一件事情完成一件事情,共分共分n个个步骤,关键词是步骤,关键词是“分步分步”区别二区别二每类办法都能每类办法都能独立完成独立完成这件事情。这件事情。每一步得到的只是中
7、间结果,每一步得到的只是中间结果,任何一步都任何一步都不能能独立完成不能能独立完成这件事情这件事情,缺少任何一步也,缺少任何一步也不能完成这件事情,只有每不能完成这件事情,只有每个步骤完成了,才能完成这个步骤完成了,才能完成这件事情。件事情。分类计数原理和分步计数原理,回答的都是关于分类计数原理和分步计数原理,回答的都是关于完成一件事情的不同方法的种数的问题。完成一件事情的不同方法的种数的问题。区别三区别三各类办法是互斥的、各类办法是互斥的、并列的、独立的并列的、独立的各步之间是相关联的各步之间是相关联的分类计数与分步计数原理的区别和联系:分类计数与分步计数原理的区别和联系:例例1在填写高考志
8、愿表时,一名高中毕业生了解到在填写高考志愿表时,一名高中毕业生了解到A、B两两所大学各有一些自己感兴趣的强项专业,具体情况如下:所大学各有一些自己感兴趣的强项专业,具体情况如下:A大学大学B大学大学生物学生物学化学化学医学医学物理学物理学工程学工程学数学数学会计学会计学信息技术学信息技术学法学法学如果这名同学只能选一个专业,那么他共有多少种选择呢?如果这名同学只能选一个专业,那么他共有多少种选择呢?解:这名同学在解:这名同学在A大学中有大学中有5种专业选择,在种专业选择,在B大学中有大学中有4种专业选择。种专业选择。根据分类计数原理:这名同学可能的专业选择共有根据分类计数原理:这名同学可能的专
9、业选择共有5+49种。种。例例2、设某班有男生设某班有男生30名,女生名,女生24名。现要从中选出名。现要从中选出男、女生各一名代表班级参加比赛,共有多少种不同男、女生各一名代表班级参加比赛,共有多少种不同的选法?的选法?例例3、肥城市的部分电话号码是肥城市的部分电话号码是0538323,后面每个后面每个数字来自数字来自09这这10个数个数,问可以产生多少个不同的电话问可以产生多少个不同的电话号码号码?变式变式: 若要求最后若要求最后4个数字不重复个数字不重复,则又有多少种不同则又有多少种不同的电话号码的电话号码?053832310 10 10 10=104分析分析:分析分析:=504010
10、987例例4、 书架上第书架上第1层放有层放有4本不同的计算机书本不同的计算机书,第第 2层放有层放有3本不同的文艺书本不同的文艺书,第第3层放有层放有2本不同的本不同的体育杂志体育杂志.(2)从书架的第从书架的第1、 2、 3层各取层各取1本书本书,有多少种有多少种 不同取法不同取法? N43+29 N4 3224(1)从书架上任取从书架上任取1本书本书,有多少种不同的取法有多少种不同的取法?解:需先分类再分步解:需先分类再分步. .(3 3)从书架上取)从书架上取2 2本不同种的书本不同种的书, ,有多少种不同有多少种不同的取法的取法? ?根据两个基本原理,不同的取法总数是根据两个基本原理
11、,不同的取法总数是 N=43+42+32=26N=43+42+32=26第一类:从一、二层各取一本,第一类:从一、二层各取一本,有有43=1243=12种方法;种方法;第二类:从一、三层各取一本,第二类:从一、三层各取一本,有有42=842=8种方法;种方法;第三类:从二、三层各取一本,第三类:从二、三层各取一本,有有32=632=6种方法;种方法;答答: : 从书架上取从书架上取2 2本不同种的书本不同种的书, ,有有2626种不同种不同的取法的取法. .例例 要从甲、乙、丙要从甲、乙、丙3 3幅不同的画中选出幅不同的画中选出2 2幅,幅,分别挂在左右两边墙上的指定位置,问共有多分别挂在左右
12、两边墙上的指定位置,问共有多少种不同的挂法?少种不同的挂法?326.三个比赛项目,六人报名参加。三个比赛项目,六人报名参加。)每人参加一项有多少种不同的方法?每人参加一项有多少种不同的方法?)每项人,且每人至多参加一项,有多每项人,且每人至多参加一项,有多少种不同的方法?少种不同的方法?)每项人,每人参加的项数不限,有多)每项人,每人参加的项数不限,有多少种不同的方法?少种不同的方法?7.现要安排一份现要安排一份5天值班表,每天有一个人值班。共有天值班表,每天有一个人值班。共有5个人,个人,每个人都可以值多天班或不值班,但相邻两天不能由同一个每个人都可以值多天班或不值班,但相邻两天不能由同一个
13、人值班,问此值班表由多少种不同的排法?人值班,问此值班表由多少种不同的排法?解:分解:分5步进行:步进行:第一步:先排第一天,可排第一步:先排第一天,可排5人中的任一个,有人中的任一个,有5种排法;种排法;第二步:再排第二天,此时不能排第一天的人,有第二步:再排第二天,此时不能排第一天的人,有4种排法种排法;第三步:再排第三天,此时不能排第二天的人,有第三步:再排第三天,此时不能排第二天的人,有4种排法种排法;第四步:同前第四步:同前第五步:同前第五步:同前由分步计数原理可得不同排法有由分步计数原理可得不同排法有544441280种种8.个班分别从个风景点中选择一处游览,不同选法的种个班分别从
14、个风景点中选择一处游览,不同选法的种数是数是还是还是?9.乘积(乘积(a1+a2+a3 )()(b1+b2+b3+b4 )()(c1+c2+c3+c4+c5)展开后共有多少项?展开后共有多少项? 10.如图如图,该该电路电路,从从A到到B共有多少条共有多少条不同的线路不同的线路可通电?可通电?AB解解: 从总体上看由从总体上看由A到到B的通电线路可分三类的通电线路可分三类, 第一类第一类, m1 = 3 条条 第二类第二类, m2 = 1 条条 第三类第三类, m3 = 22 = 4, 条条 所以所以, 根据分类原理根据分类原理, 从从A到到B共有共有 N = 3 + 1 + 4 = 8 条不
15、同的线路可通电。条不同的线路可通电。在解题时有时既要分类又要分步。在解题时有时既要分类又要分步。1、分类加法计数原理、分类加法计数原理:完成一件事,有:完成一件事,有n类办法,在类办法,在第第1类办法中有类办法中有m1种不同的方法种不同的方法,在第在第2类办法中有类办法中有m2种不同的方法种不同的方法在第在第n类办法中类办法中有有m mn n种不同的方法种不同的方法. .那么完成这件事共有那么完成这件事共有 种不同的方种不同的方法法. .2 2、分步乘法计数原理、分步乘法计数原理:完成一件事,需要分成完成一件事,需要分成n n个步个步骤,做第骤,做第1 1步有步有m m1 1种不同的方法种不同
16、的方法, ,做第做第2 2步有步有m m2 2种不同的种不同的方法方法,做第,做第n n步有步有m mn n种不同的方法种不同的方法. .那么完成这件事那么完成这件事共有共有 种不同的方法种不同的方法. .分类加法计数原理和分步乘法计数原理的分类加法计数原理和分步乘法计数原理的共同点:共同点:不同点:不同点:分类加法计数原理与分类有关,分类加法计数原理与分类有关,分步乘法计数原理与分步有关。分步乘法计数原理与分步有关。回答的都是有关做一件事的不同方法种数的问题回答的都是有关做一件事的不同方法种数的问题分类计数原理分类计数原理 分步计数原理分步计数原理完成一件事,共有完成一件事,共有n类类办法,
17、关键词办法,关键词“分类分类”区别区别1完成一件事,共分完成一件事,共分n个个步骤,关键词步骤,关键词“分步分步”区别区别2区别区别3每类办法都能独立地完成每类办法都能独立地完成这件事情,它是独立的、这件事情,它是独立的、一次的、且每次得到的是一次的、且每次得到的是最后结果,最后结果,只须一种方法只须一种方法就可完成这件事就可完成这件事。每一步得到的只是中间结果,每一步得到的只是中间结果,任何一步都不能独立完成这件任何一步都不能独立完成这件事,缺少任何一步也不能完成事,缺少任何一步也不能完成这件事,这件事,只有各个步骤都完成只有各个步骤都完成了,才能完成这件事了,才能完成这件事。各类办法是各类
18、办法是互相独立互相独立的。的。各步之间是各步之间是互相互相关联的。关联的。即:即:类类独立,步步关联类类独立,步步关联。例例1. 1. 五名学生报名参加四项体育比赛,每人限五名学生报名参加四项体育比赛,每人限报一项,报名方法的种数为多少?又他们争夺报一项,报名方法的种数为多少?又他们争夺这四项比赛的冠军,获得冠军的可能性有多少这四项比赛的冠军,获得冠军的可能性有多少种?种? 解:(解:(1)5名学生中任一名均可报其中的任一项,因此每名学生中任一名均可报其中的任一项,因此每个学生都有个学生都有4种报名方法,种报名方法,5名学生都报了项目才能算完成名学生都报了项目才能算完成这一事件故报名方法种数为
19、这一事件故报名方法种数为44444= 种种 .(2)每个项目只有一个冠军,每一名学生都可能获得)每个项目只有一个冠军,每一名学生都可能获得其中的一项获军,因此每个项目获冠军的可能性有其中的一项获军,因此每个项目获冠军的可能性有5种种故有故有n=5= 种种 .例例2.给程序模块命名,需要用给程序模块命名,需要用3个字符,其中首个字个字符,其中首个字符要求用字母符要求用字母AG或或UZ,后两个要求用数字后两个要求用数字19,问最多可以给多少个程序命名?,问最多可以给多少个程序命名?分析:分析:要给一个程序模块命名,可以分三个步骤:第一步,要给一个程序模块命名,可以分三个步骤:第一步,选首字符;第二
20、步,先中间字符;第三步,选末位字符。选首字符;第二步,先中间字符;第三步,选末位字符。解:解:首字符共有首字符共有7+613种不同的选法,种不同的选法,答:答:最多可以给最多可以给10531053个程序命名。个程序命名。中间字符和末位字符各有中间字符和末位字符各有9种不同的选法种不同的选法根据分步计数原理,最多可以有根据分步计数原理,最多可以有13991053种不同的选法种不同的选法例例3.核糖核酸(核糖核酸(RNA)分子是在生物细胞中发现的化学成分,一个分子是在生物细胞中发现的化学成分,一个RNA分子分子是一个有着数百个甚至数千个位置的长链,长链中每一个位置上都由一种称是一个有着数百个甚至数
21、千个位置的长链,长链中每一个位置上都由一种称为碱基的化学成分所占据,总共有个不同的碱基,分别用为碱基的化学成分所占据,总共有个不同的碱基,分别用A,C,G,U表表示,在一个示,在一个RNA分子中,各种碱基能够以任意次序出现,所以在任意一个位分子中,各种碱基能够以任意次序出现,所以在任意一个位置上的碱基与其他位置上的碱基无关。假设有一类置上的碱基与其他位置上的碱基无关。假设有一类RNA分子由分子由100个碱基组个碱基组成,那么能有多少种不同的成,那么能有多少种不同的RNA分子?分子?UUUAAACCCGGG分析分析:用用100个位置表示由个位置表示由100个碱基组成的长链,每个位置都可以从个碱基
22、组成的长链,每个位置都可以从A、C、G、U中任选一个来占据。中任选一个来占据。第1位第2位第3位第100位4种4种4种4种解:解:100个碱基组成的长链共有个碱基组成的长链共有100个位置,在每个位置中,从个位置,在每个位置中,从A、C、G、U中任选一个来填入,每个位置有中任选一个来填入,每个位置有4种填充方法。根据分步计数原理,共有种填充方法。根据分步计数原理,共有种不同的种不同的RNA分子分子.例例4.电子元件很容易实现电路的通与断、电位的高与底等两种电子元件很容易实现电路的通与断、电位的高与底等两种状态,而这也是最容易控制的两种状态。因此计算机内部就采状态,而这也是最容易控制的两种状态。
23、因此计算机内部就采用了每一位只有用了每一位只有0或或1两种数字的计数法,即二进制,为了使计两种数字的计数法,即二进制,为了使计算机能够识别字符,需要对字符进行编码,每个字符可以用一算机能够识别字符,需要对字符进行编码,每个字符可以用一个或多个字节来表示,其中字节是计算机中数据存储的最小计个或多个字节来表示,其中字节是计算机中数据存储的最小计量单位,每个字节由个二进制位构成,问量单位,每个字节由个二进制位构成,问(1)一个字节()一个字节(8位)最多可以表示多少个不同的字符?位)最多可以表示多少个不同的字符?(2)计算机汉字国标码()计算机汉字国标码(GB码)包含了码)包含了6763个汉字,一个
24、汉个汉字,一个汉字为一个字符,要对这些汉字进行编码,每个汉字至少要用多字为一个字符,要对这些汉字进行编码,每个汉字至少要用多少个字节表示?少个字节表示?第1位第2位第3位第8位2种2种2种2种如如00000000,10000000,11111111.开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A例例5.计算机编程人员在编计算机编程人员在编写好程序以后要对程序进写好程序以后要对程序进行测试。程序员需要知道行测试。程序员需要知道到底有多少条执行路(即到底有多少条执行路(即程序从开始到结束的线),程序从开始到结束的线),以便知
25、道需要提供多少个以便知道需要提供多少个测试数据。一般的,一个测试数据。一般的,一个程序模块又许多子模块组程序模块又许多子模块组成,它的一个具有许多执成,它的一个具有许多执行路径的程序模块。问:行路径的程序模块。问:这个程序模块有多少条执这个程序模块有多少条执行路径?另外为了减少测行路径?另外为了减少测试时间,程序员需要设法试时间,程序员需要设法减少测试次数,你能帮助减少测试次数,你能帮助程序员设计一个测试方式,程序员设计一个测试方式,以减少测试次数吗?以减少测试次数吗?开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A分析:
26、分析:整个模块的任整个模块的任意一条路径都分两步意一条路径都分两步完成完成:第:第1步是从开步是从开始执行到始执行到A点;第点;第2步步是从是从A点执行到结束。点执行到结束。而第步可由子模块而第步可由子模块1或子模块或子模块2或子模块或子模块3来完成;第二步可由来完成;第二步可由子模块子模块4或子模块或子模块5来来完成。因此,分析一完成。因此,分析一条指令在整个模块的条指令在整个模块的执行路径需要用到两执行路径需要用到两个计数原理。个计数原理。开始子模块118条执行路径子模块328条执行路径子模块245条执行路径子模块543条执行路径子模块438条执行路径结束A再测试各个模块之间的信再测试各个
27、模块之间的信息交流是否正常,需要测息交流是否正常,需要测试的次数为:试的次数为:3*2=6。如果每个子模块都正常工如果每个子模块都正常工作,并且各个子模块之间作,并且各个子模块之间的信息交流也正常,那么的信息交流也正常,那么整个程序模块就正常。整个程序模块就正常。这样,测试整个这样,测试整个模块的次数就变为模块的次数就变为 172+6=178(次)(次)2)在实际测试中,程序)在实际测试中,程序员总是把每一个子模块看员总是把每一个子模块看成一个黑箱,即通过只考成一个黑箱,即通过只考察是否执行了正确的子模察是否执行了正确的子模块的方式来测试整个模块。块的方式来测试整个模块。这样,他可以先分别单独
28、这样,他可以先分别单独测试测试5个模块,以考察每个模块,以考察每个子模块的工作是否正常。个子模块的工作是否正常。总共需要的测试次数为:总共需要的测试次数为:18+45+28+38+43=172。例例6.随着人们生活水平的提高,某城市家庭汽车拥有量迅速增随着人们生活水平的提高,某城市家庭汽车拥有量迅速增长,汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌长,汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌照组成办法,每一个汽车牌照都必须有个不重复的英文字母照组成办法,每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字,并且个字母必须合成一组出现,和个不重复的阿拉伯数字,并且个字母
29、必须合成一组出现,个数字也必须合成一组出现,那么这种办法共能给多少辆汽个数字也必须合成一组出现,那么这种办法共能给多少辆汽车上牌照车上牌照?课堂练习课堂练习1、乘积、乘积 展开后共有几项?展开后共有几项?2、某商场有、某商场有6个门,如果某人从其中的任意一个个门,如果某人从其中的任意一个门进入商场,并且要求从其他的门出去,共有多门进入商场,并且要求从其他的门出去,共有多少种不同的进出商场的方式?少种不同的进出商场的方式? 3.如图如图,该该电路电路,从从A到到B共有多少条共有多少条不同的线路不同的线路可通电?可通电?AB课堂练习课堂练习所以所以, 根据分类原理根据分类原理, 从从A到到B共有共
30、有 N = 3 + 1 + 4 = 8 条不同的线路可通电。条不同的线路可通电。在解题有时既要分类又要分步。在解题有时既要分类又要分步。解解: 从总体上看由从总体上看由A到到B的通电线路可分三类的通电线路可分三类,第一类第一类, m1 = 3 条条第二类第二类, m2 = 1 条条第三类第三类, m3 = 22 = 4, 条条 4 4 4 4、如图,从甲地到乙地有、如图,从甲地到乙地有、如图,从甲地到乙地有、如图,从甲地到乙地有2 2 2 2条路,从乙地到丁地有条路,从乙地到丁地有条路,从乙地到丁地有条路,从乙地到丁地有3 3 3 3条路;条路;条路;条路;从甲地到丙地有从甲地到丙地有从甲地到
31、丙地有从甲地到丙地有4 4 4 4条路可以走,从丙地到丁地有条路可以走,从丙地到丁地有条路可以走,从丙地到丁地有条路可以走,从丙地到丁地有2 2 2 2条路。从甲地条路。从甲地条路。从甲地条路。从甲地到丁地共有多少种不同地走法?到丁地共有多少种不同地走法?到丁地共有多少种不同地走法?到丁地共有多少种不同地走法?甲甲丙丙丁丁乙乙 变式变式1:1:要把要把3 3个球放入个球放入2 2两个不同的口袋两个不同的口袋, ,有几种不有几种不同的放法同的放法? ? 变式变式2:2: 要从甲、乙、丙要从甲、乙、丙3 3名工人中选出名工人中选出2 2名分别上名分别上日班和晚班,有多少种不同的选法?日班和晚班,有
32、多少种不同的选法? 变式变式3:3: 要把要把1,2,3,41,2,3,4四个数放入下面三个格子里四个数放入下面三个格子里, ,数字不可重复数字不可重复, ,有多少种不同的放法?有多少种不同的放法? 变式变式4:4:体育彩票中的排列体育彩票中的排列5 5中奖号码有中奖号码有5 5位数码,每位数位数码,每位数若是若是0-90-9这十个数字中任一个,则产生中奖号码所有可能的这十个数字中任一个,则产生中奖号码所有可能的种数是多少?种数是多少?10=10510101010变式变式5 5:0-90-9这十个数一共可以组成多少这十个数一共可以组成多少5 5位数字?位数字?9=9 10410101010注意
33、:分步乘法计数关键要算好每一步的方法注意:分步乘法计数关键要算好每一步的方法数数 变式变式6 6:0-90-9这十个数一共可以组成多少个数字不重复这十个数一共可以组成多少个数字不重复的的5 5位数字?位数字?9 9=27216=272169 98 87 76 6 变式变式7:7:如图如图, ,要给下面要给下面A A、B B、C C、D D四个区域分别涂上四个区域分别涂上5 5种种不同颜色中的某一种不同颜色中的某一种, ,允许同一种颜色使用多次允许同一种颜色使用多次, ,但相邻区域但相邻区域必须涂不同的颜色必须涂不同的颜色, ,不同的涂色方案有多少种?不同的涂色方案有多少种?N = 5 4 34
34、 = 240注意:分步乘法计数关键要算好每一步的方法注意:分步乘法计数关键要算好每一步的方法数数 变式变式8 8:五名学生报名参加四项体育比赛,每人限报一项,五名学生报名参加四项体育比赛,每人限报一项,报名方法的种数为多少?报名方法的种数为多少?N=44444注意:分步乘法计数关键要算好每一步的方法注意:分步乘法计数关键要算好每一步的方法数数 2 2、某商场有、某商场有6 6个门,如果某人从其中的任意一个门进入商个门,如果某人从其中的任意一个门进入商场,并且要求从其他的门出去,共有多少种不同的进出商场的场,并且要求从其他的门出去,共有多少种不同的进出商场的方式?方式?课堂练习:课堂练习: 1
35、1 1 1、一个商店销售某种型号的电视机,其中本地的产品有、一个商店销售某种型号的电视机,其中本地的产品有、一个商店销售某种型号的电视机,其中本地的产品有、一个商店销售某种型号的电视机,其中本地的产品有4 4 4 4种,外地的产品有种,外地的产品有种,外地的产品有种,外地的产品有7 7 7 7种,要买种,要买种,要买种,要买1 1 1 1台这种型号的电视机,有多少台这种型号的电视机,有多少台这种型号的电视机,有多少台这种型号的电视机,有多少种不同的选法?种不同的选法?种不同的选法?种不同的选法? 3 3、如图、如图, ,要给下面四个区域分别涂上要给下面四个区域分别涂上5 5种不同颜色中的某一种
36、不同颜色中的某一种种, ,允许同一种颜色使用多次允许同一种颜色使用多次, ,但相邻区域必须涂不同的颜色但相邻区域必须涂不同的颜色, ,不不同的涂色方案有多少种?同的涂色方案有多少种?典例讲评典例讲评典例讲评典例讲评第第1 1类:从会唱歌者中选类:从会唱歌者中选1 1人唱歌;人唱歌;第第2 2类:从会跳舞者中选类:从会跳舞者中选1 1人跳舞;人跳舞;第第3 3类:从能歌善舞者中选类:从能歌善舞者中选1 1人唱歌人唱歌 或跳舞;或跳舞;典例讲评典例讲评典例讲评典例讲评 例例11 11 某某4 4名田径运动员报名参加名田径运动员报名参加100m100m,200m200m和和400m400m三项短跑比
37、赛三项短跑比赛. .(1 1)每人限报)每人限报1 1个项目,共有多少种不个项目,共有多少种不 同的报名方法?同的报名方法?(2 2)每个项目限报)每个项目限报1 1人,共有多少种不人,共有多少种不同的报名方法?同的报名方法?(1 1)3 34 48181种;种; (2 2)4 43 36464种种. . 例例12 63012 630的正约数(包括的正约数(包括1 1和和630630)共有多少个?共有多少个?6306302 23 32 25 57 7正约数正约数:2:2a3 3b5 5c7 7d 2 23 32 22 22424(个)(个) 典例讲评典例讲评 例例13 13 将将2020个大小
38、相同的小球放入编号个大小相同的小球放入编号为为1 1,2 2,3 3的三个盒子中,要求每个盒子的三个盒子中,要求每个盒子内的球数不小于该盒子的编号数,求共内的球数不小于该盒子的编号数,求共有多少种不同的放法?有多少种不同的放法?151514142 21 1120120(种)(种) 典例讲评典例讲评 例例14 14 某电视节目中有某电视节目中有A A、B B两个信箱,两个信箱,分别存放着先后两次竞猜中入围的观众分别存放着先后两次竞猜中入围的观众来信,其中来信,其中A A信箱中有信箱中有3030封来信,封来信,B B信箱信箱中有中有2020封来信封来信. .现由主持人从现由主持人从A A信箱或信箱
39、或B B信信箱中抽取箱中抽取1 1名幸运观众,再由该幸运观众名幸运观众,再由该幸运观众从从A A、B B两个信箱中各抽取两个信箱中各抽取1 1名幸运伙伴,名幸运伙伴,求共有多少种不同的可能结果?求共有多少种不同的可能结果? 3030292920202020191930 30 174001740011400114002880028800(种)(种) 课堂小结课堂小结相同点相同点:回答的都是有关做一件事的不同方法总数回答的都是有关做一件事的不同方法总数的问题的问题分类计数原理与分步计数原理的异同分类计数原理与分步计数原理的异同:区别在于:分类计数原理针对的是区别在于:分类计数原理针对的是“分类分类
40、”问题,问题,其中各种方法相互独立,用任何一种方法都可以其中各种方法相互独立,用任何一种方法都可以做完这件事;分步计数原理针对的是做完这件事;分步计数原理针对的是“分步分步”问问题,各个步骤中的方法相互依存,只有各个步骤题,各个步骤中的方法相互依存,只有各个步骤都完成才算做完这件事都完成才算做完这件事 分类计数原理:分类计数原理:分类计数原理:分类计数原理:针对的是针对的是针对的是针对的是“ “分类分类分类分类” ”问题。问题。问题。问题。各类方法相互独立。各类方法相互独立。各类方法相互独立。各类方法相互独立。 分步计数原理:分步计数原理:分步计数原理:分步计数原理:针对的是针对的是针对的是针
41、对的是“ “分步分步分步分步” ”问题。问题。问题。问题。 每步相互依存。每步相互依存。每步相互依存。每步相互依存。 若若完成完成一件事情一件事情可以有可以有n n类方案,在第一类方案中有类方案,在第一类方案中有m m1 1种不同种不同的方法,在第二类中有的方法,在第二类中有m m2 2种不同的方法种不同的方法, ,在第在第n n类方案中有类方案中有m mn n种不种不同的方法,那么完成这件事情有同的方法,那么完成这件事情有: :N=mN=m1 1+m+m2 2+m+m3 3+m+m4 4+ +.+.+m mn n种不同的方法种不同的方法若完成一件事情需要若完成一件事情需要n n个个步骤步骤,
42、在第一,在第一步步中有中有m m1 1种不同的方法,种不同的方法,在第二在第二步步中有中有m m2 2种不同的方法,种不同的方法,在第在第n n步步方法中有方法中有m mn n种不同的方法,种不同的方法,那么完成这件事情有:那么完成这件事情有:N=mN=m1 1m m2 2m m3 3m m4 4. . m mn n种不同的方法种不同的方法一般归纳:一般归纳:分类加法计数原理分类加法计数原理分类加法计数原理分类加法计数原理分步乘法计数原理分步乘法计数原理分步乘法计数原理分步乘法计数原理 1.1.分类加法计数原理和分步乘法计数分类加法计数原理和分步乘法计数原理,都是解决完成一件事的方法数的原理,
43、都是解决完成一件事的方法数的计数问题,其不同之处在于,前者是针计数问题,其不同之处在于,前者是针对对“分类分类”问题的计数方法,后者是针问题的计数方法,后者是针对对“分步分步”问题的计数方法问题的计数方法. . 2.2.在在“分类分类”问题中,各类方案中的问题中,各类方案中的每一种方法相互独立,选取任何一种方每一种方法相互独立,选取任何一种方法都能完成这件事;在法都能完成这件事;在“分步分步”问题中,问题中,各步骤中的方法相互依存,只有各步骤各步骤中的方法相互依存,只有各步骤各选一种方法才能完成这件事各选一种方法才能完成这件事. .课堂小结课堂小结 3.3.在应用分类加法计数原理时,分在应用分类加法计数原理时,分类方法不惟一,但分类不能重复,也类方法不惟一,但分类不能重复,也不能遗漏不能遗漏. . 在应用分步乘法计数原理在应用分步乘法计数原理时,分步方法不惟一,但分步不能重时,分步方法不惟一,但分步不能重叠,也不能缺少叠,也不能缺少. .课堂小结课堂小结