计数原理CountingTheory.ppt

计数原理 Counting theory,或一个阿拉伯数字给一个小班教室里的座位编号，总共能够编出多少种不同的号码？,请思考:,问题1：用一个大写的英文字母,加法,分类,36种,两类,能,26种 10种,26+10=36种,或一个阿拉伯数字给一个小班教室里的座位编号，总共能够编出多少种不同的号码？,请思考:,问题1：用一个大写的英文字母,用一个大写的英文字母或一个阿拉伯数字给教室里的座位编号,分类加法计数原理,N=m+n,完成一件事,分两类,不重不漏,(Addition principle),深圳,练习:从深圳到长沙，可以乘火车，也可以乘汽车。一天中，火车有3班，汽车有2班。那么一天中，乘坐这些交通工具从甲地到乙地共有多少种不同的走法？,长沙,3+2=5（种）,例1.在填写申请大学专业时,一名高中毕业生了解到两所大学各有一些自己感兴趣的强项专业,具体情况如下:,如果这名同学只能选一个专业,那么他共有多少种选择呢?,变式：在填写申请大学专业时,一名高中毕业生了解到,三所大学各有一些自己感兴趣的强项专业,具体情况如下:,如果这名同学只能选一个专业,那么他共有多少种选择呢?,N=5+4+5=14(种),如果完成一件事情有3类不同方案，在第1类方案中有m1种不同的方法，在第2类方案中有m2种不同的方法，在第3类方案中有m3种不同的方法，那么完成这件事情有 种不同的方法,N=m1+m2+m3,如果完成一件事情有n类不同方案，在第1类方案中有m1种不同的方法，在第2类方案中有m2种不同的方法， 在第n类方案中有mn种不同的方法，那么完成这件事情有 种不同的方法.,N=m1+m2+m3+.+mn,如果完成一件事情有n类不同方案，在每一类中都有若干种不同方法，那么应当如何计数呢？,分类加法计数原理 Addition Principle,思维的轨迹：,问题1,分类加法计数原理,从特殊到一般的思想,分类加法计数原理(一般情况),归纳,思考：,问题1：用一个大写的英文字母或一个阿拉伯数字给一个小班教室里的座位编号，总共能够编出多少种不同的号码？,思考：,A,1,3,2,5,4,6,8,7,9,A1,A2,A3,A4,A5,A6,A7,A8,A9,分析：,第1步,第2步,树形图,6,9,=54种,完成一件事需要两个步骤，做第1步有m种不同的方法，做第2步有n种不同的方法,那么完成这件事共有: 种不同的方法.,分步乘法计数原理,分步,相互依存，缺一不可,完成一件事,(Multiplication principle),探究1：,探究2：,类比的思想,分步乘法计数原理 Multiplication Principle,练习： 从甲地到乙地，要从甲地先乘火车到丙地，再于次日从丙地乘汽车到乙地。一天中，火车有3班，汽车有2班，那么两天中，从甲地到乙地共有多少种不同的走法？,例3.书架的第1层放有4本不同的计算机书，第2层放有3本不同的文艺书，第3层放2本不同的体育书. 从书架上任取1本书，有多少种不同的取法？ 从书架的第1、2、3层各取1本书，有多少种不同的取法？,若完成一件事情可以有n类方案，在第一类方案中有m1种不同的方法，在第二类中有m2种不同的方法,在第n类方案中有mn种不同的方法，那么完成这件事情有:,若完成一件事情需要n个步骤，在第一步中有m1种不同的方法，在第二步中有m2种不同的方法，在第n步方法中有mn种不同的方法，那么完成这件事情有：,Addition principle,Multiplication principle,计数原理 Counting theory,完成一件事情的不同方法种数问题,一步完成(分类),多步完成(分步),每类中的任一种方法都能独立完成这件事情 不重复、不遗漏,相互依存 缺一不可,分类加法计数原理与分步乘法计数原理的联系与区别,例1. 五名学生报名参加四项体育比赛，每人限报一项，报名方法的种数为多少？又他们争夺这四项比赛的冠军，获得冠军的可能性有多少种？,解：（1）5名学生中任一名均可报其中的任一项，因此每个学生都有4种报名方法，5名学生都报了项目才能算完成这一事件故报名方法种数为44444= 种 .,（2）每个项目只有一个冠军，每一名学生都可能获得其中的一项获军，因此每个项目获冠军的可能性有5种故有n=5= 种 .,例2.给程序模块命名，需要用3个字符，其中首个字符要求用字母AG或UZ，后两个要求用数字19，问最多可以给多少个程序命名？,分析：要给一个程序模块命名，可以分三个步骤：第一步，选首字符；第二步，先中间字符；第三步，选末位字符。,解：首字符共有7+613种不同的选法，,答：最多可以给1053个程序命名。,中间字符和末位字符各有9种不同的选法,根据分步计数原理，最多可以有13991053种不同的选法,例3.核糖核酸（RNA）分子是在生物细胞中发现的化学成分，一个RNA分子 是一个有着数百个甚至数千个位置的长链，长链中每一个位置上都由一种称 为碱基的化学成分所占据，总共有个不同的碱基，分别用A，C，G，U表 示，在一个RNA分子中，各种碱基能够以任意次序出现，所以在任意一个位 置上的碱基与其他位置上的碱基无关。假设有一类RNA分子由100个碱基组 成，那么能有多少种不同的RNA分子？,分析:用100个位置表示由100个碱基组成的长链，每个位置都可以从A、C、G、U中任选一个来占据。,解：100个碱基组成的长链共有100个位置，在每个位置中，从A、C、G、U中任选一个来填入，每个位置有4种填充方法。根据分步计数原理，共有,种不同的RNA分子.,例4.电子元件很容易实现电路的通与断、电位的高与底等两种状态，而这也是最容易控制的两种状态。因此计算机内部就采用了每一位只有0或1两种数字的计数法，即二进制，为了使计算机能够识别字符，需要对字符进行编码，每个字符可以用一个或多个字节来表示，其中字节是计算机中数据存储的最小计量单位，每个字节由个二进制位构成，问 （1）一个字节（8位）最多可以表示多少个不同的字符？ （2）计算机汉字国标码（GB码）包含了6763个汉字，一个汉字为一个字符，要对这些汉字进行编码，每个汉字至少要用多少个字节表示？,如00000000，10000000， 11111111.,例5.随着人们生活水平的提高，某城市家庭汽车拥有量迅速增长，汽车牌照号码需要扩容。交通管理部门出台了一种汽车牌照组成办法，每一个汽车牌照都必须有个不重复的英文字母和个不重复的阿拉伯数字，并且个字母必须合成一组出现，个数字也必须合成一组出现，那么这种办法共能给多少辆汽车上牌照?,Homework,2、乘积 展开后共有几项？,3、某商场有6个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，共有多少种不同的进出商场的方式？,1、A code consists of two letters of the alphabet followed by 4 digits. How many such codes are possible?,4.如图,该电路,从A到B共有多少条不同的线路可通电？,A,B,思考1：计算机编程人员在编写好程序以后要对程序进行测试。程序员需要知道到底有多少条执行路（即程序从开始到结束的线），以便知道需要提供多少个测试数据。一般的，一个程序模块又许多子模块组 成，它的一个具有许多执行路径的程序模块。问：这个程序模块有多少条执行路径？另外为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方式， 以减少测试次数吗？,如图,要给地图A、B、C、D四个区域分别涂上红、黄、蓝3种不同颜色中的某一种,允许同一种颜色可使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种？,解: 按地图A、B、C、D四个区域依次分四步完成, 第一步, m1 = 3 种, 第二步, m2 = 2 种, 第三步, m3 = 1 种, 第四步, m4 = 1 种,思考2,所以根据乘法原理, 得到不同的涂色方案种数共有 N = 3 2 11 = 6 种.,所以, 根据分类原理, 从A到B共有 N = 3 + 1 + 4 = 8 条不同的线路可通电。,在解题有时既要分类又要分步。,解: 从总体上看由A到B的通电线路可分三类,第一类, m1 = 3 条,第二类, m2 = 1 条,第三类, m3 = 22 = 4, 条,练习(2),2答案,分析：如图，A、B、C三个区域两两相邻， A与D不相邻，因此A、B、C三个区域的颜色两两不同，A、D两个区域可以同色，也可以不同色，但D与B、C不同色。由此可见我们需根据A与D同色与不同色分成两大类。,解：先分成两类：第一类，D与A不同色，可分成四步完成。 第一步涂A有5种方法，第二步涂B有4种方法；第三步涂C 有3种方法；第四步涂D有2种方法。根据分步计数原理， 共有5432120种方法。,根据分类计数原理，共有120+60180种方法。,第二类，A、D同色，分三步完成，第一步涂A和D有5种方法，第二步涂B有4种方法；第三步涂C有3种方法。根据分步计数原理，共有54360种方法。,1 用1,2,3,4,5五个数字,组成比2000大的没有重复数字的四位数有多少个?,变式2:用1,2,3,4,5五个数字,组成比2000大且比5000小的没有重复数字的数有多少个?,变式1:用1,2,3,4,5五个数字,组成比2000大的没有重复数字的数有多少个?,N=4432=96,N=96+54321=216,N=3432=72,练习1,2 用1,2,3,4,5,6中的两个数分别作为对数的底数和真数,得到不同的对数值有多少个?,变式1: 用1,2,3,4,5,6,7,8,9中的两个数分别作为对数的底数和真数,得到不同的对数值有多少个?,变式2: 用0,1,2,3,4,5,6中的两个数分别作为分数的分子与分母,得到不同的值有多少个?,N=54+1=21,N=87+1-1-1=55,N=65+1-8=23,3 用0,1,2,3,4,5这六个数字, (1)可以组成多少个各位数字不允许重复的三位的奇数? (2)可以组成多少个各位数字不重复的小于1000的自然数? (3)可以组成多少个大于3000,小于5421且各位数字不允许重复的四位数?,,4 在一条线段上取6个点(不包括线段的两端点),以这6个点和线段的两端点为起点和终点的有向线段共有多少条?,变式1:2007年中超联赛共有15个足球队,实行主客场赛制,既每两个球队之间要打两场比赛.整个赛季一共要安排多少场比赛?,变式2:有红,黄两个拳击队,红队有6名选手,黄队有4名选手,不同队之间的两名选手要进行一场拳击赛,问一共要进行多少场比赛?,N=87=56,N=1514=210,N=64=24,练习2,5(染色问题)用5种不同的颜色去染图中标有1至4号的平面, 要求每个区域都必须染色,一个区域只能染一种颜色,并且相邻(有公共边)的区域不能染相同的颜色,分别求图中不同的染色方法总数.,图1,图2,图3,图4,N=5434=240,N=5433=180,N=5413+5432=180,N=5414+5433=260,6 有n种不同颜色为下列两块广告牌着色,要求在四个区域中相邻(有公共边界)区域中不用同一种颜色. (1)若n=6,为(1)着色时共有多少种方法? (2)若为(2)着色时共有120种不同方法,求n (1) (2),7 将一个四棱锥的每个顶点染上一种颜色，并使同一条棱上的两端点颜色不同，如果只有5种颜色可供使用，求共有多少种不同的染色方法？,涂S点 涂A点 涂D点 涂B、C点,N5437420（种）,n元集合 的子集有多少个?,结论:,n元集合 的不同子集有 个.,分析：整个模块的任意一条路径都分两步完成：第1步是从开始执行到A点；第2步是从A点执行到结束。而第步可由子模块1或子模块2或子模块3来完成；第二步可由子模块4或子模块5来完成。