組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用

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