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

组合数学在程序设计竞赛中的应用,内容提要,排列组合和容斥原理 群论与Polya定理 递推关系,两个基本原则,1、加法原则 如果完成一件事情有两种方案，而第一个方案有m种方法，第二个方案有n中方法，则完成该事情共有m+n种方法。 2、乘法原则 如果完成一件事情需要两个步骤，第一步有m中方法，第二步又有n种方法，则完成该事情共有m*n种方法,排列组合的几个基本结论,1、相异元素不允许重复的排列数和组合数：,2、不尽相异元素的全排列,排列组合的几个基本结论,3、相异元素不允许重复的圆排列,4、相异元素允许重复的组合数,集合描述：设S=e1, e2, en,，从S中允许重复地取出r个元素，称为r可重组合,排列组合例题,例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人在场至少缺少一种此人所具有的特征 而无法打开锁。每张磁卡至少应有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 4 1 1 0 0 Sample Output (路径数目) 126 2,排列组合例题,我们用组合数学的思路来解题。最短路径必定是一条只向右上走得路。设向右走一步为x，向上走一步为y。则每一条路线一定对应由n个x，m个y共m+n个元素组成的排列。,以n=5，m=4为例，,任意一条路线如下图所示，对应的xy序列 为：xyxxxyxyy,可见，只要能确定9个位置中4个y的位置 就唯一确定了一条路径。,所以，本题答案就是C(n+m,m),排列组合数的一般计算方法,怎么计算？设计一个求阶乘的函数？,20！= 2432902008176640000 12！= 479001600 8！ = 40320 C(20,12) = 125970,显然20！用int表示一定是失败的，而C(20,12)的结果又完全 可以用int来表示。,回想我们是怎么计算的?,先约分再计算！,排列组合数的一般计算方法,（一）计算组合数的函数,int gcd(int a, int b) if(b=0)return a; else 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); return product; ,/* 在输出结果是应该注意要以 整数形式输出.*/,#include #include using namespace std; int main int 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-1pk的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)个数字，要求按字典序输出所有从该n个数字中取6个的组合。,Sample Input 7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0,Sample Output 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7,1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 1 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 #include using namespace std; int k; int used13; int lotto13; void 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; ,容斥原理,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-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!,容斥原理应用,#include #include using 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;,群论,群：给定非空集合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互不相同 。,置换群:置换群的元素是置换，运算是置换的连接。例如：,群论,循环 记： (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)、对换的两个元素属于同一个轮换一个轮换拆分成了 两个轮换,(a1,a2,a3,an)(a1,ai) = (a1,a2,ai-1)(ai,ai+1,an),群论,例：传球游戏 两个组进行传球比赛。每组n人，围成一个圈，每人有一个 在该组中唯一的编号（1n之间），每人有一个编号（1n） 在该组唯一的球。每个人的球的编号是任意给定的。然后，游 戏开始，每组的人开始进行组内对传，争取以最短的时间把球 传到位。传到位是指一个组中的每个人手中的球的编号与他自 己的编号相同。最后获胜的就是那个用最少的传球次数把球 传到位的组。 现需要你编一个程序从初始状态确定至少需几次对传才能将球传到位。,群论,分析： 初始状态为一个置换，假设为：,末状态为n个长度为1的轮换：,(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种 翻转方式，用 轮换相乘来表 示：,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+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