排列组合专题课件.ppt

排列组合专题第1页，此课件共85页哦1.加法原理加法原理:如果完成一项工作有两类如果完成一项工作有两类相互独立的方式相互独立的方式A和和B,在方式在方式A中有中有m种完成任务的途径种完成任务的途径,在方式在方式B中有中有n种完成任务的途径种完成任务的途径,则完成则完成这项工作的总的途径有这项工作的总的途径有m+n种种.2.乘法原理乘法原理:如果完成一项工作有两个如果完成一项工作有两个连续的步骤连续的步骤A和和B,在步骤在步骤A中有中有m种种不同的方式不同的方式,在步骤在步骤B中有中有n种不同的方式种不同的方式,则完成这项工作的总的则完成这项工作的总的方法有方法有m*n种种.第2页，此课件共85页哦例例1、从从1到到4这这4个数码中个数码中不重复地任取不重复地任取3个构成一个三个构成一个三位数位数,求这样的三位数一共有多少个求这样的三位数一共有多少个?分析分析:构成三位数的过程可以看成是由连续的三步完成构成三位数的过程可以看成是由连续的三步完成:第一步第一步:取百位上的数字取百位上的数字,共有共有4种方法种方法第二步第二步:取十位上的数字取十位上的数字,共有共有3种方法种方法(即不能取百位上已经取走的即不能取百位上已经取走的数码数码)第三步第三步:取个位上的数字取个位上的数字,共有共有2种方法种方法(即不能取百位和十位上已即不能取百位和十位上已经取走的数码经取走的数码)因此由因此由乘法原理乘法原理,这样的三位数一共有这样的三位数一共有:4*3*2=24种种.第3页，此课件共85页哦例2、一个三位数，如果它的每一位数字都不小于另一个三位数一个三位数，如果它的每一位数字都不小于另一个三位数对应数位上的数字，就称它对应数位上的数字，就称它“吃掉吃掉”后一个三位数，例如后一个三位数，例如543吃掉吃掉432，543吃掉吃掉543，但是，但是543不能吃掉不能吃掉534。那么能。那么能吃掉吃掉587的三位数共有多少个？的三位数共有多少个？百位上有百位上有5、6、7、8、9五种选择，十位上有五种选择，十位上有8、9两种选择，个两种选择，个位上有位上有7，8，9三种选择，所以共有三种选择，所以共有523=30（个）三位数。（个）三位数。第4页，此课件共85页哦例例3、如图，一方形花坛分成编号为如图，一方形花坛分成编号为，四块，现有四块，现有红、黄、蓝、紫四种颜色的花供选种，要求每块只种一种颜色红、黄、蓝、紫四种颜色的花供选种，要求每块只种一种颜色的花，且相邻的两块种不同颜色的花。的花，且相邻的两块种不同颜色的花。如果编号为如果编号为的已经种的已经种上红色花上红色花，那么其余三块不同的种法有，那么其余三块不同的种法有 种。种。21 编号为编号为的有三种选择，对于编号为的有三种选择，对于编号为的，可以的，可以分成以下二类：分成以下二类：1、若编号为若编号为的与编号为的与编号为的同色的同色，则编号为，则编号为的有三种选择。这种情况下共有的有三种选择。这种情况下共有33种方案。种方案。2、若编号为若编号为的与编号为的与编号为的不同色的不同色，则编号为，则编号为的有二种选择，编号为的有二种选择，编号为的有二种选择。这种的有二种选择。这种情况下共有情况下共有322种方案。种方案。第5页，此课件共85页哦例例4、用红、黄、绿、蓝、黑五种颜色涂在如下图所用红、黄、绿、蓝、黑五种颜色涂在如下图所示的示的ABCDE五区域，颜色可重复使用，但同色不五区域，颜色可重复使用，但同色不相邻，涂法有几种？相邻，涂法有几种？AC同色同色:5*4*4*1*4AC不同色不同色:5*4*4*3*31040 第6页，此课件共85页哦例例5、在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有_种。分析：采取分类的方法。第一类：A在第一垄，B有3种选择；第二类：A在第二垄，B有2种选择；第三类：A在第三垄，B有一种选择，同理A、B位置互换，共12种。第7页，此课件共85页哦例例6、某某小小组组有有10人人，每每人人至至少少会会英英语语和和日日语语的的一一门门，其其中中8人人会会英英语语，5人人会会日日语语，从从中中选选出出会会英英语语与与会会日日语语的的各各1人，有多少种不同的选法人，有多少种不同的选法?由由于于8+51310，所所以以10人人中中必必有有3人人既既会会英英语语又又会会日语。日语。（5+2+3）所以可分三类：所以可分三类：52+53+23=31第8页，此课件共85页哦例例7、在所有的三位数中，有且只有两个数字相同的三位在所有的三位数中，有且只有两个数字相同的三位数共有多少个数共有多少个?（1），（2），（3），（1），（2），（3）类类中中每每类类都都是是99种种，共共有有99+99+99399243个只有两个数字相同的三位数。个只有两个数字相同的三位数。第9页，此课件共85页哦例例8、求正整数求正整数1400的正因数的个数的正因数的个数 因为因为任何一个正整数的任何一个正因数任何一个正整数的任何一个正因数(除除1外外)都是这个数的一些都是这个数的一些质因数的积质因数的积，因此，我们先把，因此，我们先把1400分解成质因数的连乘积分解成质因数的连乘积1400=23527.所以这个数的任何一个正因数都是由所以这个数的任何一个正因数都是由2，5，7中的中的若若干干个相乘而得到个相乘而得到(有的可重复有的可重复)。于是取于是取1400的一个正因数，这件事情是分如下三个步骤完成的：的一个正因数，这件事情是分如下三个步骤完成的：(1)取取23的正因数是的正因数是20，21，22，23，共，共3+1种；种；(2)取取52的正因数是的正因数是50，51，52，共，共2+1种；种；(3)取取7的正因数是的正因数是70，71，共，共1+1种种所以所以1400的正因数个数为的正因数个数为(3+1)(2+1)(1+1)=24第10页，此课件共85页哦例例9、从从1到到300的自然数中，完全不含有数字的自然数中，完全不含有数字3的有的有多少个？多少个？将将0到到299的整数都看成三位数，其中数字的整数都看成三位数，其中数字3不出现不出现的，百位数字可以是的，百位数字可以是0，1或或2三种情况。十位数字与个三种情况。十位数字与个位数字均有九种，因此位数字均有九种，因此除去除去0共有共有3991=242(个个)第11页，此课件共85页哦例例10、在小于在小于10000的自然数中，含有数字的自然数中，含有数字1的数有多少的数有多少个？个？不妨将不妨将0至至9999的自然数均看作四位数，凡位数不到四位的自然数均看作四位数，凡位数不到四位的自然数在前面补的自然数在前面补0,使之成为四位数。使之成为四位数。先求不含数字先求不含数字1的这样的四位数共有几个，即有的这样的四位数共有几个，即有0，2，3，4，5，6，7，8，9这九个数字所组成的四位数的个数。由于每一位这九个数字所组成的四位数的个数。由于每一位都可有都可有9种写法，所以，根据乘法原理，由这九个数字组成的四位数个种写法，所以，根据乘法原理，由这九个数字组成的四位数个数为数为99996561。于是，小于于是，小于10000且含有数字且含有数字1的自然数共有的自然数共有9999-6561=3438个个第12页，此课件共85页哦排列的定义排列的定义 数学上，把若干元素，按照任何一种顺序排成一数学上，把若干元素，按照任何一种顺序排成一列，叫做排列。列，叫做排列。如果两个排列满足下列条件之一，它们就被认为是如果两个排列满足下列条件之一，它们就被认为是不同的排列：不同的排列：1.所含元素不全相同所含元素不全相同 2.所含元素相同，但顺序不同。所含元素相同，但顺序不同。第13页，此课件共85页哦相异元素不重复的排列相异元素不重复的排列从从n个不同的元素中，取出个不同的元素中，取出r个不重复的元素，按个不重复的元素，按次序排成一列，当次序排成一列，当rn时，称为从时，称为从n个中取个中取r个的一种选排个的一种选排列。列。如：从如：从a,b,c这三个字母中，每次取出这三个字母中，每次取出2个，有多少种排列方法个，有多少种排列方法?第一步：确定左边的字母，在三个字母中任取一个，有种方法；第一步：确定左边的字母，在三个字母中任取一个，有种方法；第二步：确定右边的字母，从剩下的个字母中选取一个，有种方法；第二步：确定右边的字母，从剩下的个字母中选取一个，有种方法；根据根据乘法原理乘法原理，共有，共有种不同的排法种不同的排法.ab ac ba bc ca cb 第14页，此课件共85页哦 一般地，从一般地，从n个不同的元素中取出个不同的元素中取出r个元素的选排个元素的选排列数用列数用 表示，则表示，则 n!/(n-r)!第15页，此课件共85页哦例例全国足球甲级（组）联赛共有队参加，每全国足球甲级（组）联赛共有队参加，每队都要与其它各队在队都要与其它各队在主、客场主、客场分别比赛一次，共进行多分别比赛一次，共进行多少场比赛？少场比赛？任何二个队进行一次主场比赛和一场客场比任何二个队进行一次主场比赛和一场客场比赛，相当于从赛，相当于从14个元素中任取个元素中任取2个元素的一个排个元素的一个排列，共需进行的比赛场次是列，共需进行的比赛场次是 =14!/12!=14*13=182第16页，此课件共85页哦当当n=r时时,叫做叫做n个不同元素的个不同元素的全排列全排列n个不同元素的全排列数个不同元素的全排列数Pnn n!例例个人站成一排照相，共有多少种不同的排个人站成一排照相，共有多少种不同的排列方法？列方法？!第17页，此课件共85页哦例例3、求有多少个、求有多少个没有重复数字没有重复数字且能被且能被5整除的四整除的四位奇数。位奇数。要能被要能被5整除又是奇数，所以个位上数字只能是整除又是奇数，所以个位上数字只能是5,有有1种选法，由于种选法，由于5已用过，又不可能是已用过，又不可能是0,所以千位上数所以千位上数有有P18种选法种选法,已用过已用过2个数，所以百位、十位上的数有个数，所以百位、十位上的数有P28种选法。种选法。所以符合题意的个数为：所以符合题意的个数为：1 P18 P28448第18页，此课件共85页哦例例4、用、用0、1、2、3、4、5六个数字，可以组成多六个数字，可以组成多少个没有重复数字的三位偶数？少个没有重复数字的三位偶数？1.个位为个位为0,十位为十位为1、2、3、4、5中的一个，百位为剩下的四个数中的一个，百位为剩下的四个数字中的一个，所以这样的偶数共有字中的一个，所以这样的偶数共有1P15P142.个位为个位为2,百位为百位为1、3、4、5中的一个，十位为剩下的四个数字中中的一个，十位为剩下的四个数字中的一个，所以这样的偶数共有的一个，所以这样的偶数共有1P14P143.个位为个位为4,百位为百位为1、2、3、5中的一个，十位为剩下的四个数字中中的一个，十位为剩下的四个数字中的一个，所以这样的偶数共有的一个，所以这样的偶数共有1P14P14所以符合题意的个数为所以符合题意的个数为20161652第19页，此课件共85页哦例例5、8位同学排成相等的两行，要求某两位同学必须位同学排成相等的两行，要求某两位同学必须排在前排，有多少种排法？排在前排，有多少种排法？这两个同学排在前排这两个同学排在前排4个位置的排列数是个位置的排列数是P24，其它，其它同学在余下的同学在余下的6个位置排的排列数是个位置排的排列数是6！，所以符合题！，所以符合题意的个数为意的个数为P246！127208640。第20页，此课件共85页哦例例6、某车站有编号为某车站有编号为1到到6的的6个入口处，每个入口个入口处，每个入口处处每次只能进一人每次只能进一人，问一个小组，问一个小组4人进站的方案有几人进站的方案有几种？种？第一个人有第一个人有6种方案，第二个人有种方案，第二个人有7种方案，因为他选择种方案，因为他选择和第一个人相同入口处时，还有前后之分和第一个人相同入口处时，还有前后之分9*8*7*6=3024 o o oo 在两个入口之间加一个标志在两个入口之间加一个标志，共共5个无区别的标志，问题归结为个无区别的标志，问题归结为9个元素中有个元素中有5个无个无区别的元素，区别的元素，4个不同元素的排列数。所以个不同元素的排列数。所以4个人进站个人进站的方案数有：的方案数有：9！/5！9*8*7*6=3024第21页，此课件共85页哦相异元素的可重复排列相异元素的可重复排列 从从n个不同元素中取出个不同元素中取出r个元素的可重复的排列种数为个元素的可重复的排列种数为nr.93=729例例7由数字由数字1,2,3,9共能组成多少个三位数？共能组成多少个三位数？第22页，此课件共85页哦相异元素的循环排列相异元素的循环排列 n个不同元素不分首尾排成一个圆圈，称为循环排个不同元素不分首尾排成一个圆圈，称为循环排列。其排列数为列。其排列数为n!/n=(n-1)!。如如1,2,3三个数的循环排列只有，二三个数的循环排列只有，二种。种。第23页，此课件共85页哦例例8在圆形花坛外侧摆放盆菊花和盆兰花，在圆形花坛外侧摆放盆菊花和盆兰花，要求兰花不能相邻摆放，一共有多少种摆法？要求兰花不能相邻摆放，一共有多少种摆法？盆菊花摆成一周的排列方法有盆菊花摆成一周的排列方法有n1=！盆兰花插入个空中的排列总数有盆兰花插入个空中的排列总数有n2=P=8!/4!摆放总数为摆放总数为n=n1*n2=8467200第24页，此课件共85页哦例例9有男女各五个人，其中有对是夫妻，沿圆有男女各五个人，其中有对是夫妻，沿圆桌就座，若每对夫妻都坐在相邻的位置，问有多桌就座，若每对夫妻都坐在相邻的位置，问有多少种坐法？少种坐法？设对夫妻分别为和设对夫妻分别为和a,和和b,和和c，先让，先让，三人和另外个人沿圆桌就座的方法为！种三人和另外个人沿圆桌就座的方法为！种又对上述每种坐法，又对上述每种坐法，a坐在的邻座的方式有左右两种，坐在的邻座的方式有左右两种，b,c也如此也如此所以共有！种所以共有！种第25页，此课件共85页哦不全相异元素的排列不全相异元素的排列 如果在如果在n个元素中，有个元素中，有n1个元素彼此相同，有个元素彼此相同，有n2个元素个元素彼此相同，彼此相同，,又有又有nm个元素彼此相同，若个元素彼此相同，若n1+n2+nm=n，则这，则这n个元素的全排列叫做个元素的全排列叫做不全相异不全相异元素的全排列元素的全排列，其排列数为，其排列数为:n!/(n1!*n2!*nm!).若若n1+n2+nm=rn，则这，则这n个元素的全排列叫个元素的全排列叫做做不全相异元素的选排列不全相异元素的选排列，其排列数为，其排列数为:prn/(n1!*n2!*nm!).第26页，此课件共85页哦例例10、将将N个红球和个红球和M个黄球排成一行。如个黄球排成一行。如:N=2,M=3可得可得到到10种排法。问题种排法。问题:当当N=4,M=3时有时有种不同排法种不同排法?7!/(4!*3!)=35NOIP2002 第27页，此课件共85页哦例例11、把两个红球、一个蓝球和一个白球放到十个编号、把两个红球、一个蓝球和一个白球放到十个编号不同的盒子中去，有多少种方法？不同的盒子中去，有多少种方法？排列数为排列数为p410/(2!*1!*1!)2520第28页，此课件共85页哦生成排列的算法生成排列的算法 下下面面程程序序的的功功能能是是利利用用递递归归方方法法生生成成从从1到到n(n10)的的n个个数数的的全全部部可可能能的的排排列列（不不一一定定按按升升序序输输出）。出）。例如，例如，输输入入3，则应该输则应该输出（每行出（每行输输出出5个排列）：个排列）：123 132 213 231 321 312 求全排列求全排列(06年初赛题年初赛题)第29页，此课件共85页哦var var i,n,k:integer;i,n,k:integer;a:array1.10 of integer;a:array1.10 of integer;count:longint;count:longint;procedure perm(procedure perm(k k:integer);:integer);var j,p,t:integer;var j,p,t:integer;begin begin if()then if()then begin begin ();();for p:=1 to k do for p:=1 to k do write(ap:1);write(ap:1);write();write();if()then if()then writeln;writeln;exit;exit;end;end;for j:=k to n do for j:=k to n do begin begin t:=ak;t:=ak;ak:=aj;ak:=aj;aj:=t;aj:=t;perm(k+1)perm(k+1);t:=ak;()t:=ak;()end end end;end;begin begin writeln(Entry n:);writeln(Entry n:);read(n);read(n);count:=0;count:=0;for i:=1 to n do ai:=i;for i:=1 to n do ai:=i;()()end.end.perm(1)K=ninc(count)count mod 5=0ak:=aj;aj:=t;123 132 213 231 321 312第30页，此课件共85页哦算法过程算法过程:用数组：用数组：a:array1.r of integer;表示排列表示排列;初始化时，初始化时，ai:=i(i=1,2,r);设中间的某一个排列为设中间的某一个排列为a1,a2,，ar，则求出下一个排列的算法为：，则求出下一个排列的算法为：从后面向前找，直到找到一个顺序为止从后面向前找，直到找到一个顺序为止（设下标为（设下标为j-1,则则aj-1aj）从从aj ar中，找出一个比中，找出一个比aj-1大的最小元素大的最小元素ak将将aj-1与与ak交换交换将将aj，aj+1ar由小到大排序。由小到大排序。问题描述问题描述:用生成法求出用生成法求出1，2，r的全排列的全排列(raj(ai1aj-1)and(ai1ak1 3 2 5 41 3 4 5 21 3 4 2 5第32页，此课件共85页哦【问题描述问题描述】人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。的回答。火星人用一种非常简单的方式来表示数字火星人用一种非常简单的方式来表示数字掰手指。火星人只有一只手，掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。一个火星人用一个火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指人类的手演示了如何用手指计数。如果把五根手指拇指、食指、中指、无名指和小指分别拇指、食指、中指、无名指和小指分别编号为编号为1，2，3，4和和5，当它们按正常顺序排列时，形成了，当它们按正常顺序排列时，形成了5位数位数12345，当你交，当你交换无名指和小指的位置时，会形成换无名指和小指的位置时，会形成5位数位数12354，当你把五个手指的顺序完全颠倒，当你把五个手指的顺序完全颠倒时，会形成时，会形成54321，在所有能够形成的，在所有能够形成的120个个5位数中，位数中，12345最小，它表示最小，它表示1；12354第二小，它表示第二小，它表示2；54321最大，它表示最大，它表示120。下表展示了只有。下表展示了只有3根手指时能根手指时能够形成的够形成的6个个3位数和它们代表的数字：位数和它们代表的数字：三进制数三进制数123132213231312321代表的数字代表的数字123456火星人（火星人（04年普及组）年普及组）第33页，此课件共85页哦 现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。个结果不会超出火星人手指能表示的范围。【输入文件输入文件】输入文件输入文件martian.in包括三行，第一行有一个正整数包括三行，第一行有一个正整数N，表示火星人手指的数目（，表示火星人手指的数目（1=N=10000）。第二行是一个正整数）。第二行是一个正整数M，表示要加上去的小整数（，表示要加上去的小整数（1=M=100）。）。下一行是下一行是1到到N这这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。【输出文件输出文件】输出文件输出文件martian.out只有一行，这一行含有只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。序。每两个相邻的数中间用一个空格分开，不能有多余的空格。【样例输入样例输入】531 2 3 4 5【样例输出样例输出】1 2 4 5 3【数据规模数据规模】对于对于30%的数据，的数据，N=15；对于对于60%的数据，的数据，N=50；对于全部的数据，对于全部的数据，N0 do一次循环产生下一个排列一次循环产生下一个排列 begin j:=n;while(j1)and(ajaj-1 min:=aj;k:=j;for i:=j to n do if(aiaj-1)and(aiak then ss:=k;if ssi then begin temp:=ai;ai:=ass;ass:=temp;end;end;在在j到到n中，从小到大排列中，从小到大排列 m:=m-1;end;for i:=1 to n do write(ai,);end.531 2 3 4 51 2 3 5 4 1 2 4 5 3 1 2 4 3 51 2 4 5 3 第36页，此课件共85页哦组合的定义组合的定义 数学上，把若干元素，不论次序并成一组，叫做数学上，把若干元素，不论次序并成一组，叫做组合。组合。如果两个组合中，至少有一个元素不同，它们就如果两个组合中，至少有一个元素不同，它们就被认为是不同的组合。被认为是不同的组合。abc,abd第37页，此课件共85页哦相异元素不重复的组合相异元素不重复的组合 设从设从n个不同的元素中，取出个不同的元素中，取出m个不同元素，个不同元素，不考虑顺序不考虑顺序并成并成一组，叫作从一组，叫作从n个不同的元素中，取出个不同的元素中，取出m个不同元素的一个组合。个不同元素的一个组合。如：写出从如：写出从a,b,c,d四个元素中，任取三个元素的所有组合。四个元素中，任取三个元素的所有组合。abc,abd,acd,bcd从从n个不同的元素中，取出个不同的元素中，取出m个不同元素的组合数记为个不同元素的组合数记为Cmn;则有则有CmnPmn/m!=n!/m!(n-m)!规定规定C0n=1abc,bac,cab,acb,bca,cba第38页，此课件共85页哦例例1、八年级八年级6个班进行排球比赛，每班的排球队要与个班进行排球比赛，每班的排球队要与其他其他5个班分别比赛一场，求共要进行多少场比赛？个班分别比赛一场，求共要进行多少场比赛？C26P26/2!=6*5/2*1=15第39页，此课件共85页哦例例2、平面上有平面上有n个点且无三点或三点以上共线，任意两点个点且无三点或三点以上共线，任意两点可以连成一条直线，一共能连成多少条直线？可以连成一条直线，一共能连成多少条直线？C2nn*(n-1)/2第40页，此课件共85页哦例例3、某班第一组有、某班第一组有10名同学，第二组有名同学，第二组有8名同学，现要求每组选出名同学，现要求每组选出2名学生代表参加座谈会，有多少种选法？名学生代表参加座谈会，有多少种选法？C210C281260第41页，此课件共85页哦例例4.一元、二元、五元、十元人民币各一张，一共可以组成一元、二元、五元、十元人民币各一张，一共可以组成多少种不同的币值？多少种不同的币值？C14C24C34C44464115第42页，此课件共85页哦例例5、5年级有年级有8个班，六年级有个班，六年级有6个班，先分别举行各年级的篮个班，先分别举行各年级的篮球赛，采用单循环制，然后由两个年级的第一名争夺冠军，球赛，采用单循环制，然后由两个年级的第一名争夺冠军，共需要比赛多少场？共需要比赛多少场？C28C26+1=8*7/2+6*5/2+1=28+15+1=44第43页，此课件共85页哦例例6：某班第一组有：某班第一组有10名同学，其中有名同学，其中有4名女同学，现要求选名女同学，现要求选出出3名学生代表名学生代表,其中至少有一名女同学去参加座谈会，有多少其中至少有一名女同学去参加座谈会，有多少种选法？种选法？代表中有代表中有1名女同学名女同学的选法为的选法为C14C26种，种，代表中有代表中有2名女同学名女同学的选法为的选法为C24C16种，种，代表中有代表中有3名女同学名女同学的选法为的选法为C34种，种，C14C26C24C16C34100第44页，此课件共85页哦例例7 7、欲登上第欲登上第1010级楼梯，如果规定每步只能跨上一级级楼梯，如果规定每步只能跨上一级或两级，则不同的走法共有或两级，则不同的走法共有()()。第45页，此课件共85页哦例例8、A的一边的一边AB上有上有4个点，另一边个点，另一边AC上有上有5个点，连个点，连同同A的顶点共的顶点共10个点，以这些点为顶点，可以构成个点，以这些点为顶点，可以构成_个三角形个三角形.90第46页，此课件共85页哦例例9、平面上有三条平行直线，每条直线上分别有平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？（点为顶点，能组成多少个不同三角形？（2001年年p）C(7,2)*(5+6)+C(5,2)*(7+6)+C(6,2)*(7+5)+7*6*5=21*11+10*13+15*12+210=231+130+180+210=751第47页，此课件共85页哦例例10、平面上有三条平行直线，每条直线上分别有平面上有三条平行直线，每条直线上分别有7，5，6个点，个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形能组成多少个不同四边形?（2001年年t）C(7,2)*C(5,2)+C(7,2)*C(6,2)+C(5,2)*C(6,2)+C(7,2)*5*6+C(5,2)*7*6+C(6,2)*5*7=21*10+21*15+10*15+21*5*6+10*7*6+15*5*7=2250第48页，此课件共85页哦 例例11、10名名划划船船运运动动员员中中，3人人只只会会划划左左舷舷，2人人只只会会划划右右舷舷，5人人左左右右舷舷都都会会划划，从从中中选选6人人，平平均均分分在在左左、右右舷舷，共共有有多多少少种种不同的选法？不同的选法？1.会划左舷的全划左舷：会划左舷的全划左舷：2.派一个全能划左舷：派一个全能划左舷：3.派二个全能划左舷：派二个全能划左舷：4.派三个全能划左舷：派三个全能划左舷：675第49页，此课件共85页哦例例12、小陈现有小陈现有2个任务个任务A，B要完成，每个任务分别有要完成，每个任务分别有若干步骤如下：若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3-b3是合法的，而是合法的，而a2-b3-a3-b2是不合法的。小陈从是不合法的。小陈从B任务的任务的b1步骤开始做，当步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务回来时，只记得自己已经完成了整个任务A，其他的都忘，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有了。试计算小陈饭前已做的可能的任务步骤序列共有种。种。(2009年年p)70第50页，此课件共85页哦排列组合排列组合+加法原理加法原理:B任务中的任务中的b1一定做，而且肯定是第一个做的。除了一定做，而且肯定是第一个做的。除了b1外，外，第一类：完成第一类：完成A任务任务只有只有1种。种。第二类：完成第二类：完成A任务和任务和b2有有C(4,1)=4种。种。第三类：完成第三类：完成A任务和任务和b2、b3有有C(5,2)=10种。种。第四类：完成第四类：完成A任务和任务和b2、b3、b4有有C(6,3)=20种。种。第五类：完成第五类：完成A任务和任务和b2、b3、b4、b5有有C(7,4)=35种。种。加起来加起来1+4+10+20+35=70。b2 a1 a2 a3a1 b2 a2 a3a1 a2 b2 a3a1 a2 a3 b2 第51页，此课件共85页哦例例13、袋中有已编号的袋中有已编号的20个球，其中个球，其中110号是红球，号是红球，1120号是白球，每取得一个红球得号是白球，每取得一个红球得2分，取得一个白球得分，取得一个白球得3分，分，若取得若干个球，共得若取得若干个球，共得20分，有多少种不同取法？分，有多少种不同取法？2x+3y=20,y必是偶数，必是偶数，所以所以y=0,2,4,6；相应地；相应地x=10,7,4,1；C010C1010C210C710 C410C410 C610C110 51601第52页，此课件共85页哦例例14、从从1300之间任取之间任取3个不同的数，使得这个不同的数，使得这3个数的个数的和恰好被和恰好被3除尽，有多少种方法？除尽，有多少种方法？被被3除所得的余数不外乎：除所得的余数不外乎：0，1，2。所以可把。所以可把1300之间的数之间的数分成三组：分成三组：A1,4,7,298 B2,5,8,299 C3,6,9,300 三个数同属于集合三个数同属于集合A，有，有C3100种，种，三个数同属于集合三个数同属于集合B，有，有C3100种，种，三个数同属于集合三个数同属于集合C，有，有C3100种，种，三个数分属于集合三个数分属于集合A，B，C，有，有1003种。加起来等于种。加起来等于 1485100种。种。第53页，此课件共85页哦例例15、若将一个正整数化为二进制数，在此二进制数中，我们将若将一个正整数化为二进制数，在此二进制数中，我们将数字数字0的个数多于数字的个数多于数字1的个数的这类二进制数称为的个数的这类二进制数称为A类数。类数。例如：例如：（24）10=（11000）2 其中其中1的个数为的个数为2，0的个数为的个数为3，则称此数为，则称此数为A类数；类数；请你求出请你求出1112之中（包括之中（包括1与与112），全部），全部A类数的个数。类数的个数。（112）10=（1110000）2可根据二进制数的前缀来分类。可根据二进制数的前缀来分类。第54页，此课件共85页哦111：这类数中：这类数中A类数只有一个，即类数只有一个，即1110000110：这类数中：这类数中A类数个数为：类数个数为：C44C34510：这类数中：这类数中A类数个数为：类数个数为：C55C45 C35 160：位数不确定，需对位数进行讨论。：位数不确定，需对位数进行讨论。第55页，此课件共85页哦1位数，即位数，即1,不是不是A类数，类数，2位数，即位数，即1，10和和11都不是都不是A类数，类数，3位数，即位数，即1，只有，只有100一个，一个，4位数，即位数，即1，只有，只有1000一个，一个，5位数，即位数，即1，A类数个数有类数个数有C44C345,6位数，即位数，即1，A类数个数有类数个数有C55C456,1516（1156）35第56页，此课件共85页哦例16、某城市有4条东西街道和6条南北的街道，街道之间的间距相同。若规定只能向东或向北两个方向沿图中路线前进，则从M到N有多少种不同的走法?(2007年p)MN（一）从M到N必须向上走三步，向右走五步，共走八步。（二）每一步是向上还是向右，决定了不同的走法。（三）事实上，当把向上的步骤决定后，剩下的步骤只能向右。从而，任务可叙述为：从八个步骤中选出哪三步是向上走，就可以确定走法数。本题答案为56。第57页，此课件共85页哦相异元素的可重复组合相异元素的可重复组合 设从设从n个不同的元素中，取出个不同的元素中，取出m个不同元素，个不同元素，若允许这个元素可以若允许这个元素可以重复使用重复使用，也允许，也允许mn，则把这样的组合称为重复组合，其组合数记为，则把这样的组合称为重复组合，其组合数记为Hmn。Hmn=Cmn+m-1 如如1,2,3,4,四个数字中取三个，允许重复的组合有以下四个数字中取三个，允许重复的组合有以下20种：种：111,122,134,224,333 112,123,144,233,334 113,124,222,234,344 114,133,223,244,444第58页，此课件共85页哦组合的生成算法组合的生成算法 从1,2,3,n共n个数中任取m个数，请输出所有组合并计算组合数。var n,m,i,k,s:integer;a,b:array0.100 of integer;begin readln(n,m);for i:=1 to m do begin ai:=i;bi:=;end;k:=m;s:=0;repeat if then begin s:=s+1;for i:=1 to m do write(ai);write();end;if akbk then begin ;if km then for k:=k+1 to m do ;end else ;until k=0;writeln;writeln(s=,s);end.n-m+ik=mak:=ak+1ak:=ak-1+1k:=k-1第59页，此课件共85页哦Jam的计数法的计数法【问题描述问题描述】Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，小写英文字母计