關于c語言編程中八皇后問題的設計報告

1、關于 c 語言編程中八皇后問題的設計報告一、課題的來源及意義八皇后問題是一個古老而著名的問題，該問題是十九世紀著名的數(shù)學家高斯1850 年提出的。在國際象棋中，皇后是最有權利的一個棋子；只要別的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時，它就能把對方棋子吃掉。所以高斯提出了一個問題：在8*8 的格的國際象棋上擺放八個皇后，使其不能相互攻擊，即任意兩個皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法。到了現(xiàn)代，隨著計算機技術的飛速發(fā)展，這一古老而有趣的數(shù)學游戲問題也自然而然的被搬到了計算機上。運用所學計算機知識來試著解決這個問題是個鍛煉和提高我自己編程能力和獨立解決

2、問題能力的好機會，可以使我增強信心，為我以后的編程開個好頭，故我選擇了這個有趣的課題。二、面對的問題1）解決沖突問題：這個問題包括了行，列，兩條對角線；列：規(guī)定每一列放一個皇后，不會造成列上的沖突；行：當?shù)贗 行被某個皇后占領后，則同一行上的所有空格都不能再放皇后，要把以I 為下標的標記置為被占領狀態(tài)；2）使用數(shù)據(jù)結構的知識，用遞歸法解決問題。三、需求分析1、涉及到的知識本次設計中，用到的主要知識有：遞歸法的運用，for 語句的靈活運用，數(shù)據(jù)結構中樹知識的靈活運用、棧及數(shù)組的掌握。2、軟硬件的需求1）系統(tǒng)要求：win xp 以上操作系統(tǒng)；2）語言平臺：tc+或 vc+6.0；3、功能需求當運行

3、程序時，在屏幕上顯示每一種方法八個皇后的相對位置，要用比較直觀的界面顯示。我的思想是用循環(huán)遞歸循環(huán)來實現(xiàn)的，分別一一測試了每一種擺法， 并把它擁有的92種變化表現(xiàn)出來。在這個程序中，我的主要思路以及思想是這樣的：1）解決沖突問題：這個問題包括了行，列，兩條對角線；列：規(guī)定每一列放一個皇后，不會造成列上的沖突；行：當?shù)贗 行被某個皇后占領后，則同一行上的所有空格都不能再放皇后，要把以I 為下標的標記置為被占領狀態(tài)；對角線：對角線有兩個方向。在這我把這兩條對角線稱為：主對角線和從對角線。在同一對角線上的所有點（設下標為（i,j） ） ，要么 （i+j） 是常數(shù)，要么（i-j） 是常數(shù)。因此，當?shù)贗

4、 個皇后占領了第 J 列后， 要同時把以（i+j） 、 （i-j） 為下標的標記置為被占領狀態(tài)。2）數(shù)據(jù)結構的實現(xiàn)而對于數(shù)據(jù)結構的實現(xiàn)，學生則是著重于:數(shù)組 aI ： a I 表示第 I 個皇后放置的列；I 的范圍：1.8;對角線數(shù)組：bj（ 主對角線）,cj （從對角線），根據(jù)程序的運行，去決定主從對角線是否放入皇后；五、詳細設計和實現(xiàn)1、算法描述A、 數(shù)據(jù)初始化。B、 從n 列開始擺放第n 個皇后（因為這樣便可以符合每一豎列一個皇后的要求），先測試當前位置（n，m）是否等于0（未被占領） 。如果是，擺放第n 個皇后，并宣布占領（記得姚橫列豎列斜列一起設置），接著進行遞歸；如果不是，測試下一

5、個位置（n， m+1） ，但是如果當n<=8， m=8時，發(fā)現(xiàn)此時已無法擺放時，便要進行回溯。從問題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解的方法，稱為“回溯法”。C、使用數(shù)組實現(xiàn)回溯法的思想。D、當n>8時，便打印出結果。E、 輸出函數(shù)我使用printf 輸出， 運行形式為：第 m種方法為：* * * * * * * *2、算法流程圖六、代碼編寫及詳細注釋#include <conio.h>#include <math.h>#include <stdlib.h>#include <stdio.h>#

6、include <iostream.h>#define QUEENS 8int iCount = 0; /!記錄解的序號的全局變量。int SiteQUEENS; /!記錄皇后在各行上的放置位置的全局數(shù)組。void Queen(int n); /! 遞歸求解的函數(shù)。void Output();/! 輸出一個解。int IsValid(int n);/! 判斷第 n 個皇后放上去之后，是否有沖突。void main() /*Main： 主 函 數(shù) 。*/ system("title葉青 - 遞歸算法八皇后問題");cout<<""&

7、lt;<"八皇后的解法："<<endl;cout<<" "<<""<<endl;Queen(0); /! 從第 0行開始遞歸試探。getch();/! 按任意鍵返回。void Queen(int n) /*Queen：遞歸放置第n 個皇后，程序的核心!*/ int i;if(n = QUEENS) /! 參數(shù) n 從 0 開始，等于8 時便試出了一個解，將它輸出并回溯。 Output(); return; 還沒到8，在第n 行的各個行上for(i = 1 ; i <= QUE

8、ENS ; i+) /!n依次試探。Siten = i; /!在該行的第i 行上放置皇后。if(IsValid(n) /! 如果放置沒有沖突，就開始下一行的試探。Queen(n + 1); n 個皇后放上去之后，是int IsValid(int n) /*IsValid否合法，即是否無沖突。*/int i;for(i = 0 ; i < n ; i+) /!將第 n 個皇后的位置依次于前面n 1 個皇后的位置比較。if(Sitei = Siten) /!兩個皇后在同一列上，返回0。return 0;兩個皇后在同一對角線上，if(abs(Sitei - Siten) = (n - i) /

9、!返回0。return 0; return 1; /! 沒有沖突，返回1。void Output()/*Output ：輸出一個解，即一種沒有沖突的放置方案。 */int i;printf("No.%-5d" , +iCount); /!輸出序號。for(i = 0 ; i < QUEENS ; i+)/!依次輸出各個行上的皇后的位置，即所在的列數(shù)。printf("%d " , Sitei);printf("n");七、程序調(diào)試調(diào)試過程、步驟及遇到的問題在完整程序調(diào)試時遇到幾個小問題，后經(jīng)細心改正后才把調(diào)試工作做完。例如 : 當

10、用 printf 輸出時 , 出現(xiàn)了一些錯誤, 幾經(jīng)調(diào)試后, 發(fā)現(xiàn)原來是缺少了stdio.h 這樣一個頭文件, 添加了頭文件后, 還出現(xiàn)了一些問題, 邏輯錯誤導致程序死循環(huán)或不循環(huán)或循環(huán)一小部分, 但是編譯時卻沒有錯誤, 就是沒有正確的輸出答案, 一開始我也不知道是怎么回事, 通過和同學的交流, 發(fā)現(xiàn)是邏輯錯誤, 經(jīng)過改正后, 程序終于可以運行了.八、運行與測試運行演示九、總結在這次的程序設計，我從中得到了許多的經(jīng)驗以及軟件設計的一些新的思路；從這個八皇后問題設計以及分析中，本人從中理解到了數(shù)據(jù)結構對于計算機軟件設計的重要性，它的使用，可以改變一個軟件的運行周期，也可以將軟件的思路從繁化簡，并

11、且都能夠通過數(shù)據(jù)結構的相關引導，將本身以前編程思想進行擴充，發(fā)展；這也是在這次課程設計中我所掌握得到的。但由于我的基本知識還不是那么扎實，也缺乏對軟件設計的經(jīng)驗，在這過程中也出現(xiàn)了一些問題，如，八皇后在變成初期由于沒真正體會到數(shù)據(jù)結構中“樹”在里面的運用， 將程序往大一時c 語言的方向發(fā)展，不自覺的采用了非遞歸的算法，結果大大增加了程序的復雜程度。 并且也讓整個程序的時間復雜度變得更大；在后來學生對數(shù)據(jù)結構的第六章進行了比較深入的研讀，才發(fā)現(xiàn)了數(shù)據(jù)結構樹的實際運用的空間是相當?shù)拇螅⑶?，通過了重溫樹的回溯，以及二叉樹的遍歷，最終將程序進行了一次較大的改造。并且通過思考，再將以前的數(shù)組知識加以運

12、用才最終解決了這個問題，整個程序的算法的可看性也有了相當?shù)母倪M。以前對數(shù)據(jù)結構的學習還是具有相當大的意義，它從一個程度上改變了我們的編程思想，如何將一個程序快速而又準備的進行編寫，進行編譯，都成為了我們思考的重點，也通過這一門課的學習，我們將數(shù)據(jù)結構的思想帶入到了我們以后的編程學習中去。在這個階段，我也明白了，好的思想，不能提留于字面上的認知，還需要的是平時多練多寫一些相關的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關鍵。我覺得還可以考慮開發(fā)N皇后問題, 在主界面中添加一個int 型的變量 , 程序一開始要求輸入一個數(shù)（ 確定是幾皇后問題）, 輸入后按下 enter 后 , 輸出各種解. 主程序與八皇后的求解大體相同.十、參考文獻1 蘇仕華 , 數(shù)據(jù)結構課程設計.- 北京 : 機械工業(yè)出版社,2005.52 于永彥 , 趙建洋 . 課程設計指導書. 淮安：江蘇淮陰工學院計算機工程系 ,20063 劉振安 , 劉燕君，孫忱. C+ 語言課程設計. 北京：高等教育出版社 ,20034 陳志泊 , 張海燕 , 王春玲 . Visual C+ 程序設計