NOIP数学--排列组合.ppt

1、信息学竞赛 -之数学知识,组合数学,Noip历年提高组决赛题中的数学题及难度（最难5星）,第一节 排列组合, 加法原理、乘法原理 排列组合生成算法,加法原理,若事件X能以x种方式发生，另一个不同的时间Y能以y种不同的方式发生，则事件X或者事件Y能以（x+y）种方式发生。 例：全系共三个班级，这三个班级准备参加acm竞赛的学生人数分别是3，4，5，则全系准备参加acm竞赛的人数3+4+5=12.,乘法原理,若事件X能以x种方式发生，另一个不同的事件Y能以y种不同的方式发生，则事件x和事件y能以xy种方式发生。 例：求小于10亿且不包含数字1的正整数的个数。 解： 首先计算不包含数字1的数的个数，

2、从0，2-9中寻找9个符号的字符串，第一个数字有9种选择，第二个数字有9种选择，等等。 根据加法原理共有99=387420489个数，其中包括000000000.如果从100000000中减去这样的数字，得到的答案为612579511.,排列与全排列,从n个不同元素中，有次序的选取r个元素，称为从n中取r个的排列，其排列数记为P(n,r).当r=n时，称为全排列。 例如：从A,B,C,D中有序选取两个字母，则有12种选择。 AB AC AD BA BC BD CA CB CD DA DB DC P (4,2)=12.,定理：p(n,r)=n!/(n-r)!,例题：从n个不同元素中选取r个元素围

3、成一个圆。求选取的方案总数。 解：从n个不同元素中选取r个元素选取的方案总数为p(n,r). a1ar为其中一组解。 将其变换，a2-ar,a1;a3-ar,a1,a2;.共有r个排列。但是这n个排列对一个圆。所以题目中所求方案为p/r,组合,从n个不同元素中，选取r个元素而不考虑其次序，成为从n个中取r个的组合，记为c(n,r). 例：从（a,b,c,d）中选取出2个元素的组合，则有如下情况： （a,b）(a,c) (a,d) (b,c) (b,d) (c,d) 记作 c(4,2)=6; C(n,r)=p(n,r)/r!=n!/r!(n-r)!,例题1如图所示的棋盘，若从左下角走到右上角，并

4、且规定只能向上想右走，问共多少种方案？,解题思路： 左右 4步 下上 3步 无论怎么选择均为右4+上3。 0向右走1向上走 所以可以走法可以看作由01组 成的字符串 即所求方案数为4个0和3个1组成的 7位字符串的个数。 C(7,4)=?,排列组合生成算法,R-排列生成算法： 采用回溯法生成从n中选r个元素的所有排列情况： n个元素用1，2，n来表示 函数done递归的层数i表示当前正在生成排列中第i个位置的数。 函数done(i)执行时，首先判断j是否在该排列以前的几个位置上出现过，若出现则说明j不可能出现在当前位置上，此时j值增1重复以上判断，j=n时回溯；若j没有在该排列以前的位置上出现

5、，则该位置上的值就是j，后判断递归的层数i与r的值是否相等。若i=r，输出一个新的排列并回溯。若ir,则继续进行递归。,错位排列生成算法,错位排列生成算法与r排列生成算法的不同：生成错排第i个位置上的元素时，必须保证该元素不等于i。,R-组合生成算法,从n个元素中取出r个元素的一个组合情况恰对应了r！个r-排列情况。 所以当按照元素的递增次序放置相应位置上的元素时，就可以产生从n个元素中取出r个元素的所有组合情况。,试题,购票问题： 农夫John和他的朋友们一起去参加cownty展览会，cownty展览会的门票为$50,john发现一个奇怪的现象：排队购票的2n人中,总有n个人拿的是面值$10

6、0的钞票，而另外n个人拿的是面值$50的钞票。John想知道的是在这种情况下这2n个人共有多少种排队的方法，使售票处不至于出现找不开钱的局面（假设售票处原来没有零钱）？,算法1：搜索 算法2：栈模型 算法3：递归算法 算法4：递推算法 算法5：组合算法,算法1：搜索法,使用回溯法，枚举所有情况。 变量k为记录售票处有$50的情况， 初始：k=0; 回溯：若某人手拿100钞票且k=0时，否则继续递 归。 输出“：若第2n个人购票后即递归到2n层时计算器累加1，递归结束后，计数器中变为排队总方案数。,2：栈模型,在任意时候，若第n人手持100的钞票，在此之前有M个人手持50的钞票购票，使得m=n;

7、 即： 售票处将收到的50的钞票最终全部找出，将100的钞票全部留下，并且一旦收到一张面值为100的钞票，则一定要找出一张面值50的钞票。 栈模型表示：若一人手持50的钞票购票，相当于一个元素进栈。将问题转化为：1n共n个元素依次进栈，问共多少中出栈顺序。 n个元素的全排列共有n！种方案，那么n!种方案是否都是可能的出栈顺序？,若a1,a2,a3,an是可能的出栈顺序，则一定不存在这样的情况，使得iaj,那么aj出栈时，如果ak已经在栈中，则ak比aj先入栈，由输入序列知道：akaj,所以有akajai;当aj出栈时，如果ak 尚未入栈，则由输入序列知道ajaiak. (2）如果aIaj, a

8、iajak. 因此：不可能出现ijk,aJakai的情况,栈模型算法,算法先产生1-n共n个数的全排列，对于每种排列，若符合前面所讲的出栈规则，那么这个排列便是一个可能的出栈序列。计数器加1，当n个全排列列举结束时，得到问题的解。,递归算法,令f（m,n）表示m个人手持50的钞票。N个人手持100的钞票时总共的方案数。 （1）当n=0时， n=0意味着排队购票的所有人手中拿的都是50的，那么这个m的人排队方案总数为1，即f(m,0)=1 (2)当mn 当mn时，即使m张50全部找出，仍会找不开，所以排队数为0,（3）其他 第（m+n）个人站在第（m+n-1）的后面，则第（m+n）个人的排队方式

9、可由下列2种情况获得： 1，第（m+n）个人手持100，则在他之前的M+n-1 个人中m人手持50的，n-1个人手持100的钞票，此种情况共f(m,n-1) 2,第（m+n）个人手持50，则在他之前的M+n-1 个人中m-1人手持50的，n 个人手持100的钞票，此种情况共f(m-1,n) 加法原理：f(m,n)=f(m-1,n)+f(m,n-1) f(m,n)= 0 1 f(m,n)=f(m-1,n)+f(m,n-1),4)递推算法,递归算法： f(4,4) 14 f(3,4) 0 f(4,3)14 f(3,3) 5 f(4,2)9 f(2,3)0 f(3,2)5 f(3,2) f(4,1)

10、4 f(2,2) 2 f(3,1)3 f(2,2) f(3,1) f(1,2)0 f(2,1)2 f(1,2) 0 f(2,1)2,我们发现f（3，2）等节点有重复计算，课件递归算法产生大量的数据冗余，这些冗余数据是限制递归算法的主要因素，从而导致了模型3虽进行了数学抽象，但是算法实现起来的效率并不高。如何解决呢？计算中保留数值-采用递推法保证同一个数据只计算一次。,O(n2)复杂度 Done () for （a=1;a=n;a+）dataa1=a; for(a=2;a=n;a+) for(b=2;b=a;b+) dataab=dataa-1b+dataab-1 ,组合算法,二叉树 模型来考虑

11、， 依据下列原则对n个节点的二叉树定点编号：若节点i是节点j的子节点，则ij;若节点i是节点K的左儿子，节点j是节点k的右儿子，则ij. 中序遍历时最左边的节点一定是第一个节点，最右边的节点一定是最后一个节点。对于任意一个具有n个节点的二叉树，前序遍历顺序为1n,即n个元素的入栈顺序，中序遍历顺序便是这n个元素的出栈顺序，即2n个人的排队方式总数为n个节点的二叉树的个数，又因为具有n个节点的二叉树的个数为cn=1/n+1 c(2n n )catalan数。,前序遍历遍历结果：ABDECF 中序遍历遍历结果：DBEAFC,排列组合的方法： 用1表示一个手拿50的人，用0表示一个手拿100的人，那

12、么求解的问题可以转化为：n个1和n个0组合一个2n位的二进制数，要求从左向右扫描，1的累计数不小于0的累计数，求满足这个条件的二进制的数的个数。 在2n位上填入n个1的方案数为c(2n,n)不填1的其余n位自动填入0.从c(2n,n)中减去不符合要求的方案数就是问题的解。不符合要求的方案即从左向右扫描，出现0的累计次比1的多。,不符合条件数的特征：从左向右扫描，必然会在某一个奇数位2m+1位上首先出现m+1个0和m个1；而后的2（n-m）-1位上有n-m个1，n-m-1个0.如果把后面这部分2（n-m）-1位的0和1交换，使之成为n-m个0，n-m-1个1，结果得到一个由n+1个0和n-1个1组成的2n位数。即不符合要求的数字对应一个由n+1个0和n-1个1 组成的一个排列。 反之，任何一个由n+1个0 和n-1个1组成的2n