数学选择性必修 第三册第六章 计数原理6.1 分类加法计数原理与分步乘法计数原理教学设计

《分类加法计数原理与分步乘法计数原理的应用》教学设计

一、温故知新,引入课题

1.分类加法计数原理与分步乘法计数原理的内容是什么?你能理解“完成一件事”的含义吗?

2.在应用两个计数原理解决有关问题时,如何区分“分类”或“分步”?

教师提出问题,让学生思考.

分类加法计数原理与分步乘法计数原理解决的都是有关做一件事的不同方法种数的问题.区别在于:分类加法计数原理针对的是“分类”问题,其中各种方法相互独立,用其中任何一种方法都可以完成这件事;分步乘法计数原理针对的是“分步”问题,各个步骤中的方法互相依存,只有每一个步骤都完成才算完成这件事.

设计意图:通过设置问题情境,复习回顾上一节课所学内容,为学习本节内容作准备.

二、应用举例

例1  要从甲、乙、丙3幅不同的画中选出2幅,分别挂在左、右两边墙上的指定位置,共有多少种不同的挂法?

【师生活动】教师提出以下问题让学生思考:

1.要完成的一件事是什么?

2.要完成的一件事是否与顺序有关?

3.如何用计数原理求解有多少种不同的挂法?

设计意图:通过问题的设计引发学生思考.本题背景虽然简单,但学生认识这个问题中要完成的一件事可能会有困难.实际上,这里的“一件事”不仅要从3幅画中选出2幅,而且还要“挂在左、右两边的墙上的指定位置”,所以要分两步完成.

分析:要完成的一件事是“从3幅画中选出2幅,并分别挂在左、右两边墙上”,可以分步完成.

解:从3幅画中选出2幅分别挂在左、右两边墙上,可以分两个步骤完成:第1步,从3幅画中选1幅挂在左边墙上,有3种选法;第2步,从剩下的2幅画中选1幅挂在右边墙上,有2种选法.根据分步乘法计数原理,不同挂法的种数为.

教师追问:同学们还有没有其他解法?

解:第1步,从3幅画中选出2幅,有3种选法(“甲、乙”“甲、丙”“乙、丙”);第2步,将选出的两幅画挂上,有2种挂法,所以共有3×2=6种挂法.

设计意图:第2种方法为后续排列、组合的学习作准备.

例2  给程序模块命名,需要用3个字符,其中首字符要求用字母A~G或U~Z,后两个字符要求用数字1~9,最多可以给多少个程序模块命名?

【师生活动】教师提出问题让学生思考.

1.要完成的一件事是什么?

2.要完成的一件事需要分类还是分步?

3.如何利用计数原理解答?

分析:要完成的一件事是“给一个程序模块命名”,可以分三个步骤完成:第1步,选首字符;第2步,选中间字符;第3步,选最后一个字符.而首字符又可以分为两类.

解:由分类加法计数原理,首字符不同选法的种数为7+6=13.

后两个字符从1~9中选,因为数字可以重复,所以不同选法的种数都为9.

由分步乘法计数原理,不同名称的个数是13×9×9=1053,即最多可以给1053个程序模块命名.

追问:还有不同的解法吗?

解:首字符从字母A~G中选一个,有7种不同的选法,后两个字符从1~9中选,因为数字可以重复,所以不同选法的种数都为9.由分步乘法计数原理,不同名称的个数是7×9×9=567.

首字符从U~Z中选一个,有6种不同的选法,后两个字符从1~9中选,因为数字可以重复,所以不同选法的种数都为9.由分步乘法计数原理,不同名称的个数是6×9×9=486.

所以由分类加法计数原理,最多可以命名的程序模块个数为567+486=1053.

例3  电子元件很容易实现电路的通与断、电位的高与低等两种状态,而这也是最容易控制的两种状态.因此计算机内部就采用了每一位只有0或1两种数字的记数法,即二进制.为了使计算机能够识别字符,需要对字符进行编码,每个字符可以用1个或多个字节来表示,其中字节是计算机中数据存储的最小计量单位,每个字节由8个二进制位构成.

(1)1个字节(8位)最多可以表示多少个不同的字符?

(2)计算机汉字国标码包含了6763个汉字,一个汉字为一个字符,要对这些汉字进行编码,每个汉字至少要用多少个字节表示?

【师生活动】教师可以先结合学生的情况介绍一下有关计算机编码、存储的知识.这里关键是要知道“一个字符用一个字节来表示”,例如00000000,10000000,11111111,…都分别表示一个字符.

提出问题:

1.对于问题(1),要完成的一件事是什么?

2.要完成的一件事需要分类还是分步?如何用计数原理解答?

3.1个字节最多能表示多少个字符?能够表示6763个汉字吗?

4.2个字节可以表示多少个不同的字符?能够表示6763个汉字吗?

分析:对于问题(1),要完成的一件事是“确定1个字节各二进制位上的数字”.由于每个字节有8个二进制位,每一位上的值都有0,1两种选择,而且不同的顺序代表不同的字符,因此可以用分步乘法计数原理求解.问题(1)就是一个与例2一样的“可重复排列”问题.对于问题(2),由于国标码包含了6763个汉字,至少需要6763个不同字符,而用一个字节最多只能表示256个字符,因此不够,这样就考虑2个字节能够表示多少个不同的字符,这是一个分步计数问题.只要计算出多少个字节所能表示的不同字符不少于6763个即可.

解:(1)用下图表示1个字节,每一格代表一位.

1个字节共有8位,每位上有2种选择.根据分步乘法计数原理,1个字节最多可以表示不同字符的个数.

(2)由(1)知,1个字节所能表示的不同字符不够6763个,考虑2个字节能够表示多少个字符.前1个字节有256种不同的表示方法,后1个字节也有256种不同的表示方法.根据分步乘法计数原理,2个字节可以表示不同字符的个数是.这已经大于汉字国标码包含的汉字个数6763.因此要对这些汉字进行编码,每个汉字至少要用2个字节表示.

设计意图:介绍有关计算机编码、储存的知识,有利于学生更好地理解题意,在此基础上,提出问题,引发学生思考.在使用计数原理解决问题时,要先理解清楚完成的一件事是什么,如何完成一件事,是分类还是分步,从而加深对两个计数原理的理解.

巩固练习:教材第7页练习第题.

利用多媒体展示学生的解答.

参考答案:

1..

2..

3..

4.方法一:被5除余2的数的个位数是2或7,满足条件的一位数有2个,两位数有个,三位数有个,所以共有100个.

方法二:被5除余2的数可以表示为为整数),可解得,所以共有100个.

5..

设计意图:通过利用两个计数原理分析解决问题,进一步理解两个计数原理中的“完成一件事”的含义,进一步巩固使用两个计数原理解决实际问题的方法步骤.

例4  计算机编程人员在编写好程序以后需要对程序进行测试.程序员需要知道到底有多少条执行路径(程序从开始到结束的路线),以便知道需要提供多少个测试数据.一般地,一个程序模块由许多子模块组成.下图是一个具有许多执行路径的程序模块,它有多少条执行路径?

另外,为了减少测试时间,程序员需要设法减少测试次数.你能帮助程序员设计一个测试方法,以减少测试次数吗?

【师生活动】这是两个计数原理的综合应用,教师提出以下问题引导学生思考.

1.这里要完成的“一件事”是指什么?

2整个模块的每一条执行路径是分几步完成的?

3.在每一步中又需要分几类?

4.如何减少测试次数?能否通过测试整个模块来减少测试的次数?

给学生一定的思考、讨论的时间,然后指定几个学生进行分析.

整个模块的任意一条执行路径都分两步完成:第1步是从开始执行到A点;第2步是从A点执行到结束.而第1步可由子模块1、子模块2、子模块3中任何一个来完成;第2步可由子模块4、子模块5中任何一个来完成.因此,分析一条指令在整个模块的执行路径需要用到两个计数原理.

让学生写出解答过程.

解:由分类加法计数原理,子模块1、子模块2、子模块3中的子路径条数共为18+45+28=91;子模块4、子模块5中的子路径条数共为38+43=81.

又由分步乘法计数原理,整个模块的执行路径条数共为91×81=7371.

在实际测试中,程序员总是把每一个子模块看成一个黑箱,即通过只考察是否执行了正确的子模块的方式来测试整个模块.这样,他可以先分别单独测试5个模块,以考察每个子模块的工作是否正常.总共需要的测试次数为18+45+28+38+43=172.

再测试各个模块之间的信息交流是否正常,只需要测试程序第1步中的各个子模块和第2步中的各个子模块之间的信息交流是否正常,需要的测试次数为3×2=6.

如果每个子模块都工作正常,并且各个子模块之间的信息交流也正常,那么整个程序模块就工作正常.这样,测试整个模块的次数就变为172+6=178.

显然,178与7371的差距是非常大的.

设计意图:这是一个综合应用题,需要综合运用分类加法计数原理与分步乘法计数原理解答.一般解法需要先分类,再分步.怎样做可以减少测试次数?通过解决这个问题,可以使学生了解两个计数原理的实际意义,即通过比较不同测试方法所需要的测试次数的差异,感受改进测试方法的重要性.

例5  通常,我国民用汽车号牌的编号由两部分组成:第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号,第二部分为由阿拉伯数字和英文字母组成的序号,如图所示.

其中,序号的编码规则为:

(1)由10个阿拉伯数字和除O,I之外的24个英文字母组成;

(2)最多只能有2个英文字母.

如果某地级市发牌机关采用5位序号编码,那么这个发牌机关最多能发放多少张汽车号牌?

【师生活动】教师提出问题让学生思考、交流.

1.要完成的一件事是什么?

2.“最多能发放的牌照数”的含义是什么?序号中的数字、字母是否可以重复?

3.计算过程中分类的标准是什么?

在问题的引导下,学生分析、思考、讨论、交流.

分析:由号牌编号的组成可知,序号的个数决定了这个发牌机关所能发放的最多号牌数.按序号编码规则可知,每个序号中的数字、字母都是可重复的,并且可将序号分为三类:没有字母,有1个字母,有2个字母.以字母所在位置为分类标准,可将有1个字母的序号分为五个子类,将有2个字母的序号分为十个子类.

解:由号牌编号的组成可知,这个发牌机关所能发放的最多号牌数就是序号的个数.根据序号编码规则,5位序号可以分为三类:没有字母,有1个字母,有2个字母.

(1)当没有字母时,序号的每一位都是数字.确定一个序号可以分5个步骤,每一步都可以从10个数字中选1个,各有10种选法.根据分步乘法计数原理,这类号牌张数为.

(2)当有1个字母时,这个字母可以分别在序号的第1位、第2位、第3位、第4位或第5位,这类序号可以分为五个子类.

当第1位是字母时,分5个步骤确定一个序号中的字母和数字:第1步,从24个字母中选1个放在第1位,有24种选法;第步都是从10个数字中选1个放在相应的位置,各有10种选法.根据分步乘法计数原理,号牌张数为.

同样,其余四个子类号牌也各有240000张.

根据分类加法计数原理,这类号牌张数一共为.

(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种选法;第步都是从10个数字中选1个放在相应的位置,各有10种选法.根据分步乘法计数原理,号牌张数为.

同样,其余九个子类号牌也各有576000张.

于是,这类号牌张数一共为.

综合(1)(2)(3),根据分类加法计数原理,这个发牌机关最多能发放的汽车号牌张数为.

设计意图:本例题的背景是真实的,一方面让学生进一步理解计数原理,另一方面可引出下一节的排列问题.因为没有排列知识,所以给出的解法是比较烦琐的.之所以如此不厌其烦地把步骤一一列出,主要是为下一节的学习作准备,因为学生可以从中感受到这样做太麻烦,产生“能否简化”的想法,而且也可以从中发现各步骤在结构上的一致性.

巩固练习:教材第11页练习第题.

【师生活动】教师先让学生独立完成.然后找几名学生核对答案,也可用多媒体展示部分学生的解答过程.

参考答案:

1..

2.45(点拨:当个位数字为时,十位数字满足的有种取法.)

3..

4.(1)   (2)

三、归纳总结

1.用两个计数原理解决计数问题时,最重要的是在开始计算之前要仔细分析两点:(1)要完成的“一件事”是什么;(2)需要分类还是需要分步.

分类要做到“不重不漏”.分类后再分别对每一类进行计数,最后用分类加法计数原理求和,得到总数.

分步要做到“步骤完整”,即完成了所有步骤,恰好完成任务.分步后再计算每一步的方法数,最后根据分步乘法计数原理,把完成每一步的方法数相乘,得到总数.

【师生活动】教师引导学生自己进行总结.一般来说,解决计数问题时,可以“先分类,再对每一类分步计算”,分类或分步时都要注意按照统一标准进行.

2.思考:

乘法运算是特定条件下加法运算的简化,分步乘法计数原理和分类加法计数原理也有这种类似的关系吗?

教师让学生通过教材第6页的例4思考这一问题.

一方面,先分为“甲在左”“乙在左”“丙在左”三类,然后再计算每一类中的挂法,即“甲乙、甲丙”“乙甲、乙丙”“丙甲、丙乙”,不同挂法种数为.另一方面,由于每一类的挂法都是2种,因此可以简化为“分步”:第1步,选左边的画(选法3种);第2步,选右边的画(选法2种),不同挂法的种数为.

实际上,分步乘法计数原理也可以看成是特定条件下的分类加法计数原理的简化.

设计意图:目的是让学生用联系的观点,类比(正整)数的加法与乘法的关系,进一步认识两个计数原理之间的关系.

四、布置作业

教材第11页习题6.1第1~6题.

板书设计:

教学研讨:

分类加法计数原理与分步乘法计数原理都是讨论“完成一件事情”所有不同方法种数问题的方法.这里,“完成一件事情”是一个比较抽象的概念,分析这一问题时,可先让学生思考、讨论、交流,然后教师评价指导.学生对两个计数原理本身的理解难度不大,但对问题的背景分析往往有困难,同时还需要通过一定的技巧对问题进行转化,这也是困难的.特别是综合应用两个计数原理解决问题时,学生常常会在该用哪个计数原理、该如何分解不同的情况、如何安排计数步骤、如何避免重复计数等方面感到困难.对此,教师应进行指导、点拔.本节安排了比较多的例题,引导学生逐步体会两个计数原理的基本思想及其应用方法.教师可以根据情况,补充一些适合自己学生的相应的具有实际背景的问题.