c++利用棧解決八皇后問題-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

XX級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)二——棧和隊(duì)列學(xué)生姓名：韓博班級(jí)：2009211121班內(nèi)序號(hào)：01學(xué)號(hào)：09210604日期：10.11.251．實(shí)驗(yàn)要求【實(shí)驗(yàn)?zāi)康摹窟M(jìn)一步掌握指針、模板類、異常處理的使用掌握棧的操作的實(shí)現(xiàn)方法掌握隊(duì)列的操作的實(shí)現(xiàn)方法學(xué)習(xí)使用棧解決實(shí)際問題的能力學(xué)習(xí)使用隊(duì)列解決實(shí)際問題的能力【實(shí)驗(yàn)內(nèi)容】利用棧結(jié)構(gòu)實(shí)現(xiàn)八皇后問題。八皇后問題19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。他的問題是：在8*8的棋盤上放置8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列、同一斜線上。請(qǐng)?jiān)O(shè)計(jì)算法打印所有可能的擺放方法。提示：1、可以使用遞歸或非遞歸兩種方法實(shí)現(xiàn)2、實(shí)現(xiàn)一個(gè)關(guān)鍵算法：判斷任意兩個(gè)皇后是否在同一行、同一列和同一斜線上2.程序分析2.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：棧（遞歸）2.2關(guān)鍵算法分析【設(shè)計(jì)思想】由于八皇后問題，可以分解成算法相同的子問題，所以使用遞歸的方法【偽代碼】輸入皇后個(gè)數(shù)nk=1判斷k是否大于n3.1是：打印一組可能3.2否：循環(huán)行位置1~n判斷該位置是否符合要求，若符合記錄q[k]的坐標(biāo)y值k+1重復(fù)3【關(guān)鍵算法】1、遞歸voidQueen::queen(intn)//遞歸函數(shù)的具體定義{if(n==Number+1)//如果一到八行都已安排了皇后，則輸出皇后位置{Print();return;}for(inti=1;i<=Number;i++)//從行號(hào)n=1開始逐個(gè)試探，即從i=1列開始{Site[n]=i;if(IsValid(n))//如果第n行可以取第i列上的位置，則開始試探第n+1行{queen(n+1);}intQueen::IsValid(intn)//判定位置函數(shù)的具體定義，當(dāng)皇后位于第n行時(shí){for(intm=1;m<n;m++)//從m=1行皇后位置一直到m=n-1行皇后位置依次與第n行皇后位置進(jìn)行判斷{if(Site[m]==Site[n])return0;//當(dāng)m行與n行皇后位于同一列時(shí)，不符合要求，返回0if(abs(Site[m]-Site[n])==abs(m-n))return0;//當(dāng)m行與n行皇后位于同一對(duì)角線時(shí)，不符合要求，返回0}return1;//第n行皇后位置符合要求，返回1};voidQueen::Print()//輸出函數(shù)的具體定義{count++;//解法的號(hào)數(shù)for(inti=1;i<=Number;i++){cout<<"("<<i<<","<<Site[i]<<")"<<"";}//依次輸出皇后行坐標(biāo)與列坐標(biāo)cout<<"No."<<count<<endl;//第count種解法};2.3其他源代碼：時(shí)間復(fù)雜度：O(n)#include<iostream>#include<cmath>usingnamespacestd;#defineN10classQueen{public: Queen(){num=-1;} voidPrint(intn);//輸出皇后的排列，打出的數(shù)字為每個(gè)皇后的坐標(biāo) intCheck(inti,intk);//判斷位置是否符合要求 voidQueens(intk,intn);//遞歸調(diào)用 intcount();//計(jì)數(shù)private: intq[N]; intnum;};voidmain(){ QueenQ; intn; cout<<"請(qǐng)輸入Queen的數(shù)目(n>0):"<<endl; cin>>n; if(n>0) { cout<<"Queen可能的位置坐標(biāo):"<<endl; Q.Queens(1,n); cout<<"共有"<<Q.count()<<"種方法放置Queen"<<endl; } else cout<<"ERROR輸入數(shù)字錯(cuò)誤"<<endl;}voidQueen::Queens(intk,intn)//計(jì)算出皇后的排列，k是當(dāng)前皇后數(shù)量，n是數(shù)量上限{inti; if(k>n)//如果達(dá)到里要求的數(shù)量輸出皇后排列 {Print(n); count(); } else//否則在適當(dāng)?shù)奈恢锰砑右粋€(gè)新皇后 { for(i=1;i<=n;i++) if(Check(i,k))//判斷該行中該位置放置'皇后'是否符合要求 { q[k]=i;//記錄改行中該點(diǎn)的位置 Queens(k+1,n);//放置下一行的'皇后' } }}voidQueen::Print(intn){ inti; for(i=1;i<=n;i++) cout<<"("<<i<<","<<q[i]<<")"; cout<<endl;}intQueen::Check(inti,intk){ intj; j=1; while(j<k) { if((q[j]==i)||abs(q[j]-i)==abs(j-k))//判斷列，判斷斜線 return0;//不符合返回0 j++; } return1;//符合返回}intQueen::count(){ num++;