數(shù)據(jù)結(jié)構(gòu)課程實踐.doc

課程實踐數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告學(xué)校:哈爾濱理工大學(xué)學(xué)院：管理學(xué)院專業(yè)：信息管理與信息系統(tǒng)姓名：蘇雅班級：信管112學(xué)號：1106040213N皇后問題一、設(shè)計要求與分析 1.設(shè)計要求在一個n*n的棋盤上放置n個皇后，要求放置的n個皇后不會互相吃掉；皇后棋子可以吃掉它所在的那一行、那一列，以及那兩條對角線上的任何棋子。 2設(shè)計分析此問題由八皇后問題演變而來，是八皇后問題的升級版，你可以隨意輸入一個比4大的數(shù)字，本程序?qū)⒆詣忧蟪鱿嚓P(guān)的某皇后問題。回溯算法是嘗試搜索算法中最為基本的一種算法，并采用了一種“走不通就掉頭”的思想，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回，嘗試跌的路徑。解決8皇后的算法有多種，其中加約束條件的枚舉算法擁有最好的可讀性，也能從中體會到回溯的思想，但是它職能解決皇后“個數(shù)為常量”的問題，卻不能解決任意的n皇后問題，因此也不是典型的回溯算法模型。非遞歸算法可以說是典型的回溯算法模型但是對于回溯算法，更方便的是用遞歸控制方式實現(xiàn)，用這種方法可以解決任意的n皇后問題。算法思想同樣實現(xiàn)用深度優(yōu)先搜索，并在不滿足約束條件時及時回溯二、算法求精這個問題包括了行，列，兩條對角線；列：規(guī)定每一列放一個皇后，不會造成列上的沖突；行：當(dāng)?shù)趇行被某個皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以i為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；對角線：對角線有兩個方向。在這我把這兩條對角線稱為：主對角線和從對角線。在同一對角線上的所有點（設(shè)下標(biāo)為(i,j)），要么(i+j)是常數(shù)，要么(i-j)是常數(shù)。因此，當(dāng)?shù)趇個皇后占領(lǐng)了第j列后，要同時把以(i+j)、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。/*-回溯法-*/ static： 避免命名有沖突/棋盤初始化時，空格的地方為+，放置皇后的地方為?static char Queen2020; static int a20; /數(shù)組ai：ai表示第i個皇后放置的列,i的范圍：-8static int b40; /主對角線數(shù)組static int c40; /從對角線數(shù)組，根據(jù)程序的運行，去決定主從對角線是否放入皇后static int iQueenNum=0; /記錄總的棋盤狀態(tài)數(shù)static int Num=1;int n;void iQueen(int row); /參數(shù)i代表行void location() int row; /橫行int cow; /縱行 for(row=0;rown;row+) arow=0; /列標(biāo)記初始化，表示無列沖突 for(cow=0;cown;cow+) Queenrowcow=+; for(row=0;row2*n;row+) /主、從對角線標(biāo)記初始化，表示沒有沖突brow=crow=0; iQueen(0);void iQueen(int row) /row為當(dāng)前處理的行 int cow; for(cow=0;cown;cow+) if(acow=0&brow-cow+n-1=0&crow+cow=0) /如果無沖突 Queenrowcow=?; /放皇后acow=1; /標(biāo)記，下一次該列上不能放皇后 brow-cow+n-1=1; /標(biāo)記，下一次該主對角線上不能放皇后 crow+cow=1; /標(biāo)記，下一次該從對角線上不能放皇后if(rown-1) iQueen(row+1); /如果行還沒有遍歷(沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問)完，進入下一行else /否則輸出 int row; /棋盤狀態(tài)int cow；coutn個皇后擺放位置的第Num種情況為：endl; for(row=0;rown;row+) /棋盤的輸出 for(cow=0;cown;cow+) coutsetw(2)Queenrowcow; coutendl; cout皇后位置坐標(biāo): ; /坐標(biāo)的輸出 for(row=0;rown;row+) for(cow=0;cown;cow+) if(Queenrowcow=?)cout(row+1,cow+1); coutendl;Num+;coutendl;n皇后問題解的情況N=1 X=(1)N=2 無解N=3 無解N=4 X1=(2,4,1,3);X2=(3,1,4,2)N=5 X1=(1,3,5,2,4);X2=(1,4,2,5,3);X3=(2,4,1,3,5);X4=(2,5,3,1,4)；X5=(3,1,4,2,5);X6=(3,5,2,4,1);X7=(4,1,3,5,2);X8=(4,2,5,3,1)；X9=(5,2,4,1,3);X10=(5,3,1,4,2)N=6 X1=(2,4,6,1,3,5);X2=(3,6,2,5,1,4);X3=(4,1,5,2,6,3);X4=(5,3,1,6,4,2)N=7 40個解N=8 92個解三、完整的算法實現(xiàn)#include/數(shù)據(jù)流輸入/輸出#include/參數(shù)化輸入/輸出#include/定義雜項函數(shù)及內(nèi)存分配函數(shù)#include/定義輸入/輸出函數(shù)/*-回溯法-*/ static： 避免命名有沖突/棋盤初始化時，空格的地方為+，放置皇后的地方為?static char Queen2020; static int a20; /數(shù)組ai：ai表示第i個皇后放置的列,i的范圍：-8static int b40; /主對角線數(shù)組static int c40; /從對角線數(shù)組，根據(jù)程序的運行，去決定主從對角線是否放入皇后static int iQueenNum=0; /記錄總的棋盤狀態(tài)數(shù)static int Num=1;int n;void iQueen(int row); /參數(shù)i代表行void location() int row; /橫行int cow; /縱行 for(row=0;rown;row+) arow=0; /列標(biāo)記初始化，表示無列沖突 for(cow=0;cown;cow+) Queenrowcow=+; for(row=0;row2*n;row+) /主、從對角線標(biāo)記初始化，表示沒有沖突brow=crow=0; iQueen(0);void iQueen(int row) /row為當(dāng)前處理的行 int cow; for(cow=0;cown;cow+) if(acow=0&brow-cow+n-1=0&crow+cow=0) /如果無沖突 Queenrowcow=?; /放皇后acow=1; /標(biāo)記，下一次該列上不能放皇后 brow-cow+n-1=1; /標(biāo)記，下一次該主對角線上不能放皇后 crow+cow=1; /標(biāo)記，下一次該從對角線上不能放皇后if(rown-1) iQueen(row+1); /如果行還沒有遍歷(沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問)完，進入下一行else /否則輸出 int row; /棋盤狀態(tài)int cow; coutn個皇后擺放位置的第Num種情況為：endl; for(row=0;rown;row+) /棋盤的輸出 for(cow=0;cown;cow+) coutsetw(2)Queenrowcow; coutendl; cout皇后位置坐標(biāo): ; /坐標(biāo)的輸出 for(row=0;rown;row+) for(cow=0;cown;cow+) if(Queenrowcow=?)cout(row+1,cow+1); coutendl;Num+;coutendl;/如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，則回溯，重新標(biāo)記Queenrowcow=+; acow=0; brow-cow+n-1=0; crow+cow=0; / if endsvoid show() /輸出界面 system(cls);coutendl;coutt *n皇后問題實驗設(shè)計* endl;coutt *endl;coutt * n皇后問題 * endl;coutt * * endl;coutt * * endl;coutt * 1. 回溯算法 0.退出 * endl;coutt * * endl;coutt * * endl;coutt * 請選擇 1或者0 * endl; coutt * endl;coutt * endl;int main()/主函數(shù) system(color 5E); for(;) A: show(); cout