數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)──n皇后八皇后_第1頁
已閱讀1頁,還剩40頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、<p>  課 程 設(shè) 計(jì) 報(bào) 告</p><p>  課設(shè)課題: 數(shù) 據(jù) 結(jié) 構(gòu) ━━ N皇后(八皇后) </p><p>  學(xué) 院: 電 子 信 息 學(xué) 院 1</p><p>  專 業(yè): 計(jì) 算 機(jī) 科 學(xué) 與 技 術(shù) 1</p&g

2、t;<p>  姓 名: 1</p><p>  班 級(jí): 1</p><p>  指導(dǎo)老師: 1</p>&

3、lt;p>  報(bào)告日期: </p><p>  年 月 制</p><p><b>  目 錄</b></p><p>  一、設(shè)計(jì)目的………………………………………………………………………………………4</p>&l

4、t;p>  二、課程設(shè)計(jì)基本要求……………………………………………………………………………4</p><p>  三、課程設(shè)計(jì)內(nèi)容及安排…………………………………………………………………………4</p><p>  四、八皇后背景知識(shí)………………………………………………………………………………5</p><p>  五、八皇后問題的實(shí)現(xiàn)………………………………

5、……………………………………………6</p><p>  5.1、遞歸方法解八皇后問題…………………………………………………………………6</p><p>  5.1.1、遞歸介紹…………………………………………………………………………7</p><p>  5.1.2、使用到的函數(shù)和變量……………………………………………………………8</p><

6、;p>  5.1.3、具體運(yùn)行結(jié)果…………………………………………………………………10</p><p>  5.1.4、算法流程圖……………………………………………………………………11</p><p>  5.1.5、遞歸算法代碼…………………………………………………………………12</p><p>  5.1.6、算法分析…………………………………………

7、……………………………13</p><p>  5.2、回溯法解決八皇后問題…………………………………………………………………13</p><p>  5.2.1、回溯法介紹……………………………………………………………………13</p><p>  5.2.2、使用到的函數(shù)與變量…………………………………………………………14</p><p&g

8、t;  5.2.3、具體運(yùn)行結(jié)果…………………………………………………………………15</p><p>  5.2.4、算法流程圖……………………………………………………………………16</p><p>  5.2.5、回溯算法代碼…………………………………………………………………17</p><p>  5.2.6、算法分析……………………………………………………

9、…………………18</p><p>  5.3、堆棧法解八皇后問題……………………………………………………………………18</p><p>  5.3.1、堆棧法介紹……………………………………………………………………18</p><p>  5.3.2、使用到的函數(shù)與變量…………………………………………………………19</p><p>  

10、5.3.3、具體運(yùn)行過程…………………………………………………………………20</p><p>  5.3.4、算法流程圖……………………………………………………………………21</p><p>  5.3.5、堆棧法實(shí)現(xiàn)的源代碼…………………………………………………………21</p><p>  5.3.6、算法分析………………………………………………………………

11、………25</p><p>  5.4、三種算法的比較…………………………………………………………………………25</p><p>  5.5、八皇后問題所有輸出結(jié)果………………………………………………………………26</p><p>  六、N皇后問題的實(shí)現(xiàn)……………………………………………………………………………30</p><p>  

12、6.1、N皇后問題介紹…………………………………………………………………………30</p><p>  6.2、使用到的函數(shù)與變量……………………………………………………………………30</p><p>  6.3、具體的執(zhí)行………………………………………………………………………………31</p><p>  6.4、算法流程圖…………………………………………………

13、……………………………31</p><p>  6.5、N皇后的源代碼…………………………………………………………………………32</p><p>  6.6、算法分析…………………………………………………………………………………32</p><p>  七、經(jīng)驗(yàn)和體會(huì)……………………………………………………………………………………32</p><

14、;p>  八、參考文獻(xiàn)………………………………………………………………………………………32</p><p>  九、附錄……………………………………………………………………………………………33</p><p>  附錄一:遞歸算法代碼………………………………………………………………………34</p><p>  附錄二:回溯算法代碼………………………………

15、………………………………………34</p><p>  附錄三:堆棧法的源代碼……………………………………………………………………36</p><p>  附錄四:N皇后的源代碼……………………………………………………………………39</p><p><b>  一、設(shè)計(jì)目的</b></p><p>  《數(shù)據(jù)結(jié)構(gòu)》是一

16、門實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課程,為了學(xué)好這門課程,必須在掌握理論知識(shí)的同時(shí),加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合,使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性,學(xué)會(huì)數(shù)據(jù)組織的方法,能把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來,并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。</p><p>  二、課程設(shè)計(jì)基本要求</p><p>  1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法,具備初步的獨(dú)立分析和設(shè)

17、計(jì)能力;</p><p>  2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能;</p><p>  3、提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力;</p><p>  4、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā),培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。</p><p>  5、設(shè)計(jì)的

18、題目要求達(dá)到一定工作量(300行以上代碼),并具有一定的深度和難度。</p><p>  6、編寫出課程設(shè)計(jì)說明書,說明書不少于10頁(代碼不算)。</p><p><b>  三、課程設(shè)計(jì)內(nèi)容</b></p><p>  1、問題分析和任務(wù)定義:根據(jù)設(shè)計(jì)題目的要求,充分地分析和理解問題,明確問題要求做什么?(而不是怎么做?)限制條件是什么?

19、</p><p>  2、邏輯設(shè)計(jì):對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型,并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊,定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說明),各個(gè)主要模塊的算法,并畫出模塊之間的調(diào)用關(guān)系圖;</p><p>  3、詳細(xì)設(shè)計(jì):定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中,要綜合考慮

20、系統(tǒng)功能,使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試,抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝,基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精,寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義,寫出函數(shù)形式的算法框架;</p><p>  4、程序編碼:把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時(shí)加入一些注解和斷言,使程序中邏輯概念清楚;</p><p>  5、程序調(diào)試與

21、測(cè)試:采用自底向上,分模塊進(jìn)行,即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能,設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn),通過修改程序來證實(shí)它或繞過它。調(diào)試正確后,認(rèn)真整理源程序及其注釋,形成格式和風(fēng)格良好的源程序清單和結(jié)果;</p><p>  6、結(jié)果分析:程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析;</p><p>  7、編寫課程設(shè)計(jì)報(bào)告;<

22、/p><p><b>  四、八皇后背景知識(shí)</b></p><p>  國際象棋中皇后威力很大,它可以象“車”一樣沿直線上下或左右移動(dòng);也可以如同“象”那樣沿著斜線移動(dòng)。雙方的皇后是不能在同一行或同一列或同一斜線上對(duì)持的。那么,在一張空白的國際象棋盤上最多可以放上幾個(gè)皇后并且不讓它們互相攻擊呢?這個(gè)問題是偉大數(shù)學(xué)家高斯在十九世紀(jì)中期提出來的,并作了部分解答。高斯在棋盤上

23、放下了八個(gè)互不攻擊的皇后,他還認(rèn)為可能有76種不同的放法,這就是有名的“八皇后”問題。現(xiàn)在我們已經(jīng)知道八皇后問題有92個(gè)解答。那么你能試著找出幾種方法嗎?如果你動(dòng)手試試,就一定會(huì)發(fā)現(xiàn)開頭幾顆皇后很容易放置,越到后來就越困難。由于我們的記憶有限,很可能在某個(gè)位置放過子后來證明不行取消了,但是以后又重新放上子去試探,這樣就會(huì)不斷地走彎路,花費(fèi)大量的精力。因此,必須找到一個(gè)簡(jiǎn)易有效、有條不紊的法則才行。</p><p>

24、;  讓我們先從四皇后談起。若要在如圖1所示的4×4棋盤中,放置四個(gè)互不攻擊的皇后,可以如下從上到下逐行地考慮:當(dāng)然在每行中只能放置一個(gè)而且必須放置一個(gè)皇后,問題是每行中的皇后應(yīng)放在第幾列?</p><p>  圖1                

25、;        圖2</p><p>  如果第一行的皇后放置在第一列,第二行的皇后就不能放置在第一、二列,只能放置在第三列或第四列。如果第二行的皇后放置在第三列,那第三行的皇后就沒有安身之處了。那么暫且把第二行的皇后放在第四列,看看情況如何。這時(shí),第三行的皇后可以放在第二列(見圖2)。然而,第四行的皇后仍然無家可歸!要放置好第四個(gè)皇后,必須

26、對(duì)前幾個(gè)皇后的位置予以修正。</p><p>  前面已經(jīng)說過,第三行以至于第二行的所有位置均已考慮過了,只得考慮讓第一行的皇后挪一下。如果把第一行的皇后放在第二列,第二行的皇后放在第四列上,第三行的皇后放在第一列上,第四行的皇后放在第三列上,正好四個(gè)皇后互不攻擊(見圖3a)。如果繼續(xù)這樣逐行逐列地考慮下去,還可以找到四皇后問題地另一個(gè)解答(見圖3b)。</p><p><b>

27、  圖3</b></p><p>  對(duì)于八皇后問題,也可如此解決:從上到下每行放一個(gè)皇后;在每一行中均從左至右逐列試放。能放則放(繼續(xù)考慮下一行)不能放則換(列數(shù)加1)換不成則退(退回前一行,讓前一皇后所在列數(shù)加1后繼續(xù)考慮),這就是探索八皇后解答的途徑。</p><p>  為了記住在探索過程中每行皇后放置的位置就需要用棧。我們可用數(shù)組T來作棧;在T(P)中存放第P行皇后所

28、在的列數(shù)。例如在第1行的皇后放在第3列,則可置T(1)=3。對(duì)于八皇后問題,如此安排后,數(shù)組T只需有八個(gè)分量就夠了。</p><p>  由于我們?cè)诿啃兄兄环乓粋€(gè)皇后,故而皇后之間保證不會(huì)左右相互攻擊了;那么如何檢查它們是否在上下或斜線方向相互攻擊呢?</p><p>  我們用一個(gè)數(shù)組C來記錄每一列上是否放了皇后,不管在哪一行上的第1列上放了一個(gè)皇后,就令C(1)=1,...。若把放在第

29、1列上的皇后取走放到別的位置上去了,那么再令C(1)=0,...。這樣,只要查看C(I)是否為零,就可以知道第I列上是否可以放置皇后了!顯然,八皇后問題中的數(shù)組C也只需八個(gè)分量就可以了。</p><p>  在8×8的國際象棋棋盤上,有15條從左上走向右下的斜線,稱為主斜線(如圖4中左圖);同樣有15條從右上走向左下的斜線,稱為副斜線。由于每放一個(gè)皇后,它所在的兩條斜線上就不能再放皇后了。我們可以如同前

30、面所述的那樣,再引進(jìn)兩個(gè)數(shù)組S,M(每個(gè)數(shù)組有15個(gè)分量),分別記錄相應(yīng)的主斜線和副斜線上是否已經(jīng)放下了皇后。在圖4中右圖,若在第2行第3列放了一個(gè)皇后,則應(yīng)令S(7)=1,M(4)=1,表示第7條主斜線,第4條副斜線上已有皇后,以后不能再放置了。因?yàn)椋鲗?duì)角線數(shù)7可由8+行數(shù)-列數(shù)=8+2-3=7計(jì)算得到,副斜線數(shù)4可由行數(shù)+列數(shù)-1=2+3-1=4計(jì)算得到。所以一般地說,在第P行,第T(P)列放置皇后以后,應(yīng)該令:C(T(P))=1

31、;S(8+P-T(P))=1;M(P+T(P)-1)=1。有了以上準(zhǔn)備知識(shí),就能為八皇后問題寫算法了</p><p>  五、八皇后問題的實(shí)現(xiàn)</p><p>  5.1、遞歸方法解八皇后問題</p><p>  5.1.1、遞歸的介紹</p><p><b>  調(diào)用子程序的含義:</b></p><

32、;p>  在過程和函數(shù)的學(xué)習(xí)中,我們知道調(diào)用子程序的一般形式是:主程序調(diào)用子程序A,子程序A調(diào)用子程序B,如圖如示,這個(gè)過程實(shí)際上是:</p><p>  當(dāng)主程序執(zhí)行到調(diào)用子程序A語句時(shí),系統(tǒng)保存一些必要的現(xiàn)場(chǎng)數(shù)據(jù),跳轉(zhuǎn)到子程序A(為了說得簡(jiǎn)單些,我這里忽略了參數(shù)傳遞這個(gè)過程)。</p><p>  當(dāng)子程序A執(zhí)行到調(diào)用子程序B語句時(shí),系統(tǒng)作法如上,跳轉(zhuǎn)到子程序B。</p&g

33、t;<p>  子程序B執(zhí)行完所有語句后,跳轉(zhuǎn)回子程序A調(diào)用子程序B語句的下一條語句(我這又忽略了返回值處理)</p><p>  子程序A執(zhí)行完后,跳轉(zhuǎn)回主程序調(diào)用子程序A語句的下一條語句</p><p><b>  主程序執(zhí)行到結(jié)束。</b></p><p>  做個(gè)比較:我在吃飯(執(zhí)行主程序)吃到一半時(shí),某人叫我(執(zhí)行子程序

34、A),話正說到一半,電話又響了起來(執(zhí)行子程序B),我只要先接完電話,再和某人把話說完,最后把飯吃完</p><p><b>  認(rèn)識(shí)遞歸函數(shù)</b></p><p>  我們?cè)诟咧袝r(shí)都學(xué)過數(shù)學(xué)歸納法,例:</p><p><b>  求 n! </b></p><p>  我們可以把n!這么定義 

35、 </p><p>  也就是說要求3!,我們必須先求出2!,要求2!,必須先求1!,要求1!,就必須先求0!,而0!=1,所以1!=0!*1=1,再進(jìn)而求2!,3!。分別用函數(shù)表示,則如圖: </p><p>  我們可以觀察到,除計(jì)算0!子程序外,其他的子程序基本相似,我們可以設(shè)計(jì)這么一個(gè)子程序:</p><p>  int factorial(int i){

36、</p><p><b>  int res; </b></p><p>  res=factorial(I-1)*i; </p><p>  return res; </p><p><b>  } </b></p><p>  那么當(dāng)執(zhí)行主程序語句s=factorial(

37、3)時(shí),就會(huì)執(zhí)行factorial(3),但在執(zhí)行factorial(3),又會(huì)調(diào)用factorial(2),這時(shí)大家要注意,factorial(3)和factorial(2)雖然是同一個(gè)代碼段,但在內(nèi)存中它的數(shù)據(jù)區(qū)是兩份!而執(zhí)行factorial(2)時(shí)又會(huì)調(diào)用factorial(1),執(zhí)行factorial(1)時(shí)又會(huì)調(diào)用factorial(0),每調(diào)用一次factorial函數(shù),它就會(huì)在內(nèi)存中新增一個(gè)數(shù)據(jù)區(qū),那么這些復(fù)制了多份的函

38、數(shù)大家可以把它看成是多個(gè)不同名的函數(shù)來理解;</p><p>  但我們這個(gè)函數(shù)有點(diǎn)問題,在執(zhí)行factorial(0)時(shí),它又會(huì)調(diào)用factorial(-1)。。。造成死循環(huán),也就是說,在factorial函數(shù)中,我們要在適當(dāng)?shù)臅r(shí)候保證不再調(diào)用該函數(shù),也就是不執(zhí)行res=factorial(I-1)*i;這條調(diào)用語句。所以函數(shù)要改成: </p><p>  int factorial(i

39、nt i){ </p><p><b>  int res; </b></p><p>  if (I>0) res=factorial(I-1)*i; else res=1;</p><p>  return res; </p><p><b>  }</b></p><

40、p>  那么求3!的實(shí)際執(zhí)行過程如圖所示: </p><p>  5.1.2、使用到的函數(shù)和變量</p><p>  在這個(gè)算法中共有六個(gè)函數(shù),除了Main()主函數(shù),還有IsValid(int n),Output(),Queen(int n),變量icount,Site這些組成程序,</p><p>  紅框圈出的是遞歸函數(shù)的應(yīng)用,既自己調(diào)用自己在Queen

41、(int n)中調(diào)用queen是典型的遞歸調(diào)用。</p><p><b>  編譯沒有錯(cuò)誤</b></p><p>  5.1.3、具體運(yùn)行結(jié)果</p><p>  運(yùn)行結(jié)果表示出有92種可能性</p><p>  5.1.4、算法流程圖</p><p><b>  遞歸的圖解演示<

42、;/b></p><p>  5.1.5、程序代碼見附錄一</p><p>  5.1.6、算法分析</p><p>  遞歸是一種很古老的算法,其應(yīng)用的也十分的廣泛,在和多復(fù)雜的程序中也是經(jīng)常性的使用,雖然其的程序編寫相對(duì)的簡(jiǎn)單,但其確消耗很多的資源,在沒有好的算法的前提下,這是相對(duì)能夠運(yùn)行的算法,當(dāng)然這也是在編程著能夠擁有一定的編寫能力的基礎(chǔ)上的。<

43、/p><p>  遞歸的優(yōu)點(diǎn)是:編寫簡(jiǎn)單,缺點(diǎn)是:消耗資源大。</p><p>  八皇后問題是一個(gè)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題用遞歸是最為常見的方法,由于遞歸是自己套自己,把八皇后問題的調(diào)用函數(shù)在代碼界面上融合到了一個(gè)函數(shù)中。</p><p>  該算法中所有語句的頻度之和(即算法的時(shí)間耗費(fèi))為:</p><p>  T(n)=2n3+3n2+2n+1&

44、lt;/p><p>  當(dāng)n趨向于無窮時(shí),其時(shí)間復(fù)雜度為O(n3)。</p><p>  5.2、回溯法解決八皇后問題</p><p>  5.2.1、回溯法介紹</p><p>  在計(jì)算機(jī)奧賽中,有時(shí)會(huì)遇到這樣一類題目,它的問題可以分解,但是又不能得出明確的動(dòng)態(tài)規(guī)劃或是遞歸解法,此時(shí)可以考慮用回溯法解決此類問題?;厮莘ǖ膬?yōu)點(diǎn)在于其程序結(jié)構(gòu)明確

45、,可讀性強(qiáng),易于理解,而且通過對(duì)問題的分析可以大大提高運(yùn)行效率。但是,對(duì)于可以得出明顯的遞推公式迭代求解的問題,還是不要用回溯法,因?yàn)樗ㄙM(fèi)的時(shí)間比較長(zhǎng)。</p><p><b>  回溯法的基本思想</b></p><p>  對(duì)于用回溯法求解的問題,首先要將問題進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化,得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹,枚舉每

46、種可能的解的情況;從而得出結(jié)果。但是,回溯法中通過構(gòu)造約束函數(shù),可以大大提升程序效率,因?yàn)樵谏疃葍?yōu)先搜索的過程中,不斷的將每個(gè)解(并不一定是完整的,事實(shí)上這也就是構(gòu)造約束函數(shù)的意義所在)與約束函數(shù)進(jìn)行對(duì)照從而刪除一些不可能的解,這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時(shí)間。</p><p>  回溯法中,首先需要明確下面三個(gè)概念:</p><p>  (一)約束函數(shù):約束函數(shù)是根據(jù)題意

47、定出的。通過描述合法解的一般特征用于去除不合法的解,從而避免繼續(xù)搜索出這個(gè)不合法解的剩余部分。因此,約束函數(shù)是對(duì)于任何狀態(tài)空間樹上的節(jié)點(diǎn)都有效、等價(jià)的。</p><p> ?。ǘ顟B(tài)空間樹:剛剛已經(jīng)提到,狀態(tài)空間樹是一個(gè)對(duì)所有解的圖形描述。樹上的每個(gè)子節(jié)點(diǎn)的解都只有一個(gè)部分與父節(jié)點(diǎn)不同。</p><p>  (三)擴(kuò)展節(jié)點(diǎn)、活結(jié)點(diǎn)、死結(jié)點(diǎn):所謂擴(kuò)展節(jié)點(diǎn),就是當(dāng)前正在求出它的子節(jié)點(diǎn)的節(jié)點(diǎn),

48、在DFS中,只允許有一個(gè)擴(kuò)展節(jié)點(diǎn)?;罱Y(jié)點(diǎn)就是通過與約束函數(shù)的對(duì)照,節(jié)點(diǎn)本身和其父節(jié)點(diǎn)均滿足約束函數(shù)要求的節(jié)點(diǎn);死結(jié)點(diǎn)反之。由此很容易知道死結(jié)點(diǎn)是不必求出其子節(jié)點(diǎn)的(沒有意義)。</p><p>  深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(FIFO)</p><p>  在分支界限法中,一般用的是FIFO或最小耗費(fèi)搜索;其思想是一次性將一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)求出并將其放入一個(gè)待求子節(jié)點(diǎn)的隊(duì)列。通

49、過遍歷這個(gè)隊(duì)列(隊(duì)列在遍歷過程中不斷增長(zhǎng))完成搜索。而DFS的作法則是將每一條合法路徑求出后再轉(zhuǎn)而向上求第二條合法路徑。而在回溯法中,一般都用DFS。為什么呢?這是因?yàn)榭梢酝ㄟ^約束函數(shù)殺死一些節(jié)點(diǎn)從而節(jié)省時(shí)間,由于DFS是將路徑逐一求出的,通過在求路徑的過程中殺死節(jié)點(diǎn)即可省去求所有子節(jié)點(diǎn)所花費(fèi)的時(shí)間。FIFO理論上也是可以做到這樣的,但是通過對(duì)比不難發(fā)現(xiàn),DFS在以這種方法解決問題時(shí)思路要清晰非常多。</p><p&

50、gt;  因此,回溯法可以被認(rèn)為是一個(gè)有過剪枝的DFS過程。</p><p>  利用回溯法解題的具體步驟</p><p>  首先,要通過讀題完成下面三個(gè)步驟:</p><p>  描述解的形式,定義一個(gè)解空間,它包含問題的所有解。</p><p><b>  構(gòu)造狀態(tài)空間樹。</b></p><p

51、>  構(gòu)造約束函數(shù)(用于殺死節(jié)點(diǎn))。</p><p>  然后就要通過DFS思想完成回溯,完整過程如下:</p><p>  設(shè)置初始化的方案(給變量賦初值,讀入已知數(shù)據(jù)等)。</p><p>  變換方式去試探,若全部試完則轉(zhuǎn)(7)。</p><p>  判斷此法是否成功(通過約束函數(shù)),不成功則轉(zhuǎn)(2)。</p>&l

52、t;p>  試探成功則前進(jìn)一步再試探。</p><p>  正確方案還未找到則轉(zhuǎn)(2)。</p><p>  已找到一種方案則記錄并打印。</p><p>  退回一步(回溯),若未退到頭則轉(zhuǎn)(2)。</p><p>  已退到頭則結(jié)束或打印無解。</p><p><b>  回溯法的數(shù)據(jù)結(jié)構(gòu)</

53、b></p><p>  回溯法的狀態(tài)空間樹,在計(jì)算機(jī)上的數(shù)據(jù)結(jié)構(gòu)有兩種表示方法。當(dāng)用k表示樹的節(jié)點(diǎn)層數(shù),n表示節(jié)點(diǎn)總數(shù),m表示解的總數(shù)時(shí):</p><p>  用m個(gè)k元組表示m種不同的解。其中,每組中的元素是[1,n]中的一個(gè)元素。在Pascal中,可以這樣定義變量:</p><p>  var a:array[1..k,1..m]of integer;(

54、integer可以依n的范圍決定)</p><p>  m個(gè)n元組表示m種不同的解。因?yàn)樗械墓?jié)點(diǎn)都包含在每個(gè)解的表示中,每組中的元素只有兩種情況,被選用和不被選用。在Pascal中,可以這樣定義變量:</p><p>  var a:array[1..n,1..m]of boolean;</p><p>  這兩種數(shù)據(jù)結(jié)構(gòu)的解空間最多都含有2n個(gè)不同的元組<

55、/p><p>  5.2.2、使用到的函數(shù)與變量</p><p>  回溯發(fā)是很好的算法,在所有算發(fā)中空間復(fù)雜度是最小的,其只有一個(gè)主函數(shù)main(),和一個(gè)變量total,就可以成功的解決八皇后問題,我本人對(duì)于這種算法非常的推崇,也覺的是所有解決了八皇后問題中最好的。</p><p><b>  編譯沒有錯(cuò)誤</b></p><

56、;p>  5.2.3、具體運(yùn)行結(jié)果</p><p><b>  運(yùn)行結(jié)果如圖</b></p><p>  5.2.4、算法流程圖</p><p><b>  回溯算法的圖解</b></p><p>  5.2.5、程序代碼見附錄二</p><p>  5.2.6、算法分

57、析</p><p>  回溯是一個(gè)很好的算法,其應(yīng)用的也十分的廣泛,在和多復(fù)雜的程序中也是經(jīng)常性的使用,雖然其的程序編寫相對(duì)的簡(jiǎn)單,但其確消耗很多的資源,在沒有好的算法的前提下,這是相對(duì)能夠運(yùn)行的算法,當(dāng)然這也是在編程著能夠擁有一定的編寫能力的基礎(chǔ)上的。</p><p>  回溯的優(yōu)點(diǎn)是:編寫復(fù)雜,缺點(diǎn)是:消耗資源小。</p><p>  八皇后問題是一個(gè)經(jīng)典的數(shù)據(jù)

58、結(jié)構(gòu)問題用回溯是最為常見的方法,由于回溯是自己套自己,把八皇后問題的調(diào)用函數(shù)在代碼界面上融合到了一個(gè)函數(shù)中。</p><p>  該算法中所有語句的頻度之和(即算法的時(shí)間耗費(fèi))為:</p><p>  T(n)=2n2+1</p><p>  分析:當(dāng)n趨向于無窮時(shí),其時(shí)間復(fù)雜度為O(n2+1 +2)。</p><p>  5.3、堆棧法解八

59、皇后問題</p><p>  5.3.1、堆棧法介紹</p><p><b>  堆棧的概念</b></p><p>  堆棧(Stack)是一種比較重要的線性數(shù)據(jù)結(jié)構(gòu),如果對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)不是很了解的話,我們可以把它簡(jiǎn)單的看作一維數(shù)組。但是對(duì)一維數(shù)組進(jìn)行元素的插入、刪除操作時(shí),可以在任何位置進(jìn)行,而對(duì)于棧來說,插入、刪除操作是固定在一端進(jìn)行的,

60、這一端稱為棧頂(top),另一端稱為棧底(bottom),向棧中插入數(shù)據(jù)的操作稱為壓入(Push),從棧中刪除數(shù)據(jù)稱為彈出(Pop)。</p><p><b>  二 堆棧的存儲(chǔ)方式</b></p><p>  對(duì)棧中元素的操作是按后進(jìn)先出(Last In First Out,簡(jiǎn)稱LIFO)的原則進(jìn)行的,即最后壓入的元素最先彈出。</p><p&g

61、t;  在棧的操作過程中,有一個(gè)永遠(yuǎn)指向棧頂?shù)臈m斨羔槪趬喝牒蛷棾鰯?shù)據(jù)時(shí),棧頂指針向上或向下移動(dòng)。當(dāng)棧頂指針為零時(shí)(即指向棧底的后面),棧為空棧。如果壓入的數(shù)據(jù)過多超出了棧的最大空間,則發(fā)生棧上溢。</p><p>  在程序設(shè)計(jì)中,我們可以使用一維數(shù)組實(shí)現(xiàn)對(duì)棧的操作。假設(shè)用一維數(shù)組s[1..arrmax]表示棧,則對(duì)于非空棧,s[1]為最早壓入棧的元素,同時(shí)設(shè)棧頂指針top,則s[top]為最后壓入棧的元素。

62、當(dāng)top=arrmax時(shí)棧滿,若此時(shí)有數(shù)據(jù)入棧將產(chǎn)生“數(shù)組越界”的錯(cuò)誤,極為棧上溢,反之當(dāng)top=0,意為??铡?lt;/p><p>  5.3.2、使用到的函數(shù)與變量</p><p>  組成的程序的函數(shù)有:DeSetQueen(int row,int col),DisplayAndSet(),main(),NoConflict(int row,int col),Pop(),Push(int

63、 row,int col),Queen(),SetQueen(int row,int col),變量有:ArrayQueen,OutQueen,Top 。</p><p><b>  沒有編譯錯(cuò)誤</b></p><p>  5.3.3、具體運(yùn)行過程</p><p>  運(yùn)行結(jié)果放在queen.txt文件中</p><p&g

64、t;<b>  八皇后問題的源代碼</b></p><p>  運(yùn)行在queen.txt文件中的92種結(jié)果</p><p>  5.3.4、算法流程圖</p><p>  5.3.5、程序代碼見附錄三</p><p>  5.3.6、算法分析</p><p>  堆棧是一個(gè)很好的算法,其應(yīng)用的也十

65、分的廣泛,在和多復(fù)雜的程序中也是經(jīng)常性的使用,雖然其的程序編寫相對(duì)的簡(jiǎn)單,但其確消耗很多的資源,在沒有好的算法的前提下,這是相對(duì)能夠運(yùn)行的算法,當(dāng)然這也是在編程著能夠擁有一定的編寫能力的基礎(chǔ)上的。</p><p>  堆棧的優(yōu)點(diǎn)是:算法比較的平均,運(yùn)行十分的復(fù)雜。</p><p>  八皇后問題是一個(gè)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題用遞歸是最為常見的方法,由于遞歸是自己套自己,把八皇后問題的調(diào)用函數(shù)在代

66、碼界面上融合到了一個(gè)函數(shù)中。</p><p>  該算法中所有語句的頻度之和(即算法的時(shí)間耗費(fèi))為:</p><p>  T(n)=2nn+1</p><p>  分析:當(dāng)n趨向于無窮時(shí),其時(shí)間復(fù)雜度為O(n2 +1)。</p><p>  5.4、三種算法的比較</p><p>  遞歸簡(jiǎn)單,但消耗資源。</p

67、><p>  回溯比較的復(fù)雜,但消耗資源少。</p><p><b>  堆棧比較的平均</b></p><p>  5.5、八皇后問題所有輸出結(jié)果為(8×8棋盤):</p><p>  第1種情況: 第2種情況: 第3種情況:</p><p>

68、  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * * * * * Q * * * * * * * Q * * * * * * Q * *</p><p>  * * * * Q * * * * * * Q * * * * *

69、 * * * * * * Q</p><p>  * * * * * * * Q * * * * * Q * * * * Q * * * * *</p><p>  * Q * * * * * * * * * * * * * Q * * * * * * Q *</p><p>  * * * Q * * *

70、 * Q * * * * * * * * * * Q * * * *</p><p>  * * * * * Q * * * * * * Q * * * * Q * * * * * *</p><p>  * * Q * * * * * * * Q * * * * * * * * * Q * * *

71、</p><p>  第4種情況: 第5種情況: 第6種情況:</p><p>  Q * * * * * * * * * * * * Q * * * * * Q * * * *</p><p>  * * * * Q * * * Q * * * * * * *

72、 Q * * * * * * *</p><p>  * * * * * * * Q * * * * Q * * * * * * * Q * * *</p><p>  * * * * * Q * * * Q * * * * * * * * * * * * * Q</p><p>  *

73、 * Q * * * * * * * * * * * * Q * Q * * * * * *</p><p>  * * * * * * Q * * * Q * * * * * * * * * * * Q * </p><p>  * Q * * * * * * * * * * * * Q *

74、 * * Q * * * * * </p><p>  * * * Q * * * * * * * Q * * * * * * * * * Q * *</p><p>  第7種情況: 第8種情況: 第9種情況:</p><p>  * * * * Q * * *

75、 * * Q * * * * * * * * * Q * * *</p><p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * * * * * * Q * * * * * * Q * * * * Q * * * *</

76、p><p>  * * * Q * * * * * * * * Q * * * * * * * * Q * *</p><p>  * Q * * * * * * * * * * * * * Q * * * * * * * Q</p><p>  * * * * * * Q * *

77、Q * * * * * * * Q * * * * * *</p><p>  * * Q * * * * * * * * Q * * * * * * * * * * Q *</p><p>  * * * * * Q * * * * * * * Q * * * * Q * * * * * </p>

78、;<p>  第10種情況: 第11種情況: 第12種情況:</p><p>  * * * * * * Q * * * * * Q * * * * * * Q * * * *</p><p>  Q * * * * * * * Q * * * * * * * Q

79、 * * * * * * *</p><p>  * * Q * * * * * * * * * * * * Q * * * * Q * * *</p><p>  * * * * * * * Q * * * * * Q * * * * * * * * * Q</p><p>  * * * * *

80、 Q * * * * Q * * * * * * * * * * Q * *</p><p>  * * * Q * * * * * * * * * * Q * * * Q * * * * *</p><p>  * Q * * * * * * * Q * * * * * * * * *

81、* * * Q *</p><p>  * * * * Q * * * * * * Q * * * * * Q * * * * * *</p><p>  第13種情況: 第14種情況: 第15種情況:</p><p>  * Q * * * * * * * * *

82、* Q * * * * * * * * * * Q</p><p>  * * * * * Q * * * * Q * * * * * * * Q * * * * *</p><p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p>&l

83、t;p>  * * * * * * Q * * * * * * * Q * * * * * * Q * *</p><p>  * * * Q * * * * * Q * * * * * * * Q * * * * * *</p><p>  * * * * * * * Q * * * * * *

84、 * Q * * * * Q * * *</p><p>  * * Q * * * * * * * * * * Q * * * * * * * * Q *</p><p>  * * * * Q * * * * * * Q * * * * * * * Q * * * *</p><p&g

85、t;  第16種情況: 第17種情況: 第18種情況:</p><p>  * * * Q * * * * * * * * Q * * * * * * * * Q * *</p><p>  * * * * * Q * * * * * * * * Q * * * Q * *

86、 * * *</p><p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * * * Q * * * * * * Q * * * * * * * * * * * Q</p><p>  * Q * * * * * *

87、 * Q * * * * * * * * * Q * * * *</p><p>  * * * * * * * Q * * * * * * * Q * Q * * * * * *</p><p>  * * Q * * * * * * * * * * Q * * * * * * *

88、 * Q *</p><p>  * * * * * * Q * * * Q * * * * * * * * * Q * * *</p><p>  第19種情況: 第20種情況: 第21種情況:</p><p>  * * * * Q * * * * * * *

89、 * Q * * * * * Q * * * *</p><p>  * * Q * * * * * * * Q * * * * * * * * * * * * Q</p><p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p>

90、<p>  * * * * * Q * * * * * * * * * Q * * Q * * * * *</p><p>  * * * * * * * Q * * * * Q * * * * * * * * Q * *</p><p>  * Q * * * * * * * Q * *

91、 * * * * * Q * * * * * *</p><p>  * * * Q * * * * * * * Q * * * * * * * * * * Q *</p><p>  * * * * * * Q * * * * * * * Q * * * * * Q * * *</p>

92、<p>  第22種情況: 第23種情況: 第24種情況:</p><p>  * * * * * * * Q * * * Q * * * * * * * Q * * * *</p><p>  * * * Q * * * * * * * * * * * Q *

93、* * * * * Q *</p><p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * Q * * * * * * * * * Q * * * * * * * * * * Q</p><p>  * * * *

94、* Q * * * * * * * * Q * * * * * Q * * *</p><p>  * Q * * * * * * * Q * * * * * * * Q * * * * * *</p><p>  * * * * * * Q * * * * * * Q * * *

95、* * * * Q * *</p><p>  * * * * Q * * * * * Q * * * * * * * Q * * * * *</p><p>  第25種情況: 第26種情況: 第27種情況:</p><p>  * * * * * Q * * *

96、 * * * * Q * * * * * * * * Q *</p><p>  * * * Q * * * * * * Q * * * * * * * Q * * * * *</p><p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p

97、><p>  * * * * Q * * * * * * * * * Q * * * * * * Q * *</p><p>  * * * * * * * Q * * * * Q * * * * * * * * * * Q</p><p>  * Q * * * * * * *

98、 * * * * * * Q * * * * Q * * *</p><p>  * * * * * * Q * * Q * * * * * * * Q * * * * * *</p><p>  * * Q * * * * * * * * Q * * * * * * * Q * * * *</p

99、><p>  第28種情況: 第29種情況: 第30種情況:</p><p>  * * * * Q * * * * Q * * * * * * * Q * * * * * * </p><p>  * * * * * * Q * * * * * Q * * *

100、 * * * * * * * Q</p><p>  Q * * * * * * * * * * * * * Q * * * * * * Q * *</p><p>  * * Q * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * *

101、 * * * * Q * * Q * * * * * * * Q * * * * *</p><p>  * * * * * Q * * * * * * * * * Q * * * * Q * * *</p><p>  * * * Q * * * * * * * * * Q * * *

102、* * * * * Q *</p><p>  * Q * * * * * * * * * Q * * * * * * * Q * * * *</p><p>  第31種情況: 第32種情況: 第33種情況:</p><p>  * * * * * Q * *

103、* * * * * * Q * * * * * * * * Q</p><p>  * Q * * * * * * * Q * * * * * * * Q * * * * * *</p><p>  * * * * * * Q * * * * Q * * * * * * * Q * * * *</p&g

104、t;<p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * Q * * * * * * * * * * * * Q * * * * * * Q *</p><p>  * * * * Q * * * * * *

105、 * Q * * * * * * * Q * * *</p><p>  * * * * * * * Q * * Q * * * * * * * Q * * * * *</p><p>  * * * Q * * * * * * * * * Q * * * * * * * Q * *</p>&

106、lt;p>  第34種情況: 第35種情況: 第36種情況:</p><p>  * * * * Q * * * * * * * * Q * * * * * * Q * * *</p><p>  * Q * * * * * * * Q * * * * * * * Q

107、 * * * * * *</p><p>  * * * * * * * Q * * * * * * Q * * * * * * Q * *</p><p>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * * Q * *

108、 * * * * * Q * * * * * * * * * * Q *</p><p>  * * * * * * Q * * * * * * * * Q * * * Q * * * *</p><p>  * * Q * * * * * * * * * Q * * * * * * *

109、* * * Q</p><p>  * * * * * Q * * * * Q * * * * * * * Q * * * * *</p><p>  第37種情況: 第38種情況: 第39種情況:</p><p>  * * Q * * * * * * * * * *

110、 Q * * * * * * Q * * *</p><p>  * * * * Q * * * * * * Q * * * * * * * * * * * Q</p><p>  * * * * * * Q * * * * * * * Q * * * * Q * * * *</p><p

111、>  Q * * * * * * * Q * * * * * * * Q * * * * * * *</p><p>  * * * Q * * * * * * * * * * * Q * * * * * * Q *</p><p>  * Q * * * * * * * Q * * * * *

112、* * Q * * * * * *</p><p>  * * * * * * * Q * * * * Q * * * * * * * * Q * *</p><p>  * * * * * Q * * * * Q * * * * * * * Q * * * * *</p><p> 

113、 第40種情況: 第41種情況: 第42種情況:</p><p>  * * Q * * * * * * * * * * * Q * * * * * * Q * *</p><p>  * * * * * Q * * * * * * Q * * * * * * Q * * * *<

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論