八皇后問(wèn)題實(shí)驗(yàn)報(bào)告 遞歸 非遞歸 java C語(yǔ)言 +分析

《八皇后問(wèn)題實(shí)驗(yàn)報(bào)告 遞歸 非遞歸 java C語(yǔ)言 +分析》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

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

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

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

4、人之一。1874年，S.岡德?tīng)柼岢隽艘粋€(gè)通過(guò)行列式來(lái)求解的方法。八皇后問(wèn)題出現(xiàn)在1990年代初期的著名電子游戲第七訪客中。設(shè)置一個(gè)三維數(shù)組，第一個(gè)下標(biāo)是皇后的行坐標(biāo)，第二個(gè)下標(biāo)是皇后的列坐標(biāo)，第三個(gè)下標(biāo)是殘卷號(hào)。相當(dāng)于有N張疊在一起的8*8棋盤(pán)，每張棋盤(pán)只在復(fù)制前面棋盤(pán)及皇后后加放置一個(gè)皇后。直到放滿(mǎn)8皇后后才是一張完整的8皇后圖，稱(chēng)完卷。這里實(shí)際操作時(shí)多加一行多加一列即第0行第0列，但這一行/列不作輸出，只是作此行/列有無(wú)皇后的參考?？偟膩?lái)說(shuō)現(xiàn)在解八皇后問(wèn)題的總體算法都是采用回溯法，也叫作窮搜法，再窮搜的時(shí)候去掉分支，減少不必要的運(yùn)算，對(duì)于八皇后問(wèn)題的求解，一

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

6、dowsserver200332位（3）編譯語(yǔ)言：Java，C語(yǔ)言2.2程序框架（1）MainQueen：實(shí)現(xiàn)可視化界面，可以選擇遞歸和非遞歸兩種算法得到八皇后問(wèn)題的解，并將答案打印出來(lái)。（2）QueenNR：采用非遞歸方法求解問(wèn)題。（3）QueenRS：采用遞歸方法求解問(wèn)題。（4）編譯C語(yǔ)言程序。2.3算法分析2.3.1總體算法分析算法的核心是回溯法，也稱(chēng)為試探法，它并不考慮問(wèn)題規(guī)模的大小，而是從問(wèn)題的最明顯的最小規(guī)模開(kāi)始逐步求解出可能的答案，并以此慢慢地?cái)U(kuò)大問(wèn)題規(guī)模，迭代地逼近最終問(wèn)題的解。這種迭代類(lèi)似于窮舉并且是試探性的，因?yàn)楫?dāng)目前的可能答案被測(cè)試出不可能

7、可以獲得最終解時(shí)，則撤銷(xiāo)當(dāng)前的這一步求解過(guò)程，回溯到上一步尋找其他求解路徑。為了能夠撤銷(xiāo)當(dāng)前的求解過(guò)程，必須保存上一步以來(lái)的求解路徑。當(dāng)撤銷(xiāo)之后滿(mǎn)足條件，就一直做下去，直到試探完所有的可能解?？偨Y(jié)如下：(1)設(shè)置初始化的方案（給變量賦初值，讀入已知數(shù)據(jù)等）。(2)變換方式去試探，若全部試完則轉(zhuǎn)(7)。(3)判斷此法是否成功（通過(guò)約束函數(shù)），不成功則轉(zhuǎn)(2)。(4)試探成功則前進(jìn)一步再試探。(5)正確方案還未找到則轉(zhuǎn)(2)。(6)已找到一種方案則記錄并打印。(7)退回一步（回溯），若未退到頭則轉(zhuǎn)(2)。(8)已退到頭則結(jié)束或打印無(wú)解另外一個(gè)關(guān)鍵就是對(duì)于每一個(gè)部分解

8、的判定，可歸納問(wèn)題的條件