八皇后課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告 C++

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

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

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

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

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

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

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

8、思想編寫(xiě)代碼，實(shí)現(xiàn)八皇后問(wèn)題的所有（92 種） 擺放情況。要求在 DOS 界面上顯示出每一種方式。 1.3 八皇后問(wèn)題課題要求八皇后問(wèn)題課題要求 編寫(xiě)代碼，用至少三種方法解決八皇后問(wèn)題。運(yùn)行程序后，顯現(xiàn)下面的參 考界面： 八皇后問(wèn)題 = 1方法一 2方法二 3方法三 請(qǐng)選擇（請(qǐng)選擇（1、2 或或 3，0：退出）：退出）： 圖 1-2 輸出界面實(shí)例 選擇一個(gè)菜單后，要求輸入棋盤(pán)的階層，即 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 輸出樣式實(shí)例 1.4 面對(duì)的問(wèn)題面對(duì)的問(wèn)題 需要用三種方法解決八皇后問(wèn)題，在這里需要查閱大量資料并多加練習(xí)，才 能成功編寫(xiě)程序。主要要解決下面的問(wèn)題： 沖突：包括列、行、兩條對(duì)角線； 1. 列：規(guī)定每一列放一個(gè)皇后，就不會(huì)造成列上的沖突； 2. 行：當(dāng)?shù)?i 行被某個(gè)皇后占據(jù)時(shí)，該行所有空格就都不能放置其他皇后； 3. 對(duì)角線：對(duì)角線有兩個(gè)方向，在同一對(duì)角線上的所有點(diǎn)都不能有沖突。 2 需求分析需求分析 2.1 涉及到的知識(shí)基礎(chǔ)涉及到的知識(shí)基礎(chǔ) 在本次的課程設(shè)計(jì)中，用到的知識(shí)點(diǎn)主要有：類(lèi)、函數(shù)、選擇結(jié)構(gòu)里的條

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、第i個(gè)皇后放置的列,i的范圍：- -8 static int b15; /主對(duì)角線數(shù)組 static int c15; /從對(duì)角線數(shù)組，根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是 否放入皇后 static int iQueenNum=0; /記錄總的棋盤(pán)狀態(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; /列標(biāo)記初始化，表示無(wú)列沖突 for(iColumn=0;iColumn8;iCo

25、lumn+) QueeniLineiColumn=*; for(iLine=0;iLine15;iLine+) /主、從對(duì)角線標(biāo)記初始化，表示 沒(méi)有沖突 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āo)記，下一次該列上不能放皇后 bi-iColumn+7=1; /標(biāo)記，下一次該主對(duì)角線上不能放皇 后 ci+iColumn=1; /標(biāo)記，下一次該從對(duì)角線上不能放皇 后 i

26、f(i7) iQueen(i+1); /如果行還沒(méi)有遍歷(沿著某條搜索路線， 依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn))完，進(jìn)入下一行 else /否則輸出 int iLine; /輸出棋盤(pán)狀態(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命令,一 個(gè)結(jié)果一個(gè)結(jié)果地看 iNum+; coutendl; /如果前次的皇后放置導(dǎo)致后面的放置無(wú)論如何都不能滿足要求，則回溯， 重新標(biāo)記 QueeniiColumn=*; aiColumn=0; bi-iColumn+7=0; ci+iColumn=0; / if ends /*-*/ /*-方法二：運(yùn)用類(lèi)-*/ /*-*/ /自定義一個(gè)類(lèi)：CQueen class cQueen int aQueen8; /可以在類(lèi)外訪

28、問(wèn)的私有成員(默認(rèn)) int sum; public: /只能被該類(lèi)的成員函數(shù)所訪問(wèn)的公有成員 cQueen(); /構(gòu)造函數(shù)：確保每個(gè)對(duì)象正確地初始化 int judge(int x,int y); void show(); void step(); ; cQueen:cQueen()/通過(guò)構(gòu)造函數(shù)對(duì)aQueen1-8初始化 sum=0; for(int i=0;i8;i+) aQueeni=0; int cQueen:judge(int x,int y) /判斷皇后擺放位置是否有沖突，如果沒(méi)有 沖突，則返回；如果有沖突，則返回 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() /一步一步進(jìn)行查找擺放 int x=0,y=0;/標(biāo)記皇后所在鍵盤(pán)位置，x代表列，y代表行（相當(dāng)于坐標(biāo)） while(aQueen08) while(y8) if(judge(x,y) /調(diào)用類(lèi)函數(shù)judge(x,y),如果 aQueen1-8都已經(jīng)標(biāo)記，則執(zhí)行該語(yǔ)句 aQueenx=y; /擺放皇后 x+; /進(jìn)行下一列時(shí) y=0; /y進(jìn)行重置 else /否則，進(jìn)入下一行 y+; /當(dāng)執(zhí)行到最后一行時(shí)，繼續(xù)執(zhí)行下一 個(gè)if語(yǔ)句 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()/輸出棋盤(pán)狀態(tài) cout(非遞歸法)皇后擺放方式的第+sum種情況：endl; for(int i=0;i8;i+) /輸出八皇后的各種狀態(tài)，有皇后的位置用 表示， 沒(mé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命令,一個(gè)結(jié)果一個(gè)結(jié)果地看 void measure2() cQueen a; a.step(); /*-*/ /*-方法三:窮舉法-*/ /*-*/ /使用優(yōu)化后的窮舉法,用遞歸實(shí)現(xiàn)N層窮舉,每調(diào)用一次窮舉函數(shù)則窮舉一列 const int LINE=8;/const定義整新型常量LINE和ROW(8*8的棋盤(pán)) 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、向下一列窮舉傳遞信息時(shí)使用tmprec,不丟失rec的記錄 for(int i=1;i=row;i+) tmpreci=reci;/復(fù)制數(shù)組 if (row!=ROW)/不是最后一列時(shí)(第ROW列即為最后一列) for (i=1;i=ROW;i+) if(isqueen(i,rec,row) /i與已放下的棋子不能相互攻擊時(shí) tmprecrow=i; queen(row+1,tmprec);/繼續(xù)窮舉下一列 else/最后一列時(shí) for (i=1;i=ROW;i+) if(isqueen(i,rec,row)/i與已放下的棋子不能相互攻擊時(shí) tmprecrow=i; printqueen(tm

34、prec);/輸出符合條件的棋子擺放方式 bool isqueen(int i,int rec,int row)/判斷當(dāng)前i是否與已放下的棋子能 相互攻擊 /(row,i)即是此次窮舉出來(lái)的棋子的坐標(biāo) 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;/記錄已輸出符合條件的棋盤(pán)數(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 八皇后問(wèn)題 endl; coutt = endl; coutt 1.方法一： 遞歸法 endl; coutt 2.方法二： 運(yùn)用類(lèi) endl; coutt 3.方法三： 窮舉法 endl; coutt 0.后退 endl; coutt endl; coutt 請(qǐng)選擇(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抱歉，沒(méi)有該選項(xiàng)，請(qǐng)重新作出選擇!endl; return 0; 5 程序調(diào)試分析程序調(diào)試分析 1)運(yùn)行時(shí)有些函數(shù)的頭文件未定義，導(dǎo)致無(wú)法進(jìn)行編譯；而且在調(diào)試時(shí)有 些頭文件的使用范疇弄混淆了； 2)開(kāi)始編第一種方法（遞歸回溯）時(shí)，for與if的循環(huán)嵌套未能很好掌握， 導(dǎo)致幾次調(diào)試都出現(xiàn)比較嚴(yán)重的錯(cuò)

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

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

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

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