八皇后課程設(shè)計實驗報告 C++

1、淮陰工學(xué)院 C+C+程序設(shè)計課程設(shè)計報告程序設(shè)計課程設(shè)計報告 選題名稱選題名稱: 八皇后 系（院）系（院）: 計 算 機 工 程 學(xué)院 專專 業(yè)業(yè): 計算機科學(xué)與技術(shù) 班班 級級: 計 1102 班 姓姓 名名: 李金偉 學(xué)學(xué) 號號: 指導(dǎo)教師指導(dǎo)教師: 王曉燕、戴俊峰 學(xué)年學(xué)期學(xué)年學(xué)期: 2010 2011 學(xué)年 第 1 學(xué)期 2010年 12 月 25 日 設(shè)計任務(wù)書 課題 名稱 八皇后 設(shè)計 目的 1.調(diào)研并熟悉八皇后的基本功能、數(shù)據(jù)流程與工作規(guī)程； 2.學(xué)習(xí)八皇后相關(guān)的算法和基于 VC+集成環(huán)境的編程技術(shù)； 3.通過實際編程加深對基礎(chǔ)知識的理解，提高實踐能力； 4.學(xué)習(xí)開發(fā)資料的收集與

2、整理，學(xué)會撰寫課程設(shè)計報告。 實驗 環(huán)境 1.微型電子計算機（PC）； 2.安裝 Windows 2000 以上操作系統(tǒng)，Visual C+6.0 開發(fā)工具。 任務(wù) 要求 1.利用課余時間去圖書館或上網(wǎng)查閱課題相關(guān)資料，深入理解課題含義及設(shè)計要 求，注意材料收集與整理； 2.在第 16 周末之前完成預(yù)設(shè)計，并請指導(dǎo)教師審查，通過后方可進行下一步工作； 3.本課題要求至少用三種方法解決八皇后問題，輸入棋盤的階層，然后顯示共有 多少種布局方案，并顯示每一種方案的具體情況。 4.結(jié)束后，及時提交設(shè)計報告（含紙質(zhì)稿、電子稿），要求格式規(guī)范、內(nèi)容完整、 結(jié)論正確，正文字數(shù)不少于 3000 字（不含代碼）

3、。 工作進度計劃 序號起止日期工 作 內(nèi) 容 12009.06.72009.06.7 在預(yù)設(shè)計的基礎(chǔ)上，進一步查閱資料，完善設(shè)計方案， 形成書面材料。 22009.06. 72009.06.10 設(shè)計總體方案，構(gòu)建、繪制流程框圖，編寫代碼，上機 調(diào)試。 32009.06.112009.06.12測試程序，優(yōu)化代碼，增強功能，撰寫設(shè)計報告。 42009.06.122009.06.13 提交軟件代碼、設(shè)計報告，參加答辯，根據(jù)教師反饋意 見，修改、完善設(shè)計報告。 指導(dǎo)教師（簽章）： 年 月 日 摘要： 眾所周知的八皇后問題是一個非常古老的問題，具體如下：在 8*8 的國際象棋棋 盤上放置了八個皇后，

4、要求沒有一個皇后能吃掉另一個皇后，即任意兩個皇后都不處 于棋盤的同一行、同一列或同一對角線上,這是做出這個課題的基礎(chǔ)。要求編寫實現(xiàn)八 皇后問題的遞歸解法或非遞歸解法，對于任意給定的一個初始位置，輸出八皇后問題 的一個布局。本次設(shè)計旨在學(xué)習(xí)各種算法，訓(xùn)練對基礎(chǔ)知識和基本方法的綜合運用及 變通能力，增強對算法的理解能力，提高軟件設(shè)計能力。在實踐中培養(yǎng)獨立分析問題 和解決問題的作風(fēng)和能力。 要求熟練運用 C+語言、基本算法的基礎(chǔ)知識，獨立編制一個具有中等難度的、 解決實際應(yīng)用問題的應(yīng)用程序。通過對題意的分析與計算，用遞歸法回溯法及枚舉法 解決八皇后是比較適合的。遞歸是一種比較簡單的且比較古老的算法。

5、回溯法是遞歸 法的升華，在用來求問題的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索 遍才結(jié)束。而枚舉法，更是一種基礎(chǔ)易懂簡潔的方法。把它們綜合起來，就構(gòu)成了今 天的算法。不論用什么法做這個課題，重要的就是先搞清楚哪個位置是合法的放皇后 的位置，哪個不能，要先判斷，后放置。 關(guān)鍵詞：八皇后；遞歸法；回溯法；數(shù)組；枚舉法. 目目 錄錄 1 1 課題綜述課題綜述 1 1 1.1 八皇后問題概述八皇后問題概述 -1 1.2 預(yù)期目標預(yù)期目標 -1 1.3 八皇后問題課題要求八皇后問題課題要求 -2 1.4 面對的問題面對的問題 -3 2 2 需求分析需求分析 3 3 2.1 涉及到的知識基礎(chǔ)涉及

6、到的知識基礎(chǔ)-3 2.2 總體方案總體方案-8 3 3 模塊及算法設(shè)計模塊及算法設(shè)計8 8 3.1 算法描述算法描述-8 3.23.2詳細流程圖詳細流程圖 -11 4.4.代碼編寫代碼編寫.1212 5 5 程序調(diào)試分析程序調(diào)試分析.2525 6 6 運行與測試運行與測試.2626 總總 結(jié)結(jié) .3131 致致 謝謝 3232 參參 考考 文文 獻獻 .3333 指指導(dǎo)導(dǎo)教教師師評評語語3434 1 課題綜述課題綜述 1.1 八皇后問題概述八皇后問題概述 八皇后問題是一個古老而著名的問題。該問題是十九世紀著名的數(shù)學(xué)家高 斯 1850 提出；在 88 格的國際象棋上擺放八皇后，使其不能互相攻擊，

7、即任 意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯 認為有 76 種方案。1854 年在柏林的象棋雜志上不同的作者發(fā)表了 40 種不同的 解，后人有人用圖論的方法解出 92 宗結(jié)果。雖然問題的關(guān)鍵在于如何判定某個 皇后所在的行、列、斜線是否有別的皇后；可以從矩陣的特點上找到規(guī)律，如 果在同一行，則行號相同；如果在同一列上，則列號相同；如果同在“/”斜線 上的行列值之和相同；如果在對角線上，則行列號之和或之差相等，逐個紀錄 符合題意的情況,最終得出解。(如圖 1-1，是八皇后問題的一個實例圖) 圖 1-1 八皇后棋盤實例 1.2 預(yù)期目標預(yù)期目標 運用 C+程序設(shè)計的編程

8、思想編寫代碼，實現(xiàn)八皇后問題的所有（92 種） 擺放情況。要求在 DOS 界面上顯示出每一種方式。 1.3 八皇后問題課題要求八皇后問題課題要求 編寫代碼，用至少三種方法解決八皇后問題。運行程序后，顯現(xiàn)下面的參 考界面： 八皇后問題 = 1方法一 2方法二 3方法三 請選擇（請選擇（1、2 或或 3，0：退出）：退出）： 圖 1-2 輸出界面實例 選擇一個菜單后，要求輸入棋盤的階層，即 N。輸入后，顯示共有多少種布局 方案，并顯示每一種方案的具體情況，如下圖： 77: (0,2) (1,0) (2,6) (3,4) (4,7) (5,1) (6,3) (7,5) 78: (0,7) (1,1)

9、 (2,4) (3,2) (4,0) (5,6) (6,3) (7,5) 圖 1-3 輸出樣式實例 1.4 面對的問題面對的問題 需要用三種方法解決八皇后問題，在這里需要查閱大量資料并多加練習(xí)，才 能成功編寫程序。主要要解決下面的問題： 沖突：包括列、行、兩條對角線； 1. 列：規(guī)定每一列放一個皇后，就不會造成列上的沖突； 2. 行：當(dāng)?shù)?i 行被某個皇后占據(jù)時，該行所有空格就都不能放置其他皇后； 3. 對角線：對角線有兩個方向，在同一對角線上的所有點都不能有沖突。 2 需求分析需求分析 2.1 涉及到的知識基礎(chǔ)涉及到的知識基礎(chǔ) 在本次的課程設(shè)計中，用到的知識點主要有：類、函數(shù)、選擇結(jié)構(gòu)里的條

10、 件語句、循環(huán)結(jié)構(gòu)里的 while 語句以及 for 循環(huán)語句、控制語句里的 break 語 句、以及字符串函數(shù)的運用等等,并且應(yīng)用到遞歸、回溯及窮舉等比較經(jīng)典的 算法。 2.1.1 類類 2.1.1.1 類定義 類就是用戶自定義的數(shù)據(jù)類型。 類定義的一般形式如下： class 類名 細節(jié)；(數(shù)據(jù)成員，成員函數(shù)) ; 2.1.1.2 類函數(shù)定義 類成員函數(shù)類的成員函數(shù)通常在類外定義，一般形式如下: 返回類型 類名:函數(shù)名(形參表) 函數(shù)體; 雙冒號: :是域運算符，主要用于類的成員函數(shù)的定義。 2.1.2 函數(shù) 2.1.2.1 函數(shù)的定義 定義函數(shù)需要指明：函數(shù)執(zhí)行結(jié)果返回值的類型、函數(shù)名、形

11、式參數(shù)(簡稱 形參)和函數(shù)體。 一般形式為： 數(shù)據(jù)類型 函數(shù)名（行參表） 語句序列； Return 合適類型數(shù)值 2.1.2.2 數(shù)據(jù)類型 規(guī)定了函數(shù)返回值類型。黨執(zhí)行函數(shù)體中的語句后，通常會產(chǎn)生一個結(jié)果， 這就是函數(shù)的返回值，它可以是任何有效的類型。若函數(shù)執(zhí)行后不返回值，數(shù) 據(jù)類型習(xí)慣用 void 來表示。如果在函數(shù)定義時沒有數(shù)據(jù)類型出現(xiàn)，則默認為函 數(shù)返回值為整型值(int)。 2.1.2.3 函數(shù)調(diào)用 調(diào)用一個函數(shù)之前必須對該函數(shù)進行說明。 函數(shù)調(diào)用由函數(shù)名和函數(shù)調(diào)用運算符( )組成，( )內(nèi)有 0 個或多個逗號分隔 的參數(shù)(稱為實參)。每一個參數(shù)是一個表達式，且參數(shù)的個數(shù)與參數(shù)的類型要

12、 與被調(diào)函數(shù)定義的參數(shù)(稱為形參)個數(shù)和類型匹配。 當(dāng)被調(diào)函數(shù)執(zhí)行時，首先計算實參表達式，并將結(jié)果值傳送給行參，然后 執(zhí)行函數(shù)體，返回的返回值被傳送到調(diào)用函數(shù)。 如果函數(shù)調(diào)用后有返回值，調(diào)用表達是可以用在表達式中，而無參函數(shù)的 調(diào)用是一個單獨的語句。 2.1.3 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 2.1.3.1 用 if 語句實現(xiàn)選擇結(jié)構(gòu)設(shè)計 if 語句的基本形式可分為兩種： （1） if (表達式) 語句 其執(zhí)行過程是，首先計算表達式的值，若不為 0，條件判斷為真，則執(zhí)行( )后 面的語句，否則，if 語句中止執(zhí)行，即不執(zhí)行( )后面的語句。 （2） if(表達式) 語句 1 else 語句 2 其執(zhí)行過程

13、是，首先計算表達式的值，若不為 0，條件判斷為真，則執(zhí)行( )后 面的語句，否則執(zhí)行語句 2。 2.1.3.2 if 語句嵌套 if 語句中的任何一個子句可以是任意可執(zhí)行語句，當(dāng)然也可以是一條 if 語 句，這種情況稱為 if 語句嵌套。當(dāng)出現(xiàn) if 語句的嵌套時，不管書寫格式如何， else 格式都將與它前面最靠近的未曾配對的 if 語句相配對，構(gòu)成一條完整的 if 語句。它的格式為： if(表達式 1) 語句 1； else if （表達式 2） 語句 2； else if （表達式 n） 語句 n； else 語句 n1； 2.1.3.3 while 和 do-while 語句 whil

14、e 語句用來實現(xiàn)“當(dāng)型”循環(huán)結(jié)構(gòu)，即先判斷表達式，然后判斷循環(huán)條 件是否成立。其一般形式為： do 語句；/循環(huán)體 while（條件表達式）； 其中要注意的是 while 后面的括號理是表達式而不是語句，表達式是沒有 分號的；而 do-while 中最后結(jié)束時要有分號。 2.1.4 循環(huán)結(jié)構(gòu) 2.1.4.1 for 語句 這種循環(huán)語句不僅用于循環(huán)次數(shù)已知的情況，還能用于循環(huán)次數(shù)預(yù)先不能 確定只給出循環(huán)結(jié)束條件的情況下。 for 語句的一般形式： for (表達式 1；表達式 2；表達式 3) 語句；/循環(huán)體 其執(zhí)行的過程有以下幾個步驟： 求解表達式 1； 求解表達式 2，若其值為真，則執(zhí)行 f

15、or 語句中指定的循環(huán)體語句，然后執(zhí) 行下面的第 3)步。若為假，則結(jié)束循環(huán)； 求解表達式 3； 轉(zhuǎn)回上面第 2）步繼續(xù)執(zhí)行； 循環(huán)結(jié)束，執(zhí)行 for 語句后面的其他語句。 2.1.4.2 Break 語句 該語句被限定使用在任一種循環(huán)語句和 switch 語句中，但 break 語句僅僅 退出包含該 break 語句的那層循環(huán)，即 break 語句不能使程序控制退出一層以 上的循環(huán)。 2.1.5 字符串處理函數(shù)字符串處理函數(shù) 字符比較函數(shù) strcmp 格式：strcmp(字符串 1，字符串 2) 它的功能是，比較字符串 1 和字符串 2。 如果字符串 1 小于字符串 2，該函數(shù)返回一個負整

16、數(shù)值；如果字符串 1 等于字 符串 2，該函數(shù)返回 0；如果字符串 1 大于字符串 2，該函數(shù)返回一個正整數(shù)值。 2.2 總體方案總體方案 顯然問題的鍵在于如何判定某個皇后所在的行、列、斜線上是否有別的皇 后；可以從矩陣的特點上找到規(guī)律，如果在同一行，則行號相同；如果在同一 列上，則列號相同；如果同在斜線上的行列值之和相同；如果同在/斜線上的 行列值之差相同；如果斜線不分方向，則同一斜線上兩皇后的行號之差的絕對 值與列號之差的絕對值相同。下圖是一個范例(圖 2-1 是八皇后排列方式在 vs6.0 中的結(jié)果顯示，圖 2-2 是棋盤中八皇后位置顯示) 將把皇后問題用三種方法表示出來,三種方法用 s

17、witch 語句連接. 圖 2-1 “1”作為皇后 圖 2-2 棋盤中的八皇后位置顯示 3 3 模塊及算法設(shè)計模塊及算法設(shè)計 3.1 算法描述算法描述 3.1.1 遞歸法 遞歸是指函數(shù)/過程/子程序在運行過程序中直接或間接調(diào)用自身而產(chǎn)生的重 入現(xiàn)像. 遞歸算法一般用于解決三類問題： (1)數(shù)據(jù)的定義是按遞歸定義的。(Fibonacci函數(shù)) (2)問題解法按遞歸算法實現(xiàn)。(回溯) (3)數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。(樹的遍歷，圖的搜索) 能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問題，設(shè)法 將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構(gòu)造出大問題的解， 并且這些規(guī)模較小的

18、問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的 問題，并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解。 3.1.2 回溯法 回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法。按選優(yōu)條件 向前搜索，以達到目標。但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到 目標，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足 回溯條件的某個狀態(tài)的點稱為“回溯點”。 可用回溯法求解的問題P，通常要能表達為：對于已知的由n元組 (x1，x2，xn)組成的一個狀態(tài)空間E=(x1，x2，xn)|xiSi ，i=1，2，n，給定關(guān)于n元組中的一個分量的一個約束集D，要求E中滿足 D的全部約束條件的所有

19、n元組。其中Si是分量xi的定義域，且 |Si| 有限， i=1，2，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。 回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為n的帶權(quán)有序樹 T，把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問題P的所有解。樹T類似于檢索 樹，它可以這樣構(gòu)造： 設(shè)Si中的元素可排成xi(1) ，xi(2) ，xi(mi-1) ，|Si| =mi，i=1，2，n。從根開始，讓T的第I層的每一個結(jié)點都有mi個兒子。這 mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+1(1) ，xi+1(2) ，xi+1(mi) ，i=0，1，2，n-1。照這種構(gòu)

20、造方式，E中的一個n元組 (x1，x2，xn)對應(yīng)于T中的一個葉子結(jié)點，T的根到這個葉子結(jié)點的路徑上 依次的n條邊的權(quán)分別為x1，x2，xn，反之亦然。另外，對于任意的0in- 1，E中n元組(x1，x2，xn)的一個前綴I元組(x1，x2，xi)對應(yīng)于T中的一 個非葉子結(jié)點，T的根到這個非葉子結(jié)點的路徑上依次的I條邊的權(quán)分別為 x1，x2，xi，反之亦然。特別，E中的任意一個n元組的空前綴( )，對應(yīng)于T 的根。 因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結(jié)點，要求從T 的根到該葉子結(jié)點的路徑上依次的n條邊相應(yīng)帶的n個權(quán)x1，x2，xn滿足約 束集D的全部約束。在T中搜索所要求的

21、葉子結(jié)點，很自然的一種方式是從根出 發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組(x1i)、 前綴2元組(x1，x2)、，前綴I元組(x1，x2，xi)，直到i=n為止。 在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結(jié) 點被稱為問題P的狀態(tài)結(jié)點；樹T上的任意一個葉子結(jié)點被稱為問題P的一個解 狀態(tài)結(jié)點；樹T上滿足約束集D的全部約束的任意一個葉子結(jié)點被稱為問題P的 一個回答狀態(tài)結(jié)點，它對應(yīng)于問題P的一個解。 3.1.3 窮舉法 顧名思義，窮舉法就是通過把需要解決問題的所有可能情況逐一試驗來找 出符合條件的解的方法，對于許多毫無規(guī)律的問題而言，窮舉法用時間上的

22、犧 牲換來了解的全面性保證，尤其是隨著計算機運算速度的飛速發(fā)展，窮舉法的 形象已經(jīng)不再是最低等和原始的無奈之舉，比如經(jīng)常有黑客在幾乎沒有任何已 知信息的情況下利用窮舉法來破譯密碼，足見這種方法還是有其適用的領(lǐng)域的。 可是，在實際生活中，只有很少的一些問題是真正意義上的“毫無規(guī)律”，其余 的大多數(shù)仍有內(nèi)在規(guī)律可循，對于這些問題，使用窮舉法在效率上就顯得比較 低下，而在一些對速度要求較高的區(qū)域和規(guī)模較大的問題上，效率的低下往往 是致命的。 3.23.2詳細流程圖詳細流程圖 數(shù)據(jù)初始化 從當(dāng)前點當(dāng)前方 向開始，判斷能 否向前走 結(jié)束程序 向前走一步 （入棧） 是否已到達目 標位置 輸出結(jié)果 新位置作

23、為 當(dāng)前點 方向數(shù)加 1 方向數(shù)是否 超界 退回一步 （退棧） 是否已經(jīng)回 到起點 能 否 否 否是 是 是 否 圖 3-3 解決八皇后問題的基本流程圖 4.4.代碼編寫代碼編寫 八皇后問題是在限制條件下的排序問題 include/數(shù)據(jù)流輸入/輸出 #include/參數(shù)化輸入/輸出 #include/定義雜項函數(shù)及內(nèi)存分配函數(shù) #include/定義輸入/輸出函數(shù) /*-*/ /*-方法一：遞歸法-*/ /*-*/ / static： 避免命名有沖突 /棋盤初始化時，空格的地方為*，放置皇后的地方為 static char Queen88; static int a8; /數(shù)組ai：ai表示

24、第i個皇后放置的列,i的范圍：- -8 static int b15; /主對角線數(shù)組 static int c15; /從對角線數(shù)組，根據(jù)程序的運行，去決定主從對角線是 否放入皇后 static int iQueenNum=0; /記錄總的棋盤狀態(tài)數(shù) static int iNum=1; void iQueen(int i); /參數(shù)i代表行 void measure1() int iLine; /橫行 int iColumn; /縱行 for(iLine=0;iLine8;iLine+) aiLine=0; /列標記初始化，表示無列沖突 for(iColumn=0;iColumn8;iCo

25、lumn+) QueeniLineiColumn=*; for(iLine=0;iLine15;iLine+) /主、從對角線標記初始化，表示 沒有沖突 biLine=ciLine=0; iQueen(0); ; void iQueen(int i) /i為當(dāng)前處理的行 int iColumn; for(iColumn=0;iColumn8;iColumn+) if(aiColumn=0 /放皇后 aiColumn=1; /標記，下一次該列上不能放皇后 bi-iColumn+7=1; /標記，下一次該主對角線上不能放皇 后 ci+iColumn=1; /標記，下一次該從對角線上不能放皇 后 i

26、f(i7) iQueen(i+1); /如果行還沒有遍歷(沿著某條搜索路線， 依次對樹中每個結(jié)點均做一次且僅做一次訪問)完，進入下一行 else /否則輸出 int iLine; /輸出棋盤狀態(tài) int iColumn; cout(遞歸法)皇后擺放方式的第iNum種情況為： endl; for(iLine=0;iLine8;iLine+) for(iColumn=0;iColumn8;iColumn+) coutsetw(2)QueeniLineiColumn; coutendl; coutiNum: ; for(iLine=0;iLine8;iLine+) for(iColumn=0;iCo

27、lumn8;iColumn+) if(QueeniLineiColumn=) cout(iLine+1,iColumn+1); coutnul); /從程序里調(diào)用pause命令,一 個結(jié)果一個結(jié)果地看 iNum+; coutendl; /如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，則回溯， 重新標記 QueeniiColumn=*; aiColumn=0; bi-iColumn+7=0; ci+iColumn=0; / if ends /*-*/ /*-方法二：運用類-*/ /*-*/ /自定義一個類：CQueen class cQueen int aQueen8; /可以在類外訪

28、問的私有成員(默認) int sum; public: /只能被該類的成員函數(shù)所訪問的公有成員 cQueen(); /構(gòu)造函數(shù)：確保每個對象正確地初始化 int judge(int x,int y); void show(); void step(); ; cQueen:cQueen()/通過構(gòu)造函數(shù)對aQueen1-8初始化 sum=0; for(int i=0;i8;i+) aQueeni=0; int cQueen:judge(int x,int y) /判斷皇后擺放位置是否有沖突，如果沒有 沖突，則返回；如果有沖突，則返回 for(int i=0;ix;i+) if(aQueeni=y

29、 | aQueeni+x-i=y | aQueeni-x+i=y) return 0; return 1; void cQueen:step() /一步一步進行查找擺放 int x=0,y=0;/標記皇后所在鍵盤位置，x代表列，y代表行（相當(dāng)于坐標） while(aQueen08) while(y8) if(judge(x,y) /調(diào)用類函數(shù)judge(x,y),如果 aQueen1-8都已經(jīng)標記，則執(zhí)行該語句 aQueenx=y; /擺放皇后 x+; /進行下一列時 y=0; /y進行重置 else /否則，進入下一行 y+; /當(dāng)執(zhí)行到最后一行時，繼續(xù)執(zhí)行下一 個if語句 if(y=8 e

30、lse if(aQueen0!=7) y=+aQueen-x; else aQueen0=8; if(x=8) /最后一列 show(); /x,y從至結(jié)束,大循環(huán)結(jié)束 if(aQueen-x!=7) y=+aQueenx; else y=+aQueen-x; void cQueen:show()/輸出棋盤狀態(tài) cout(非遞歸法)皇后擺放方式的第+sum種情況：endl; for(int i=0;i8;i+) /輸出八皇后的各種狀態(tài)，有皇后的位置用 表示， 沒有皇后的位置用* 表示 for(int j=0;jaQueeni;j+) coutsetw(2)*; coutsetw(2); for

31、(j+;j8;j+) coutsetw(2)*; coutendl; coutsum: ; for(int k=0;k8;k+) cout(k+1,aQueenk+1); coutendlendl; / system(pause);/從程序里調(diào)用pause命令,一個結(jié)果一個結(jié)果地看 void measure2() cQueen a; a.step(); /*-*/ /*-方法三:窮舉法-*/ /*-*/ /使用優(yōu)化后的窮舉法,用遞歸實現(xiàn)N層窮舉,每調(diào)用一次窮舉函數(shù)則窮舉一列 const int LINE=8;/const定義整新型常量LINE和ROW(8*8的棋盤) const int ROW

32、=8; void queen(int row,int rec);/row為當(dāng)前窮舉的列，rec記錄已窮舉的 信息，rec3=2代表(3,2)已放下棋子 bool isqueen(int i,int rec,int row);/判斷當(dāng)前i是否與已放下的棋子能 相互攻擊 void printqueen(int rec);/輸出符合條件的棋子擺放方式 void measure3() int rec9=0;/記錄窮舉信息數(shù)組 queen(1,rec);/執(zhí)行八皇后 system(pause); void queen(int row,int rec)/八皇后函數(shù) int tmprecROW+1=0; /

33、向下一列窮舉傳遞信息時使用tmprec,不丟失rec的記錄 for(int i=1;i=row;i+) tmpreci=reci;/復(fù)制數(shù)組 if (row!=ROW)/不是最后一列時(第ROW列即為最后一列) for (i=1;i=ROW;i+) if(isqueen(i,rec,row) /i與已放下的棋子不能相互攻擊時 tmprecrow=i; queen(row+1,tmprec);/繼續(xù)窮舉下一列 else/最后一列時 for (i=1;i=ROW;i+) if(isqueen(i,rec,row)/i與已放下的棋子不能相互攻擊時 tmprecrow=i; printqueen(tm

34、prec);/輸出符合條件的棋子擺放方式 bool isqueen(int i,int rec,int row)/判斷當(dāng)前i是否與已放下的棋子能 相互攻擊 /(row,i)即是此次窮舉出來的棋子的坐標 if (row=1) return 1;/第一列 for(int j=1;jrow;j+) if(recj=i|recj=i+row-j|recj=i-row+j)/如果(有棋子在 同一直線|有棋子在同一斜線) return 0; return 1; void printqueen(int rec)/輸出符合條件的棋子擺放方式 char qLINE+1ROW+1=0; static int nu

35、m=1;/記錄已輸出符合條件的棋盤數(shù)量 for (int i=1;i=LINE;i+) for (int j=1;j=ROW;j+) if(reci!=j) qij=*; else qij=; /將一維記錄轉(zhuǎn)換成LINE*ROW的矩陣，方便打印 cout(窮舉法)皇后擺放方式第num種情況:endl;/輸 出數(shù)量 for (i=1;i=ROW;i+) for (int j=1;j=ROW;j+) coutsetw(2)qij; coutendl; coutnum: ; for (i=1;i=ROW;i+) for (int j=1;j=ROW;j+) if (reci=j) cout(i,j)

36、; coutendlendl; num+; / system(pause); void menu() /輸出界面 coutt _ endl; coutt-endl; coutt endl; coutt 八皇后問題 endl; coutt = endl; coutt 1.方法一： 遞歸法 endl; coutt 2.方法二： 運用類 endl; coutt 3.方法三： 窮舉法 endl; coutt 0.后退 endl; coutt endl; coutt 請選擇(1、2，或者0)： endl; coutt-endl; coutt_endl; int main()/主函數(shù) for(;) men

37、u(); coutendl; coutnumber; switch(number) case 1: measure1();break; case 2: measure2();break; case 3: measure3();break; case 0: return 0; default: cout抱歉，沒有該選項，請重新作出選擇!endl; return 0; 5 程序調(diào)試分析程序調(diào)試分析 1)運行時有些函數(shù)的頭文件未定義，導(dǎo)致無法進行編譯；而且在調(diào)試時有 些頭文件的使用范疇弄混淆了； 2)開始編第一種方法（遞歸回溯）時，for與if的循環(huán)嵌套未能很好掌握， 導(dǎo)致幾次調(diào)試都出現(xiàn)比較嚴重的錯

38、誤；且在運用該方法時，未能將八皇后問題 的具體思路搞清，沒有考慮“如果前次的皇后放置導(dǎo)致后面的放置無論如何都不 能滿足要求”的問題； 3)在統(tǒng)計方法的個數(shù)時，未將累加的那個整型變量進行初始化，導(dǎo)致無法 顯示，八皇后擺放的是“第X種情況”，也無法統(tǒng)計出八皇后的排列方式是否一定 是92種情況。 4)在第三種方法(窮舉)編譯時，開始我把二維數(shù)組定義成整型，但其后在 輸出棋盤格式時，更本無法調(diào)試成功，出現(xiàn)了類型之間的沖突，因為在輸出時， 我又給那二維數(shù)組付成了字符型； 5)未用setw( )函數(shù)時，顯示的結(jié)果相當(dāng)難看，所定義的標志符都緊靠在一 起；多加了一個換行符后，各種情況的間距增大，閱讀時舒服多了

39、； 6)如果將92種情形全部打印，則前面的幾十種情況將無法顯示出，要想看 到前面的狀態(tài)，必須添加一個控制語句，使其能一個一個的輸出。 6 運行與測試運行與測試 開始運行界面，如圖6-1所示 輸入1時,按enter后如圖 6-2所示; 輸入2時,按enter后如圖6-3所示; 輸入3時,按enter后如圖6-4所示。 輸入0時,按enter后如圖6-5所示。 圖6-1 八皇后運行界面 （這是把皇后程序進入后的歡迎界面，使用者可以根據(jù)需要，選擇1,2，3或者0來進 行相應(yīng)的活動） 圖 6-2 遞歸回溯法界面 （這是把皇后第一種方法運行后顯示的界面，其中*是棋盤中棋子的位置，是棋盤 中皇后的位置，坐

40、標表示在當(dāng)前情況下皇后所處位置） 圖6-3 非遞歸界面 （這是把皇后第二種方法運行后顯示的界面，其中*是棋盤中棋子的位置，是棋盤 中皇后的位置，坐標表示在當(dāng)前情況下皇后所處位置） 圖6-4 窮舉遞歸法界面 （這是把皇后第三種方法運行后顯示的界面，其中*是棋盤中棋子的位置，是棋盤 中皇后的位置，坐標表示在當(dāng)前情況下皇后所處位置） 圖6-4 退出界面 （此時，按任意鍵便可以退出八皇后的運行界面） 總總 結(jié)結(jié) 就編寫的程序而言，雖然能達到預(yù)期的結(jié)果，但在運行時所需的時間比較長， 而且總體結(jié)構(gòu)還不夠簡潔，不太容易去理解。許多問題還需要繼續(xù)研究，許多 技術(shù)還需要更多的改進。去圖書館借了不少書，也去網(wǎng)上看

41、了些資料，只是對 大概的知識有了點了解，但還是很難著手于寫代碼，后來就按照老師說的，先 搞清楚原理，再考慮如何去實現(xiàn)！后來又去上網(wǎng)查看相關(guān)資料，又到圖書館借 了很多書看，總算有頭緒了。但在調(diào)試過程中，還是遇到了很多困難，后來通 過了很多同的幫助才把問題解決了。 通過這次的課程設(shè)計，讓我了解了八皇后這一經(jīng)典的問題。同時讓我更好地 掌握了棧思想以及一維數(shù)組等等知識,以及一些書本上沒有的東西，這對我以后 的學(xué)習(xí)生涯以及將來步入社會起到很大的幫助。這次課程設(shè)計雖然花了我很多 時間和精力，但很值得,因為它對我能力提高起到很大幫助。這次課程設(shè)計也提 醒我以前知識的匱乏,它給我敲響了警鐘,讓我意識到自己基礎(chǔ)的不扎實.當(dāng)然這 次實驗還是有很多問題的。比如程序設(shè)計的界面不夠好，一些程序并非自己所 寫,而是修改某些程序而成,但這些不該,在下次課程設(shè)計時不會再發(fā)生. 在編寫代碼時，我希望能隨機選擇一數(shù) X(192)后