資源描述:
《八皇后問(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)題的條件