八皇后課程設(shè)計實驗報告 C++_第1頁
八皇后課程設(shè)計實驗報告 C++_第2頁
八皇后課程設(shè)計實驗報告 C++_第3頁
八皇后課程設(shè)計實驗報告 C++_第4頁
八皇后課程設(shè)計實驗報告 C++_第5頁
已閱讀5頁,還剩31頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

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)后

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論