組合數學競賽中的應用.ppt

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工作人員每人發(fā)一張磁卡，卡上有開鎖的密碼特征，為了確保安全，規(guī)定至少有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 0 Sample Output (路徑數目) 1262,排列組合例題,我們用組合數學的思路來解題。最短路徑必定是一條只向右上走得路。設向右走一步為x，向上走一步為y。則每一條路線一定對應由n個x，m個y共m+n個元素組

4、成的排列。,以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

5、 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; in

6、t 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為第一個排列，排序規(guī)則，即：由一個排列P(

7、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，交換兩數字，原排列變?yōu)?39657421最后將

8、5位置右端的數字倒序排列，即變?yōu)?39651247，這就是原排列的下一排列。,組合的生成算法,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,組合的

9、生成算法,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 choosenex

10、t(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進行全排列，求每個元素不在自己原

11、來位置上的排列數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!-+(-

12、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/

13、(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;

14、,(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互不相同 。,置換群:置換群的元素是置換，運算是置換的連接。例如：,群論,循環(huán) 記： (a1a2an)=,稱為：n階循環(huán)。每個置換都可以寫成若干個互不相交的 循環(huán)的乘積，兩個循環(huán)(a1a2an)和(b1b2bn)互不相交

15、 是指ai bj, i,j = 1,2,n.,例如：,= (1 3 6)(2 5)(4),循環(huán)又叫輪換，二階輪換叫對換,群論,輪換上乘上一個對換的效果：,(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),群論,例：傳球游戲 兩個

16、組進行傳球比賽。每組n人，圍成一個圈，每人有一個 在該組中唯一的編號（1n之間），每人有一個編號（1n） 在該組唯一的球。每個人的球的編號是任意給定的。然后，游 戲開始，每組的人開始進行組內對傳，爭取以最短的時間把球 傳到位。傳到位是指一個組中的每個人手中的球的編號與他自 己的編號相同。最后獲勝的就是那個用最少的傳球次數把球 傳到位的組。 現需要你編一個程序從初始狀態(tài)確定至少需幾次對傳才能將球傳到位。,群論,分析： 初始狀態(tài)為一個置換，假設為：,末狀態(tài)為n個長度為1的輪換：,(1)(2)(3)(4)(5)(6),= (1 3 6)(2 5)(4),(1 3 6)(2)(5)(4),(1 6)(

17、3)(2)(5)(4),所以：在該假設下，至少需要次對換，分別是(2 5)(1 3)(1 6),群論,結論: 1、把初始狀態(tài)轉化成一系列輪換之積 2、若原輪換的長度為n，次數為n-1；,Polya定理,例：手鐲pku1286 如果手鐲有n個位置可用來嵌入寶石，有m種寶石可以嵌入，能生產出多少種不同類的手鐲？ 如果將其中一只手鐲做某種旋轉或翻轉使得兩個手鐲完全一樣，我們認為這兩個手鐲是同類的。,Polya定理,對于有4個嵌寶 石位置的手鐲 來說，有4種旋 轉方式，有4種 翻轉方式，用 輪換相乘來表 示：,Polya定理,Polya定理：,設G是p個對象的一個置換群，用k種顏色涂染這p個對象，若一

18、種染色方案在群G的作用下變?yōu)榱硪环N方案，則這兩個方案當作是同一種方案，這樣的不同染色方案數為：,對于手鐲一題，設n=4,m=2,L = (24+2+22+2+22+23+22+23)/8=6,|G| -置換群的元素是置換 c(f)-循環(huán)節(jié)數,Polya定理,置換及循環(huán)節(jié)數的計算方法:,對于有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); el