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

1、組合數(shù)學(xué)組合數(shù)學(xué)(shxu)在程序設(shè)計在程序設(shè)計中的應(yīng)用中的應(yīng)用長沙市第一(dy)中學(xué)曹利國第一頁，共16頁。 程序設(shè)計一直與數(shù)學(xué)聯(lián)系得非常的緊密，特別是像組合數(shù)學(xué)這一分支，與程序設(shè)計有著千絲萬縷的聯(lián)系。對于某些題目，我們用正常的做法想法也許無從下手，但是如果我們把題目的全局或者局部(jb)與組合數(shù)學(xué)聯(lián)系起來，或許就會“柳暗花明又一村”找到了一種特別獨特，特別有效率的數(shù)學(xué)方法，把無從下手的棘手題變得簡單易行。這就是組合數(shù)學(xué)在程序中的運用。 下面使用幾個實例說明組合數(shù)學(xué)在程序中的運用。引言引言(ynyn)第二頁，共16頁。Catalan數(shù)定義：一個凸n邊形通過不相交于n邊形內(nèi)部的對角線把n邊形拆

2、分成若干(rugn)三角形的不同拆分?jǐn)?shù)。第三頁，共16頁。分析(fnx)設(shè)Cn表示凸n邊形的拆分方案總數(shù)。由題目(tm)中的要求可知一個凸n邊形的任意一條邊都必然是一個三角形的一條邊，邊P1 Pn也不例外，再根據(jù)“不在同一直線上的三點可以確定一個三角形”，只要在P2，P3，Pn-1點中找一個點Pk(1k=0的數(shù)列個數(shù)。 第六頁，共16頁。 序列a1a2.ak的元素順序保持不變，按不同結(jié)合方式插入合法(hf)圓括號對的方案數(shù)。n=4(a(bc)d)(a(b(cd)(ab)(cd)(ab)c)d)(a(bc)d) 第七頁，共16頁。一個操作數(shù)序列，從一個操作數(shù)序列，從1，2，一直到，一直到n，棧，

3、棧A的深度大于的深度大于n?，F(xiàn)在可以進(jìn)行兩種操?，F(xiàn)在可以進(jìn)行兩種操作：作：1將一個數(shù)，從操作數(shù)列的頭端移至棧的頭端（對應(yīng)棧的將一個數(shù)，從操作數(shù)列的頭端移至棧的頭端（對應(yīng)棧的push操作）操作）2將將一個數(shù)，從棧的頭端移至輸出序列的尾端（對應(yīng)棧的一個數(shù)，從棧的頭端移至輸出序列的尾端（對應(yīng)棧的pop操作）。操作）。使用使用(shyng)這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列，這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列，下表為由下表為由123生成序列生成序列231的過程。的過程。步驟0123456操作數(shù)序列1232333 棧 1211311 輸出序列 2223231你的程

4、序?qū)o定的n，計算并輸出由操作數(shù)序列1，2，n經(jīng)過操作可能(knng)得到的輸出序列總數(shù)。一一棧棧(Noip2003普及普及(pj)組第三題組第三題)第八頁，共16頁。結(jié)合定義我們很容易能發(fā)現(xiàn)：如果進(jìn)?？闯?，出?？闯?，在任何一位上累計的“0”的個數(shù)不大于累計的“1”的個數(shù)，因為必須(bx)在棧里有數(shù)的情況下才能向外彈數(shù)。原題轉(zhuǎn)化為n個1和n個0組成(z chn)一個2n位的二進(jìn)制數(shù)，要求從左到右掃描，“0”的累計數(shù)不大于“1”的累計數(shù)，求滿足條件的數(shù)有多少。第九頁，共16頁。 二 Little rooks(SGU 222) 將k個車擺在n*n的棋盤上，使得任何(rnh)兩個車不能互相攻擊

5、（車可以橫著或豎著走無限格，不能走斜線） 第十頁，共16頁。算法算法(sun f)描描述述 組合數(shù)學(xué)(shxu)：排列與組合由于題目里的棋子是“車”而不是“后”，所以一個棋子不會影響(yngxing)到與其不同行或與其不同列的棋子。結(jié)合n皇后問題的方案表示法，我們很容易想到排列組合。排列的定義：設(shè)A=a1,a2,a3an是n個不同元素的集合，r滿足0=r=k，先從簡單的情況下手：n=k。此時的公式非常簡單：P(n,k)。主要就是(jish)對于nk的情況時的處理。因為每一列最多只能放一顆棋子，所以我們首先把沒有棋子的列去掉，再合并成一個n*k的棋盤，結(jié)合剛才的數(shù)據(jù)結(jié)構(gòu)我們能很快知道在這個新棋盤

6、上擺k個棋子還是P( n , k )種方案，再把去掉的(n-k+1)列插入(ch r)擺棋子的k行中，插入(ch r)方案總數(shù)易得為C( n , k )種。根據(jù)(gnj)乘法原理，總方案數(shù)為C( n , k ) * P( n , k )種。這樣一來程序?qū)崿F(xiàn)起來就方便多了。第十二頁，共16頁。錯排問題：n個數(shù)，分別為1n，排成一個長度為n的排列(pili)。若每一個數(shù)的位置都與數(shù)的本身不相等，則稱這個排列(pili)是一個錯排。例如，n=3，則錯排有2 3 1、3 1 2。編寫程序，求n的錯排個數(shù)。三三錯排問題錯排問題(wnt)（經(jīng)典問題（經(jīng)典問題(wnt)）第十三頁，共16頁。組合(zh)數(shù)學(xué)

7、：遞推我們(w men)設(shè)k個元素的錯位全排列的個數(shù)記做：W(k)。四個元素(yun s)的錯位排列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，1，3)(2，3，4，1)它們有什么規(guī)律呢？第十四頁，共16頁。通過反復(fù)的試驗，我們(w men)發(fā)現(xiàn)事實上有兩種方式產(chǎn)生錯位排列： A.將k與(1，2，k1)的某一個數(shù)互換，其他k2個數(shù)進(jìn)行錯排，這樣可以得到(d do)(k1)W(k-2)個錯位排列。 B.另一部分是將前k1個元素的每一個錯位(cu wi)排列（有W(k-1)個）中的每一個數(shù)與k互換，這樣可以得到剩下的(k1)W(k-1) 個錯位(cu wi)排列。根據(jù)加法原理，我們得到求錯位排列的遞推公式W(k):W(k) = (k1) * W(k1)+W(k2)第十五頁，共16頁。結(jié)論結(jié)論(jiln)其實視野看得發(fā)散一些，擴展一些，能融入程序設(shè)計的知識點不僅限于組合數(shù)學(xué)，還有拓?fù)鋵W(xué)，微積分，計算幾何甚至是物理，化學(xué)。這樣跨學(xué)科的融合(rngh)相信能給信息學(xué)計算機這門學(xué)科煥發(fā)新的光彩。 從上述題我們能發(fā)現(xiàn)一個共同特點，也就是將組合數(shù)學(xué)融入題目中，簡單而又快速的解決題目。它說明：程序設(shè)計不一定是拿著現(xiàn)成