第四章組合數(shù)學中的程序設計.ppt

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

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

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

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

5、aj+2)(aj+m-j)。 例如，給定n=13，m= 6，組合4 5 7 8 12 13，于是可見j=3。將8 12 13依次修改為9 10 11。那么組合4 5 7 8 12 13的下一個組合為4 5 7 9 10 11。,排列與組合及有關的生成算法,4.字典序全排列與序號的轉換 字典序全排列的序號 記P=a1a2an。記ki為元素ai的逆序數(shù)，則排列P的序號為,問題：給定排列的序號，如何求全排列？,排列1 2 3 4 5 8 6 9 7的逆序數(shù)分別為0 0 0 0 0 2 0 1 0，序號為 345,給定排列的序號,/給定元素個數(shù)n，及全排列p /返回字典序全排列下排列序號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)!，注意下標從0開始 for (j=i+1;jn;j+) if (pjpi) num+=k;/是否有逆序，如有，統(tǒng)計 return num; ,給定排列的序號求排列,/給定元素個數(shù)n，排列序號num /返回對應的排列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ù)組進行調整 ,排列與組合及有關的生成算法,5字典序組合與序號的轉換 實例：設n=9，m=4。將從n個元素取m個的所有組合從1開始從小到大編序，組合3 5 7 9的序號是多少？ 一種計算方法：首位小于3的組合的個數(shù)為91；首位是3，第2位小于5的組合的個數(shù)為10；前2位是3 5，第3位小于7的組合的個數(shù)為3；前3位是3 5 7，第4位小于9的組合的個數(shù)為1。所有這些數(shù)之和105，加上它本身的1個號，得組合3 5 7 9的序號是106。,另一種思路由組合求序號,考慮從當前考察的組合的后面有多少個組合。 /傳入n、

8、m及組合c，返回c的序號num /下面的comb(n,m)是n個元素取m個的組合數(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; ,由序號求組合,由序號求組合算法是前面由組合求序號的逆過程 /輸入n、m，序號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ù)）。 給定一個序列，可確定對應的母函數(shù)；反過來，給定一個母函數(shù)，那么也能確定對應的序列。 例：斐波那契數(shù)列an，n=0，1，2， a0=a1= 1，an = an-1 +an-2 。對應的母函數(shù)可表示為,可求得,舉例,問題描述 小明手中有3張一元,2張2元和3張5元的錢幣,問小明都能買價值為多少的物品？對每種價值的物品他有幾種付款方法？如小明手中有k張一元，m張2元和n張5元的錢幣，結果又如何？

10、輸入 輸入的第一行是一個整數(shù)T，（1T10）,表示測試數(shù)據(jù)的個數(shù)。接下來有T行，每行上有3個非負整數(shù)k，m，n，（1k，m，n10），分別表示一元、二元和五元的錢幣數(shù)。k，m，n中至少有一個非0。 輸出 對輸入中的三種錢幣數(shù)，輸出小明能買物品的價值總數(shù)以及所有的付款方法數(shù)。,輸入與輸出樣例,輸入樣例 1 3 2 3 輸出樣例 22 47,對實例的說明,k=3，m=2，n=3 一元、二元、五元錢幣對應的能買物品的生成函數(shù),小明能買的物品對應的生成函數(shù)為,結論,小明可以買價值分別為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。,容斥原理與錯排,容斥原理 設A為任一個有限集合。用|A|記集合A中元素的個數(shù)。當A為空集時，|A|=0。 定理6.1 設A，B為兩個有限集合，那么,定理6.2 設A1，A2，An是n個有限集合，則,錯排,當n1 時，若n個元素1，2，n的排列P其每個元素都不在原來的位置上（即元素k不在位置k上），則該排列稱為錯排。 n個元素的集合1，2，n的錯排個數(shù)為Dn。 有遞推關系,很容易得到關于Dn 的關系式 Dn =,抽屜原理,將m個物品放入n個抽屜，則其中至少有一個抽屜里含有 個物品 設m1、m2，m1， mn都是正整數(shù)，且將n個物品放入

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

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

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

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

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

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

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

19、只要你告訴她方法數(shù)的最后一位數(shù)。 注意：因客人不同，下圖所示的2種方法是不同的。因此你不應混為一談。,輸入 輸入有多組測試數(shù)據(jù)。每一組測試數(shù)據(jù)由兩個整數(shù)m，n組成，其中整數(shù)m是果醬顏色數(shù)，整數(shù)n是客人數(shù)，也是蛋糕塊數(shù)，(0m100，1n10 000)。 當輸入m=n=0時表示輸入結束，這種情況你不必處理。 輸出 對每種情況，如輸入描述中所說，輸出將果醬放在蛋糕上的方法數(shù)的個位數(shù)。,輸入與輸出樣例,分析與討論,令an表示這n塊蛋糕用m種果醬的的擺設方案數(shù)。大蛋糕切成n塊后的形狀如圖所示，各塊分別標記為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塊小蛋糕的著色方案一一對應。此時小蛋糕Cn可用m-1種顏色。這種情況，n塊蛋糕的顏色涂法數(shù)為(m-1)an-2。 第二種情況： C1與Cn-1顏色不同，Cn的顏色可用m-2種。此時C1，C2，Cn-1的著色方案與大蛋糕切成n-1塊小蛋糕的著色方案一一對應。這種情況，n塊蛋糕的顏色涂法數(shù)為(m-2)an-1。,結論：,參考程序,#include using namespace std; int comput(int n,int m) int i,

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

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

23、則 g(m)=2 g( ),另一種分析方法,楊輝三角第n行中奇數(shù)的項數(shù)是二項式 的展開式中系數(shù)為奇數(shù)的項數(shù)。,（1） (x+1)n-1中系數(shù)為奇數(shù)的項數(shù)= (x+1)n-1(mod 2) 中系數(shù)非0的項數(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寫為二進制數(shù)akak-1a1a0，那么,分析,對等式兩邊作mod 2運算，丟掉那些使ai=0的項 (mod 2)。 于是， (x+1)n-1中系數(shù)為奇數(shù)的項數(shù)就

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

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

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

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

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

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

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

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

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

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

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

35、，有n/2個；以頂點i與i+1的中點與中心的連線為軸的翻轉，共n/2個；,分析,對任何輸入的n，恰有2n種不同的置換。 對于各置換的循環(huán)節(jié)計算，本題的旋轉形式的置換i，可直接根據(jù)置換的形式算出，循環(huán)節(jié)長度為GCD(i,n)； 在無法用公式求循環(huán)節(jié)長度時，根據(jù)求循環(huán)節(jié)長度的程序實現(xiàn)。 以下程序中，給出一個示例，構造所有置換，并用程序計算置換的循環(huán)節(jié)長度。,求置換perm的循環(huán)節(jié)數(shù)repetend,int cycle(int* perm,int n,int ,構造所有置換,double polya(int c,int 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) /構造第i個翻轉 for (i=0;i=n-1;i+)/i保持不動 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+)/構造第i個翻轉 for (j=0;j=n-1;j+)/i保持不動，共n/2個 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個 perm(i-j+n)%n=(i+j+1)%n; cycle(perm, n, x); t=t+pow(m,x); return t/(2*n); ,統(tǒng)計棋局數(shù),問題描述 一個有NN個格子的正方形棋盤，每個格子可以用C種不同顏色來染色，一共可以得到多少種不同的棋盤。如果一個棋盤，經(jīng)過任意旋轉、反射后變成另一個棋盤，這兩個棋盤就是屬于同一種棋盤。 比如當N=C=2的時候，有如下圖所示6種不同的棋盤。 現(xiàn)在告訴你N和C，請你算算到底有多少種不同的棋盤？,輸入

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

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