數(shù)據(jù)結(jié)構課程設計報告-8皇后問題

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：11 大?。?5.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩10頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結(jié)構課程設計　　選題：八皇后問題　　姓名：　　學號：　　指

2、導老師： 　　目錄一.選題概述---------------------------------------3　　設計要求與分析--------------------------------3　　數(shù)據(jù)結(jié)構與定義--------------------------

3、------4　　1.結(jié)構體定義　　2.函數(shù)定義　　3.函數(shù)之間的定義　　程序段與分析----------------------------------5&

4、lt;/p>　　完整程序代碼及運行結(jié)果截圖------------------7　　心得體會--------------------------------------10　　參考文獻--------------------------------------10

5、一．選題概述：　　在實際應用中，有相當一類問題需要找出它的解集合，或者要求找出某些約束條件下的最優(yōu)解。求解時經(jīng)常使用一種稱為回溯的方法來解決。所謂回溯就是走回頭路，該方法是在一定的約束條件下試探地搜索前進，若前進中受阻，則回頭另擇通路繼續(xù)搜索。為了能夠沿著原路逆序回退，需用棧來保存曾經(jīng)到達的每一個狀態(tài)，棧頂?shù)臓顟B(tài)即為回退的第一站，因此回溯法均可利用棧來實現(xiàn)。而解決八皇后問題就

6、是利用回溯法和棧來實現(xiàn)的。　　二．設計要求與分析　　八皇后問題是在8x8的國際象棋棋盤上，安放8個皇后，要求沒有一個皇后能夠“吃掉”任何其他一個皇后，即沒有兩個或兩個以上的皇后占據(jù)棋盤上的同一行、同一列或同一條對角線。　　八皇后在棋盤上分布的各種可能的格局，其數(shù)目非常大，約等

7、于232種，但是，可以將一些明顯不滿足問題要求的格局排除掉。由于任意兩個皇后不能同行，即每一行只能放置一個皇后，因此將第i個皇后放置在第i行上。這樣在放置第i個皇后時，只要考慮它與前i一1個皇后處于不同列和不同對角線位置上即可。因此，其算法基本思想如下：　　從第1行起逐行放置皇后，每放置一個皇后均需要依次對第1，2，…，8列進行試探，并盡可能取小的列數(shù)。若當前試探的列位置是安全的，即不與已放置的

8、其他皇后沖突，則將該行的列位置保存在棧中，然后繼續(xù)在下一行上尋找安全位置；若當前試探的列位置不安全，則用下一列進行試探，當8列位置試探完畢都未找到安全位置時，就退?；厮莸缴弦恍?，修改棧頂保存的皇后位置，然后繼續(xù)試探。　　該算法抽象描述如下：　?。?)置當前行當前列均為1;　　（2）while(當前行號《8)<

9、;/p>　　（3）｛檢查當前行，從當前列起逐列試探，尋找安全列號；　?。?）if（找到安全列號）　?。?）放置皇后，將列號記入棧中，并將下一行置成當前行，第1列置為當前列；　?。?）else　　（7）退?；?/p>

10、溯到上一行，移去該行已放置的皇后，以該皇后所在列的下一列作為　　當前列；　?。?）｝結(jié)束程序。　　數(shù)據(jù)結(jié)構與定義　　結(jié)構體定義</b&

11、gt;　　typedef struct　　{　　int col[MaxSize]; //col[i]存放第i個皇后的列號　　int top; //棧頂指針　　}Typ

12、e;　　2.函數(shù)定義　　bool place(Type st,int i,int j) //測試(i,j)是否與1~i-1皇后有沖突 　　void queen(int n) //求解皇后問題　　void ma

13、in() //主函數(shù)　　函數(shù)之間的調(diào)用關系　　main queen place　　程序塊與分析　　bool place(Type st,int i,int j)//測試

14、(i,j)是否與1~i-1皇后有沖突　　{　　int k=1;　　if(i==1) return true;//存放第一個皇后時沒有沖突　　while(k<=i-1)//j=1到k-1是已經(jīng)

15、放置了皇后的列　　{　　if((st.col[k]==j)||(abs(j-st.col[k])==abs(k-i)))　　return false;　　k++;<p

16、>　　}　　return true;　　}　?。╧，st.col[k]）（k，st.col[k]）　　j-st.col[k]

17、 j-st.col[k] 　　(i,j) i-k i-k (i,j)　　//測試(i,j)位置是否與已經(jīng)放好的第1個到第i~1皇后有沖突。已經(jīng)放置好的第1個到第1~i-1個皇后已放置在st棧中。St棧用

18、的是順序棧，棧頂指針從1開始，st.col[k]用于存放第k（1<=i<=k-1）個皇后的列號，即皇后的位置是（k,st.col[k]）。對于（i，j）位置上的皇后與已經(jīng)放置的皇后（k，st.col[k]）發(fā)生沖突的情況時，則有：st.col[k]==j;對角線的沖突情況是：|j-st.col[k]|==|k-i|。　　void queen(int n)//求解n皇后問題</p

19、>　　{　　int i,j,k;　　bool find;　　Type st;//定義棧st　　st.top=0;//初始化棧頂指針　　st.top++;//將(1,

20、1)放進棧　　st.col[st.top]=1;　　while(st.top>0)//棧不空時循環(huán)　　{　　i=st.top;//當前皇后為第i個皇后　　if(st.top==n)//所

21、有皇后都放置好了，輸出一個解　　{　　printf("第%d個解：",++count);　　for(k=1;k<=st.top;k++)　　printf("(%d,%d)",k,st.co

22、l[k]);　　printf("\n");　　}　　find=false;　　for(j=1;j<=n;j++)　　{</

23、p>　　if(place(st,i+1,j))//在i+1行找到一個放置皇后的位置(i+1,j)　　{　　st.top++;　　st.col[st.top]=j;　　f

24、ind=true;　　break;　　}　　}　　if(find==false)//在i+1行找不到放皇后的位置，回溯

25、;　　{　　while(st.top>0)　　{　　if(st.col[st.top]==n)//本行也沒有可放的位置，則退棧　　st.top--;&l

26、t;/p>　　for(j=st.col[st.top]+1;j<=n;j++)//在本行的下一個位置找　　if(place(st,st.top,j))　　{　　st.col[st.top]=j;<

27、;b>　　break;　　}　　if(j>n)//當前皇后在本行沒有可放的位置　　st.top--;//退棧　　else//本行找到一個位置后，推出回溯<

28、b>　　break;　　}　　}　　}　　}　　vo

29、id main() //主函數(shù)　　{　　int n;　　printf("請輸入皇后個數(shù)n=");　　scanf("%d",&n);

30、;　　printf("%d皇后問題求解如下:\n",n);　　queen(n);　　printf("\n");　　}　　完整程序代碼及

31、運行結(jié)果截圖　　#include <stdio.h>　　#include <stdlib.h>　　#define MaxSize 100　　typedef struct　　{</b&

32、gt;　　int col[MaxSize];//col[i]存放第i個皇后的列號　　int top;//棧頂指針　　}StType;//定義順序棧類型　　int count=0;　　bool place(StType st,int

33、 i,int j)//測試(i,j)是否與1~i-1皇后有沖突　　{　　int k=1;　　if(i==1) return true;//存放第一個皇后時沒有沖突　　while(k<=i-1

34、)//j=1到k-1是已經(jīng)放置了皇后的列　　{　　if((st.col[k]==j)||(abs(j-st.col[k])==abs(k-i)))　　return false;　　k++;<

35、/p>　　}　　return true;　　}　　void queen(int n)//求解n皇后問題　　{

36、　　int i,j,k;　　bool find;　　StType st;//定義棧st　　st.top=0;//初始化棧頂指針　　st.top++;//將(1,1)放進棧　　st.col[st.top]=1;&

37、lt;/p>　　while(st.top>0)//棧不空時循環(huán)　　{　　i=st.top;//當前皇后為第i個皇后　　if(st.top==n)//所有皇后都放置好了，輸出一個解

38、{　　printf("第%d個解：",++count);　　for(k=1;k<=st.top;k++)　　printf("(%d,%d)",k,st.col[k]);　　printf("\n&q

39、uot;);　　}　　find=false;　　for(j=1;j<=n;j++)　　if(place(st,i+1,j))//在i+1行找到一個放置皇后的位置(i+1,j)<b&

40、gt;　　{　　st.top++;　　st.col[st.top]=j;　　find=true;　　break;

41、}　　if(find==false)//在i+1行找不到放皇后的位置，回溯　　{　　while(st.top>0)　　{　　if

42、(st.col[st.top]==n)//本行也沒有可放的位置，則退棧　　st.top--;　　for(j=st.col[st.top]+1;j<=n;j++)//在本行的下一個位置找　　if(place(st,st.top,j))<p&g

43、t;　　{　　st.col[st.top]=j;　　break;　　}　　if(j>n)//當前皇后在本行沒有可放的位置<

44、p>　　st.top--;//退棧　　else//本行找到一個位置后，推出回溯　　break;　　}　　}&l

45、t;b>　　}　　}　　void main()　　{　　int n;　　printf(&q

46、uot;請輸入皇后個數(shù)n=");　　scanf("%d",&n);　　printf("%d皇后問題求解如下:\n",n);　　queen(n);　　printf("\

47、n");　　}　　心得體會　　善于學習別人,多請教牛人,才會更快提高自己。有些問題也許就是自己在某一點想不通，想法轉(zhuǎn)不過來，這就消耗了很多時間。而經(jīng)過牛人的點撥問題就解決了，牛人們也會更直接，更清晰的教導一些技術，通過向他們學習

48、，才會更快的提高自己的技能。　　多找一些題目來練習，多敲代碼，才會更有感覺。在練習的過程中找出規(guī)則，形成編程思想。　　小組合作形成共同進步。小組成員的討論過程中，將各自的想法提出來，分析優(yōu)缺點，這過程中每個成員也可以學習到其他成員的解題思想，也可以審視自己的解題思想，獲得提升。　　參考文獻<

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構課程設計報告-8皇后問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構課程設計報告-8皇后問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載