八皇后問題的C課程設(shè)計(jì)

課 程 設(shè) 計(jì) 報(bào) 告學(xué)院、系：專業(yè)名稱：課程設(shè)計(jì)科目VC+程序課程設(shè)計(jì)學(xué)生姓名：指導(dǎo)教師：完成時(shí)間：八皇后問題一、設(shè)計(jì)任務(wù)與目標(biāo) 1. 用c+語言平臺(tái)將一個(gè)的棋盤上放上個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)。2. 通過這次課程設(shè)計(jì),提高自己的編程能力,熟悉c+的編程壞境,為以后的程序開發(fā)打基礎(chǔ)。 二、方案設(shè)計(jì)與論證在8*8的格的國(guó)際象棋上擺放八個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面。我的主要思路以及思想如下：1. 解決沖突問題： 這個(gè)問題包括了行，列，兩條對(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)、(i-j)為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。 2.數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn) ：數(shù)組aI：a I表示第I個(gè)皇后放置的列；I的范圍：1.8; 對(duì)角線數(shù)組：bj(主對(duì)角線),cj（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后；算法描述A、 數(shù)據(jù)初始化。B、 從n列開始擺放第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í)已無法擺放時(shí)，便要進(jì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 <conio.h>#include <math.h>#include <stdlib.h>#include <stdio.h>#include <iostream.h>#define QUEENS 8int iCount = 0; /!記錄解的序號(hào)的全局變量。int SiteQUEENS; /!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。void Queen(int n); /!遞歸求解的函數(shù)。void Output();/!輸出一個(gè)解。int IsValid(int n); /!判斷第n個(gè)皇后放上去之后，是否有沖突。void main() /*-Main：主函數(shù)。-*/ system("title 遞歸算法八皇后問題 ");cout<<" "<<"八皇后的解法："<<endl;cout<<" "<<"-"<<endl; Queen(0); /!從第0行開始遞歸試探。 getch();/!按任意鍵返回。 void Queen(int n) /*-Queen：遞歸放置第n個(gè)皇后，程序的核心!-*/ int i; if(n = QUEENS) /!參數(shù)n從0開始，等于8時(shí)便試出了一個(gè)解，將它輸出并回溯。 Output(); return; for(i = 1 ; i <= QUEENS ; i+) /!n還沒到8，在第n行的各個(gè)行上依次試探。 Siten = i; /!在該行的第i行上放置皇后。 if(IsValid(n) /!如果放置沒有沖突，就開始下一行的試探。 Queen(n + 1); int IsValid(int n) /*-IsValid：判斷第n個(gè)皇后放上去之后，是否合法，即是否無沖突。-*/ int i; for(i = 0 ; i < n ; i+) /!將第n個(gè)皇后的位置依次于前面n1個(gè)皇后的位置比較。 if(Sitei = Siten) /!兩個(gè)皇后在同一列上，返回0。 return 0; if(abs(Sitei - Siten) = (n - i) /!兩個(gè)皇后在同一對(duì)角線上，返回0。 return 0; return 1; /!沒有沖突，返回1。 void Output()/*-Output：輸出一個(gè)解，即一種沒有沖突的放置方案。-*/ int i; printf("No.%-5d" , +iCount); /!輸出序號(hào)。 for(i = 0 ; i < QUEENS ; i+)/!依次輸出各個(gè)行上的皇后的位置，即所在的列數(shù)。 printf("%d " , Sitei); printf("n"); 五、程序運(yùn)行的測(cè)試與分析 六、結(jié)論與心得 通過這次的程序設(shè)計(jì)，我從中得到了許多的經(jīng)驗(yàn)以及軟件設(shè)計(jì)的一些新的思路；從這個(gè)八皇后問題設(shè)計(jì)以及分析中，本人從中理解到了數(shù)據(jù)結(jié)構(gòu)對(duì)于計(jì)算機(jī)軟件設(shè)計(jì)的重要性，它的使用，可以改變一個(gè)軟件的運(yùn)行周期，也可以將軟件的思路從繁化簡(jiǎn)，并且都能夠通過數(shù)據(jù)結(jié)構(gòu)的相關(guān)引導(dǎo)，將本身以前編程思想進(jìn)行擴(kuò)充，發(fā)展；這也是在這次課程設(shè)計(jì)中我所掌握得到的。 但由于我的基本知識(shí)還不是那么扎實(shí)，也缺乏對(duì)軟件設(shè)計(jì)的經(jīng)驗(yàn)，在這過程中也出現(xiàn)了一些問題，如，八皇后在變成初期由于沒真正體會(huì)到數(shù)據(jù)結(jié)構(gòu)中“樹”在里面的運(yùn)用，將程序往大一時(shí)c語言的方向發(fā)展，不自覺的采用了非遞歸的算法，結(jié)果大大增加了程序的復(fù)雜程度。并且也讓整個(gè)程序的時(shí)間復(fù)雜度變得更大；在后來學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)的第六章進(jìn)行了比較深入的研讀，才發(fā)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)樹的實(shí)際運(yùn)用的空間是相當(dāng)?shù)拇螅⑶?，通過了重溫樹的回溯，以及二叉樹的遍歷，最終將程序進(jìn)行了一次較大的改造。并且通過思考，再將以前的數(shù)組知識(shí)加以運(yùn)用才最終解決了這個(gè)問題，整個(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)行編寫，進(jìn)行編譯，都成為了我們思考的重點(diǎn)，也通過這一個(gè)學(xué)期的學(xué)習(xí)，我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個(gè)階段，我也明白了，好的思想，不能提留于字面上的認(rèn)知，還需要的是平時(shí)多練多寫一些相關(guān)的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關(guān)鍵。 課程設(shè)計(jì)已經(jīng)接近尾聲了，但它給我的不只是程序設(shè)計(jì)上的滿足，更重要的是對(duì)自己編程思想的一次更新，以及對(duì)算法的一個(gè)全新的認(rèn)識(shí)！ 我覺得還可以考慮開發(fā)N皇后問題,在主界面中添加一個(gè) int型的變量,程序一開始要求輸入一個(gè)數(shù)(確定是幾皇后問題),輸入后按下 enter 后,輸出各種解.主程序與八皇后的求解大體相同. 七、參考資料 參考文獻(xiàn)1 陳守孔，孟佳娜，算法與數(shù)據(jù)結(jié)構(gòu)c語言版. 機(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ì)工作過程的簡(jiǎn)短介紹和自我評(píng)價(jià) 學(xué)生簽名：2010年 月 日（以下由評(píng)定小組教師填寫）質(zhì)量評(píng)價(jià)指標(biāo)（在相應(yīng)欄目打）評(píng) 價(jià) 項(xiàng) 目評(píng) 價(jià) 質(zhì) 量?jī)?yōu)秀良好一般及格不及格工作量和態(tài)度實(shí)驗(yàn)、計(jì)算可靠性文字和圖表質(zhì)量總體評(píng)價(jià)評(píng)定成績(jī)（百分制）評(píng)定小組成員簽名2010年 月 日制定人： 審定人：10 / 11文檔可自由編輯打印