實(shí)驗(yàn)二八皇后問題

《實(shí)驗(yàn)二八皇后問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、2009級數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)二棧和隊(duì)列學(xué)生姓名：班級：班內(nèi)序號：學(xué)號：日期：一、實(shí)驗(yàn)要求1．實(shí)驗(yàn)?zāi)康?進(jìn)一步掌握指針、模板類、異常處理的使用；掌握棧的操作的實(shí)現(xiàn)方法；掌握隊(duì)列的操作的實(shí)現(xiàn)方法；培養(yǎng)使用棧解決實(shí)際溫特的能力；培養(yǎng)使用隊(duì)列解決實(shí)際問題的能力；2．實(shí)驗(yàn)內(nèi)容利用棧結(jié)構(gòu)是八皇后問題。八皇后問題：在8X8的棋盤上放置8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列、同一斜線上。3．代碼要求必須有異常處理，保持良好的編程風(fēng)格，遞歸程序注意調(diào)用的過程，防止棧溢出。二、程序分析1．創(chuàng)建棋盤constintMAXSIZE=8;//棋盤大

2、小intchess[MAXSIZE][MAXSIZE]={0};introw;intcol;2解決個行、列、對角線上是否有皇后的方法intSolve(){stackstack;intcol[MAXSIZE]={0},md[2*MAXSIZE-1]={0},sd[2*MAXSIZE-1]={0};//互斥標(biāo)志，表示同一列及對角線上是否有皇后，intstr,stc,i,j;intscount=0;NodetopNode;for(i=0;i

3、.isMarked=false;stack.push(topNode);}以行為單位回溯while(!stack.empty()){topNode=stack.top();str=topNode.row;stc=topNode.col;if(topNode.isMarked==false){//如果棧頂元素的位置并沒有確立if(col[stc]

4、

5、md[str-stc+MAXSIZE-1]

6、

7、sd[str+stc]){//如果同一列或同一對角線上已有皇后，則退回*/stack.pop();}else{//占據(jù)這個位置，設(shè)置列、對角線上的互斥標(biāo)志col[stc]=

8、1;md[str-stc+MAXSIZE-1]=1;sd[str+stc]=1;//標(biāo)記棧頂元素的isMarked值topNode.isMarked=true;stack.pop();stack.push(topNode);chess[str][stc]=1;//標(biāo)記棋盤對應(yīng)位置if(str==MAXSIZE-1){//如果此時已經(jīng)到達(dá)最后一行,則表示此種布局方法是成功的,輸出相關(guān)信息cout<<"Asolutionis:"<

9、){cout<<"("<

10、+stc]=0;chess[str][stc]=0;stack.pop();}}returnscount;}三、運(yùn)行結(jié)果測試結(jié)果為92種，把行列以坐標(biāo)的形式列出來了，結(jié)果正確。四、總結(jié)這次編寫主要是考察用棧解決實(shí)際問題的能力。以及遞歸的運(yùn)用。實(shí)驗(yàn)中要運(yùn)用到回溯。整體上講對許多方面都起到了鍛煉的作用。問題的難點(diǎn)是怎樣判斷行。列。對角斜線上有沒有八皇后。通過這次的實(shí)驗(yàn)我發(fā)現(xiàn)了自己還有很多很多的不足，考慮問題思路不過清晰周全，許多基礎(chǔ)沒有掌握好，以后還需多多努力。