實驗二八皇后問題

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

1、2009級數(shù)據結構實驗報告實驗名稱：實驗二棧和隊列學生姓名：班級：班內序號：學號：日期：一、實驗要求1．實驗目的:進一步掌握指針、模板類、異常處理的使用；掌握棧的操作的實現(xiàn)方法；掌握隊列的操作的實現(xiàn)方法；培養(yǎng)使用棧解決實際溫特的能力；培養(yǎng)使用隊列解決實際問題的能力；2．實驗內容利用棧結構是八皇后問題。八皇后問題：在8X8的棋盤上放置8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列、同一斜線上。3．代碼要求必須有異常處理，保持良好的編程風格，遞歸程序注意調用的過程，防止棧溢出。二、程序分析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};//互斥標志，表示同一列及對角線上是否有皇后，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{//占據這個位置，設置列、對角線上的互斥標志col[stc]=

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

9、){cout<<"("<

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