數(shù)據(jù)結(jié)構(gòu)課程設計──N皇后八皇后

1、上 海 電 機 學 院 課 程 設 計 報 告課設課題： 數(shù) 據(jù) 結(jié) 構(gòu) N皇后（八皇后） 學 院： 電 子 信 息 學 院 1專 業(yè)： 計 算 機 科 學 與 技 術 1姓 名： 1班 級： 1指導老師： 1報告日期： 年 月 制目 錄一、設計目的4二、課程設計基本要求4三、課程設計內(nèi)容及安排4四、八皇后背景知識5五、八皇后問題的實現(xiàn)65.1、遞歸方法解八皇后問題6、遞歸介紹7、使用到的函數(shù)和變量8、具體運行結(jié)果10、算法流程圖11、遞歸算法代碼12、算法分析135.2、回溯法解決八皇后問題13、回溯法介紹13、使用到的函數(shù)與變量14、具體運行結(jié)果15、算法流程圖16、回溯算法代碼17、算法

2、分析185.3、堆棧法解八皇后問題18、堆棧法介紹18、使用到的函數(shù)與變量19、具體運行過程20、算法流程圖21、堆棧法實現(xiàn)的源代碼21、算法分析255.4、三種算法的比較255.5、八皇后問題所有輸出結(jié)果26六、N皇后問題的實現(xiàn)306.1、N皇后問題介紹306.2、使用到的函數(shù)與變量306.3、具體的執(zhí)行316.4、算法流程圖316.5、N皇后的源代碼326.6、算法分析32七、經(jīng)驗和體會32八、參考文獻32九、附錄33附錄一：遞歸算法代碼34附錄二：回溯算法代碼34附錄三：堆棧法的源代碼36附錄四：N皇后的源代碼39一、設計目的數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強的軟件基礎課程，為了學好這門課程，必須

3、在掌握理論知識的同時，加強上機實踐。本課程設計的目的就是要達到理論與實際應用相結(jié)合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設計技能。二、課程設計基本要求1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設計方法，具備初步的獨立分析和設計能力；2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；3、提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；4、訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。5、設計的題目要求達到一定工作量（300行以上代碼），并

4、具有一定的深度和難度。6、編寫出課程設計說明書，說明書不少于10頁（代碼不算）。三、課程設計內(nèi)容1、問題分析和任務定義：根據(jù)設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ 2、邏輯設計：對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設計的結(jié)果應寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調(diào)用關系圖；3、詳細設計：定義相應的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、

5、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；4、程序編碼：把詳細設計的結(jié)果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；5、程序調(diào)試與測試：采用自底向上，分模塊進行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結(jié)果；6、結(jié)果分析：程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)

6、果。算法的時間、空間復雜性分析；7、編寫課程設計報告；四、八皇后背景知識國際象棋中皇后威力很大，它可以象“車”一樣沿直線上下或左右移動；也可以如同“象”那樣沿著斜線移動。雙方的皇后是不能在同一行或同一列或同一斜線上對持的。那么，在一張空白的國際象棋盤上最多可以放上幾個皇后并且不讓它們互相攻擊呢？這個問題是偉大數(shù)學家高斯在十九世紀中期提出來的，并作了部分解答。高斯在棋盤上放下了八個互不攻擊的皇后，他還認為可能有76種不同的放法，這就是有名的“八皇后”問題?，F(xiàn)在我們已經(jīng)知道八皇后問題有92個解答。那么你能試著找出幾種方法嗎？如果你動手試試，就一定會發(fā)現(xiàn)開頭幾顆皇后很容易放置，越到后來就越困難。由于

7、我們的記憶有限，很可能在某個位置放過子后來證明不行取消了，但是以后又重新放上子去試探，這樣就會不斷地走彎路，花費大量的精力。因此，必須找到一個簡易有效、有條不紊的法則才行。讓我們先從四皇后談起。若要在如圖1所示的44棋盤中，放置四個互不攻擊的皇后，可以如下從上到下逐行地考慮：當然在每行中只能放置一個而且必須放置一個皇后，問題是每行中的皇后應放在第幾列？圖1 圖2如果第一行的皇后放置在第一列，第二行的皇后就不能放置在第一、二列，只能放置在第三列或第四列。如果第二行的皇后放置在第三列，那第三行的皇后就沒有安身之處了。那么暫且把第二行的皇后放在第四列，看看情況如何。這時，第三行的皇后可以放在第二列（

8、見圖2）。然而，第四行的皇后仍然無家可歸！要放置好第四個皇后，必須對前幾個皇后的位置予以修正。前面已經(jīng)說過，第三行以至于第二行的所有位置均已考慮過了，只得考慮讓第一行的皇后挪一下。如果把第一行的皇后放在第二列，第二行的皇后放在第四列上，第三行的皇后放在第一列上，第四行的皇后放在第三列上，正好四個皇后互不攻擊（見圖3a）。如果繼續(xù)這樣逐行逐列地考慮下去，還可以找到四皇后問題地另一個解答（見圖3b）。圖3對于八皇后問題，也可如此解決：從上到下每行放一個皇后；在每一行中均從左至右逐列試放。能放則放（繼續(xù)考慮下一行）不能放則換（列數(shù)加1）換不成則退（退回前一行，讓前一皇后所在列數(shù)加1后繼續(xù)考慮），這就

9、是探索八皇后解答的途徑。為了記住在探索過程中每行皇后放置的位置就需要用棧。我們可用數(shù)組T來作棧；在T(P)中存放第P行皇后所在的列數(shù)。例如在第1行的皇后放在第3列，則可置T(1)=3。對于八皇后問題，如此安排后，數(shù)組T只需有八個分量就夠了。由于我們在每行中只放一個皇后，故而皇后之間保證不會左右相互攻擊了；那么如何檢查它們是否在上下或斜線方向相互攻擊呢？我們用一個數(shù)組C來記錄每一列上是否放了皇后，不管在哪一行上的第1列上放了一個皇后，就令C(1)=1，.。若把放在第1列上的皇后取走放到別的位置上去了，那么再令C(1)=0,.。這樣，只要查看C(I)是否為零，就可以知道第I列上是否可以放置皇后了！

10、顯然，八皇后問題中的數(shù)組C也只需八個分量就可以了。在88的國際象棋棋盤上，有15條從左上走向右下的斜線，稱為主斜線（如圖4中左圖）；同樣有15條從右上走向左下的斜線，稱為副斜線。由于每放一個皇后，它所在的兩條斜線上就不能再放皇后了。我們可以如同前面所述的那樣，再引進兩個數(shù)組S,M(每個數(shù)組有15個分量），分別記錄相應的主斜線和副斜線上是否已經(jīng)放下了皇后。在圖4中右圖，若在第2行第3列放了一個皇后，則應令S(7)=1,M(4)=1,表示第7條主斜線，第4條副斜線上已有皇后，以后不能再放置了。因為，主對角線數(shù)7可由8行數(shù)列數(shù)8+2-3=7計算得到，副斜線數(shù)4可由行數(shù)列數(shù)12+3-14計算得到。所以

11、一般地說，在第P行，第T(P)列放置皇后以后，應該令：C(T(P)=1；S(8+P-T(P)=1；M(P+T(P)-1)=1。有了以上準備知識，就能為八皇后問題寫算法了五、八皇后問題的實現(xiàn)5.1、遞歸方法解八皇后問題、遞歸的介紹調(diào)用子程序的含義：在過程和函數(shù)的學習中，我們知道調(diào)用子程序的一般形式是：主程序調(diào)用子程序A，子程序A調(diào)用子程序B，如圖如示，這個過程實際上是：當主程序執(zhí)行到調(diào)用子程序A語句時，系統(tǒng)保存一些必要的現(xiàn)場數(shù)據(jù)，跳轉(zhuǎn)到子程序A（為了說得簡單些，我這里忽略了參數(shù)傳遞這個過程）。當子程序A執(zhí)行到調(diào)用子程序B語句時，系統(tǒng)作法如上，跳轉(zhuǎn)到子程序B。子程序B執(zhí)行完所有語句后，跳轉(zhuǎn)回子程序

12、A調(diào)用子程序B語句的下一條語句（我這又忽略了返回值處理）子程序A執(zhí)行完后，跳轉(zhuǎn)回主程序調(diào)用子程序A語句的下一條語句主程序執(zhí)行到結(jié)束。做個比較：我在吃飯（執(zhí)行主程序）吃到一半時，某人叫我（執(zhí)行子程序A），話正說到一半， 又響了起來（執(zhí)行子程序B），我只要先接完 ，再和某人把話說完，最后把飯吃完認識遞歸函數(shù)我們在高中時都學過數(shù)學歸納法，例：求 n！ 我們可以把n！這么定義 也就是說要求3！，我們必須先求出2！，要求2！，必須先求1！，要求1！，就必須先求0！，而0!=1，所以1!=0!*1=1，再進而求2!，3!。分別用函數(shù)表示，則如圖： 我們可以觀察到，除計算0！子程序外，其他的子程序基本相似，

13、我們可以設計這么一個子程序： int factorial(int i) int res; res=factorial(I-1)*i; return res; 那么當執(zhí)行主程序語句s=factorial(3)時，就會執(zhí)行factorial(3),但在執(zhí)行factorial(3)，又會調(diào)用factorial(2)，這時大家要注意，factorial(3)和factorial(2)雖然是同一個代碼段，但在內(nèi)存中它的數(shù)據(jù)區(qū)是兩份！而執(zhí)行factorial(2)時又會調(diào)用factorial（1），執(zhí)行factorial（1）時又會調(diào)用factorial（0），每調(diào)用一次factorial函數(shù)，它就會在內(nèi)

14、存中新增一個數(shù)據(jù)區(qū)，那么這些復制了多份的函數(shù)大家可以把它看成是多個不同名的函數(shù)來理解；但我們這個函數(shù)有點問題，在執(zhí)行factorial（0）時，它又會調(diào)用factorial（1）。造成死循環(huán)，也就是說，在factorial函數(shù)中，我們要在適當?shù)臅r候保證不再調(diào)用該函數(shù)，也就是不執(zhí)行res=factorial(I-1)*i;這條調(diào)用語句。所以函數(shù)要改成： int factorial(int i) int res; if (I0) res=factorial(I-1)*i; else res=1;return res; 那么求3!的實際執(zhí)行過程如圖所示： 、使用到的函數(shù)和變量在這個算法中共有六個函數(shù)

15、，除了Main()主函數(shù)，還有IsValid(int n)，Output()，Queen(int n)，變量icount，Site這些組成程序，紅框圈出的是遞歸函數(shù)的應用，既自己調(diào)用自己在Queen(int n)中調(diào)用queen是典型的遞歸調(diào)用。編譯沒有錯誤、具體運行結(jié)果運行結(jié)果表示出有92種可能性、算法流程圖遞歸的圖解演示、程序代碼見附錄一、算法分析遞歸是一種很古老的算法，其應用的也十分的廣泛，在和多復雜的程序中也是經(jīng)常性的使用，雖然其的程序編寫相對的簡單，但其確消耗很多的資源，在沒有好的算法的前提下，這是相對能夠運行的算法，當然這也是在編程著能夠擁有一定的編寫能力的基礎上的。遞歸的優(yōu)點是：

16、編寫簡單，缺點是：消耗資源大。八皇后問題是一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題用遞歸是最為常見的方法，由于遞歸是自己套自己，把八皇后問題的調(diào)用函數(shù)在代碼界面上融合到了一個函數(shù)中。該算法中所有語句的頻度之和(即算法的時間耗費)為： T(n)=2n3+3n2+2n+1當n趨向于無窮時，其時間復雜度為O(n3)。5.2、回溯法解決八皇后問題、回溯法介紹在計算機奧賽中，有時會遇到這樣一類題目，它的問題可以分解，但是又不能得出明確的動態(tài)規(guī)劃或是遞歸解法，此時可以考慮用回溯法解決此類問題?；厮莘ǖ膬?yōu)點在于其程序結(jié)構(gòu)明確，可讀性強，易于理解，而且通過對問題的分析可以大大提高運行效率。但是，對于可以得出明顯的遞推公式迭代求

17、解的問題，還是不要用回溯法，因為它花費的時間比較長?；厮莘ǖ幕舅枷雽τ谟没厮莘ㄇ蠼獾膯栴}，首先要將問題進行適當?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得出結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大提升程序效率，因為在深度優(yōu)先搜索的過程中，不斷的將每個解（并不一定是完整的，事實上這也就是構(gòu)造約束函數(shù)的意義所在）與約束函數(shù)進行對照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時間?；厮莘ㄖ?，首先需要明確下面三個概念：（一）約束函數(shù)：約束函數(shù)是根據(jù)題意定出的。通過描述合法解的一般特征用于去除不合

18、法的解，從而避免繼續(xù)搜索出這個不合法解的剩余部分。因此，約束函數(shù)是對于任何狀態(tài)空間樹上的節(jié)點都有效、等價的。（二）狀態(tài)空間樹：剛剛已經(jīng)提到，狀態(tài)空間樹是一個對所有解的圖形描述。樹上的每個子節(jié)點的解都只有一個部分與父節(jié)點不同。（三）擴展節(jié)點、活結(jié)點、死結(jié)點：所謂擴展節(jié)點，就是當前正在求出它的子節(jié)點的節(jié)點，在DFS中，只允許有一個擴展節(jié)點。活結(jié)點就是通過與約束函數(shù)的對照，節(jié)點本身和其父節(jié)點均滿足約束函數(shù)要求的節(jié)點；死結(jié)點反之。由此很容易知道死結(jié)點是不必求出其子節(jié)點的（沒有意義）。深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（FIFO）在分支界限法中，一般用的是FIFO或最小耗費搜索；其思想是一次性將一個節(jié)

19、點的所有子節(jié)點求出并將其放入一個待求子節(jié)點的隊列。通過遍歷這個隊列（隊列在遍歷過程中不斷增長）完成搜索。而DFS的作法則是將每一條合法路徑求出后再轉(zhuǎn)而向上求第二條合法路徑。而在回溯法中，一般都用DFS。為什么呢？這是因為可以通過約束函數(shù)殺死一些節(jié)點從而節(jié)省時間，由于DFS是將路徑逐一求出的，通過在求路徑的過程中殺死節(jié)點即可省去求所有子節(jié)點所花費的時間。FIFO理論上也是可以做到這樣的，但是通過對比不難發(fā)現(xiàn)，DFS在以這種方法解決問題時思路要清晰非常多。因此，回溯法可以被認為是一個有過剪枝的DFS過程。利用回溯法解題的具體步驟首先，要通過讀題完成下面三個步驟：(1) 描述解的形式，定義一個解空間

20、，它包含問題的所有解。(2) 構(gòu)造狀態(tài)空間樹。(3) 構(gòu)造約束函數(shù)（用于殺死節(jié)點）。然后就要通過DFS思想完成回溯，完整過程如下：(1) 設置初始化的方案（給變量賦初值，讀入已知數(shù)據(jù)等）。(2) 變換方式去試探，若全部試完則轉(zhuǎn)(7)。(3) 判斷此法是否成功（通過約束函數(shù)），不成功則轉(zhuǎn)(2)。(4) 試探成功則前進一步再試探。(5) 正確方案還未找到則轉(zhuǎn)(2)。(6) 已找到一種方案則記錄并打印。(7) 退回一步（回溯），若未退到頭則轉(zhuǎn)(2)。(8) 已退到頭則結(jié)束或打印無解?；厮莘ǖ臄?shù)據(jù)結(jié)構(gòu)回溯法的狀態(tài)空間樹，在計算機上的數(shù)據(jù)結(jié)構(gòu)有兩種表示方法。當用k表示樹的節(jié)點層數(shù)，n表示節(jié)點總數(shù)，m表示

21、解的總數(shù)時：（一） 用m個k元組表示m種不同的解。其中，每組中的元素是1,n中的一個元素。在Pascal中，可以這樣定義變量： var a:array1.k,1.mof integer;（integer可以依n的范圍決定）（二） m個n元組表示m種不同的解。因為所有的節(jié)點都包含在每個解的表示中，每組中的元素只有兩種情況，被選用和不被選用。在Pascal中，可以這樣定義變量：var a:array1.n,1.mof boolean;這兩種數(shù)據(jù)結(jié)構(gòu)的解空間最多都含有2n個不同的元組、使用到的函數(shù)與變量回溯發(fā)是很好的算法，在所有算發(fā)中空間復雜度是最小的，其只有一個主函數(shù)main()，和一個變量tot

22、al，就可以成功的解決八皇后問題，我本人對于這種算法非常的推崇，也覺的是所有解決了八皇后問題中最好的。編譯沒有錯誤、具體運行結(jié)果運行結(jié)果如圖、算法流程圖回溯算法的圖解、程序代碼見附錄二、算法分析回溯是一個很好的算法，其應用的也十分的廣泛，在和多復雜的程序中也是經(jīng)常性的使用，雖然其的程序編寫相對的簡單，但其確消耗很多的資源，在沒有好的算法的前提下，這是相對能夠運行的算法，當然這也是在編程著能夠擁有一定的編寫能力的基礎上的?；厮莸膬?yōu)點是：編寫復雜，缺點是：消耗資源小。八皇后問題是一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題用回溯是最為常見的方法，由于回溯是自己套自己，把八皇后問題的調(diào)用函數(shù)在代碼界面上融合到了一個函數(shù)中

23、。該算法中所有語句的頻度之和(即算法的時間耗費)為： T(n)=2n2+1分析：當n趨向于無窮時，其時間復雜度為O(n2+1 +2)。5.3、堆棧法解八皇后問題、堆棧法介紹堆棧的概念堆棧(Stack)是一種比較重要的線性數(shù)據(jù)結(jié)構(gòu)，如果對數(shù)據(jù)結(jié)構(gòu)知識不是很了解的話，我們可以把它簡單的看作一維數(shù)組。但是對一維數(shù)組進行元素的插入、刪除操作時，可以在任何位置進行，而對于棧來說，插入、刪除操作是固定在一端進行的，這一端稱為棧頂(top)，另一端稱為棧底(bottom)，向棧中插入數(shù)據(jù)的操作稱為壓入(Push)，從棧中刪除數(shù)據(jù)稱為彈出(Pop)。二 堆棧的存儲方式對棧中元素的操作是按后進先出(Last I

24、n First Out,簡稱LIFO)的原則進行的，即最后壓入的元素最先彈出。在棧的操作過程中，有一個永遠指向棧頂?shù)臈ｍ斨羔?，在壓入和彈出?shù)據(jù)時，棧頂指針向上或向下移動。當棧頂指針為零時(即指向棧底的后面)，棧為空棧。如果壓入的數(shù)據(jù)過多超出了棧的最大空間，則發(fā)生棧上溢。在程序設計中，我們可以使用一維數(shù)組實現(xiàn)對棧的操作。假設用一維數(shù)組s1.arrmax表示棧，則對于非空棧，s1為最早壓入棧的元素，同時設棧頂指針top，則stop為最后壓入棧的元素。當top=arrmax時棧滿，若此時有數(shù)據(jù)入棧將產(chǎn)生“數(shù)組越界”的錯誤，極為棧上溢，反之當top=0,意為?？?。、使用到的函數(shù)與變量組成的程序的函數(shù)有

25、：DeSetQueen(int row，int col)，DisplayAndSet()，main()，NoConflict(int row,int col)，Pop()，Push(int row，int col)，Queen()，SetQueen(int row，int col)，變量有：ArrayQueen,OutQueen,Top 。沒有編譯錯誤、具體運行過程八皇后問題的源代碼、算法流程圖、程序代碼見附錄三、算法分析堆棧是一個很好的算法，其應用的也十分的廣泛，在和多復雜的程序中也是經(jīng)常性的使用，雖然其的程序編寫相對的簡單，但其確消耗很多的資源，在沒有好的算法的前提下，這是相對能夠運行的算

26、法，當然這也是在編程著能夠擁有一定的編寫能力的基礎上的。堆棧的優(yōu)點是：算法比較的平均，運行十分的復雜。八皇后問題是一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題用遞歸是最為常見的方法，由于遞歸是自己套自己，把八皇后問題的調(diào)用函數(shù)在代碼界面上融合到了一個函數(shù)中。該算法中所有語句的頻度之和(即算法的時間耗費)為： T(n)=2nn+1分析：當n趨向于無窮時，其時間復雜度為O(n2 +1)。5.4、三種算法的比較遞歸簡單，但消耗資源?；厮荼容^的復雜，但消耗資源少。堆棧比較的平均5.5、八皇后問題所有輸出結(jié)果為（88棋盤）：第1種情況: 第2種情況: 第3種情況:Q * * * * * * * Q * * * * * * *

27、 Q * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * * * * * Q* * * * * * * Q * * * * * Q * * * * Q * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * Q * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * Q *

28、* * * * * * Q * * * * * * * * * Q * * * 第4種情況: 第5種情況: 第6種情況:Q * * * * * * * * * * * * Q * * * * * Q * * * * * * * Q * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * Q * * * * * * * * * * * * * Q* * Q * * * * * * * * * * * * Q * Q * * * * * * * * * *

29、 * Q * * * Q * * * * * * * * * * * Q * * Q * * * * * * * * * * * * Q * * * Q * * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * *第7種情況: 第8種情況: 第9種情況:* * * * Q * * * * * Q * * * * * * * * * Q * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * Q

30、 * * * * * * * * Q * * * * * * * * Q * * Q * * * * * * * * * * * * * Q * * * * * * * Q* * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * * Q * * * * * Q * * * * * * * Q * * * * Q * * * * * 第10種情況: 第11種情況: 第12種情況:* * * * * * Q * * * * * Q * * * * * * Q * * * *Q *

31、* * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * * * Q * * * * * * * * * Q* * * * * Q * * * * Q * * * * * * * * * * Q * * * * Q * * * * * * * * * * Q * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * Q * *

32、 * * * Q * * * * * *第13種情況: 第14種情況: 第15種情況:* Q * * * * * * * * * * Q * * * * * * * * * * Q* * * * * Q * * * * Q * * * * * * * Q * * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * *

33、 * * Q * * * * Q * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * Q * * * * * * Q * * * * * * * Q * * * *第16種情況: 第17種情況: 第18種情況:* * * Q * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * * * * * * Q * * * Q * * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * Q

34、* * * * * * * * * * * Q* Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * Q * * * * * * * * * Q * * *第19種情況: 第20種情況: 第21種情況:* * * * Q * * * * * * * * Q * * * * * Q * * * * * Q * * * * * * * Q *

35、 * * * * * * * * * * * QQ * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * * * * Q * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * Q * *

36、*第22種情況: 第23種情況: 第24種情況:* * * * * * * Q * * * Q * * * * * * * Q * * * * * * Q * * * * * * * * * * * Q * * * * * * Q *Q * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * Q* * * * * Q * * * * * * * * Q * * * * * Q * * * Q * * * * * * * Q * * * * * * * Q * * * *

37、* * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * Q * * * * * Q * * * * * * * Q * * * * *第25種情況: 第26種情況: 第27種情況:* * * * * Q * * * * * * * Q * * * * * * * * Q * * * Q * * * * * * Q * * * * * * * Q * * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * * Q * * * * * * Q

38、 * * * * * * * * Q * * * * Q * * * * * * * * * * Q* Q * * * * * * * * * * * * * Q * * * * Q * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * * *第28種情況: 第29種情況: 第30種情況:* * * * Q * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * Q * * * * * * *

39、* * * QQ * * * * * * * * * * * * * Q * * * * * * Q * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * Q * * * * Q * * * * * Q * * * * * * * * * Q * * * * * * * * Q * Q * * * * * * * * * Q * * * * * * * Q * * * *第31種情況: 第32種情況:

40、第33種情況:* * * * * Q * * * * * * * * Q * * * * * * * * Q* Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * Q * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q

41、 * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * Q * *第34種情況: 第35種情況: 第36種情況:* * * * Q * * * * * * * * Q * * * * * * Q * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * * Q * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * *

42、* * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * * Q * * * Q * * * * * Q * * * * * * * * * Q * * * * * * * * * * Q* * * * * Q * * * * Q * * * * * * * Q * * * * *第37種情況: 第38種情況: 第39種情況:* * Q * * * * * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * * * * * * Q* * * * * *

43、Q * * * * * * * Q * * * * Q * * * *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * Q * * * * *第40種情況: 第41種情況: 第42種情況:* * Q * * * * * * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * * * * * Q * * Q * * * * * * * * * * * Q *Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * Q *