组合数学竞赛中的应用.ppt

《组合数学竞赛中的应用.ppt》由会员分享，可在线阅读，更多相关《组合数学竞赛中的应用.ppt（38页珍藏版）》请在三一办公上搜索。

1、组合数学在程序设计竞赛中的应用,内容提要,排列组合和容斥原理群论与Polya定理 递推关系,两个基本原则,1、加法原则如果完成一件事情有两种方案，而第一个方案有m种方法，第二个方案有n中方法，则完成该事情共有m+n种方法。2、乘法原则如果完成一件事情需要两个步骤，第一步有m中方法，第二步又有n种方法，则完成该事情共有m*n种方法,排列组合的几个基本结论,1、相异元素不允许重复的排列数和组合数：,2、不尽相异元素的全排列,排列组合的几个基本结论,3、相异元素不允许重复的圆排列,4、相异元素允许重复的组合数,集合描述：设S=e1,e2,en,，从S中允许重复地取出r个元素，称为r可重组合,排列组合

2、例题,例1：电子锁某机要部门安装了电子锁。M工作人员每人发一张磁卡，卡上有开锁的密码特征，为了确保安全，规定至少有N人同时使用各自的磁卡才能将锁打开。现在需要计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少要有多少特征。,排列组合例题,先做一个简单的假设：M=7，N=4。,对于问题一：任意N-1人在一起，至少缺一种特征，不能打开,剩下的M-(N-1)个人中的任意一个到场即可开锁。M个人中的M-(N-1)的组合数为C(M,M-N+1)=C(M,N-1),故电子锁的至少应有C(7,3)=35种特征。,对于问题二：对任一位工作者的磁卡而言，其余M-1人中任意N-1人在场至少缺少一种此人所具有

3、的特征而无法打开锁。每张磁卡至少应有C(M-1,N-1)种特征，故C(6,3)=20种特征。,所以最终答案是C(M,N-1)和C(M-1,N-1),排列组合例题,例2：zju1976 Path On a Grid,求n*m的方格图形中，从点（0，0）到点（n，m）的最短路径数目,（0，0）,（n，m）,Sample Input（给定n，m）5 41 10 0Sample Output(路径数目)1262,排列组合例题,我们用组合数学的思路来解题。最短路径必定是一条只向右上走得路。设向右走一步为x，向上走一步为y。则每一条路线一定对应由n个x，m个y共m+n个元素组成的排列。,以n=5，m=4为

4、例，,任意一条路线如下图所示，对应的xy序列为：xyxxxyxyy,可见，只要能确定9个位置中4个y的位置就唯一确定了一条路径。,所以，本题答案就是C(n+m,m),排列组合数的一般计算方法,怎么计算？设计一个求阶乘的函数？,20！=243290200817664000012！=4790016008！=40320C(20,12)=125970,显然20！用int表示一定是失败的，而C(20,12)的结果又完全可以用int来表示。,回想我们是怎么计算的?,先约分再计算！,排列组合数的一般计算方法,（一）计算组合数的函数,int gcd(int a,int b)if(b=0)return a;el

5、se return gcd(b,a%b);/欧几里德辗转相除法求最大公约数gcd(a,b)=gcd(b,a mod b),int C(int n,int m)int i,a,fz=1,fm=1;,for(i=1;i=m;i+)fz*=(n-i+1);fm*=i;a=gcd(fz,fm);fz/=a;fm/=a;return fz/fm;,分子,分母,排列组合数的一般计算方法,（二）使用double类型,double C2(int n,int m)double product=1;int i;for(i=m;i=1;i-)product=product*(n-m+i)/(m-i+1);retur

6、n product;,/*在输出结果是应该注意要以整数形式输出.*/,#include#include using namespace std;int mainint n,m;cinnm;coutsetiosflags(ios:fixed)setprecision(0)C2(n,m)endl;return 0;,排列的生成算法,字典序法:顾名思义,这种方法就是将所有n元排列按“字典顺序”排成队，以12n为第一个排列，排序规则，即：由一个排列P(p1,p2pn)直接生成下一个排列的算法可归结为：,（1）求满足pk-1pk的k的最大值，设为i,即 i=maxk|pk-1pk,（2）求满足pi-1p

7、k的pk的最小值，其位置设为j,即 pj=minpk|pi-1pk,（3）pi-1与pj互换位置得（q）=（q1q2qn）,（4）(q)=（q1q2qi-1qiqi+1qn）中qiqi+1qn部分的顺 序逆转，得q1q2qi-1qnq i+1 qi 这便是下一个排列.,如排列839647521，首先从最右端开始，找到第一个比它的右临位小的数字，即4，然后从该数字的右边找到比它大的最小的数字，即5，交换两数字，原排列变为839657421最后将5位置右端的数字倒序排列，即变为839651247，这就是原排列的下一排列。,组合的生成算法,Zju1089有n(n=6)个数字，要求按字典序输出所有从该

8、n个数字中取6个的组合。,Sample Input7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0,Sample Output1 2 3 4 5 6 1 2 3 4 5 71 2 3 4 6 71 2 3 5 6 7,1 2 4 5 6 71 3 4 5 6 72 3 4 5 6 71 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21,n,组合的生成算法,Code:,#include#include#includeusing namespace std;int k;int used13;int lotto13;vo

9、id output();void choosenext(int I,int num);,int main()int n_case=0,i;while(cink,组合的生成算法,void output()int i,n=0;for(i=0;i k;i+)if(usedi)if(n)cout;coutlottoi;n+;coutendl;,void choosenext(int I,int num)if(num=6)output();return;if(I=k)return;for(int i=I;i k;i+)usedi=1;choosenext(i+1,num+1);usedi=0;,容斥原理

10、,2、逐步淘汰原理|A1.A2An|=|S|-|Ai|+|AiAj|-|AiAjAk|+(-1)n|A1A2An|,i=1,n,1 ij n,1 ijk n,另外容斥原理还有：Jordan公式和对称原理等。,容斥原理应用,错排问题。问题描述：n个元素一次给以标号1，2，n进行全排列，求每个元素不在自己原来位置上的排列数Dn。,解 令Ai表示数i排在第i个位置上的所有排列，则,|Ai|=(n-1)!,i=1,2,n,|AiAj|=(n-2)!i,j=1,2,n;i j,|AiAjAk|=(n-3)!i,j,k=1,2,n;i,j,k两两不相等,容斥原理应用,一般地，|Ai1Ai2Aik|=(n-

11、k)!,k=1,2,n,我们所求的是：1不在第一位，2不在第二位，3不在第三位n不在第n位的全排列数.,根据逐步淘汰原理得：Dn=n!C(n,1)(n-1)!+C(n,2)(n-2)!-(-1)nC(n,n)0!=n!(1-1/1!+1/2!-+(-1)n1/n!),容斥原理应用,例：zju1619Present n个朋友每人买了一份礼物，混合在一起后，每人拿一份，求恰有m人拿到了恰好是自己买的礼物的概率。,即:n个数的全排列中，m个保位,(n-m)个错位的排列数占总排列数的比例。,全排列数：n!,m个保位,(n-m)错位的排列数：C(n,m)Dn-m,结论：p=C(n,m)Dn-m/n!,容

12、斥原理应用,#include#includeusing namespace std;double jc100;void JC()jc0=1.0;int i;for(i=1;i 100;i+)jci=jci-1/(double)i;,容斥原理应用,int main()int m,n,curr=1;JC();while(cinnm)double res=0;int i;for(i=0;i=n-m;i+)if(i%2=0)res+=jci;else res-=jci;res*=jcm;coutsetiosflags(ios:fixed)setprecision(8)resendl;return 0;

13、,群论,群：给定非空集合G及定义在G上的二元运算“.”，若满足以下四个条件，则称集合G在运算“.”下构成一个群，简称G群：,(1)、封闭性：a,b G,则a.b G;,(2)、结合律：(a.b).c=a.(b.c),(3)、单位元：存在e G,对任意aG,有a.e=e.a=a;,(4)、逆元素：对任意a G,存在b G,使得a.b=b.a=e,称b为a的 逆元素，记为a-1;,群论,置换：n个元素1,2,n之间的一个置换：,表示1被1到n中的某个数 a1取代，2被1到n中的某个数a2取代，直到n被1到n中的某个数an取代，且a1,a2an互不相同。,置换群:置换群的元素是置换，运算是置换的连接

14、。例如：,群论,循环 记：(a1a2an)=,称为：n阶循环。每个置换都可以写成若干个互不相交的循环的乘积，两个循环(a1a2an)和(b1b2bn)互不相交是指ai bj,i,j=1,2,n.,例如：,=(1 3 6)(2 5)(4),循环又叫轮换，二阶轮换叫对换,群论,轮换上乘上一个对换的效果：,(1)、对换的两个元素分属于不同 的轮换中两个轮换合并 成一个轮换。,有连个轮换(a1,a2,a3,an),(b1,b2,b3,bn),一个对换(a1,b1)(a1,a2,a3,an)(a1,b1)(b1,b2,b3,bn)=(a1,a2,b1,b2bn),(2)、对换的两个元素属于同一个轮换一个

15、轮换拆分成了 两个轮换,(a1,a2,a3,an)(a1,ai)=(a1,a2,ai-1)(ai,ai+1,an),群论,例：传球游戏 两个组进行传球比赛。每组n人，围成一个圈，每人有一个在该组中唯一的编号（1n之间），每人有一个编号（1n）在该组唯一的球。每个人的球的编号是任意给定的。然后，游戏开始，每组的人开始进行组内对传，争取以最短的时间把球传到位。传到位是指一个组中的每个人手中的球的编号与他自己的编号相同。最后获胜的就是那个用最少的传球次数把球传到位的组。现需要你编一个程序从初始状态确定至少需几次对传才能将球传到位。,群论,分析：初始状态为一个置换，假设为：,末状态为n个长度为1的轮换

16、：,(1)(2)(3)(4)(5)(6),=(1 3 6)(2 5)(4),(1 3 6)(2)(5)(4),(1 6)(3)(2)(5)(4),所以：在该假设下，至少需要次对换，分别是(2 5)(1 3)(1 6),群论,结论:1、把初始状态转化成一系列轮换之积2、若原轮换的长度为n，次数为n-1；,Polya定理,例：手镯pku1286如果手镯有n个位置可用来嵌入宝石，有m种宝石可以嵌入，能生产出多少种不同类的手镯？如果将其中一只手镯做某种旋转或翻转使得两个手镯完全一样，我们认为这两个手镯是同类的。,Polya定理,对于有4个嵌宝石位置的手镯来说，有4种旋转方式，有4种翻转方式，用轮换相乘

17、来表示：,Polya定理,Polya定理：,设G是p个对象的一个置换群，用k种颜色涂染这p个对象，若一种染色方案在群G的作用下变为另一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为：,对于手镯一题，设n=4,m=2,L=(24+2+22+2+22+23+22+23)/8=6,|G|-置换群的元素是置换c(f)-循环节数,Polya定理,置换及循环节数的计算方法:,对于有n个位置的手镯，有n种旋转置换和n种翻转置换,对于旋转置换:c(fi)=gcd(n,i)i为一次转过i颗宝石。i=0 时 c=n;,对于翻转置换:,如果n为偶数 c(f)=n/2 的置换有n/2个;c(f)=n/2

18、+1 的置换有n/2个,如果n为奇数，c(f)=n/2+1;,Polya定理,Code,#include#include#include using namespace std;int gcd(int a,int b)return b?gcd(b,a%b):a;double go(int n);,int main()int n;while(cinn,Polya定理,double go(int n)double r=0;int i;for(i=0;in;i+)if(i=0)r+=pow(4.0,n);else r+=pow(4.0,gcd(n,i);if(n%2=0)r+=n/2*(pow(4.

19、0,n/2+1)+pow(4.0,n/2);else r+=n*(pow(4.0,n/2+1);return r/n/2;,递推关系,在一些计数问题中，很难直接得到计数序列ai的通项公式，但是可以建立相邻几项的关系，可以利用这些关系一步步计算出需要的值，或者求解递推关系得到通项公式。,例1上楼梯问题 某人欲登上n级楼梯，若每次只能跨一级或 两级，问他从地面上到第n级楼梯，共有多少种不同的方法。,解，假设上到第n级楼梯的方法数为an，那么，第一步无非有两种走法：（1）跨一级，则余下的n-1级有an-1种上法；（2）跨两级，则余下的n-2级有an-2种上法；所以 an=an-1+an-2;,递推关系,例zju1475 ranklistn个人参加比赛，有多少种不同的名次排列方法，注意多人并列的情况。,Sample Input123-1,Sample Output1313,递推关系,分析：设n个人参加比赛，m个不同名次的ranklist共有F(n,m)个，则：,F(n,m)=,(在n-1个人m-1个不同名次的ranklist中增加一个名次共有m种方法),mF(n-1,m-1),mF(n-1,m),(将新增加的一人加到m个名次中的任一个中有m种方法),结论：An=F(n,1)+F(n,2)+F(n,n),+,