《組合數(shù)學(xué)在程序設(shè)計中的應(yīng)用》由會員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)在程序設(shè)計中的應(yīng)用（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,組合數(shù)學(xué)在程序設(shè)計中的應(yīng)用,長沙市第一中學(xué),曹利國,程序設(shè)計一直與數(shù)學(xué)聯(lián)系得非常的緊密，特別是像組合數(shù)學(xué)這一分支，與程序設(shè)計有著千絲萬縷的聯(lián)系。對于某些題目，我們用正常的做法想法也許無從下手，但是如果我們把題目的全局或者局部與組合數(shù)學(xué)聯(lián)系起來，或許就會“柳暗花明又一村”,找到了一種特別獨(dú)特，特別有效率的數(shù)學(xué)方法，把無從下手的棘手題變得簡單易行。這就是組合數(shù)學(xué)在程序中的運(yùn)用。,下面使用幾個實(shí)例說明組合數(shù)學(xué)在程序中的運(yùn)用。,引言,Catalan,數(shù),定義：一個凸,n,邊形通過不相交于,n,邊形內(nèi)部的對角線把,n
2、,邊形拆分成若干三角形的不同拆分?jǐn)?shù)。,分析,設(shè),Cn,表示凸,n,邊形的拆分方案總數(shù)。由題目中的要求可知一個凸,n,邊形的任意一條邊都必然是一個三角形的一條邊，邊,P1 Pn,也不例外，再根據(jù)“不在同一直線上的三點(diǎn)可以確定一個三角形”，只要在,P2,，,P3,，,，,Pn-1,點(diǎn)中找一個點(diǎn),Pk(1k=0,的數(shù)列個數(shù)。,序列,a1a2.ak,的元素順序保持不變，按不同結(jié)合方式插入合法圓括號對的方案數(shù)。,n=4(a(bc)d)(a(b(cd)(ab)(cd)(ab)c)d)(a(bc)d),一個操作數(shù)序列，從,1,，,2,，一直到,n,，棧,A,的深度大于,n,。,現(xiàn)在可以進(jìn)行兩種操作：,1,將
3、一個數(shù)，從操作數(shù)列的頭端移至棧的頭端（對應(yīng)棧的,push,操作）,2,將一個數(shù)，從棧的頭端移至輸出序列的尾端（對應(yīng)棧的,pop,操作）。,使用這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列，下表為由,1 2 3,生成序列,2 3 1,的過程。,步驟,0,1,2,3,4,5,6,操作數(shù)序列,123,23,3,3,棧,1,21,1,31,1,輸出序列,2,2,23,231,你的程序?qū)o定的,n,，,計算并輸出由操作數(shù)序列,1,，,2,，,，,n,經(jīng)過操作可能得到的輸出序列總數(shù)。,一,棧,(,Noip2003,普及組第三題,),結(jié)合定義我們很容易能發(fā)現(xiàn)：如果進(jìn)?？闯?1,，出棧看成,0,，
4、在任何一位上累計的“,0,”,的個數(shù)不大于累計的“,1,”,的個數(shù)，因?yàn)楸仨氃跅＠镉袛?shù)的情況下才能向外彈數(shù)。,原題轉(zhuǎn)化為,n,個,1,和,n,個,0,組成一個,2,n,位的二進(jìn)制數(shù)，要求從左到右掃描，“,0,”,的累計數(shù)不大于“,1,”,的累計數(shù)，求滿足條件的數(shù)有多少。,二,Little rooks(SGU 222),將,k,個車擺在,n*n,的棋盤上，使得任何兩個車不能互相攻擊（車可以橫著或豎著走無限格，不能走斜線）,算法描述,組合數(shù)學(xué)：排列與組合,由于題目里的棋子是“車”而不是“后”，所以一個棋子不會影響到與其不同行或與其不同列的棋子。結(jié)合,n,皇后問題的方案表示法，我們很容易想到排列組合
5、。,排列的定義：設(shè),A=a1,a2,a3,an,是,n,個不同元素的集合，,r,滿足,0=,r=k,，,先從簡單的情況下手：,n=k,。,此時的公式非常簡單：,P(n,k),。,主要就是對于,nk,的情況時的處理。,因?yàn)槊恳涣凶疃嘀荒芊乓活w棋子，所以我們首先把沒有棋子的列去掉，再合并成一個,n*k,的棋盤，結(jié)合剛才的數(shù)據(jù)結(jié)構(gòu)我們能很快知道在這個新棋盤上擺,k,個棋子還是,P(n,k),種方案，再把去掉的,(,n-k+1),列插入擺棋子的,k,行中，插入方案總數(shù)易得為,C(n,k),種。,根據(jù)乘法原理，總方案數(shù)為,C(n,k)*P(n,k),種。這樣一來程序?qū)崿F(xiàn)起來就方便多了。,錯排問題：,n,
6、個數(shù)，分別為,1,n,，,排成一個長度為,n,的排列。若每一個數(shù)的位置都與數(shù)的本身不相等，則稱這個排列是一個錯排。例如，,n=3,，,則錯排有,2 3 1,、,3 1 2,。編寫程序，求,n,的錯排個數(shù)。,三,錯排問題（經(jīng)典問題）,組合數(shù)學(xué)：遞推,我們設(shè),k,個元素的錯位全排列的個數(shù)記做：,W(k),。,四個元素的錯位排列,W(4),我們用窮舉法可以找到如下,9,個：,(4,，,3,，,2,，,1)(3,，,4,，,1,，,2)(2,，,1,，,4,，,3),(4,，,1,，,2,，,3)(3,，,4,，,2,，,1)(3,，,1,，,4,，,2),(4,，,3,，,1,，,2)(2,，,4,
7、，,1,，,3)(2,，,3,，,4,，,1),它們有什么規(guī)律呢？,通過反復(fù)的試驗(yàn)，我們發(fā)現(xiàn)事實(shí)上有兩種方式產(chǎn)生,錯位排列,：,A.,將,k,與,(1,，,2,，,，,k,1),的某一個數(shù)互換，其他,k,2,個數(shù)進(jìn)行錯排，這樣可以得到,(,k,1),W(k-2),個錯位排列,。,B.,另一部分是將前,k,1,個元素的每一個錯位排列（有,W(k-1),個）中的每一個數(shù)與,k,互換，這樣可以得到剩下的,(,k,1),W(k-1),個錯位排列。,根據(jù)加法原理，我們得到求,錯位排列的遞推公式,W(k):,W(k)=(k,1)*W(k,1)+W(k,2),結(jié)論,其實(shí)視野看得發(fā)散一些，擴(kuò)展一些，能融入程序設(shè)計的知識點(diǎn)不僅限于組合數(shù)學(xué)，還有拓?fù)鋵W(xué)，微積分，計算幾何,甚至是物理，化學(xué)。這樣跨學(xué)科的融合相信能給信息學(xué)計算機(jī)這門學(xué)科煥發(fā)新的光彩。,從上述題我們能發(fā)現(xiàn)一個共同特點(diǎn)，也就是將組合數(shù)學(xué)融入題目中，簡單而又快速的解決題目。它說明：程序設(shè)計不一定是拿著現(xiàn)成的思路或算法去生搬硬套，也許我們換個角度，換個思路，或者進(jìn)行數(shù)學(xué)建模與變換，將組合數(shù)學(xué)里的一些結(jié)論，定理，性質(zhì)與程序結(jié)合起來，達(dá)到事半功倍的效果。當(dāng)然，要熟練的掌握這方面的技能與技巧還是在乎于我們平常的多看多想多練。,
組合數(shù)學(xué)在程序設(shè)計中的應(yīng)用
