1、信息學(xué)競(jìng)賽 -之?dāng)?shù)學(xué)知識(shí),組合數(shù)學(xué),Noip歷年提高組決賽題中的數(shù)學(xué)題及難度（最難5星）,第一節(jié) 排列組合, 加法原理、乘法原理 排列組合生成算法,加法原理,若事件X能以x種方式發(fā)生，另一個(gè)不同的時(shí)間Y能以y種不同的方式發(fā)生，則事件X或者事件Y能以（x+y）種方式發(fā)生。 例：全系共三個(gè)班級(jí)，這三個(gè)班級(jí)準(zhǔn)備參加acm競(jìng)賽的學(xué)生人數(shù)分別是3，4，5，則全系準(zhǔn)備參加acm競(jìng)賽的人數(shù)3+4+5=12.,乘法原理,若事件X能以x種方式發(fā)生，另一個(gè)不同的事件Y能以y種不同的方式發(fā)生，則事件x和事件y能以xy種方式發(fā)生。 例：求小于10億且不包含數(shù)字1的正整數(shù)的個(gè)數(shù)。 解： 首先計(jì)算不包含數(shù)字1的數(shù)的個(gè)數(shù)，

2、從0，2-9中尋找9個(gè)符號(hào)的字符串，第一個(gè)數(shù)字有9種選擇，第二個(gè)數(shù)字有9種選擇，等等。 根據(jù)加法原理共有99=387420489個(gè)數(shù)，其中包括000000000.如果從100000000中減去這樣的數(shù)字，得到的答案為612579511.,排列與全排列,從n個(gè)不同元素中，有次序的選取r個(gè)元素，稱為從n中取r個(gè)的排列，其排列數(shù)記為P(n,r).當(dāng)r=n時(shí)，稱為全排列。 例如：從A,B,C,D中有序選取兩個(gè)字母，則有12種選擇。 AB AC AD BA BC BD CA CB CD DA DB DC P (4,2)=12.,定理：p(n,r)=n!/(n-r)!,例題：從n個(gè)不同元素中選取r個(gè)元素圍

3、成一個(gè)圓。求選取的方案總數(shù)。 解：從n個(gè)不同元素中選取r個(gè)元素選取的方案總數(shù)為p(n,r). a1ar為其中一組解。 將其變換，a2-ar,a1;a3-ar,a1,a2;.共有r個(gè)排列。但是這n個(gè)排列對(duì)一個(gè)圓。所以題目中所求方案為p/r,組合,從n個(gè)不同元素中，選取r個(gè)元素而不考慮其次序，成為從n個(gè)中取r個(gè)的組合，記為c(n,r). 例：從（a,b,c,d）中選取出2個(gè)元素的組合，則有如下情況： （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、且規(guī)定只能向上想右走，問共多少種方案？,解題思路： 左右 4步 下上 3步 無論怎么選擇均為右4+上3。 0向右走1向上走 所以可以走法可以看作由01組 成的字符串 即所求方案數(shù)為4個(gè)0和3個(gè)1組成的 7位字符串的個(gè)數(shù)。 C(7,4)=?,排列組合生成算法,R-排列生成算法： 采用回溯法生成從n中選r個(gè)元素的所有排列情況： n個(gè)元素用1，2，n來表示 函數(shù)done遞歸的層數(shù)i表示當(dāng)前正在生成排列中第i個(gè)位置的數(shù)。 函數(shù)done(i)執(zhí)行時(shí)，首先判斷j是否在該排列以前的幾個(gè)位置上出現(xiàn)過，若出現(xiàn)則說明j不可能出現(xiàn)在當(dāng)前位置上，此時(shí)j值增1重復(fù)以上判斷，j=n時(shí)回溯；若j沒有在該排列以前的位置上出現(xiàn)

5、，則該位置上的值就是j，后判斷遞歸的層數(shù)i與r的值是否相等。若i=r，輸出一個(gè)新的排列并回溯。若ir,則繼續(xù)進(jìn)行遞歸。,錯(cuò)位排列生成算法,錯(cuò)位排列生成算法與r排列生成算法的不同：生成錯(cuò)排第i個(gè)位置上的元素時(shí)，必須保證該元素不等于i。,R-組合生成算法,從n個(gè)元素中取出r個(gè)元素的一個(gè)組合情況恰對(duì)應(yīng)了r！個(gè)r-排列情況。 所以當(dāng)按照元素的遞增次序放置相應(yīng)位置上的元素時(shí)，就可以產(chǎn)生從n個(gè)元素中取出r個(gè)元素的所有組合情況。,試題,購票問題： 農(nóng)夫John和他的朋友們一起去參加cownty展覽會(huì)，cownty展覽會(huì)的門票為$50,john發(fā)現(xiàn)一個(gè)奇怪的現(xiàn)象：排隊(duì)購票的2n人中,總有n個(gè)人拿的是面值$10

6、0的鈔票，而另外n個(gè)人拿的是面值$50的鈔票。John想知道的是在這種情況下這2n個(gè)人共有多少種排隊(duì)的方法，使售票處不至于出現(xiàn)找不開錢的局面（假設(shè)售票處原來沒有零錢）？,算法1：搜索 算法2：棧模型 算法3：遞歸算法 算法4：遞推算法 算法5：組合算法,算法1：搜索法,使用回溯法，枚舉所有情況。 變量k為記錄售票處有$50的情況， 初始：k=0; 回溯：若某人手拿100鈔票且k=0時(shí)，否則繼續(xù)遞 歸。 輸出“：若第2n個(gè)人購票后即遞歸到2n層時(shí)計(jì)算器累加1，遞歸結(jié)束后，計(jì)數(shù)器中變?yōu)榕抨?duì)總方案數(shù)。,2：棧模型,在任意時(shí)候，若第n人手持100的鈔票，在此之前有M個(gè)人手持50的鈔票購票，使得m=n;

7、 即： 售票處將收到的50的鈔票最終全部找出，將100的鈔票全部留下，并且一旦收到一張面值為100的鈔票，則一定要找出一張面值50的鈔票。 棧模型表示：若一人手持50的鈔票購票，相當(dāng)于一個(gè)元素進(jìn)棧。將問題轉(zhuǎn)化為：1n共n個(gè)元素依次進(jìn)棧，問共多少中出棧順序。 n個(gè)元素的全排列共有n！種方案，那么n!種方案是否都是可能的出棧順序？,若a1,a2,a3,an是可能的出棧順序，則一定不存在這樣的情況，使得iaj,那么aj出棧時(shí)，如果ak已經(jīng)在棧中，則ak比aj先入棧，由輸入序列知道：akaj,所以有akajai;當(dāng)aj出棧時(shí)，如果ak 尚未入棧，則由輸入序列知道ajaiak. (2）如果aIaj, a

8、iajak. 因此：不可能出現(xiàn)ijk,aJakai的情況,棧模型算法,算法先產(chǎn)生1-n共n個(gè)數(shù)的全排列，對(duì)于每種排列，若符合前面所講的出棧規(guī)則，那么這個(gè)排列便是一個(gè)可能的出棧序列。計(jì)數(shù)器加1，當(dāng)n個(gè)全排列列舉結(jié)束時(shí)，得到問題的解。,遞歸算法,令f（m,n）表示m個(gè)人手持50的鈔票。N個(gè)人手持100的鈔票時(shí)總共的方案數(shù)。 （1）當(dāng)n=0時(shí)， n=0意味著排隊(duì)購票的所有人手中拿的都是50的，那么這個(gè)m的人排隊(duì)方案總數(shù)為1，即f(m,0)=1 (2)當(dāng)mn 當(dāng)mn時(shí)，即使m張50全部找出，仍會(huì)找不開，所以排隊(duì)數(shù)為0,（3）其他 第（m+n）個(gè)人站在第（m+n-1）的后面，則第（m+n）個(gè)人的排隊(duì)方式

9、可由下列2種情況獲得： 1，第（m+n）個(gè)人手持100，則在他之前的M+n-1 個(gè)人中m人手持50的，n-1個(gè)人手持100的鈔票，此種情況共f(m,n-1) 2,第（m+n）個(gè)人手持50，則在他之前的M+n-1 個(gè)人中m-1人手持50的，n 個(gè)人手持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ā)現(xiàn)f（3，2）等節(jié)點(diǎn)有重復(fù)計(jì)算，課件遞歸算法產(chǎn)生大量的數(shù)據(jù)冗余，這些冗余數(shù)據(jù)是限制遞歸算法的主要因素，從而導(dǎo)致了模型3雖進(jìn)行了數(shù)學(xué)抽象，但是算法實(shí)現(xiàn)起來的效率并不高。如何解決呢？計(jì)算中保留數(shù)值-采用遞推法保證同一個(gè)數(shù)據(jù)只計(jì)算一次。,O(n2)復(fù)雜度 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、， 依據(jù)下列原則對(duì)n個(gè)節(jié)點(diǎn)的二叉樹定點(diǎn)編號(hào)：若節(jié)點(diǎn)i是節(jié)點(diǎn)j的子節(jié)點(diǎn)，則ij;若節(jié)點(diǎn)i是節(jié)點(diǎn)K的左兒子，節(jié)點(diǎn)j是節(jié)點(diǎn)k的右兒子，則ij. 中序遍歷時(shí)最左邊的節(jié)點(diǎn)一定是第一個(gè)節(jié)點(diǎn)，最右邊的節(jié)點(diǎn)一定是最后一個(gè)節(jié)點(diǎn)。對(duì)于任意一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，前序遍歷順序?yàn)?n,即n個(gè)元素的入棧順序，中序遍歷順序便是這n個(gè)元素的出棧順序，即2n個(gè)人的排隊(duì)方式總數(shù)為n個(gè)節(jié)點(diǎn)的二叉樹的個(gè)數(shù)，又因?yàn)榫哂衝個(gè)節(jié)點(diǎn)的二叉樹的個(gè)數(shù)為cn=1/n+1 c(2n n )catalan數(shù)。,前序遍歷遍歷結(jié)果：ABDECF 中序遍歷遍歷結(jié)果：DBEAFC,排列組合的方法： 用1表示一個(gè)手拿50的人，用0表示一個(gè)手拿100的人，那

12、么求解的問題可以轉(zhuǎn)化為：n個(gè)1和n個(gè)0組合一個(gè)2n位的二進(jìn)制數(shù)，要求從左向右掃描，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)，求滿足這個(gè)條件的二進(jìn)制的數(shù)的個(gè)數(shù)。 在2n位上填入n個(gè)1的方案數(shù)為c(2n,n)不填1的其余n位自動(dòng)填入0.從c(2n,n)中減去不符合要求的方案數(shù)就是問題的解。不符合要求的方案即從左向右掃描，出現(xiàn)0的累計(jì)次比1的多。,不符合條件數(shù)的特征：從左向右掃描，必然會(huì)在某一個(gè)奇數(shù)位2m+1位上首先出現(xiàn)m+1個(gè)0和m個(gè)1；而后的2（n-m）-1位上有n-m個(gè)1，n-m-1個(gè)0.如果把后面這部分2（n-m）-1位的0和1交換，使之成為n-m個(gè)0，n-m-1個(gè)1，結(jié)果得到一個(gè)由n+1個(gè)0和n-1個(gè)1組成的2n位數(shù)。即不符合要求的數(shù)字對(duì)應(yīng)一個(gè)由n+1個(gè)0和n-1個(gè)1 組成的一個(gè)排列。 反之，任何一個(gè)由n+1個(gè)0 和n-1個(gè)1組成的2n