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