《八皇后問(wèn)題的C課程設(shè)計(jì)》由會(huì)員分享,可在線閱讀,更多相關(guān)《八皇后問(wèn)題的C課程設(shè)計(jì)(11頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、
課 程 設(shè) 計(jì) 報(bào) 告
學(xué)院、系:
專業(yè)名稱:
課程設(shè)計(jì)科目
VC++程序課程設(shè)計(jì)
學(xué)生姓名:
指導(dǎo)教師:
完成時(shí)間:
八皇后問(wèn)題
一、設(shè)計(jì)任務(wù)與目標(biāo)
1. 用c++語(yǔ)言平臺(tái)將一個(gè)8*8的棋盤(pán)上放上8?jìng)€(gè)皇后,使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后,也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)。
2. 通過(guò)這次課程設(shè)計(jì),提高自己的編程能力,熟悉c++的編程壞境,為以后的程序開(kāi)發(fā)打 基礎(chǔ)。
二、方案設(shè)計(jì)與論證
2、
在8*8的格的國(guó)際象棋上擺放八個(gè)皇后,使其不能相互攻擊,即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面。
我的主要思路以及思想如下:
1. 解決沖突問(wèn)題:
這個(gè)問(wèn)題包括了行,列,兩條對(duì)角線;
列:規(guī)定每一列放一個(gè)皇后,不會(huì)造成列上的沖突;
行:當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后,則同一行上的所有空格都不能再放皇后,要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài);
對(duì)角線:對(duì)角線有兩個(gè)方向。在這我把這兩條對(duì)角線稱為:主對(duì)角線和從對(duì)角線。在同一對(duì)角線上的所有點(diǎn)(設(shè)下標(biāo)為(i,j)),要么(i+j)是常數(shù),要么(i-j)是常數(shù)。因此,當(dāng)?shù)贗個(gè)皇后占領(lǐng)了第J列后,要同時(shí)把以(i+j)
3、、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。
2. 數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn) :
數(shù)組a[I]:a [I]表示第I個(gè)皇后放置的列;I的范圍:1..8;
對(duì)角線數(shù)組:b[j](主對(duì)角線),c[j](從對(duì)角線),根據(jù)程序的運(yùn)行,去決定主從對(duì)角線是否放入皇后;
算法描述
A、 數(shù)據(jù)初始化。
B、 從n列開(kāi)始擺放第n個(gè)皇后(因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求),先測(cè)試當(dāng)前位置(n,m)是否等于0(未被占領(lǐng))。如果是,擺放第n個(gè)皇后,并宣布占領(lǐng)(記得要橫列豎列斜列一起設(shè)置),接著進(jìn)行遞歸;如果不是,測(cè)試下一個(gè)位置(n,m+1),但是如果當(dāng)n<=8,m=8時(shí),發(fā)現(xiàn)此時(shí)已無(wú)法擺放時(shí),便要進(jìn)行回溯。從
4、問(wèn)題的某一種可能出發(fā),搜索從這種情況能出發(fā),繼續(xù)搜索,這種不斷“回溯”的尋找解的方法,稱為“回溯法”。
C、使用數(shù)組實(shí)現(xiàn)回溯法的思想。
D、當(dāng)n>8時(shí),便打印出結(jié)果。
E、輸出函數(shù)我使用printf輸出,運(yùn)行形式為:第m種方法為:* * * * * * * *
三、程序框圖或流程圖,程序清單與調(diào)用關(guān)系
4、 全部源程序清單
#include
#include
#include
#include
#include
#define QUEENS 8
i
5、nt iCount = 0; //!記錄解的序號(hào)的全局變量。
int Site[QUEENS]; //!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。
void Queen(int n); //!遞歸求解的函數(shù)。
void Output();//!輸出一個(gè)解。
int IsValid(int n);
//!判斷第n個(gè)皇后放上去之后,是否有〉沖突。
void main() /*----------------------------Main:主函數(shù)。----------------------------*/
{ system("title 遞歸算法八皇后問(wèn)題 ");
6、
cout<<" "<<"八皇后的解法:"<
7、始,等于8時(shí)便試出了一個(gè)解,將它輸出并回溯。
{ Output(); return; }
for(i = 1 ; i <= QUEENS ; i++) //!n還沒(méi)到8,在第n行的各個(gè)行上依次試探。
{ Site[n] = i; //!在該行的第i行上放置皇后。
if(IsValid(n)) //!如果放置沒(méi)有沖突,就開(kāi)始下一行的試探。
Queen(n + 1); }}
int IsValid(int n) /*------IsValid:判斷第n個(gè)皇后放上去
8、之后,是否合法,即是否無(wú)沖突。------*/
{ int i;
for(i = 0 ; i < n ; i++) //!將第n個(gè)皇后的位置依次于前面n-1個(gè)皇后的位置比較。
{ if(Site[i] == Site[n]) //!兩個(gè)皇后在同一列上,返回0。
return 0;
if(abs(Site[i] - Site[n]) == (n - i)) //!兩個(gè)皇后在同一對(duì)角線上,返回0。
return 0; }
return 1; //!沒(méi)有沖突,返回1。
}
9、
void Output()/*------------Output:輸出一個(gè)解,即一種沒(méi)有沖突的放置方案。------------*/
{
int i;
printf("No.%-5d" , ++iCount); //!輸出序號(hào)。
for(i = 0 ; i < QUEENS ; i++)//!依次輸出各個(gè)行上的皇后的位置,即所在的列數(shù)。
printf("%d " , Site[i]);
printf("\n");
}
五、程序運(yùn)行的測(cè)試與分析
六、結(jié)論與心得
10、 通過(guò)這次的程序設(shè)計(jì),我從中得到了許多的經(jīng)驗(yàn)以及軟件設(shè)計(jì)的一些新的思路;從這個(gè)八皇后問(wèn)題設(shè)計(jì)以及分析中,本人從中理解到了數(shù)據(jù)結(jié)構(gòu)對(duì)于計(jì)算機(jī)軟件設(shè)計(jì)的重要性,它的使用,可以改變一個(gè)軟件的運(yùn)行周期,也可以將軟件的思路從繁化簡(jiǎn),并且都能夠通過(guò)數(shù)據(jù)結(jié)構(gòu)的相關(guān)引導(dǎo),將本身以前編程思想進(jìn)行擴(kuò)充,發(fā)展;這也是在這次課程設(shè)計(jì)中我所掌握得到的。
但由于我的基本知識(shí)還不是那么扎實(shí),也缺乏對(duì)軟件設(shè)計(jì)的經(jīng)驗(yàn),在這過(guò)程中也出現(xiàn)了一些問(wèn)題,如,八皇后在變成初期由于沒(méi)真正體會(huì)到數(shù)據(jù)結(jié)構(gòu)中“樹(shù)”在里面的運(yùn)用,將程序往大一時(shí)c語(yǔ)言的方向發(fā)展,不自覺(jué)的采用了非遞歸的算法,結(jié)果大大增加了程序的復(fù)雜程度。并且也讓整個(gè)程序
11、的時(shí)間復(fù)雜度變得更大;在后來(lái)學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)的第六章進(jìn)行了比較深入的研讀,才發(fā)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)樹(shù)的實(shí)際運(yùn)用的空間是相當(dāng)?shù)拇螅⑶?,通過(guò)了重溫樹(shù)的回溯,以及二叉樹(shù)的遍歷,最終將程序進(jìn)行了一次較大的改造。并且通過(guò)思考,再將以前的數(shù)組知識(shí)加以運(yùn)用才最終解決了這個(gè)問(wèn)題,整個(gè)程序的算法的可看性也有了相當(dāng)?shù)母倪M(jìn)。
課程設(shè)計(jì)隨著時(shí)間的推移,也即將結(jié)束了,但這上學(xué)期數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還是具有相當(dāng)大的意義,它從一個(gè)程度上改變了我們的編程思想,如何將一個(gè)程序快速而又準(zhǔn)備的進(jìn)行編寫(xiě),進(jìn)行編譯,都成為了我們思考的重點(diǎn),也通過(guò)這一個(gè)學(xué)期的學(xué)習(xí),我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個(gè)階段,我也明白了
12、,好的思想,不能提留于字面上的認(rèn)知,還需要的是平時(shí)多練多寫(xiě)一些相關(guān)的程序,并且通過(guò)修改,加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度,這才是關(guān)鍵。
課程設(shè)計(jì)已經(jīng)接近尾聲了,但它給我的不只是程序設(shè)計(jì)上的滿足,更重要的是對(duì)自己編程思想的一次更新,以及對(duì)算法的一個(gè)全新的認(rèn)識(shí)!
我覺(jué)得還可以考慮開(kāi)發(fā)N皇后問(wèn)題,在主界面中添加一個(gè) int型的變量,程序一開(kāi)始要求輸入一個(gè)數(shù)(確定是幾皇后問(wèn)題),輸入后按下 enter 后,輸出各種解.主程序與八皇后的求解大體相同.
七、參考資料
參
13、考文獻(xiàn)
[1] 陳守孔,孟佳娜,算法與數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言版. 機(jī)械工業(yè)出版社
[2] 嚴(yán)蔚敏,吳偉民,數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社
[3] 劉斌,王忠,面向?qū)ο蟪绦蛟O(shè)計(jì)Visual C++ . 清華大學(xué)出版社
課程設(shè)計(jì)成績(jī)?cè)u(píng)定表
對(duì)課程設(shè)計(jì)工作過(guò)程的簡(jiǎn)短介紹和自我評(píng)價(jià)
學(xué)生簽名:
2010年 月 日
(以下由評(píng)定小組教師填寫(xiě))
質(zhì)量評(píng)價(jià)指標(biāo)(在相應(yīng)欄目打√)
評(píng) 價(jià) 項(xiàng) 目
評(píng) 價(jià) 質(zhì) 量
優(yōu)秀
良好
一般
及格
不及格
工作量和態(tài)度
實(shí)驗(yàn)、計(jì)算可靠性
文字和圖表質(zhì)量
總體評(píng)價(jià)
評(píng)定成績(jī)(百分制)
評(píng)定小組成員簽名
2010年 月 日
制定人: 審定人:
10 / 11文檔可自由編輯打印