1、讲课人：邢启强1复习引入复习引入完成一件事情，有完成一件事情，有n类不同方案类不同方案，在第，在第1类类方案方案中有中有m1种不同的方法，在第种不同的方法，在第2类类方案方案中有中有m2种不同的方法种不同的方法在第在第n类类方案方案中有中有mn种不同的方法种不同的方法.那么完成这件事共有那么完成这件事共有N=m1+m2+m 种不同的方法种不同的方法.1.1.分类加法计数原理分类加法计数原理 2.分步乘法计数原理分步乘法计数原理完成一件事情，需要分成完成一件事情，需要分成n个步骤个步骤:做第做第1步有步有m1种不同的方法，做第种不同的方法，做第2步有步有m2种不种不同的方法同的方法做第做第n步有
2、步有mn种不同的方法种不同的方法.那么完成这件事共有那么完成这件事共有N=m1 m2 mn种不同的方法种不同的方法.分类加法计数原理和分步乘法计数原理分类加法计数原理和分步乘法计数原理,回答的都是有关做一件事的不同方法的种数问题回答的都是有关做一件事的不同方法的种数问题.区别在于区别在于:分类加法计数原理分类加法计数原理:针对的是针对的是分类分类问题问题,其中其中各种方法相互独立各种方法相互独立,用其中任何一种方用其中任何一种方法都可以做完这件事法都可以做完这件事;分步乘法计数原理分步乘法计数原理:针对的是针对的是分步分步问题问题,各个步骤中的方法互相依存各个步骤中的方法互相依存,只有各个步骤
3、只有各个步骤都完成才算做完这件事都完成才算做完这件事.讲课人：邢启强2分类计数原理分类计数原理 分步计数原理分步计数原理区别1区别2区别3完成一件事，共有完成一件事，共有n n类办法，类办法，关键词关键词“分类分类”完成一件事，共分完成一件事，共分n n个步骤，关键个步骤，关键词词“分步分步”每类办法都能独立地完成每类办法都能独立地完成这件事情，它是独立的、这件事情，它是独立的、一次的、且每次得到的是一次的、且每次得到的是最后结果，最后结果，只须一种方法只须一种方法就可完成这件事就可完成这件事。每一步得到的只是中间结果，每一步得到的只是中间结果，任何一步都不能独立完成这任何一步都不能独立完成这
4、件事，缺少任何一步也不能件事，缺少任何一步也不能完成这件事，完成这件事，只有各个步骤只有各个步骤都完成了，才能完成这件事都完成了，才能完成这件事。各类办法是各类办法是互相独立互相独立的。的。各步之间是各步之间是互相互相关联的。关联的。即：即：类类独立，步步关联类类独立，步步关联。复习讲评复习讲评讲课人：邢启强3例题讲评例题讲评例例1.1.计算机编程人员在编写好程序以后需要对程序进行测试，程序员需要知计算机编程人员在编写好程序以后需要对程序进行测试，程序员需要知道到底有多少条执行路径（程序从开始到结束的路线）道到底有多少条执行路径（程序从开始到结束的路线）,以便知道需要提供多以便知道需要提供多少
5、个测试数据。般地，一个程序模块由许多子模块组成。如图是一个具有许少个测试数据。般地，一个程序模块由许多子模块组成。如图是一个具有许多执行路径的程序模块，它有多少条执行路径？多执行路径的程序模块，它有多少条执行路径？另外，为了减少测试时间，程序员需要设法减少测试次数，你能帮助程另外，为了减少测试时间，程序员需要设法减少测试次数，你能帮助程序员设计一个测试方法，以减少测试次数吗？序员设计一个测试方法，以减少测试次数吗？分析：整个模块的任意一条执行路径都分两分析：整个模块的任意一条执行路径都分两步完成：第步完成：第1步是从开始执行到步是从开始执行到A点；第点；第2步步是从是从A点执行到结束，而第点执
6、行到结束，而第1步可由子模块步可由子模块1、子模块子模块2、子模块、子模块3中任何一个来完成；第中任何一个来完成；第2步可由子模块步可由子模块4、子模块、子模块5中任何一个来完成，中任何一个来完成，因此，分析一条指令在整个模块的执行路径因此，分析一条指令在整个模块的执行路径需要用到两个计数原理需要用到两个计数原理讲课人：邢启强4解：由分类加法计数原理，子模块解：由分类加法计数原理，子模块1、子模块、子模块2、子模块、子模块3中的子路径条数共为中的子路径条数共为18+45+28=91;子模块子模块4、子模块、子模块5中的子路径条数共为中的子路径条数共为38+43=81.又由分步乘法又由分步乘法计
7、数原理，整个模块的执行路径条数共为计数原理，整个模块的执行路径条数共为9181=7371.在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执在实际测试中，程序员总是把每一个子模块看成一个黑箱，即通过只考察是否执行了正确的子模块的方式来测试整个模块，这样，他可以先分别单独测试行了正确的子模块的方式来测试整个模块，这样，他可以先分别单独测试5个模块，个模块，以考察每个子模块的工作是否正常，总共需要的测试次数为以考察每个子模块的工作是否正常，总共需要的测试次数为18+45+28+38+43=172.再测试各个模块之间的信息交流是否正常，只需要测试程序第再测试各个模块之间的信息交流
8、是否正常，只需要测试程序第1步中的各个子模块步中的各个子模块和第和第2步中的各个子模块之间的信息交流是否正常，需要的测试次数为步中的各个子模块之间的信息交流是否正常，需要的测试次数为32=6.如果每个子模块都工作正常，并且各个子模块之间的信息交流也正常，那么整个如果每个子模块都工作正常，并且各个子模块之间的信息交流也正常，那么整个程序模块就工作正常，这样，测试整个模块的次数就变为程序模块就工作正常，这样，测试整个模块的次数就变为172+6=178.显然，显然，178与与7371的差距是非常大的的差距是非常大的讲课人：邢启强5例题讲评例题讲评例例2通常，我国民用汽车号牌的编号由两部分组成：第一部
9、分为用汉字表示的省、自通常，我国民用汽车号牌的编号由两部分组成：第一部分为用汉字表示的省、自治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英治区、直辖市简称和用英文字母表示的发牌机关代号，第二部分为由阿拉伯数字和英文字母组成的序号，如图所示文字母组成的序号，如图所示.其中，序号的编码规则为：其中，序号的编码规则为：(1)由由10个阿拉伯数字和除个阿拉伯数字和除O,1之外的之外的24个英文字母组成；个英文字母组成；(2)最多只能有最多只能有2个英文字母个英文字母.如果某地级市发牌机关采用如果某地级市发牌机关采用5位序号编码，那么这个发牌机关最多能发放多少张汽车位序号编码
10、，那么这个发牌机关最多能发放多少张汽车号牌？号牌？分析：分析：由号牌编号的组成可知，序号的个数决定了这个发牌机关所能由号牌编号的组成可知，序号的个数决定了这个发牌机关所能发放的最多号牌数，按序号编码规则可知，每个序号中的数字、字母发放的最多号牌数，按序号编码规则可知，每个序号中的数字、字母都是可重复的，并且可将序号分为三类：没有字母，有都是可重复的，并且可将序号分为三类：没有字母，有1个字母，有个字母，有2个字母，以字母所在位置为分类标准，可将有个字母，以字母所在位置为分类标准，可将有1个字母的序号分为五个个字母的序号分为五个子类，将有子类，将有2个字母的序号分为十个子类。个字母的序号分为十个
11、子类。排队问题排队问题:讲课人：邢启强6解：由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数解：由号牌编号的组成可知，这个发牌机关所能发放的最多号牌数就是序号的个数.根据序号编码规根据序号编码规则，则，5位序号可以分为三类：没有字母，有位序号可以分为三类：没有字母，有1个字母，有个字母，有2个字母个字母.(1)当没有字母时，序号的每一位都是数字，确定一个序号可以分当没有字母时，序号的每一位都是数字，确定一个序号可以分5个步骤，每一步都可以从个步骤，每一步都可以从10个数字个数字中选中选1个，各有个，各有10种选法，根据分步乘法计数原理，这类号牌张数为种选法，根据分步乘法计数
12、原理，这类号牌张数为1010101010=100000.(2)当有当有1个字母时，这个字母可以分别在序号的第个字母时，这个字母可以分别在序号的第1位、第位、第2位、第位、第3位、第位、第4位或第位或第5位，这类序号可位，这类序号可以分为以分为五个子类五个子类。当第。当第1位是字母时，分位是字母时，分5个步骤确定一个序号中的字母和数字：第个步骤确定一个序号中的字母和数字：第1步，从步，从24个字母个字母中选中选1个放在第个放在第1位，有位，有24种选法；第种选法；第25步都是从步都是从10个数字中选个数字中选1个放在相应的位置，各有个放在相应的位置，各有10种选法，种选法，根据分步乘法计数原理，
13、号牌张数为根据分步乘法计数原理，号牌张数为2410101010=240000.同样，其余四个子类号牌也各有同样，其余四个子类号牌也各有240000张张.根据分类加法计数原理，这类号牌张数一共为根据分类加法计数原理，这类号牌张数一共为240000+240000+240000+240000+240000=1200000.(3)当有当有2个字母时，根据这个字母时，根据这2个字母在序号中的位置，可以将这类序号分为个字母在序号中的位置，可以将这类序号分为十个子类十个子类：第：第1位和第位和第2位，位，第第1位和第位和第3位，第位，第1位和第位和第4位，第位，第1位和第位和第5位，第位，第2位和第位和第3
14、位，第位，第2位和第位和第4位，第位，第2位和第位和第5位，第位，第3位和第位和第4位，第位，第3位和第位和第5位，第位，第4位和第位和第5位位.当第当第1位和第位和第2位是字母时，分位是字母时，分5个步骤确定一个序号中的字母和数字：第个步骤确定一个序号中的字母和数字：第1,2步都是从步都是从24个字母中选个字母中选1个分别放在第个分别放在第1位、第位、第2位，各有位，各有24种选法；第种选法；第35步都是从步都是从10个数字中选个数字中选1个放在相应的位置，各有个放在相应的位置，各有10种选法，根据分步乘法计数原理，号牌张数为种选法，根据分步乘法计数原理，号牌张数为2424101010=57
15、6000.同样，其余九个子类号同样，其余九个子类号牌也各有牌也各有576000张张.于是，这类号牌张数一共为于是，这类号牌张数一共为57600010=5760000.综合综合(1)(2)(3),根据分类加法计数原理，这个发牌机关最多能发放的汽车号牌张数为根据分类加法计数原理，这个发牌机关最多能发放的汽车号牌张数为100000+1200000+5760000=7060000.讲课人：邢启强7例例3.从数字从数字1,2,3,4,5中取出中取出3个数字（允许重复）个数字（允许重复）,组成三位数，各位数字组成三位数，各位数字之和等于之和等于6,则这样的三位数的个数为则这样的三位数的个数为()A.7 B
16、.9 C.10 D.13例题讲评例题讲评排队问题排队问题:解：从数字解：从数字1,2,3,4,5中取出中取出3个数字（允许重复）个数字（允许重复）,组成三位数，组成三位数，各位数字之和等于各位数字之和等于6,可分为三类情况：可分为三类情况：(1)当三个数为当三个数为1,1,4时，时，4可以在个位、十位、百位，所以共有可以在个位、十位、百位，所以共有3个这样的三位数；个这样的三位数；(2)当三个数为当三个数为1,2,3时，共有时，共有321=6个这样的三位数；个这样的三位数；(3)当三个数为当三个数为2,2,2时，只有时，只有1个这样的三位数个这样的三位数.由分类加法计数由分类加法计数原理可得，
17、共有原理可得，共有3+6+1=10个，即这样的三位数共有个，即这样的三位数共有10个个.C讲课人：邢启强8巩固练习巩固练习排队问题排队问题:假设今天是假设今天是4 4月月5 5日，某市未来六天的空气质量预报情况如下表所示日，某市未来六天的空气质量预报情况如下表所示.该市有甲、该市有甲、乙、丙三人计划在未来六天（乙、丙三人计划在未来六天（4 4月月5 5日日44月月1010日）内选择一天出游，在甲只选日）内选择一天出游，在甲只选择空气质量为优的一天出游；乙不选择择空气质量为优的一天出游；乙不选择4 4月月8 8日出游；丙不选择日出游；丙不选择4 4月月5 5日出游；日出游；甲与乙不选择同一天出游
18、甲与乙不选择同一天出游这四个条件中任选其中三个，求这三人出游的不同方法数这四个条件中任选其中三个，求这三人出游的不同方法数.4 4月月5 5日日4 4月月6 6日日4 4月月7 7日日4 4月月8 8日日4 4月月9 9日日4 4月月1010日日优优优优良良未来六天空气质量预报未来六天空气质量预报解析解析:若选择若选择,则三人出游的不同方法数则三人出游的不同方法数N=455=100.若选择若选择,则需分两类，第一类，若甲选择则需分两类，第一类，若甲选择4月月27日出游，则三人出游的日出游，则三人出游的不同方法数不同方法数N1=56=30;第二类，若甲不选择月第二类，若甲不选择月27日出游，则三
19、人出游的不同日出游，则三人出游的不同方法数方法数N2=346=72.故这三人出游的不同方法数故这三人出游的不同方法数N=N1+N2=102若选择若选择,则三人出游的不同方法数则三人出游的不同方法数N=455=100若选择若选择,则三人出游的不同方法数则三人出游的不同方法数N=555=125.讲课人：邢启强9巩固练习巩固练习排队问题排队问题:汽车维修师傅在安装好汽车轮胎后，需要紧固轮胎上的五个螺栓，记为汽车维修师傅在安装好汽车轮胎后，需要紧固轮胎上的五个螺栓，记为A A、B B、C C、D D、E(E(在正五边形的顶点上）在正五边形的顶点上）,紧固时需要按一定的顺序固定每一个螺栓，紧固时需要按一
20、定的顺序固定每一个螺栓，但不能连续固定相邻的两个，则不同固定螺栓顺序的种数为但不能连续固定相邻的两个，则不同固定螺栓顺序的种数为()()A.20 B.15 C.10 D.5 A.20 B.15 C.10 D.5此题相当于在正五边形中，对五个字此题相当于在正五边形中，对五个字母排序，要求五边形的任意相邻两个母排序，要求五边形的任意相邻两个字母不能排在相邻位置，考虑字母不能排在相邻位置，考虑A放第放第一个位置，第二步只能是一个位置，第二步只能是C或或D,只有只有ACEBD和和ADBEC两种情况；同理，两种情况；同理，分别让分别让B、C、D、E放第一个位置，放第一个位置，则各有两种情况，共则各有两种
21、情况，共25=10种情况种情况.C讲课人：邢启强10例例4、如图、如图,要给地图要给地图A、B、C、D四个区域分别涂上四个区域分别涂上3种种不同颜色中的某一种不同颜色中的某一种,允许同一种颜色使用多次允许同一种颜色使用多次,但相邻区但相邻区域必须涂不同的颜色域必须涂不同的颜色,不同的涂色方案有多少种？不同的涂色方案有多少种？染色问题染色问题:例题讲评例题讲评解解:按地图按地图A、B、C、D四个区域依次分四步完成四个区域依次分四步完成,第一步涂第一步涂D,m1=3种种,第二步第二步涂涂B,m2=2种种,第三步第三步涂涂C,m3=1种种,第四步第四步涂涂A,m4=1种种,所以根据乘法原理所以根据乘
22、法原理,得到不同的涂色方案种数共有得到不同的涂色方案种数共有 N=3 2 11=6 种。种。讲课人：邢启强11 若用若用2色、色、4色、色、5色等色等,结果又怎样呢？结果又怎样呢？答答:它们的涂色方案种数分别是它们的涂色方案种数分别是 2色：色：0种种,4色：色：4322=48种种,5色：色：5433=180种等。种等。思考：思考：练习练习：用：用红、黄、蓝红、黄、蓝三种颜色去涂图中标号为三种颜色去涂图中标号为1,2,，9的九宫格中的的九宫格中的9个小正方形（如图）个小正方形（如图）,使得使得任意相邻（有公共边）的小正方形所涂颜色都不任意相邻（有公共边）的小正方形所涂颜色都不相同，且标号为相同
23、，且标号为“1,5,9”的小正方形涂相同的颜的小正方形涂相同的颜色，则符合条件的所有涂法有色，则符合条件的所有涂法有 种种.108解解:分三步：第一步，先给标号分三步：第一步，先给标号1.5.9的正方形涂色，有的正方形涂色，有3种涂法第二步，给标号种涂法第二步，给标号2,3.6的小正方形涂色，又分两类：一是标号的小正方形涂色，又分两类：一是标号3与标号与标号1.5.9涂色相同，则标号涂色相同，则标号2.6各有各有2种涂法，共种涂法，共4种涂法；标号种涂法；标号3与标号与标号1.5.9涂色不同，则标号涂色不同，则标号3有有2种涂法，此时标号种涂法，此时标号2,6只有只有1种涂法，种涂法，综上可知
24、，标号种涂法，种涂法，综上可知，标号2.3.6的小正第三的际法有的小正第三的际法有4+2=6种然跟标号号标号种然跟标号号标号4.7.8的小正方形涂色，显的小正方形涂色，显6的小正的小正方形涂色方法一样，根据分步乘法计数原理，符合条件的所有涂法有方形涂色方法一样，根据分步乘法计数原理，符合条件的所有涂法有36讲课人：邢启强121.1.如图如图,用用5种不同颜色给图中的种不同颜色给图中的A A、B B、C C、D D四个区域涂色四个区域涂色,规定一个区规定一个区域域 只涂一种颜色只涂一种颜色,相邻区域必须涂不同的颜色相邻区域必须涂不同的颜色,不同的涂色方案有不同的涂色方案有 种。种。ABCD分析：
25、分析：如图，如图，A A、B B、C C三个区域两两相邻，三个区域两两相邻，A A与与D D不相邻，因此不相邻，因此A A、B B、C C三个区域的颜色两两不同，三个区域的颜色两两不同，A A、D D两个区域可以同色，也可以不同色，但两个区域可以同色，也可以不同色，但D D与与B B、C C不同色。由此可见我们需根据不同色。由此可见我们需根据A A与与D D同色与不同色分成两大类。同色与不同色分成两大类。解：解：先分成两类：第一类，先分成两类：第一类，D D与与A A不同色，可分成四步完成。不同色，可分成四步完成。第一步涂第一步涂A A有有5 5种方法，第二步涂种方法，第二步涂B B有有4 4
26、种方法；第三步涂种方法；第三步涂C C有有3 3种方法；第四步涂种方法；第四步涂D D有有2 2种方法。根据分步计数原理，共有种方法。根据分步计数原理，共有5 54 43 32 2120120种方法。种方法。根据分类计数原理，共有根据分类计数原理，共有12120+600+60180180种方法。种方法。第二类，第二类，A A、D D同色，分三步完成，同色，分三步完成，第一步涂第一步涂A A和和D D有有5 5种方法，第二步涂种方法，第二步涂B B有有4 4种方法；种方法；第三步涂第三步涂C C有有3 3种方法。根据分步计数原理，共有种方法。根据分步计数原理，共有5 54 43 36060种方法
27、。种方法。巩固练习巩固练习讲课人：邢启强132 2、某城市在中心广场建造一个花圃，花、某城市在中心广场建造一个花圃，花圃分为圃分为6 6个部分（如右图）现要栽种个部分（如右图）现要栽种4 4种不种不同颜色的花，每部分栽种一种且相邻部分同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法不能栽种同样颜色的花，不同的栽种方法有有_种种.?6?5?4?3?2?1（1 1）与同色，则也同色或也同色，所以共）与同色，则也同色或也同色，所以共N N1 1=4=43 32 22 21=481=48种；种；所以，共有所以，共有N=N1+N2+N3=48+48+24=120种.（2 2）与同
28、色，则或同色，所以共有）与同色，则或同色，所以共有N N2 2=4=43 32 22 21=481=48种；种；（3）与且与同色，则共与且与同色，则共N N3 3=4=43 32 21=241=24种种 解法一：从题意来看解法一：从题意来看6 6部分种部分种4 4种颜色的花，又从图形看知必有种颜色的花，又从图形看知必有2 2组同颜色的花，组同颜色的花，从同颜色的花入手分类求从同颜色的花入手分类求巩固练习巩固练习（以数字作答）（以数字作答）讲课人：邢启强14巩固练习巩固练习3.现有现有5种不同的颜色给如图所示的几何体的五个顶点种不同的颜色给如图所示的几何体的五个顶点P,A,B,C,D涂色，涂色，
29、要求同一条棱上的两个顶点颜色不能相同，则一共有要求同一条棱上的两个顶点颜色不能相同，则一共有 种涂法种涂法.420解析解析 第第1类类：顶点：顶点A,C同色同色.顶点顶点P有有5种颜色可供种颜色可供选择，顶点选择，顶点A有有4种颜色可供选择，顶点种颜色可供选择，顶点B有有3种颜种颜色可供选择，此时顶点色可供选择，此时顶点C与顶点与顶点A同色，只有同色，只有1种种颜色可选，顶点颜色可选，顶点D有有3种颜色可供选择，不同的涂种颜色可供选择，不同的涂法有法有54313=180种种.第第2类：顶点类：顶点A,C不同色，顶点不同色，顶点P有有5种颜色可供选种颜色可供选择，顶点择，顶点A有有4种颜色可供选
30、择顶点种颜色可供选择顶点B有有3种颜色可种颜色可供选择，此时顶点供选择，此时顶点C顶点顶点A不同色，有不同色，有2种颜色可种颜色可选，顶点选，顶点D有有2种颜色可供选择，不同的涂法有种颜色可供选择，不同的涂法有5432=240种种.综上，不同的涂法共有综上，不同的涂法共有180+240=420种种.讲课人：邢启强151、乘积、乘积 展开后共有几项？展开后共有几项？)()(54321321321cccccbbbaaa2、某商场有、某商场有6个门，如果某人从其中的任意一个门进入商场，并且要求个门，如果某人从其中的任意一个门进入商场，并且要求从其他的门出去，共有多少种不同的进出商场的方式？从其他的门
31、出去，共有多少种不同的进出商场的方式？提高练习提高练习讲课人：邢启强16 3.如图如图,该电路该电路,从从A到到B共有多少条不同的线路可共有多少条不同的线路可通电？通电？AB巩固练习巩固练习讲课人：邢启强17所以所以,根据分类原理根据分类原理,从从A到到B共有共有 N=3+1+4=8 条不同的线路可通电。条不同的线路可通电。在解题有时既要分类又要分步。在解题有时既要分类又要分步。解解:从总体上看由从总体上看由A到到B的通电线路可分三类的通电线路可分三类,第一类第一类,m1=3 条条第二类第二类,m2=1 条条第三类第三类,m3=22=4,条条 两大原理妙无穷两大原理妙无穷,茫茫数理此中求茫茫数
32、理此中求;万万千千说不尽万万千千说不尽,运用解题任驰骋运用解题任驰骋。讲课人：邢启强181.三个比赛项目，六人报名参加。三个比赛项目，六人报名参加。）每人参加一项有多少种不同的方法？）每人参加一项有多少种不同的方法？）每项人，且每人至多参加一项，有多少种不同的方法？）每项人，且每人至多参加一项，有多少种不同的方法？）每项人，每人参加的项数不限，有多少种不同的方法？）每项人，每人参加的项数不限，有多少种不同的方法？729366 5 4120 36216巩固练习巩固练习2.设设A=a,b,c,d,e,f,B=x,y,z,从从A到到B共有多少种不同的映射共有多少种不同的映射?33=729讲课人：邢启强19巩固练习巩固练习
