




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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種情況:沿對
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 非球形顆粒剪切動力學行為及流變模型研究
- 車輛維修保養(yǎng)與保險理賠承包合同范本
- 石油化工車間租賃及安全生產(chǎn)管理合同
- 餐飲店加盟店經(jīng)營管理規(guī)范協(xié)議
- 倉儲物流服務采購合同模板
- 新能源材料企業(yè)股權重組與產(chǎn)業(yè)鏈整合合同
- 商業(yè)停車場使用權買賣合同樣本
- 陳紈與張明的離婚后個人隱私保護及隱私權協(xié)議書
- 場地租賃規(guī)范與租賃期限合同
- 自動消防系統(tǒng)培訓課件
- 谷子介紹課件
- 初二化學全套試題及答案
- 融資代建合同模板5篇
- 甲方工期回復函
- 直播肖像權使用合同協(xié)議
- 2025屆高考政治復習重點知識大全(全7冊)
- 電梯公告板制度
- 餐飲內部考核管理制度
- 2024年山東滕州市屬國有企業(yè)第三批次招聘120人筆試參考題庫附帶答案詳解
- 酒吧股東合伙協(xié)議書
- 臥床病人康復鍛煉課件
評論
0/150
提交評論