北郵信通院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二--八皇后問題實(shí)驗(yàn)報(bào)告(內(nèi)附源代碼完整版)

1、北京郵電大學(xué)信息與通信工程學(xué)院第 1 頁數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱： 實(shí)驗(yàn)二——八皇后問題學(xué)生姓名： 班 級(jí)： 班內(nèi)序號(hào)： 學(xué) 號(hào)： 日 期： 2014 年 11 月 27 日1． 實(shí)驗(yàn)要求【實(shí)驗(yàn)?zāi)康摹? 進(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

2、 世紀(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)：棧（遞歸）北京郵電大學(xué)信息與通信工程學(xué)院第 3 頁3、計(jì)算時(shí)間復(fù)雜度：O(n²

3、)②判斷皇后位置是否合適：1、 關(guān)鍵算法偽代碼：對(duì)于一個(gè)坐標(biāo)，將前面每一個(gè)坐標(biāo)均與這個(gè)坐標(biāo)比較若在同一列或在同一斜線上，則返回 0，否則 j 自增 1，面每一個(gè)坐標(biāo)與前面做比較若與前面坐標(biāo)在同一列最后返回2、 代碼分析：bool SeqStack::Check(){for(int i=0;i<top;i++) //依次檢查前面已擺放的皇后位置if