




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱: 算法分析與復(fù)雜性理論 實(shí)驗(yàn)項(xiàng)目名稱: 八皇后問(wèn)題 學(xué)院: 計(jì)算機(jī)與軟件學(xué)院 專業(yè): 軟件工程 指導(dǎo)教師: 楊烜 報(bào)告人: 學(xué)號(hào): 班級(jí): 15級(jí)軟工學(xué)術(shù)型 實(shí)驗(yàn)時(shí)間: 2015-12-08 實(shí)驗(yàn)報(bào)告提交時(shí)間: 2015-12-09 教務(wù)部制一實(shí)驗(yàn)?zāi)康?. 掌握選回溯法設(shè)計(jì)思想。2. 掌握八皇后問(wèn)題的回溯法解法。二實(shí)驗(yàn)步驟與結(jié)果實(shí)驗(yàn)總體思路:根據(jù)實(shí)驗(yàn)要求,通過(guò)switch選擇八皇后求解模塊以及測(cè)試數(shù)據(jù)模塊操作,其中八皇后模塊調(diào)用擺放皇后函數(shù)模塊,擺放皇后模塊中調(diào)用判斷模塊。測(cè)試數(shù)據(jù)模塊主要調(diào)用判斷模塊進(jìn)行判斷,完成測(cè)試。用一維數(shù)組保存每行擺放皇后的位置
2、,根據(jù)回溯法的思想遞歸討論該行的列位置上能否放置皇后,由判斷函數(shù)judge()判斷,若不能放置則檢查該行下一個(gè)位置。相應(yīng)結(jié)果和過(guò)程如下所示(代碼和結(jié)果如下圖所示)。回溯法的實(shí)現(xiàn)及實(shí)驗(yàn)結(jié)果:1、 判斷函數(shù)代碼1:procedure btrack_queen(n)/如果一個(gè)皇后能放在第k行和x(k)列,則返回true,否則返回false。globalx(1:k);integeri,ki1whilei0 dox(k)x(k)+1 /移到下一個(gè)位置while x(k)=n and not judge(k) do /判斷能否放置皇后x(k)x(k)+1repeatif x(k)=n /找到一個(gè)位置the
3、n if k=n /是一個(gè)完整的解嗎t(yī)hen print(x) /是,打印數(shù)組else kk+1;x(k)0 /轉(zhuǎn)向下一行endifelse kk-1 /否則,回溯上一行endifrepeatend btrack_queen實(shí)驗(yàn)結(jié)果:(圖1 回溯法解八皇后問(wèn)題)(圖2 回溯法解八皇后問(wèn)題)(圖3 測(cè)試數(shù)據(jù)結(jié)果)注:根據(jù)實(shí)驗(yàn)數(shù)組中保存的列坐標(biāo),對(duì)應(yīng)行坐標(biāo)順序輸入即可。實(shí)驗(yàn)中多加入了一組不滿足八皇后問(wèn)題的解。mfc可視化下八皇后的實(shí)現(xiàn)與結(jié)果:代碼3:/判斷是否符合八皇后問(wèn)題的解int cbfhoudlg:check(int row, int col) /看同行是否合法; for(int i=0;i
4、=col-1;i+) if(arowi=1)return 0; for(i=col+1;i8;i+) if(arowi=1)return 0; /看同列是否合法; for(i=0;i=row-1;i+) if(aicol=1)return 0; for(i=row+1;i=0&j= n-1) if(aij=1)return 0; -i;+j; i=row+1; j=col-1; while(i=0) if(aij=1)return 0; +i;-j; i=row-1;j=col-1; while(i=0&j=0) if(aij=1)return 0; -i;-j; i=row+1;j=col+
5、1; while(i=n-1)&j=n-1) if(aij=1)return 0; +i;+j; return 1; 實(shí)驗(yàn)結(jié)果:(圖4 八皇后的第1種解)(圖5 八皇后的第92種解)注:由于時(shí)間有限,這個(gè)月考試較多,程序還要很多地方需要完善。三實(shí)驗(yàn)分析與結(jié)論根據(jù)八皇后問(wèn)題的規(guī)則皇后不能放置在同行、同列及同一對(duì)角線上,進(jìn)而將問(wèn)題轉(zhuǎn)化為將第i個(gè)皇后放在第i行第xi列上(1i,xin),皇后間彼此不能同列及不同對(duì)角線表示為xi != xj,|ixi| != |jxj|。八皇后問(wèn)題的解法主要有枚舉法、非遞歸回溯法、遞歸回溯法這三種,枚舉法是將所以的可能組合都進(jìn)行判斷,時(shí)間復(fù)雜度為o(nn),適用于個(gè)數(shù)
6、n比較少的情況。而非遞歸回溯法采用深度優(yōu)先搜索策略判斷當(dāng)前位置是否符合該問(wèn)題的解,時(shí)間復(fù)雜度為o(n2),在實(shí)現(xiàn)大規(guī)模的n皇后問(wèn)題上性能更好。遞歸回溯法同樣采用深度優(yōu)先搜索策略,但在搜索到不滿足約束條件時(shí)能及時(shí)回溯,整體上提高了解題的效率。時(shí)間復(fù)雜度較非回溯法更低。四實(shí)驗(yàn)心得八皇后問(wèn)題以前也看過(guò),只是以前沒(méi)有將測(cè)試數(shù)據(jù)模塊和解八皇后問(wèn)題模塊整合到主函數(shù)中,后面也想到用mfc實(shí)現(xiàn)可視化求解,但是之前都沒(méi)學(xué)過(guò)mfc編程,根據(jù)網(wǎng)上的資料還是完成了較為基本的程序。這次實(shí)驗(yàn)確實(shí)學(xué)到很多東西,不光是提高了編程能力、代碼閱讀能力,更掌握了回溯法的遞歸求解思路。 附錄:代碼#include#include#i
7、nclude#define max 8using namespace std; int queenmax, sum=0; / max為棋盤(pán)最大坐標(biāo) /*輸出所有皇后的坐標(biāo) */void show_queen() cout( ; for(int i = 0; i max; i+) coutqueeni+1 ; cout)endl; sum+; /*判斷是否滿足八皇后問(wèn)題函數(shù)*/int judge(int n) for(int i = 0; i n; i+) / 檢查橫排和對(duì)角線上是否可以放置皇后 if(queeni = queenn | abs(queeni - queenn) = (n - i
8、) return 1; return 0;/*回溯嘗試皇后位置,n為橫坐標(biāo)*/void backtrack_queen(int n) for(int i = 0; i max; i+) queenn = i; /* 將皇后擺到當(dāng)前循環(huán)到的位置 */ if(!judge(n) if(n = max-1 ) show_queen(); /* 如果全部擺好,則輸出所有皇后的坐標(biāo) */ else backtrack_queen(n + 1); /* 否則繼續(xù)擺放下一個(gè)皇后 */ int main()while(1) int n;cout*endl;cout* 選擇相應(yīng)序號(hào)進(jìn)行操作: *endl;cout* 1.八皇后問(wèn)題 2.測(cè)試數(shù)據(jù) 0.退出 *endl;cout*n;switch(n)case 0: cout退出程序成功.endl;return 0; /一個(gè)程序兩個(gè)出口 case 1: cout八皇后問(wèn)題的解為:endl;backtrack_queen(0);cout共有sum個(gè)解endl;break;case 2: cout運(yùn)行測(cè)試數(shù)據(jù):endl;while(1) cout請(qǐng)輸入要測(cè)試的數(shù)據(jù):endl;for(int j=0;jqueenj; if(judge(max)=1) cout該數(shù)據(jù)是八皇后問(wèn)題的解en
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 烘培暑假活動(dòng)方案
- 煙花拍照活動(dòng)策劃方案
- 道路清掃保潔管理辦法
- 安徽能耗預(yù)警管理辦法
- 禽畜集中屠宰管理辦法
- 廣告項(xiàng)目造價(jià)管理辦法
- 邢臺(tái)高空揚(yáng)塵管理辦法
- 接待外賓管理管理辦法
- 貨車司機(jī)進(jìn)廠管理辦法
- 肩周炎中醫(yī)推拿課件
- 超級(jí)經(jīng)典的SYB游戲模塊一規(guī)則、流程和演練課件
- 一級(jí)(含)以下醫(yī)療機(jī)構(gòu)醫(yī)學(xué)檢驗(yàn)科準(zhǔn)入現(xiàn)場(chǎng)驗(yàn)收表
- 五年級(jí)語(yǔ)文上冊(cè)各單元作文范文
- 七年級(jí)下學(xué)期暑假家長(zhǎng)會(huì)課件
- 整形美容專科病歷
- DB33T 1199-2020 農(nóng)村生活污水處理設(shè)施建設(shè)和改造技術(shù)規(guī)程
- IPQC培訓(xùn)教材
- SAE-J400-2002-中文版
- 高中物理知識(shí)點(diǎn)(力學(xué)部分)
- 啤酒生產(chǎn)線控制系統(tǒng)設(shè)計(jì)——灌裝部分
- 地埋管道更換施工組織方案
評(píng)論
0/150
提交評(píng)論