1、組合數(shù)學(xué)中的程序設(shè)計(jì),第四講：黃麗韶 郵箱：ly_,引入,組合數(shù)學(xué)是一個(gè)古老而又年輕的數(shù)學(xué)分支。隨著計(jì)算機(jī)的問(wèn)世和普遍應(yīng)用，以及程序設(shè)計(jì)與算法的推進(jìn)，組合數(shù)學(xué)得到了蓬勃的發(fā)展。組合數(shù)學(xué)涉及面很廣，內(nèi)容龐雜，因此要在本講中將如此廣泛的內(nèi)容包括進(jìn)來(lái)是很難做到的。因此本講只涉及程序設(shè)計(jì)中經(jīng)常出現(xiàn)的一些內(nèi)容。要學(xué)好組合數(shù)學(xué)一定要進(jìn)行相當(dāng)?shù)挠?xùn)練。,目錄, 組合數(shù)學(xué)中有關(guān)概念與公式 排列與組合及有關(guān)的生成算法 母函數(shù) 容斥原理與錯(cuò)排 Polya定理 實(shí)例研究,組合數(shù)學(xué)中有關(guān)概念與公式,排列與組合及有關(guān)的生成算法 排列與組合的基本概念和公式 排列、相異元素可重復(fù)的排列 組合、相異元素可重復(fù)的組合,排列與組合

2、及有關(guān)的生成算法 從n個(gè)不相同的元素里，每次取出m個(gè)不可重復(fù)的元素進(jìn)行排列，其個(gè)數(shù)為Pnm，即Pnm=n(n-1)(n-m+1).從n個(gè)不相同的元素里，每次取出m個(gè)元素（可以重復(fù)）的排列，其個(gè)數(shù)為nm,這樣的排列叫做相異元素可重復(fù)的排列。 從n個(gè)不相同的元素里，每次取出m個(gè)不可重復(fù)的元素進(jìn)行組合，其個(gè)數(shù)為Cnm，即Cnm=n！/(n-m)!m!。從n個(gè)不相同的元素里，每次取出m個(gè)元素（可以重復(fù)）的排列，其個(gè)數(shù)為Cn+m-1m,這樣的排列叫做相異元素可重復(fù)的組合。,排列與組合及有關(guān)的生成算法,全排列的生成算法 全排列的生成算法有：字典序法、遞增進(jìn)位制數(shù)法、遞減進(jìn)位制數(shù)法和鄰位對(duì)換法等 全排列的字

3、典序算法 問(wèn)題：對(duì)于給定的一個(gè)全排列P，要生成P的下一個(gè)排列Q,排列與組合及有關(guān)的生成算法,字典序全排列： 給定n個(gè)元素的集合x1，x2，x3，xn，對(duì)X中的元素規(guī)定了一個(gè)先后關(guān)系。在兩個(gè)排列中，按字典序方式對(duì)它們的位從左到右每位比較，較小的字符對(duì)應(yīng)的排列較先，按這樣的序生成的全排列稱為字典序全排列。,給定排列P，求下一個(gè)排列Q,例：求X=1，2，3，4，5，6，7上排列P= 2637541的下一個(gè)排列Q 從右到左找出比右邊數(shù)字小的第一個(gè)數(shù)，即3。 再?gòu)挠业阶罂疾毂?大的第一個(gè)數(shù)，是4 將3與4對(duì)換位置，得2647531 將得到的排列2647531從4后面的7531翻轉(zhuǎn)得1357 把前綴264

4、接在1357的前面得2641357，它就是所求的排列2647531的下一個(gè)排列。,給定排列P，求下一個(gè)排列Q算法,設(shè)X=1，2，n，求P=a1a2an的下一個(gè)排列： 在P中從右到左尋找右邊比左邊大的數(shù)的第一個(gè)位置j，即j=maxi|aiaj。此時(shí)排列P形如a1a2aj-1aj aj+1ak-1 akak+1an。 對(duì)換aj，ak，并將aj+1ak-1ajak+1an翻轉(zhuǎn)，得Q= a1a2aj-1akanak-1ajak+1an即為P的下一個(gè)排列。,排列與組合及有關(guān)的生成算法,3.組合的生成算法 令j= maxi| ain-m+i+1。那么a1a2am的下一個(gè)組合為a1a2aj-1(aj+1)(

5、aj+2)(aj+m-j)。 例如，給定n=13，m= 6，組合4 5 7 8 12 13，于是可見(jiàn)j=3。將8 12 13依次修改為9 10 11。那么組合4 5 7 8 12 13的下一個(gè)組合為4 5 7 9 10 11。,排列與組合及有關(guān)的生成算法,4.字典序全排列與序號(hào)的轉(zhuǎn)換 字典序全排列的序號(hào) 記P=a1a2an。記ki為元素ai的逆序數(shù)，則排列P的序號(hào)為,問(wèn)題：給定排列的序號(hào)，如何求全排列？,排列1 2 3 4 5 8 6 9 7的逆序數(shù)分別為0 0 0 0 0 2 0 1 0，序號(hào)為 345,給定排列的序號(hào),/給定元素個(gè)數(shù)n，及全排列p /返回字典序全排列下排列序號(hào)num int

6、 perm2num(int n, int *p) int i, j, num=0,k=1; for (i=n-2;i=0;k*=n-(i-)/因子為(n-i-1)!，注意下標(biāo)從0開(kāi)始 for (j=i+1;jn;j+) if (pjpi) num+=k;/是否有逆序，如有，統(tǒng)計(jì) return num; ,給定排列的序號(hào)求排列,/給定元素個(gè)數(shù)n，排列序號(hào)num /返回對(duì)應(yīng)的排列p void num2perm(int n, int *p,int num) int i,j; /求逆序數(shù)數(shù)組 for(i=n-1;i=0;i-)pi=num%(n-i),num/=n-i; for (i=n-1;i;i-

7、) for (j=i-1;j=0;j-) if (pj=pi) pi+;/根據(jù)逆序數(shù)數(shù)組進(jìn)行調(diào)整 ,排列與組合及有關(guān)的生成算法,5字典序組合與序號(hào)的轉(zhuǎn)換 實(shí)例：設(shè)n=9，m=4。將從n個(gè)元素取m個(gè)的所有組合從1開(kāi)始從小到大編序，組合3 5 7 9的序號(hào)是多少？ 一種計(jì)算方法：首位小于3的組合的個(gè)數(shù)為91；首位是3，第2位小于5的組合的個(gè)數(shù)為10；前2位是3 5，第3位小于7的組合的個(gè)數(shù)為3；前3位是3 5 7，第4位小于9的組合的個(gè)數(shù)為1。所有這些數(shù)之和105，加上它本身的1個(gè)號(hào)，得組合3 5 7 9的序號(hào)是106。,另一種思路由組合求序號(hào),考慮從當(dāng)前考察的組合的后面有多少個(gè)組合。 /傳入n、

8、m及組合c，返回c的序號(hào)num /下面的comb(n,m)是n個(gè)元素取m個(gè)的組合數(shù) int comb2num(int n,int m,int *c) int num=comb(n,m),i; for (i=0;im;i+) num = num- comb(n-ci,m-i); return num; ,由序號(hào)求組合,由序號(hào)求組合算法是前面由組合求序號(hào)的逆過(guò)程 /輸入n、m，序號(hào)num，傳回所求的組合c void num2combA(int n,int m,int *c,int num) int i,j=1,k; for (i=0;icomb(n-j,m-i-1) num-=comb(n-j,m

9、-i-1),j+; ci=j; ,母函數(shù),母函數(shù)：給定序列a0、a1、 a2、 an、那么函數(shù)G(x)= a0+a1x+a2x2+akxk+ 稱為序列a0、a1、 a2、 an、的母函數(shù)（也叫生成函數(shù)）。 給定一個(gè)序列，可確定對(duì)應(yīng)的母函數(shù)；反過(guò)來(lái)，給定一個(gè)母函數(shù)，那么也能確定對(duì)應(yīng)的序列。 例：斐波那契數(shù)列an，n=0，1，2， a0=a1= 1，an = an-1 +an-2 。對(duì)應(yīng)的母函數(shù)可表示為,可求得,舉例,問(wèn)題描述 小明手中有3張一元,2張2元和3張5元的錢幣,問(wèn)小明都能買價(jià)值為多少的物品？對(duì)每種價(jià)值的物品他有幾種付款方法？如小明手中有k張一元，m張2元和n張5元的錢幣，結(jié)果又如何？

10、輸入 輸入的第一行是一個(gè)整數(shù)T，（1T10）,表示測(cè)試數(shù)據(jù)的個(gè)數(shù)。接下來(lái)有T行，每行上有3個(gè)非負(fù)整數(shù)k，m，n，（1k，m，n10），分別表示一元、二元和五元的錢幣數(shù)。k，m，n中至少有一個(gè)非0。 輸出 對(duì)輸入中的三種錢幣數(shù)，輸出小明能買物品的價(jià)值總數(shù)以及所有的付款方法數(shù)。,輸入與輸出樣例,輸入樣例 1 3 2 3 輸出樣例 22 47,對(duì)實(shí)例的說(shuō)明,k=3，m=2，n=3 一元、二元、五元錢幣對(duì)應(yīng)的能買物品的生成函數(shù),小明能買的物品對(duì)應(yīng)的生成函數(shù)為,結(jié)論,小明可以買價(jià)值分別為0，1，2，21，22元的物品，即22種非零的錢數(shù)，并且付款的方法數(shù)分別為0，1，2，2，2，3，2，3，2，2，3，

11、2，3，2，2，3，2，3，2，2，2，1，1，總數(shù)為47。,容斥原理與錯(cuò)排,容斥原理 設(shè)A為任一個(gè)有限集合。用|A|記集合A中元素的個(gè)數(shù)。當(dāng)A為空集時(shí)，|A|=0。 定理6.1 設(shè)A，B為兩個(gè)有限集合，那么,定理6.2 設(shè)A1，A2，An是n個(gè)有限集合，則,錯(cuò)排,當(dāng)n1 時(shí)，若n個(gè)元素1，2，n的排列P其每個(gè)元素都不在原來(lái)的位置上（即元素k不在位置k上），則該排列稱為錯(cuò)排。 n個(gè)元素的集合1，2，n的錯(cuò)排個(gè)數(shù)為Dn。 有遞推關(guān)系,很容易得到關(guān)于Dn 的關(guān)系式 Dn =,抽屜原理,將m個(gè)物品放入n個(gè)抽屜，則其中至少有一個(gè)抽屜里含有 個(gè)物品 設(shè)m1、m2，m1， mn都是正整數(shù)，且將n個(gè)物品放入

12、n個(gè)抽屜，則：第一個(gè)抽屜至少有m1個(gè)物品，第二個(gè)抽屜至少有m2個(gè)物品，第n個(gè)抽屜至少有mn個(gè)物品，至少其中之一必定成立。,Plya定理,群: 定義 設(shè)G是一個(gè)集合，*是G上的二元運(yùn)算，如果(G，*)滿足如下條件： 封閉性：對(duì)于任何a，bG，有a*bG； 結(jié)合律：對(duì)任何a，b，cG，(a*b)*c = a*(b*c)； 單位元：存在eG，使得對(duì)aG ，有a*e=e*a=a； 逆元：對(duì)于每個(gè)元素aG，存在xG，使得a*x = x*a = e。 那么稱（G，*）為一個(gè)群。,群的例子,例1：設(shè)G=1,-1，*為普通乘法，那么（G，*）為一個(gè)群，1是單位元。 例2：設(shè)G=0，1，2，3，m-1，*為普通

13、的模m加法，那么（G，*）為一個(gè)群，0是單位元。 例3：設(shè)m=10，記G=1，3，7，9，那么G關(guān)于模10的乘法構(gòu)成一個(gè)群。,子群、交換群,子群：設(shè)（G，*）是任何一個(gè)群，又設(shè)H是G的子集，若（H，*）是一個(gè)群，則稱（H，*）是（G，*）的一個(gè)群，簡(jiǎn)稱H是G的子群。 交換群：設(shè)（G，*）是一個(gè)群，如果對(duì)于G的任何元素a，b，有ab=ba，那么稱G為交換群。 置換：設(shè)X是一個(gè)有限集，是X到X的一個(gè)一一變換，那么稱是X上的一個(gè)置換。 有限群的階：G的元素個(gè)數(shù)稱為G的階，記為|G|,置換,設(shè)X是一個(gè)有限集，是X到X的一個(gè)一一變換，那么稱是X上的一個(gè)置換 ：1a1，2a2，nan， 置換的一種記號(hào),注

14、意：上述記號(hào)下，同一置換用這樣的表示有n!種，但關(guān)鍵的對(duì)應(yīng)關(guān)系不變，只有一種。,正三角形ABC的變換,正三角形ABC的旋轉(zhuǎn)變換和軸對(duì)稱變換,正三角形的所有變換,沿中心逆時(shí)針旋轉(zhuǎn)，有0，120，240三種 旋轉(zhuǎn)0，0：AA，BB，CC 旋轉(zhuǎn)120，1：AC，BA，CB 旋轉(zhuǎn)240，2：AB，BC，CA 沿對(duì)稱軸翻轉(zhuǎn)180，也有三種： 沿AO軸翻轉(zhuǎn)，3：AA，BC，CB 沿BO軸翻轉(zhuǎn)，4：AC，BB，CA 沿CO軸翻轉(zhuǎn)，5：AB，BA，CC,正三角形的所有變換,沿中心逆時(shí)針旋轉(zhuǎn) 旋轉(zhuǎn)0 旋轉(zhuǎn)120 旋轉(zhuǎn)240,沿對(duì)稱軸翻轉(zhuǎn)180 沿AO軸翻轉(zhuǎn)，沿BO軸翻轉(zhuǎn) 沿CO軸翻轉(zhuǎn),置換的乘法運(yùn)算,置換的乘法

15、運(yùn)算是置換的連接 X的所有n!個(gè)置換關(guān)于置換的乘法構(gòu)成一個(gè)群G，記為Sn，其單位元是,舉例：設(shè)3= ，2=,=,3與2的積為置換5。,循環(huán),循環(huán)是這樣一個(gè)置換，滿足：a1a2，a2a3，aka1，但對(duì)其它的元素保持不變，稱為k階循環(huán)。 k階循環(huán)可記為：,k稱為循環(huán)節(jié)長(zhǎng)度 2階循環(huán) 也稱為對(duì)換，簡(jiǎn)記為（a1a2）,置換與循環(huán),定理 每個(gè)置換都可以寫成若干互不相交的循環(huán)的乘積，且表示是唯一的。,例：置換 可表示為(124)(35)(6)， 其循環(huán)節(jié)數(shù)是3,2Burnside引理,定義 等價(jià)：設(shè)G是有限集X上的置換群，點(diǎn)a，bX稱為“等價(jià)”的，當(dāng)且僅當(dāng)，存在置換G使得(a)=b，記為ab。 軌道：在

16、這種等價(jià)關(guān)系下，X的元素形成的等價(jià)類稱為G的軌道。aX所在的等價(jià)類Ea，即為a所在的軌道。 G的任意兩個(gè)不同的軌道之交是空集。 等價(jià)類：集合X上的所有等價(jià)類構(gòu)成X的一個(gè)劃分，等價(jià)類的個(gè)數(shù)記為L(zhǎng)。,a不動(dòng)置換類,Za：設(shè)G是X=1，2，n上的置換群。若aX，G中使a保持不變的置換的全體|有G，使(a)=a，記為Za，叫做G中使a保持不動(dòng)的置換類，簡(jiǎn)稱a不動(dòng)置換類。 性質(zhì)：對(duì)所有aX，|Ea|Za|=|G|成立。 證明 略 C()：對(duì)于一個(gè)置換G，及aX，若(a)=a，則稱a為的不動(dòng)點(diǎn)。的不動(dòng)點(diǎn)的全體記為C()。,Burnside引理,證明：略,L：等價(jià)類的個(gè)數(shù) | C() |：的不動(dòng)點(diǎn)的全體的個(gè)

17、數(shù) |Za|：G中使a保持不動(dòng)的置換類個(gè)數(shù) |G|：置換群G的元素個(gè)數(shù),Plya定理,定理 設(shè)G=1，2，t是X=a1,a2,an上一個(gè)置換群，用m種顏色對(duì)X中的元素進(jìn)行涂色，那么不同的涂色方案數(shù)為 其中Cyc(k)是置換k的循環(huán)節(jié)的個(gè)數(shù)。,證明：略,循環(huán)節(jié)個(gè)數(shù)計(jì)算,/輸入：一個(gè)置換perm，即一個(gè)排列 /返回：置換的最小周期，傳回待求置換的循環(huán)節(jié)個(gè)數(shù)num int polya(int* perm,int n,int ,實(shí)例研究,蛋糕 楊輝三角形中的奇偶問(wèn)題 足球賽票 棋盤格數(shù) 保險(xiǎn)柜上鎖 彈球游戲 最少砝碼 環(huán) 珍珠項(xiàng)鏈 統(tǒng)計(jì)棋局?jǐn)?shù),蛋糕,問(wèn)題描述 瓦爾特夫人本周六邀請(qǐng)她的朋友吃晚飯。到那個(gè)

18、時(shí)候，她想準(zhǔn)備一個(gè)大的蛋糕。晚飯后，她要把蛋糕切成幾塊給他們中的每一人。瓦爾特夫人認(rèn)為如果蛋糕塊大小不一樣，那么得到小塊的客人會(huì)不高興。因此，她將把蛋糕分成如下圖所示的形狀，即把蛋糕在中間切割。,為使蛋糕更可口，她要用各種不同顏色的果醬涂在上面。要知道，相鄰兩塊是不能有相同顏色的。如果這樣的話，她會(huì)認(rèn)為這兩塊當(dāng)作一塊看待。,她發(fā)現(xiàn)，將2種果醬放在3塊蛋糕上是不可能做到的。但如果將3種果醬放在3塊蛋糕上，她發(fā)現(xiàn)有6種方法。而如果將4種果醬放在3塊蛋糕上，她發(fā)現(xiàn)有24種方法?，F(xiàn)在，瓦爾特夫人對(duì)果醬涂在蛋糕上的方法數(shù)感興趣。她需要你的幫助，請(qǐng)你為她編寫一個(gè)程序進(jìn)行計(jì)算。也許方法數(shù)太多，因此瓦爾特夫人

19、只要你告訴她方法數(shù)的最后一位數(shù)。 注意：因客人不同，下圖所示的2種方法是不同的。因此你不應(yīng)混為一談。,輸入 輸入有多組測(cè)試數(shù)據(jù)。每一組測(cè)試數(shù)據(jù)由兩個(gè)整數(shù)m，n組成，其中整數(shù)m是果醬顏色數(shù)，整數(shù)n是客人數(shù)，也是蛋糕塊數(shù)，(0m100，1n10 000)。 當(dāng)輸入m=n=0時(shí)表示輸入結(jié)束，這種情況你不必處理。 輸出 對(duì)每種情況，如輸入描述中所說(shuō)，輸出將果醬放在蛋糕上的方法數(shù)的個(gè)位數(shù)。,輸入與輸出樣例,分析與討論,令an表示這n塊蛋糕用m種果醬的的擺設(shè)方案數(shù)。大蛋糕切成n塊后的形狀如圖所示，各塊分別標(biāo)記為C1，C2，Cn。 分兩種情況： （1）C1和Cn-1有相同的顏色 （2）C1和Cn-1有不同的

20、顏色,分析,第一種情況： C1，Cn-1顏色相同，Cn，C1，C2，Cn-2有m-1種顏色可用，；而且C1，C2，Cn-2的著色方案與大蛋糕切成n-2塊小蛋糕的著色方案一一對(duì)應(yīng)。此時(shí)小蛋糕Cn可用m-1種顏色。這種情況，n塊蛋糕的顏色涂法數(shù)為(m-1)an-2。 第二種情況： C1與Cn-1顏色不同，Cn的顏色可用m-2種。此時(shí)C1，C2，Cn-1的著色方案與大蛋糕切成n-1塊小蛋糕的著色方案一一對(duì)應(yīng)。這種情況，n塊蛋糕的顏色涂法數(shù)為(m-2)an-1。,結(jié)論：,參考程序,#include using namespace std; int comput(int n,int m) int i,

21、ret,k=m- 1; for (ret=1,i=0;imn) ,楊輝三角形中的奇偶問(wèn)題,問(wèn)題描述 在如下所示的楊輝三角形中，第1行有1個(gè)奇數(shù)，第2行有2個(gè)奇數(shù)，第3，4，5，6行分別有2，4，2，4個(gè)奇數(shù)。 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 你的任務(wù)：對(duì)一般的正整數(shù)n，計(jì)算楊輝三角形中第n行上奇數(shù)的個(gè)數(shù)。,輸入與輸出,輸入 輸入有若干行。每一行上有一個(gè)正整數(shù)n，（1n232）。 輸入直到文件結(jié)束。 輸出 對(duì)輸入文件每行上的正整數(shù)n，輸出楊輝三角形中第n行上奇數(shù)的個(gè)數(shù)。,分析,在楊輝三角形中，將每行上的奇數(shù)

22、用1表示、偶數(shù)用0表示，可得如下的簡(jiǎn)化的楊輝三角形，其中空白位置對(duì)應(yīng)的行上是數(shù)0 。 構(gòu)造下頁(yè)所示的簡(jiǎn)化楊輝三角形圖,圖例,有趣的規(guī)律,34行上的2個(gè)三角形與12行上的三角形完全一樣； 58行上稍大的2個(gè)三角形（底邊4個(gè)1）與14行上的三角形完全一樣； 916行上再稍大的2個(gè)三角形（底邊8個(gè)1）與18行上的三角形完全一樣； ,第16行上1的個(gè)數(shù)是第8行上1的個(gè)數(shù)的2倍； 第15行上1的個(gè)數(shù)是第7行上1的個(gè)數(shù)的2倍； 第8行上1的個(gè)數(shù)是第4行上1的個(gè)數(shù)的2倍； 第7行上1的個(gè)數(shù)是第3行上1的個(gè)數(shù)的2倍； ,計(jì)算公式,給定行數(shù)n，記m=n-1的二進(jìn)制表示為， 用g(m)表示第m+1行上奇數(shù)的個(gè)數(shù)，

23、則 g(m)=2 g( ),另一種分析方法,楊輝三角第n行中奇數(shù)的項(xiàng)數(shù)是二項(xiàng)式 的展開(kāi)式中系數(shù)為奇數(shù)的項(xiàng)數(shù)。,（1） (x+1)n-1中系數(shù)為奇數(shù)的項(xiàng)數(shù)= (x+1)n-1(mod 2) 中系數(shù)非0的項(xiàng)數(shù)； （2）(x+1)2 (mod 2) = (x2 +1) (mod 2) （3）(x+1)4 (mod 2) = (x4 +1) (mod 2) （4）(x+1)8 (mod 2) = (x8 +1) (mod 2) ，等等 將n-1寫為二進(jìn)制數(shù)akak-1a1a0，那么,分析,對(duì)等式兩邊作mod 2運(yùn)算，丟掉那些使ai=0的項(xiàng) (mod 2)。 于是， (x+1)n-1中系數(shù)為奇數(shù)的項(xiàng)數(shù)就

24、是所有使ai=1的項(xiàng) (mod 2)的乘積展開(kāi)式中系數(shù)為奇數(shù)的項(xiàng)數(shù)。,結(jié)論：楊輝三角形中第n行上奇數(shù)的個(gè)數(shù)為,足球賽票,問(wèn)題描述 一場(chǎng)激烈的足球賽開(kāi)始前，售票工作正在緊張地進(jìn)行中。每張球票為50元。現(xiàn)有2n個(gè)人排隊(duì)等待購(gòu)票，其中有n 個(gè)人手持50元的鈔票，另外n個(gè)人手持100元的鈔票，假設(shè)開(kāi)始售票時(shí)售票處沒(méi)有零錢。問(wèn)這2n個(gè)人有多少種排隊(duì)方式，使售票處不至出現(xiàn)找不開(kāi)錢的局面？ 輸入 輸入的每行上有一個(gè)非負(fù)整數(shù)n，（1n1000）。 輸出 對(duì)輸入每行上的整數(shù)n，輸出這2n個(gè)人的排隊(duì)方式數(shù)。,輸入與輸出樣例,分析,令f(m,n)表示有m個(gè)人手持50元的鈔票，n個(gè)人手持100元的鈔票時(shí)共有的方案總數(shù)

25、。 n=0，f(m,0 )=1 mn， f(m,n)=0 其它，考慮（m+n）個(gè)人排隊(duì)購(gòu)票 第（m+n）個(gè)人手持100元的鈔票 ：有f(m,n-1) 種 第（m+n）個(gè)人手持50元的鈔票 ：有f(m-1,n)種 由加法原理得f(m,n)=f(m-1,n)+f(m,n-1),綜合，得：,棋盤格數(shù),問(wèn)題描述 設(shè)有一個(gè)方格棋盤，求出該棋盤中包含有多少個(gè)正方形、多少個(gè)長(zhǎng)方形（不包括正方形）。 輸入 有若干個(gè)棋盤，每個(gè)棋盤對(duì)應(yīng)一行上兩個(gè)整數(shù)n，m，（ln100，1m100），表示有一個(gè)nm方格的棋盤。 輸出 對(duì)輸入的nm方格棋盤，輸出正方形的個(gè)數(shù)與長(zhǎng)方形的個(gè)數(shù)。,輸入與輸出樣例,分析,先考慮正方形的個(gè)數(shù)

26、 邊長(zhǎng)為k的正方形個(gè)數(shù)為(n-k+1) (m-k+1)。 再考慮長(zhǎng)方形（包括正方形）的個(gè)數(shù) 根據(jù)乘法原理，長(zhǎng)方形和正方形的個(gè)數(shù)總計(jì) Total=(1+2+n)( 1+2+m) 長(zhǎng)寬不等的長(zhǎng)方形個(gè)數(shù)為Rec_total= Total- Sq_total 因此，長(zhǎng)寬不等的長(zhǎng)方形個(gè)數(shù)為 Rec_total = Total Sq_total,保險(xiǎn)柜上鎖,問(wèn)題描述 有n個(gè)人組成的委員會(huì)負(fù)責(zé)保管一個(gè)保險(xiǎn)箱。該委員會(huì)經(jīng)過(guò)研究形成決議：委員會(huì)中任何m個(gè)委員同時(shí)到場(chǎng)就能打開(kāi)保險(xiǎn)柜，而任何m-1個(gè)委員則不能打開(kāi)保險(xiǎn)柜。你的任務(wù)是計(jì)算至少要給這個(gè)保險(xiǎn)柜加多少把鎖才能滿足上述要求。 輸入 輸入文件中有若干行。每一行上

27、有兩個(gè)正整數(shù)n和m是一組測(cè)試數(shù)據(jù)，（1n50，0mn）。輸入直到文件結(jié)束。 輸出 對(duì)輸入文件中的每組測(cè)試數(shù)據(jù)n，m，輸出滿足要求的鎖的最少數(shù)目。,輸入與輸出樣例,（2）如果取k= ，即加 把鎖，那么可以按問(wèn)題要求向委員們分配鑰匙。,現(xiàn)從這兩方面考慮： （1）首先確定k ：作一個(gè)表格可以說(shuō)明之,分析,設(shè)k為符合要求的最少的鎖的把數(shù)。記Ai是第i個(gè)委員可以打開(kāi)的鎖的集合，A=1，2，3，k是所有鎖的集合。 問(wèn)題的要求： A1，A2，An中任何m個(gè)的并是集合A，而任何m-1個(gè)集合的并不是集合A。,向委員們分配鑰匙的一種方案,任意取出m-1列（即取m-1個(gè)委員），記為（j1，j2，jm-1）。m-1列

28、（j1，j2，jm-1）對(duì)應(yīng)于一個(gè)行row，該行上與m-1個(gè)列j1，j2，jm-1交叉處的格子中都是0，而其他格子都是1。 將編號(hào)為row的鑰匙分配給編號(hào)不是j1，j2，jm-1 的所有其他委員，即可滿足要求。 計(jì)算的問(wèn)題，這是容易的。,彈球游戲,問(wèn)題描述 有一個(gè)三角形容器，上部開(kāi)一個(gè)小口，里面如圖中所示按層整齊地放了許多小圓棍作為阻擋物，第n層有n根阻擋物。 彈球游戲時(shí)，小球從容器上部的口子中間處跌落，碰到第一層擋物后等概率地向兩側(cè)跌落，碰到與之相鄰的第二層兩個(gè)阻擋物中的一個(gè)，再向兩側(cè)跌落第三層阻擋物，如此一直下跌最終小球落入底層。 在容器底層放了若干獎(jiǎng)品。如下頁(yè)圖所示的6層容器中，A，G區(qū)

29、獎(jiǎng)品最好，B，F(xiàn)區(qū)獎(jiǎng)品次之，C，E區(qū)獎(jiǎng)品第三，D區(qū)獎(jiǎng)品最差。為方便起見(jiàn)，約定A，B，C，D，E，F(xiàn)，G區(qū)分別用0，1，2，3，4，5，6區(qū)表示。,彈球游戲示意圖,一般地，如容器有n層，相應(yīng)地得到不同大小的容器，其底層根據(jù)位置不同也放了相應(yīng)的獎(jiǎng)品。該區(qū)域獎(jiǎng)品的價(jià)值與小球落入該區(qū)域的概率反向相關(guān)，即：區(qū)域的概率越大，該區(qū)域獎(jiǎng)品的價(jià)值越小。 你的任務(wù)：計(jì)算彈球落入某個(gè)區(qū)域的概率。 輸入 輸入文件中有若干行。每一行上有兩個(gè)整數(shù)n，m，（1n65535，0mn）。 輸入直到文件結(jié)束。 輸出 對(duì)輸入中每行上的正整數(shù)n，m，輸出彈球落入有n層的三角形容器底層中第m個(gè)區(qū)的概率（四舍五入后保留6位小數(shù)）。,輸入

30、與輸出樣例,分析,如果m=0或m=n，那么小球落入m區(qū)的概率等于它肩上一個(gè)區(qū)域概率的1/2。 如果0mn，那么小球落入m區(qū)的情況有兩種：經(jīng)左邊的球彈落與經(jīng)右邊的球彈落 小球落入m區(qū)的概率等于它肩上兩區(qū)域概率之和的1/2,舉例：6層彈球落入?yún)^(qū)域概率,分析,小球落入m區(qū)的概率，其分子與楊輝三角形完全一致。由此可以利用楊輝三角的性質(zhì)直接得出小球落到m區(qū)的概率。 一般地，彈球落入n層的三角形容器底層中第m個(gè)區(qū)的概率為 。,程序?qū)崿F(xiàn)很簡(jiǎn)單，但n可能很大，因此在必要時(shí)借助于高精度計(jì)算。,最少砝碼,問(wèn)題描述 天平的兩個(gè)托盤上都可以放置砝碼，現(xiàn)要稱出重量為1，2，3，n的物體。你的任務(wù)是確定所需的最少的砝碼個(gè)

31、數(shù)。 輸入 輸入文件中有若干行。每一行上有一個(gè)正整數(shù)n，它是一個(gè)測(cè)試數(shù)據(jù)，（1n65535）。 輸入直到文件結(jié)束。 輸出 對(duì)輸入中的每個(gè)測(cè)試數(shù)據(jù)n，輸出所需的最少的砝碼個(gè)數(shù)。,輸入與輸出樣例,分析,設(shè)所需的砝碼有s個(gè)：a1，a2，an 重量為k的物體可稱出，等價(jià)于說(shuō)k可表示為如下形式 （*）,每個(gè)i 有三種選擇，故（*）中共有3s 個(gè)數(shù)，除0以外，其他的數(shù)正、負(fù)成對(duì)出現(xiàn)。因此共有（3s-1）/2 個(gè)整數(shù)，所以s個(gè)砝碼至多稱出（3s-1）/2 種重量，即在n(3s-1)/2時(shí)，s-1個(gè)砝碼不夠。,其中，i =0，1或-1，（i=1，2，3，s）。系數(shù) i =-1表示砝碼與物體放在同一托盤，系數(shù)

32、i =1表示砝碼與物體放在不同托盤。,分析,可證，當(dāng)a2=3s-1時(shí)，(i=1，2，3，s)，滿足 的任何整數(shù)k都可表示為（*）的形式。 事實(shí)上，記M= ，那么,顯然，指數(shù)在-M與M之間的項(xiàng)都出現(xiàn)了。 這表明，當(dāng)n 滿足 時(shí)，所需的砝碼為s個(gè)，可以稱出重量n，且表示方式唯一。,環(huán),他在一個(gè)環(huán)上寫了n個(gè)字母“X”和“E”。他注意到一些不同的字母序列用循環(huán)移動(dòng)可以變到另一個(gè)（這表示這實(shí)際上是同一個(gè)環(huán)形串）。例如，串“XXE”-“XEX”-“EXX”實(shí)際上都是相同的。他想知道對(duì)于n個(gè)字母有多少種不同的環(huán)形串出現(xiàn)。請(qǐng)您幫助他找出答案。,輸入 每行有一個(gè)整數(shù)n，（1n200 000）。 輸出 輸出長(zhǎng)度為

33、n的環(huán)形串的個(gè)數(shù),分析,環(huán)只能順時(shí)針或逆時(shí)針旋轉(zhuǎn) 順時(shí)針?lè)较蛞苿?dòng)k個(gè)位置等同于逆時(shí)針?lè)较蜣D(zhuǎn)動(dòng)n-k個(gè)位置 一共有n個(gè)置換，記G=0，1，2，n-1 逆時(shí)針旋轉(zhuǎn)k個(gè)位置，那么k=,循環(huán)節(jié)個(gè)數(shù)求法,以n=8，k=6時(shí)的置換6= 為例考查循環(huán)節(jié)個(gè)數(shù)。,易見(jiàn)，6=(0642)(1753)有2個(gè)循環(huán)節(jié)。,一般情況下，可以證明k的循環(huán)節(jié)個(gè)數(shù)是GCD(n,k)，因此沒(méi)有必要構(gòu)建置換（或進(jìn)行分解）。,長(zhǎng)度為n的環(huán)形串的個(gè)數(shù),根據(jù)Plya定理，長(zhǎng)度為n的環(huán)形串的個(gè)數(shù)L=,L的數(shù)目很大，實(shí)際編程時(shí)需要自己編寫計(jì)算冪函數(shù)pow(m,x)的程序，可能需要用到高精度計(jì)算,珍珠項(xiàng)鏈,問(wèn)題描述 n顆紅、藍(lán)、綠三種顏色的珍珠

34、串起來(lái)形成一個(gè)環(huán)形項(xiàng)鏈，（n 24）。如果將沿著中心旋轉(zhuǎn)或者沿對(duì)稱軸翻轉(zhuǎn)得到的形式認(rèn)為是相同的，那么有多少種不同的項(xiàng)鏈形式？ 輸入 輸入有多行，每行一個(gè)整數(shù)n。最后一行上的-1表示輸入結(jié)束。 輸出 對(duì)應(yīng)于輸入中的數(shù)據(jù)n，輸出項(xiàng)鏈有多少種不同的形式。,示例：三色圓環(huán),輸入與輸出樣例,分析,以項(xiàng)鏈中心順時(shí)針或逆時(shí)針旋轉(zhuǎn)，位置0變到位置i的旋轉(zhuǎn)可表示為： i：0i，1i+1，2i+2，3i+3，j(i+j)%n， ，n-1 (i+(n-1)%n 以項(xiàng)鏈中心線翻轉(zhuǎn)： （1）n為奇數(shù)。此時(shí)只有一種形式，即經(jīng)過(guò)某個(gè)頂點(diǎn)i與中心的連線為軸的翻轉(zhuǎn)i，共n個(gè)； （2）n為偶數(shù)。經(jīng)過(guò)某個(gè)頂點(diǎn)與中心的連線為軸的翻轉(zhuǎn)

35、，有n/2個(gè)；以頂點(diǎn)i與i+1的中點(diǎn)與中心的連線為軸的翻轉(zhuǎn)，共n/2個(gè)；,分析,對(duì)任何輸入的n，恰有2n種不同的置換。 對(duì)于各置換的循環(huán)節(jié)計(jì)算，本題的旋轉(zhuǎn)形式的置換i，可直接根據(jù)置換的形式算出，循環(huán)節(jié)長(zhǎng)度為GCD(i,n)； 在無(wú)法用公式求循環(huán)節(jié)長(zhǎng)度時(shí)，根據(jù)求循環(huán)節(jié)長(zhǎng)度的程序?qū)崿F(xiàn)。 以下程序中，給出一個(gè)示例，構(gòu)造所有置換，并用程序計(jì)算置換的循環(huán)節(jié)長(zhǎng)度。,求置換perm的循環(huán)節(jié)數(shù)repetend,int cycle(int* perm,int n,int ,構(gòu)造所有置換,double polya(int c,int n)/旋轉(zhuǎn)和翻轉(zhuǎn)下視為相同 int i,j,x;double t=0.0,m=c

36、;/c為顏色數(shù) for (i=0;ii for (j=0;j=n-1;j+) permj=(i+j)%n; cycle(perm, n, x); t=t+pow(m,x); if(n%2=1) /構(gòu)造第i個(gè)翻轉(zhuǎn) for (i=0;i=n-1;i+)/i保持不動(dòng) for (j=0;j=n-1;j+) perm(i+j)%n=(i-j+n)%n; cycle(perm, n, x); t=t+pow(m,x); ,if(n%2=0) for (i=0;i(n/2);i+)/構(gòu)造第i個(gè)翻轉(zhuǎn) for (j=0;j=n-1;j+)/i保持不動(dòng)，共n/2個(gè) perm(i+j)%n=(i-j+n)%n; c

37、ycle(perm, n, x); t=t+pow(m,x); for (j=0;j=n-1;j+) /ii+1，i-1i+2，共n/2個(gè) perm(i-j+n)%n=(i+j+1)%n; cycle(perm, n, x); t=t+pow(m,x); return t/(2*n); ,統(tǒng)計(jì)棋局?jǐn)?shù),問(wèn)題描述 一個(gè)有NN個(gè)格子的正方形棋盤，每個(gè)格子可以用C種不同顏色來(lái)染色，一共可以得到多少種不同的棋盤。如果一個(gè)棋盤，經(jīng)過(guò)任意旋轉(zhuǎn)、反射后變成另一個(gè)棋盤，這兩個(gè)棋盤就是屬于同一種棋盤。 比如當(dāng)N=C=2的時(shí)候，有如下圖所示6種不同的棋盤。 現(xiàn)在告訴你N和C，請(qǐng)你算算到底有多少種不同的棋盤？,輸入

38、有多組測(cè)試數(shù)據(jù)。每組測(cè)試數(shù)據(jù)包含兩個(gè)正整數(shù)N和C（0N，C31），分別表示棋盤的大小是NN，用C種顏色來(lái)進(jìn)行染色。 輸出 對(duì)于每組測(cè)試數(shù)據(jù)，在一行里輸出答案。,分析,是典型的計(jì)數(shù)問(wèn)題，可應(yīng)用Plya定理解決。 本題的關(guān)鍵是置換的類型與置換的個(gè)數(shù)，以及如何求各置換的循環(huán)節(jié)個(gè)數(shù)。置換有2類型：旋轉(zhuǎn)和反射。 從具體例子入手： 如下圖所示，分別以n=4和n=5兩種情形為例進(jìn)行分析。,旋轉(zhuǎn)類置換,各種（順時(shí)針或逆時(shí)針）旋轉(zhuǎn)總可歸結(jié)為四種逆時(shí)針旋轉(zhuǎn)：0，90，180，270，分別記為0，1，2，3。 旋轉(zhuǎn)90是一種基本的旋轉(zhuǎn)。 n為偶數(shù)時(shí)（以n=4為例），1有形式：,1可表示為,n為奇數(shù)時(shí)（以n=5為例）

39、，1有形式：,1可表示為,對(duì)置換的進(jìn)一步分析,置換1中對(duì)應(yīng)位置的4個(gè)元素構(gòu)成小置換，旋轉(zhuǎn)了90； 在n為奇數(shù)時(shí)，中心元素1保持不動(dòng)。 旋轉(zhuǎn)180的置換2，對(duì)應(yīng)位置的4個(gè)元素構(gòu)成小置換，且旋轉(zhuǎn)了180 旋轉(zhuǎn)270的置換3，對(duì)應(yīng)位置的4個(gè)元素也構(gòu)成小置換，也旋轉(zhuǎn)了270。 因此，實(shí)際上只要考察4個(gè)元素的幾個(gè)置換，它們分別對(duì)應(yīng)于0、90、180、270旋轉(zhuǎn)。,對(duì)小置換的分析,0： 循環(huán)節(jié)數(shù)為4 90： 循環(huán)節(jié)數(shù)為1 180： 循環(huán)節(jié)數(shù)為2 270： 循環(huán)節(jié)數(shù)為1,大置換的循環(huán)節(jié)個(gè)數(shù),根據(jù)置換的分解形式以及進(jìn)行 當(dāng)n為偶數(shù)時(shí)，每個(gè)置換的長(zhǎng)度為n2: 0的循環(huán)節(jié)個(gè)數(shù)為R0= n2； 1與3的循環(huán)節(jié)個(gè)數(shù)均為R1= n2/4； 2的循環(huán)節(jié)個(gè)數(shù)為= n2/2。 當(dāng)n為奇數(shù)時(shí)，每個(gè)置換的長(zhǎng)度仍為n2，中心元素保持不動(dòng)： 0的循環(huán)節(jié)個(gè)數(shù)為R0= n2； 1與3的循環(huán)節(jié)個(gè)數(shù)均為R1= ； 2的循環(huán)節(jié)個(gè)數(shù)為= 。,反射類置換,反射有兩種： （1）沿對(duì)角線反射 （2）沿對(duì)邊中點(diǎn)連線反射。 第1種情況：沿對(duì)