

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p><b> 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b> 課題:八皇后問(wèn)題</b></p><p> 學(xué) 院:計(jì)算機(jī)科學(xué)與信息工程學(xué)院 </p><p> 專(zhuān) 業(yè):計(jì)算機(jī)科學(xué)與技術(shù) </p><p> 年 級(jí):2010級(jí)計(jì)本二班
2、 </p><p><b> 八皇后問(wèn)題</b></p><p><b> 八皇后問(wèn)題簡(jiǎn)述:</b></p><p> 八皇后問(wèn)題,是一個(gè)古老而著名的問(wèn)題,是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出:在8X8格的國(guó)際象棋上擺放八個(gè)皇后,使其不能互相攻擊,即任意兩個(gè)皇后都不能處于
3、同一行、同一列或同一斜線上,問(wèn)有多少種擺法。</p><p><b> 解決思路:</b></p><p> 先聲明我們根據(jù)條件可以知道皇后肯定是每行都有且只有一個(gè)所以我們創(chuàng)建一個(gè)數(shù)組x[t]讓數(shù)組角標(biāo)表示八皇后的行,用這個(gè)角標(biāo)對(duì)應(yīng)的數(shù)組值來(lái)確定這個(gè)皇后在這行的那一列。</p><p><b> 我們用遞歸來(lái)做:</b&g
4、t;</p><p> 這問(wèn)題要求皇后所在的位置必須和其他皇后的位置不在同一行、列還有 把兩個(gè)皇后看成點(diǎn)其|斜率|=1;所以我們就要寫(xiě)這個(gè)限定條件用一個(gè)函數(shù)來(lái)實(shí)現(xiàn):函數(shù)內(nèi)對(duì)每一個(gè)已經(jīng)放好的皇后的位置進(jìn)行判斷,所以就要有個(gè)循環(huán)。</p><p> 我們既然是用遞歸來(lái)解決問(wèn)題那就要把這個(gè)問(wèn)題分成一個(gè)個(gè)相同的小問(wèn)題來(lái)實(shí)現(xiàn)。</p><p> 不難發(fā)現(xiàn)我們要在8*8的
5、方格里放好8個(gè)皇后那我們就要知道在8(列)*7(行)是怎么放的在有我們事先寫(xiě)好的判斷函數(shù)放好最后行就搞定了;以此類(lèi)推我們要知道8*7的怎么方的我們就要知道8*6是怎么樣的就好了,所以我們是以一行怎么放作為一個(gè)單元。</p><p> 我們就去建一個(gè)可以放好一行的函數(shù)backtrack(int t)里面的t表示是第幾行,在main函數(shù)調(diào)用的時(shí)候第一次傳進(jìn)來(lái)的是0也就是從第一行開(kāi)始判斷。</p>&l
6、t;p> 我們就開(kāi)始寫(xiě)函數(shù)體了:</p><p> 每一行有8個(gè)位置可以放,每一個(gè)位置我們都要去判斷一下所以我們就用循環(huán)來(lái)搞定。</p><p> 在這個(gè)循環(huán)里面我們讓x[t]=i也就是從這一行的第一個(gè)開(kāi)始判斷。放好后就要去判斷是否符合條件。如果符合條件我們就在調(diào)用這個(gè)函數(shù)本身backtrack不過(guò)傳進(jìn)去的參數(shù)是t+1也就是下一行的意思。</p><p>
7、; 在進(jìn)行判斷下一行之前我們要判斷一下t是不是等于8也就是已經(jīng)是最后一行了,如果是最后一行了我們就可以將其進(jìn)行輸出。打印8*8的矩陣(提示在寫(xiě)一個(gè)函數(shù))皇后的位置用1表示出來(lái)沒(méi)有的用0表示。</p><p><b> 三.組員工作分配:</b></p><p> 尹佐斌: 算法分析,代碼編寫(xiě),后期調(diào)試</p><p> 黃文毅: 資料查
8、找,論文設(shè)計(jì),代碼編寫(xiě) </p><p> 檀衛(wèi)杰: 算法分析,代碼編寫(xiě),后期調(diào)試</p><p> 馬賑耀: 論文設(shè)計(jì),代碼編寫(xiě),后期調(diào)試 </p><p><b> 代碼與注解:</b></p><p> #include <math.h></p><p> #i
9、nclude <stdio.h></p><p> #include<string.h></p><p> #include<conio.h> //用getch()要調(diào)用的頭文件</p><p> #include <stdlib.h> //
10、要用system函數(shù)要調(diào)用的頭文件</p><p> int SUM=0; //統(tǒng)計(jì)有多少種可能</p><p> int shezhi(){ //設(shè)置為N皇后問(wèn)題</p><p><b> int N;</b></p><
11、p> printf("這是一個(gè)N皇后問(wèn)題...\n請(qǐng)輸入N=");</p><p> scanf("%d",&N);</p><p><b> return N;</b></p><p><b> }</b></p><p> void
12、 Print(int N,int x[]) //印出結(jié)果</p><p><b> { </b></p><p> int MAX=N;</p><p> for(int i=0;i<MAX;i++)</p><p><b> {</b></p>
13、<p> for(int j=0;j<MAX;j++)</p><p> if(j==x[i])</p><p> printf("●");</p><p><b> else</b></p><p> printf("○");</p>
14、<p> printf("\n");</p><p><b> }</b></p><p> SUM++; //打印一種情況統(tǒng)計(jì)一次</p><p> printf("\n");</p><p><b>
15、; }</b></p><p> int Judge(int k,int x[]) //判斷是否在同一直、橫、斜線上有其它棋子</p><p><b> {</b></p><p><b> int i;</b></p><p> for(i=0;i<
16、;k;i++)</p><p> if( abs(k-i)==abs(x[i]-x[k]) || x[i]==x[k] ) //函數(shù)名: abs; 功能: 求整數(shù)的絕對(duì)值 ;</p><p><b> return 0;</b></p><p><b> return 1;</b></p><
17、p><b> }</b></p><p> void backtrack(int t,int N,int x[]) // 把棋子放到棋盤(pán)上</p><p> { int MAX=N;</p><p><b> int i;</b></p><p> for(
18、i=0;i<MAX;i++){</p><p><b> x[t]=i;</b></p><p> if(Judge(t,x))</p><p><b> {</b></p><p> if(t==MAX-1){</p><p> Print(MAX,x);
19、 // 找到其中一種放法,印出結(jié)果</p><p> } </p><p> else backtrack(t+1,N,x);</p><p><b> }</b></p><p><b> }</b></p&
20、gt;<p><b> }</b></p><p> void Introduce(){</p><p> printf("* * * * * * * * * * * * * * * * * *\n");</p><p> printf("* 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) *
21、\n");</p><p> printf("* *\n");</p><p> printf("* 組員:尹佐斌 黃文毅 *\n");</p><p> printf("* 檀衛(wèi)杰 馬賑耀
22、 *\n");</p><p> printf("* *\n");</p><p> printf("* * * * * * * * * * * * * * * * * *\n");</p><p> printf("\n\n
23、");</p><p> printf("1.設(shè)置為N皇后問(wèn)題。\n");</p><p> printf("2.輸出棋局排布結(jié)果。\n");</p><p> printf("3.統(tǒng)計(jì)棋局排布總數(shù)。\n");</p><p> printf("4.清屏
24、。\n");</p><p> printf("\n\n");</p><p><b> } </b></p><p> void main()</p><p> { int N;</p><p> int x[10]; </p><
25、;p> printf("\n\n\n");</p><p> char flag=1;</p><p> while(flag){</p><p><b> int n;</b></p><p> Introduce(); </p><p><b>
26、 char a;</b></p><p> printf("您確定要進(jìn)行上述操作嗎?(Y/N):");</p><p> a=getchar();</p><p> while(a=='Y'||a=='y'){</p><p> printf("請(qǐng)選擇:&quo
27、t;);</p><p> scanf("%d",&n);</p><p> switch(n){</p><p><b> case 1:</b></p><p> N=shezhi();</p><p><b> break;</b>
28、</p><p><b> case 2:</b></p><p> backtrack(0,N,x);</p><p> printf("按任意鍵返回...");</p><p><b> getch();</b></p><p> syste
29、m("cls");</p><p> Introduce();</p><p><b> break;</b></p><p><b> case 3:</b></p><p> printf("統(tǒng)計(jì)結(jié)果:%d\n",SUM);</p>
30、<p> printf("按任意鍵返回...");</p><p><b> getch();</b></p><p> system("cls");</p><p> Introduce();</p><p><b> break;</b>
31、;</p><p><b> case 4:</b></p><p> printf("按任意鍵返回...");</p><p><b> getch();</b></p><p> system("cls");</p><p>
32、; Introduce();</p><p><b> break;</b></p><p><b> default:</b></p><p> printf("輸入錯(cuò)誤...\n");</p><p> printf("按任意鍵返回...");&
33、lt;/p><p><b> getch();</b></p><p> system("cls");</p><p> Introduce();</p><p><b> break;</b></p><p><b> }</b&g
34、t;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> 五.運(yùn)行效果(截圖):</p><p><b> ?。?lt;/b></p>
35、<p><b> 功能簡(jiǎn)述:</b></p><p> 解決八皇后問(wèn)題根本(遞歸法)</p><p> 可上升為解決“N皇后問(wèn)題”</p><p> 以直觀形式輸出棋局排布</p><p> 統(tǒng)計(jì)棋子排布方法總數(shù)</p><p><b> 清屏函數(shù)的調(diào)用</b
36、></p><p><b> 心得體會(huì)</b></p><p> 本次我們組做的是“八皇后問(wèn)題”,這是一個(gè)歷史經(jīng)典問(wèn)題,經(jīng)過(guò)資料查找,我們發(fā)現(xiàn)關(guān)于八皇后問(wèn)題的算法甚多,比如:回溯法,迭代法,遞歸法,殘卷法等。經(jīng)組員討論,最后我們決定使用遞歸的方法解決該問(wèn)題,分工合作。雖然我們遇到了很多問(wèn)題,但是經(jīng)過(guò)資料查找,和網(wǎng)上提問(wèn),我們最終解決了問(wèn)題。</p>
溫馨提示
- 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ù)僅提供信息存儲(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 課程設(shè)計(jì)——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(八皇后問(wèn)題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)──n皇后八皇后
- 課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(八皇后問(wèn)題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-8皇后問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--趣味問(wèn)題之八皇后 活期儲(chǔ)蓄帳目管理
- 八皇后問(wèn)題課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----huffman編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(迷宮問(wèn)題)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)迷宮問(wèn)題課程設(shè)計(jì)
- c++課程設(shè)計(jì)八皇后問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題課程設(shè)計(jì)報(bào)告
- 迷宮問(wèn)題——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)迷宮問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---學(xué)生搭配問(wèn)題
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---校園導(dǎo)航問(wèn)題
評(píng)論
0/150
提交評(píng)論