【例題1】
對2*2之方陣用黑白兩種顏色塗色，問能得到多少種不同之影象？經過旋轉使之吻合之兩種方案，算是同一種方案。
【問題分析】
由於該問題規模很小，我們可以先把所有之塗色方案列舉出來。
乙個2*2之方陣之旋轉方法一共有4種：旋轉0度、旋轉90度、旋轉180度和旋轉270度。(注：
本文中預設旋轉即為順時針旋轉) 我們經過嘗試，發現其中互異之一共只有6種：c3、c4、c5、c6是可以通過旋轉相互變化而得，算作同一種；c7、c8、c9、c10是同一種；c11、c12是同一種；c13、c14、c15、c16也是同一種； c1和c2是各自獨立之兩種。於是，我們得到了下列6種不同之方案。
但是，一旦這個問題由2*2之方陣變成20*20甚至200*200之方陣，我們就不能再一一枚舉了，利用polya原理成了乙個很好之解題方法。在接觸polya原理之前，首先簡單介紹polya原理中要用到之一些概念。
群：給定乙個集合g=和集合g上之二元運算，並滿足:
(a) 封閉性：a,bg, cg, a＊b=c。
(b) 結合律：a,b,cg, (a＊b)＊c=a＊(b＊c)。
(c) 單位元：eg, ag, a＊e=e＊a=a。
(d) 逆元：ag, bg, a＊b=b＊a=e，記b=a-1。
則稱集合g在運算＊之下是乙個群，簡稱g是群。一般a＊b簡寫為ab。
置換：n個元素1,2,…,n之間之乙個置換表示1被1到n中之某個數a1取代，2被1到n中之某個數a2取代，直到n被1到n中之某個數an取代，且a1,a2,…,an互不相同。本例中有4個置換：
轉0 a1=
轉90 a2=
轉180 a3=
轉270 a4=
置換群：置換群之元素是置換，運算是置換之連線。例如：
可以驗證置換群滿足群之四個條件。
本題中置換群g=
我們再看乙個公式：│ek│·│zk│=│g│ k=1…n
該公式之乙個很重要之研究物件是群之元素個數，有很大之用處。
zk (k不動置換類)：設g是1…n之置換群。若k是1…n中某個元素，g中使k保持不變之置換之全體，記以zk，叫做g中使k保持不動之置換類，簡稱k不動置換類。
如本例中：g是塗色方案1~16之置換群。對於方案1，四個置換都使方案1保持不變，所以z1=；對於方案3，只有置換a1使其不變，所以z3=；對於方案11，置換a1和a3使方案其保持不變，所以z11=。
ek(等價類)：設g是1…n之置換群。若k是1…n中某個元素，k在g作用下之軌跡，記作ek。即k在g之作用下所能變化成之所有元素之集合。
如本例中：方案1在四個置換作用下都是方案1，所以e1=；方案3，在a1下是3，在a2下變成6，在a3下變成5，在a4下變成4，所以e3=；方案11，在a1、a3下是11，在a2、a4下變成12，所以e11=。
本例中之資料，也完全符合這個定理。如本例中：
│e1│·│z1│= 14 = 4 =│g│
│e3│·│z3│= 41 = 4 =│g│
│e11│·│z11│= 22 = 4 =│g│
限於篇幅，這裡就不對這個定理進行證明。
接著就來研究每個元素在各個置換下不變之次數之總和。見下表：
其中 d(aj) 表示在置換aj下不變之元素之個數
如本題中：塗色方案1在a1下沒變動，s1,1=1；方案3在a3變動了， s3,3=0；在置換a1之變化下16種方案都沒變動，d(a1)=16；在置換a2下只有1、2這兩種方案沒變動，d(a2)=2。
一般情況下，我們也可以得出這樣之結論：
我們對左式進行研究。
不妨設n=中共有l個等價類，n=e1+ e2+……+el，則當j和k屬於同一等價類時，有│zj│=│zk│。所以
這裡之l就是我們要求之互異之組合狀態之個數。於是我們得出：
利用這個式子我們可以得到本題之解 l=(16+2+4+2)/4=6 與前面列舉得到之結果相吻合。這個式子叫做burnside引理。
但是，我們發現要計算d(aj)之值不是很容易，如果採用搜尋之方法，總之時間規模為o(nsp)。(n表示元素個數，s表示置換個數，p表示格仔數，這裡n之規模是很大之) 下一步就是要找到一種簡便之d(aj)之計算方法。先介紹乙個迴圈之概念：
迴圈：記
稱為n階迴圈。每個置換都可以寫若干互不相交之迴圈之乘積，兩個迴圈(a1a2…an)和(b1b2…bn)互不相交是指aibj, i,j=1,2,…,n。例如：
這樣之表示是唯一之。置換之迴圈節數是上述表示中迴圈之個數。例如(13)(25)(4)之迴圈節數為3。
有了這些基礎，就可以做進一步之研究，我們換乙個角度來考慮這個問題。我們給2*2方陣之每個方塊標號，如下圖：
構造置換群g'=,｜g'｜＝4，令gi之迴圈節數為c(gi) (i=1,2,3,4)
在g'之作用下，其中
g1表示轉0° , 即g1=(1)(2)(3)(4) c(g1)=4
g2表示轉90°, 即g2=(4 3 2 1c(g2)=1
g3表示轉180°, 即g3=(1 3)(2 4) c(g3)=2
g4表示轉270°, 即g4=(1 2 3 4) c(g4)=1
我們可以發現，gi之同乙個迴圈節中之物件塗以相同之顏色所得之影象數mc(gi) 正好對應ｇ中置換ai作用下不變之圖象數，即
2c(g1)=24=16=d(a1) 2c(g2)=21=2= d(a2)
2c(g3)=22=4=d(a3) 2c(g4)=21=2= d(a4)
由此我們得出乙個結論：
設g是p個物件之乙個置換群，用m種顏色塗染p個物件，則不同染色方案為：
其中g= c(gi )為置換gi之迴圈節數(i=1…s)
這就是所謂之polya定理。我們發現利用polya定理之時間複雜度為o(sp) (這裡s表示置換個數，p表示格仔數)，與前面得到之burnside引理相比之下，又有了很大之改進，其優越性就十分明顯了。polya定理充分挖掘了研究物件之內在聯絡，總結了規律，省去了許多不必要之盲目搜尋，把解決這類問題之時間規模降到了乙個非常低之水平。
現在我們把問題改為：nn之方陣，每個小格可塗m種顏色，求在旋轉操作下本質不同之解之總數。
【問題分析】
先看乙個很容易想到之搜尋之方法。(見附錄)
這樣搜尋之效率是極低之，它還有很大之改進之餘地。前面，我們採用之方法是先搜後判，這樣之盲目性極高。我們需要邊搜邊判，避免過多之不必要之列舉，我們更希望把判斷條件完全融入到搜尋之邊界中去，消滅無效之列舉。
這個美好之希望是可以實現之。
我們可以在方陣中分出互不重疊之長為[(n+1)/2]，寬為[n/2]之四個矩陣。當n為偶數時，恰好分完；當n為奇數時，剩下中心之乙個格仔，它在所有之旋轉下都不動，所以它塗任何顏色都對其它格仔沒有影響。令m種顏色為0~m-1，我們把矩陣中之每格之顏色所代表之數字順次(左上角從左到右，從上到下；右上角從上到下，從右到左；……)排成m進製數，然後就可以表示為乙個十進位制數，其取值範圍為0~m[n2/4]-1。
(因為[n/2]*[(n+1)/2]=[n2/4]) 這樣，我們就把乙個方陣簡化為4個整數。我們只要找到每乙個等價類中左上角之數最大之那個方案(如果左上角相同，就順時針方向順次比較) 這樣，在列舉之時候其它三個數一定不大於左上角之數，效率應該是最高之。
進一步考慮，當左上角數為i時,(0ir-1) 令r=m[n2/4]
可分為下列之4類：
其它三個整數均小於i，共i3個。
右上角為i，其它兩個整數均小於i，共i2個。
右上角、右下角為i，左下角不大於i，共i+1個。
右下角為i，其它兩個整數均小於i，且右上角之數不小於左下角之，共i(i+1)/2個。
因此，當n為奇數時，還要乘乙個m。
由此我們就巧妙地得到了乙個公式。但是，我們應該看到要想到這個公式需要很高之智慧型和付出不少之時間。另一方面，這種方法只能對這道題有用而不能廣泛地應用於一類試題，具有很大之不定性因素。
因此，如果能掌握一種適用面廣之原理，就會對解這一類題有很大之幫助。
下面我們就採用polya定理。我們可以分三步來解決這個問題。
1． 確定置換群
在這裡很明顯只有4個置換：轉0、轉90、轉180、轉270。所以，置換群g=。
2． 計算迴圈節個數
首先，給每個格仔順次編號（1~n2），再開乙個二維陣列記錄置換後之狀態。最後通過搜尋計算每個置換下之迴圈節個數，效率為一次方級。
3． 代入公式
即利用polya定理得到最後結果。
【程式題解】
const
maxn=10;
var a,b:array[1..maxn,1..maxn] of integer;
i,j,m,n:integer;
l,l1:longint;
procedure xz;
var i,j:integer;
begin
for i:=1 to n do
for j:=1 to n do
a[j,n+1-i]:=b[i,j];
b:=a
end;
procedure xhj;
var i,j,i1,j1,k,p:integer;
begin
k:=0;
《作業系統原理》綜合知識複習
字型大小 大中小 第1章作業系統概述 1.1 計算機系統 計算機硬體是指組成計算機系統的裝置或機器，是 看得見，摸得著 的物理部件，它是組成計算機系統的基礎。組成，計算機硬體一般包括 處理器 cpu 記憶體儲器 外儲存器 輸入裝置和輸出裝置，其中cpu與記憶體儲器合稱為主機，外儲存器 輸入裝置和輸出...
幼兒心理學複習題 華師
1 第1題 嬰兒恐懼可分為 d a.生理性恐懼和社會性恐懼 b.無條件反射的恐懼和條件發射的恐懼c.先天恐懼和後天習得的恐懼 d.本能的恐懼 與知覺和經驗相聯絡的恐懼 怕生 性恐懼2 第2題 科學兒童心理學建立的標誌是 c a.達爾文於1876寫成 乙個嬰兒的傳略 b.馮特於1879年在德國萊比錫成...
註冊規劃師複習筆記 規劃原理
第五章城市總體規劃 第一節城市總體規劃的作用和任務 考試大綱 1 掌握城市總體規劃的作用 2 掌握城市總體規劃的主要任務 內容精講 一 城市總體規劃的作用 城市總體規劃涉及城市的政治 經濟 文化和社會生活等各個領域，在指導城市有序發展 提高建設和管理水平等方面發揮著重要的先導和統籌作用。城市總體規劃...