八皇后問題實驗報告材料遞歸非遞歸javaC語言+分析報告

《八皇后問題實驗報告材料遞歸非遞歸javaC語言+分析報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、實用文檔數(shù)據(jù)結(jié)構(gòu)課程設計題目：八皇后問題指導教師：胡*學生院系：數(shù)學學院學生班級：信計*班學生姓名：黎*文學生學號：14070204**2016年12月30日文案大全實用文檔目錄一.功能以及需求分析31.1問題的由來和背景31.2問題的基本解決思路31.3問題的應用3二.總體設計42.1運行環(huán)境42.2程序框架42.3算法分析42.3.1總體算法分析42.3.2非遞歸算法分析62.3.3遞歸算法的分析6三.詳細設計63.1遞歸法的詳細設計63.2非遞歸法的詳細設計7四.具體實現(xiàn)及運行104.1QueenMainl類的實現(xiàn)：104.2QueenNR類：104.3QueenRS類：11

2、4.4C語言程序：11五.總結(jié)12六.代碼清單136.1Java代碼：136.2C語言源代碼：20文案大全實用文檔一.功能以及需求分析1.1問題的由來和背景八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出:在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。計算機發(fā)明后，有多種計算機語言可以解決此問題。八皇后問題是一個以國際象棋為背景的

3、問題：如何能夠在8×8的國際象棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處于同一條橫行、縱行或斜線上。八皇后問題可以推廣為更一般的n皇后擺放問題：這時棋盤的大小變?yōu)閚×n，而皇后個數(shù)也變成n。當且僅當n=1或n≥4時問題有解。1.2問題的基本解決思路八皇后問題最早是由國際西洋棋棋手馬克斯·貝瑟爾于1848年提出。之后陸續(xù)有數(shù)學家對其進行研究，其中包括高斯和康托，并且將其推廣為更一般的n皇后擺放問題。八皇后問題的第一個解是在1850年由弗朗茲·諾克給出的。諾克也是首先將問題推廣到更一般的n皇后擺放問題的人之一。1874年，S.岡德

4、爾提出了一個通過行列式來求解的方法。八皇后問題出現(xiàn)在1990年代初期的著名電子游戲第七訪客中。設置一個三維數(shù)組，第一個下標是皇后的行坐標，第二個下標是皇后的列坐標，第三個下標是殘卷號。相當于有N張疊在一起的8*8棋盤，每張棋盤只在復制前面棋盤及皇后后加放置一個皇后。直到放滿8皇后后才是一張完整的8皇后圖，稱完卷。這里實際操作時多加一行多加一列即第0行第0列，但這一行/列不作輸出，只是作此行/列有無皇后的參考?？偟膩碚f現(xiàn)在解八皇后問題的總體算法都是采用回溯法，也叫作窮搜法，再窮搜的時候去掉分支，減少不必要的運算，對于八皇后問題的求解，一般只能做出15皇后問題，有部分算法高手在有精良設

5、備的情況下算出了25皇后的解。受算法和硬件計算能力的影響，因為計算量為O(n!)，而且回溯法使用的內(nèi)存空間特別大，所以此問題的求解還有很多可以探究的地方，尤其是算法上的改進。1.3問題的應用八皇后問題可以用來解決地圖的著色問題，以及迷宮的求解問題，同時，八皇后問題是一個典型的回溯法求解問題，可以用它來類比很多和回溯法有關(guān)的問題。對于現(xiàn)在的DNA序列問題也可以從中得到啟發(fā)。文案大全實用文檔二.總體設計2.1運行環(huán)境（1）編譯環(huán)境：JDK1.8，以及eclipse，Mars4.5.2，VisualC++6.0（2）電腦系統(tǒng)：Windowsserver200332位（3）編譯語言：Jav

6、a，C語言2.2程序框架（1）MainQueen：實現(xiàn)可視化界面，可以選擇遞歸和非遞歸兩種算法得到八皇后問題的解，并將答案打印出來。（2）QueenNR：采用非遞歸方法求解問題。（3）QueenRS：采用遞歸方法求解問題。（4）編譯C語言程序。2.3算法分析2.3.1總體算法分析算法的核心是回溯法，也稱為試探法，它并不考慮問題規(guī)模的大小，而是從問題的最明顯的最小規(guī)模開始逐步求解出可能的答案，并以此慢慢地擴大問題規(guī)模，迭代地逼近最終問題的解。這種迭代類似于窮舉并且是試探性的，因為當目前的可能答案被測試出不可能可以獲得最終解時，則撤銷當前的這一步求解過程，回溯到上一步尋找其他求解路徑。

7、為了能夠撤銷當前的求解過程，必須保存上一步以來的求解路徑。當撤銷之后滿足條件，就一直做下去，直到試探完所有的可能解。總結(jié)如下：(1)設置初始化的方案（給變量賦初值，讀入已知數(shù)據(jù)等）。(2)變換方式去試探，若全部試完則轉(zhuǎn)(7)。(3)判斷此法是否成功（通過約束函數(shù)），不成功則轉(zhuǎn)(2)。(4)試探成功則前進一步再試探。(5)正確方案還未找到則轉(zhuǎn)(2)。(6)已找到一種方案則記錄并打印。(7)退回一步（回溯），若未退到頭則轉(zhuǎn)(2)。(8)已退到頭則結(jié)束或打印無解另外一個關(guān)鍵