排列組合及其在noip中的應(yīng)用

《排列組合及其在noip中的應(yīng)用》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、排列組合及其在NOIP中的應(yīng)用　　我們在數(shù)學課里面學過排列組合的基礎(chǔ)知識，內(nèi)容大致如下：這些知識，在信息學分區(qū)聯(lián)賽中有著極其廣泛的應(yīng)用。初賽和復賽有所不同：在初賽中，主要考查大家對排列、組合的理解，要求大家能夠正確的使用排列數(shù)的計算公式和組合數(shù)的計算公式；復賽則要求大家能夠比較深入的領(lǐng)會排列的產(chǎn)生過程和組合的產(chǎn)生過程。例1：（第八屆全國青少年信息學奧林匹克分區(qū)聯(lián)賽（普及組PASCAL語言）第二大題第2小題）將N個紅球和M個黃球排成一行。例如：N=2，M=2可得到以下6種排法：紅紅黃黃?紅黃紅黃?紅黃黃紅?黃

2、紅紅黃?黃紅黃紅?黃黃紅紅問題：當N=4，M=3時有多少種不同排法？（不用列出每種排法）分析：要計算出N=4，M=3的排法。球的總數(shù)是7個，我們可以理解為：有7個可以用來存放這些球的箱子，如下圖???????怎樣將這些球放入相應(yīng)的箱子中呢？如果這7個球完全不一樣，我們很容易知道，存放的方法就是7的全排列，即：。但實際上，這7個球只分為兩種：紅球和黃球。所以，只要我們把其中任意一種球的存放位置確定好，問題就算解決了。剩下的球只需往空的箱子里面放。比如，我們要確定紅球的存放位置。紅球一共有4個。要把4個紅球放入

3、已知的7個箱子中，因為這4個紅球都是一樣的，所以存放的方法實際上就是從7個箱子中任取4個的組合，即：。直接套用組合數(shù)公式進行計算　答案為：35種。例2：選數(shù)（2002年全國青少年信息學（計算機）奧林匹克分區(qū)聯(lián)賽普及組復賽試題第二題）[問題描述]：已知n個整數(shù)x1,x2,…,xn，以及一個整數(shù)k(k<=n)。從n個整數(shù)中任選k個整數(shù)相加，可分別得到一系列的和。例如當n=4,k=3，4個整數(shù)分別為3,7,12,19時，可得全部的組合與它們的和為：3+7+12=22?3+7+19=29?7+12+19=38?3+

4、12+19=34現(xiàn)在，要求你計算出和為素數(shù)共有多少種。例如上例，只有一種的和為素數(shù)：3+7+19=29。[輸入]：鍵盤輸入，格式為：??????????????n,k(1<=n<=20,k<=n)??????????????x1,x2,…,xn(1<=xi<=5000000)[輸出]：屏幕輸出，格式為：一個整數(shù)（滿足條件的種數(shù)）分析：這是一個典型的綜合題。要求我們能夠綜合運用所學過的數(shù)學知識和計算機知識對問題進行分析。從數(shù)學方面講，我們需要對素數(shù)和組合都有比較深刻的認識。從計算機方面講，主要涉及了窮舉、迭代

5、和遞歸算法；并且，要求大家能夠深入的理解遞歸算法的執(zhí)行過程。解決這道題需要做好兩個工作：①組合的產(chǎn)生；②素數(shù)的判定?？梢詫⒁阎膎個整數(shù)存放在一個數(shù)組X中。因為xi的取值范圍為1<=xi<=5000000，所以數(shù)組元素的數(shù)據(jù)類型應(yīng)該定義為長整型（LONG）。需要設(shè)計一個算法，判斷給定的整數(shù)z是素數(shù)（質(zhì)數(shù)）還是合數(shù)。將此算法定義為一個函數(shù)sushu(z)，當z為素數(shù)時返回函數(shù)值0，否則返回函數(shù)值1。參考程序如下：functionsushu(zaslong)?sushu=0?fori=2tosqr(z)???i

6、fzmodi=0then?????sushu=1?????exitfor???endif?nextendfunction設(shè)計組合的產(chǎn)生算法是本題的難點，也是重點。假如有這樣一道題：從x1、x2、x3、x4、x5五個數(shù)中任意取不同的3個數(shù)組成一組，把所有的可能情況列舉出來。對這類問題，我們在數(shù)學課上是怎樣解決的呢？首先，取出的數(shù)與順序無關(guān)，例如{x1,x2,x3}和{x2,x1,x3}屬于同一組。這是一個組合問題。為了便于列舉，我們將每一組中的元素都按順序排放。每一組由三個元素組成，這三個元素的存放位置，我們

7、從左向右依次編號為位置1、位置2和位置3，如下圖：位置1位置2位置3接下來按照上面的約定，依次對每一個位置進行分析。首先將x1放入位置1。當把x1放入位置1之后，可以放入位置2的數(shù)還有x2、x3、x4和x5。如果再把x2放入位置2，就只剩下x3、x4和x5可以放入位置3了。同樣，如果把x1放入位置1，x3放入位置2，那么可以放入位置3的數(shù)有x4和x5；如果把x1放入位置1，x4放入位置2，那么可以放入位置3的數(shù)就只有x5了（注意我們上面的約定：每一組數(shù)中的元素都按順序排放。）……如下圖：位置1位置2位置3x

8、1x2x3x4x5x3x4x5x4x5x2x3x4x5x4x5x3x4x5在計算機里面，對這一過程我們可以使用遞歸算法來實現(xiàn)。定義一個過程zh(m,h)，從已知數(shù)組x中第m個元素開始，任意取h個元素的組合。n為數(shù)組x中元素的總數(shù)。當h=1時，只需要構(gòu)造一個for循環(huán)對整個數(shù)組進行掃描，依次取出數(shù)組中的每一個元素即可。這個時候循環(huán)變量i的終值為n。當h>1時，我們首先確定存放在位置1的數(shù)。如上例，放入位置1的數(shù)可以