第一篇：關(guān)于c語言編程中八皇后問題的設(shè)計(jì)報(bào)告
關(guān)于c語言編程中八皇后問題的設(shè)計(jì)報(bào)告
一、課題的來源及意義
八皇后問題是一個(gè)古老而著名的問題，該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出的。
在國際象棋中，皇后是最有權(quán)利的一個(gè)棋子；只要?jiǎng)e的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時(shí)，它就能把對(duì)方棋子吃掉。所以高斯提出了一個(gè)問題：在8*8的格的國際象棋上擺放八個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法。
到了現(xiàn)代，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，這一古老而有趣的數(shù)學(xué)游戲問題也自然而然的被搬到了計(jì)算機(jī)上。運(yùn)用所學(xué)計(jì)算機(jī)知識(shí)來試著解決這個(gè)問題是個(gè)鍛煉和提高我自己編程能力和獨(dú)立解決問題能力的好機(jī)會(huì)，可以使我增強(qiáng)信心，為我以后的編程開個(gè)好頭，故我選擇了這個(gè)有趣的課題。
二、面對(duì)的問題
1）解決沖突問題：這個(gè)問題包括了行，列，兩條對(duì)角線； 列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突； 行：當(dāng)?shù)贗行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；
2）使用數(shù)據(jù)結(jié)構(gòu)的知識(shí)，用遞歸法解決問題。
三、需求分析
1、涉及到的知識(shí)
本次設(shè)計(jì)中，用到的主要知識(shí)有：遞歸法的運(yùn)用，for語句的靈活運(yùn)用，數(shù)據(jù)結(jié)構(gòu)中樹知識(shí)的靈活運(yùn)用、棧及數(shù)組的掌握。
2、軟硬件的需求
1)系統(tǒng)要求：winxp以上操作系統(tǒng)； 2)語言平臺(tái)：tc++或vc++6.0；
3、功能需求
當(dāng)運(yùn)行程序時(shí)，在屏幕上顯示每一種方法八個(gè)皇后的相對(duì)位置，要用比較直觀 的界面顯示。
四、概要設(shè)計(jì)
我的思想是用循環(huán)遞歸循環(huán)來實(shí)現(xiàn)的，分別一一測試了每一種擺法，并把它擁有的92種變化表現(xiàn)出來。在這個(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)
而對(duì)于數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，學(xué)生則是著重于: 數(shù)組a[I]：a [I]表示第I個(gè)皇后放置的列；I的范圍：1..8;對(duì)角線數(shù)組：b[j](主對(duì)角線),c[j]（從對(duì)角線），根據(jù)程序的運(yùn)行，去決定主從對(duì)角線是否放入皇后；
五、詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)
1、算法描述
A、數(shù)據(jù)初始化。
B、從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測試當(dāng)前位置（n，m）是否等于0（未被占領(lǐng)）。如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)（記得姚橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測試下一個(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種方法為：* * * * * * * *
2、算法流程圖
六、代碼編寫及詳細(xì)注釋
#include
void main()/*----------------------------Main：主函數(shù)。----------------------------*/ { system(“title 葉青--遞歸算法八皇后問題 ”);cout<<“ ”<<“八皇后的解法：”< { Output();return;} for(i = 1;i <= QUEENS;i++)//!n還沒到8，在第n行的各個(gè)行上依次試探。 { Site[n] = 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è)皇后的位置依次于前面n－1個(gè)皇后的位置比較。 { if(Site[i] == Site[n])//!兩個(gè)皇后在同一列上，返回0。return 0;if(abs(Site[i]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 ” , Site[i]);printf(“n”);} 七、程序調(diào)試 調(diào)試過程、步驟及遇到的問題 在完整程序調(diào)試時(shí)遇到幾個(gè)小問題，后經(jīng)細(xì)心改正后才把調(diào)試工作做完。 例如:當(dāng)用printf輸出時(shí),出現(xiàn)了一些錯(cuò)誤,幾經(jīng)調(diào)試后,發(fā)現(xiàn)原來是缺少了stdio.h這樣一個(gè)頭文件,添加了頭文件后, 還出現(xiàn)了一些問題,邏輯錯(cuò)誤導(dǎo)致程序死循環(huán)或不循環(huán)或循環(huán)一小部分,但是編譯時(shí)卻沒有錯(cuò)誤,就是沒有正確的輸出答案,一開始我也不知道是怎么回事,通過和同學(xué)的交流,發(fā)現(xiàn)是邏輯錯(cuò)誤,經(jīng)過改正后,程序終于可以運(yùn)行了.八、運(yùn)行與測試 運(yùn)行演示 九、總結(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)行周期，也可以將軟件的思路從繁化簡，并且都能夠通過數(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)。 以前對(duì)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還是具有相當(dāng)大的意義，它從一個(gè)程度上改變了我們的編程思想，如何將一個(gè)程序快速而又準(zhǔn)備的進(jìn)行編寫，進(jìn)行編譯，都成為了我們思考的重點(diǎn)，也通過這一門課的學(xué)習(xí)，我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個(gè)階段，我也明白了，好的思想，不能提留于字面上的認(rèn)知，還需要的是平時(shí)多練多寫一些相關(guān)的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關(guān)鍵。 我覺得還可以考慮開發(fā)N皇后問題,在主界面中添加一個(gè) int型的變量,程序一開始要求輸入一個(gè)數(shù)(確定是幾皇后問題),輸入后按下 enter 后,輸出各種解.主程序與八皇后的求解大體相同.十、參考文獻(xiàn) [1]蘇仕華,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).-北京:機(jī)械工業(yè)出版社,2005.5 [2]于永彥,趙建洋.課程設(shè)計(jì)指導(dǎo)書.淮安：江蘇淮陰工學(xué)院 計(jì)算機(jī)工程系,2006 [3]劉振安,劉燕君，孫忱.C++語言課程設(shè)計(jì).北京：高等教育出版社,2003 [4]陳志泊, 張海燕, 王春玲.Visual C++程序設(shè)計(jì).中國鐵道出版社 ,2005 [5]呂鳳哲,C++語言程序設(shè)計(jì)（第二版）.北京：電子工業(yè)出版社,2005 [6]殷人昆，陶永雷等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++）.北京:清華大學(xué)出版社，1999 [7]嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)．北京：清華大學(xué)出版社，1997 [8]李春葆.數(shù)據(jù)結(jié)構(gòu)—考研指導(dǎo).北京:清華大學(xué)出版社,2002 [9]陳慧南．?dāng)?shù)據(jù)結(jié)構(gòu)—C++語言描述．北京：人民郵電出版社，2005．03 數(shù)據(jù)結(jié)構(gòu) 實(shí)習(xí)報(bào)告 專業(yè)：數(shù)字媒體技術(shù) 姓名：李義 年級(jí)：2013級(jí) 學(xué)號(hào)：201301052015 完成日期：2015.12.31 題目：八皇后問題 一、項(xiàng)目簡介 八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8?8格的國際象棋棋盤上，安放八個(gè)皇后，要求沒有一個(gè)皇后能夠“吃掉”任何其他一個(gè)皇后，即任意兩個(gè)皇后都不能處于同一行、同一列或同一條對(duì)角線上，求解有多少種擺法。 高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法得出結(jié)論，有92種擺法。 二、概要設(shè)計(jì) 2.1 主要模塊： 這個(gè)程序主要由4個(gè)模塊組成，分別是畫棋盤模塊，畫皇后模塊，輸出皇后擺法模塊，和解決如何擺置皇后模塊。這4個(gè)模塊隸屬于主函數(shù)模塊。既主函數(shù)通過對(duì)這4個(gè)模塊的合理調(diào)用解決“8皇后問題”，同時(shí)這4個(gè)模塊之間也互有調(diào)用。 2.2 程序設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)及其關(guān)系： 數(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ì)角線是否放入皇后；然后進(jìn)行數(shù)據(jù)的初始化。從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測試當(dāng)前位置(n,m)是否等于０（未被占領(lǐng)）:如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)(切記要橫列豎列斜列一起來)，接著進(jìn)行遞歸；如果不是，測試下一個(gè)位置(n,m+1)，但是如果當(dāng)時(shí)，卻發(fā)現(xiàn)此時(shí)已經(jīng)無法擺放時(shí)，便要進(jìn)行回溯。 三、詳細(xì)設(shè)計(jì) 3.1 定義相關(guān)的數(shù)據(jù)類型： 3.1.1 定義的相關(guān)數(shù)據(jù)類型： int A[21],B[21],C[21],Y[8];void *buff1,*buff2 3.1.2 設(shè)計(jì)思想： 本程序通過對(duì)子函數(shù)void qu(int i)的調(diào)用，將八皇后的問題關(guān)鍵通過數(shù)據(jù)結(jié)構(gòu)的思想予以了實(shí)現(xiàn)。雖然題目以及演算看起來都比較復(fù)雜，繁瑣，但在實(shí)際中，只要當(dāng)一只皇后放入棋盤后，在橫與列、斜線上沒有另外一只皇后與其沖突，再對(duì)皇后的定位進(jìn)行相關(guān)的判斷。即可完成。如果在這個(gè)程序中，我們運(yùn)用的是非遞歸的思想，那么將大量使用if等語句，并通過不斷的判斷，去推出答案，而且這種非遞歸的思想，大大的增加了程序的時(shí)間復(fù)雜度。如果我們使用了數(shù)據(jù)結(jié)構(gòu)中的算法后，那么程序的時(shí)間復(fù)雜度，以及相關(guān)的代碼簡化都能取得不錯(cuò)的改進(jìn)。這個(gè)程序，我運(yùn)用到了數(shù)據(jù)結(jié)構(gòu)中的棧、數(shù)組，以及樹和回溯的方法。特別是在對(duì)于樹以及二叉樹的學(xué)習(xí)，更是為八皇后的問題提供了科學(xué)的解決方案，通過對(duì)樹的分析，把八皇后的問題看成了樹，而在衍生第一個(gè)變化后，上面的第一層八個(gè)變化就變成了八個(gè)結(jié)點(diǎn)，而這八個(gè)結(jié)點(diǎn)再繼續(xù)的衍生??，這樣比較形象的將八皇后的問題簡單化了。然后再通過回溯法進(jìn)行設(shè)計(jì)，回溯法是設(shè)計(jì)遞歸過程的一個(gè)重要的方法。它的求解過程實(shí)質(zhì)上是一個(gè)先序遍歷一棵“狀態(tài)樹“的過程。在這個(gè)程序設(shè)計(jì)中，它先進(jìn)行判斷，棋盤上是否已經(jīng)得到一個(gè)完整的布局（即棋盤是否已經(jīng)擺上8個(gè)棋子），如果是，則輸出布局；如果不是則依次先根遍歷滿足約束條件的各棵子樹，流程即是： 判斷該子樹根的布局是否合法：如果合法的話，則先根遍歷該子樹；如果不合法的話，則剪去該子樹的分支。 3.2 相關(guān)代碼及算法 3.2.1 主模塊C碼算法： void main(void){ Queen Q; int gdriver=DETECT,gmode; initgraph(&gdriver,&gmode,“D://Win-TC”); SetQueen(&Q); setcolor(YELLOW); QueenPic(); cleardevice(); setcolor(LIGHTGREEN); settextstyle(0,0,3); outtextxy(180,10,“Eight Queens”); setcolor(WHITE); settextstyle(0,0,1); outtextxy(250,400,“2009.11.8 3:30pm”); QueenRe(&Q,0); getch(); closegraph();} 3.2.2 棋盤模塊C碼算法 void Checker(void) /* 畫棋盤函數(shù) */ { int i,k; for(k=0;k<8;k++) for(i=0;i<8;i++) if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE); setcolor(LIGHTBLUE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE); setcolor(WHITE); rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20); floodfill(i*20+10,20+k*20+10,WHITE);} } 3.2.3 皇后模塊C碼算法： void QueenPic(void) /* 畫皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ { int size，polypoints1[10]={9,1,11,1,20,20,1,20,9,1}，polypoints2[10]={29,1,31,1,40,20,21,20,29,1}; setfillstyle(SOLID_FILL,LIGHTBLUE); /* 畫淡藍(lán)色棋格 */ setcolor(LIGHTBLUE); rectangle(1,1,20,20); floodfill(10,10,LIGHTBLUE); setfillstyle(SOLID_FILL,WHITE); /* 畫白色棋格 */ setcolor(WHITE); rectangle(21,1,40,20); floodfill(30,10,WHITE); setfillstyle(SOLID_FILL,DARKGRAY); setcolor(YELLOW); drawpoly(5,polypoints1); drawpoly(5,polypoints2); floodfill(10,10,YELLOW); floodfill(30,10,YELLOW); size=imagesize(1,1,20,20); /* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */ buff1=(void *)malloc(size); buff2=(void *)malloc(size); getimage(1,1,20,20,buff1); getimage(21,1,40,20,buff2); cleardevice();} 3.2.4 八皇后擺放方法模塊C碼: void QueenRe(Queen *Q, int y) 八皇后的遞歸算法 {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])下一棵要遍歷的子樹由狀態(tài)數(shù)確定 { Q->Y[y]=x;放置皇后 Q->A[x+7]=1;標(biāo)記下次這里不能放置皇后 Q->B[x+y+7]=1;標(biāo)記下次這里不能放置皇后 Q->C[x-y+7]=1;標(biāo)記下次這里不能放置皇后 if(y==7) PrintQueen(Q);調(diào)用輸出圖形函數(shù) QueenRe(Q,y+1);進(jìn)入下一層遞歸 Q->A[x+7]=0;如果上次擺法導(dǎo)致后面不能繼續(xù)擺放則重置標(biāo)記為0 Q->B[x+y+7]=0; Q->C[x-y+7]=0; } } 3.2.5 初始化模塊C碼: void SetQueen(Queen *Q) /* 初始化 */ {int i; for(i=0;i<21;i++) {Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;初始化為0，表示可以放置皇后。} for(i=0;i<8;i++) Q->Y[i]=-1;} 3.2.6 圖形輸出： void PrintQueen(Queen *t) /* 圖形輸出函數(shù) */ {int k; char str[20]; static total=0; total++; setviewport(240,80,400,260,1); /* 設(shè)置窗口 */ sprintf(str,“NO.%d”,total); setcolor(GREEN); settextstyle(0,0,1); outtextxy(0,0,str); Checker(); for(k=0;k<8;k++) if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0) putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);else putimage((t->Y[k])*20,20+k*20,buff2,COPY_PUT); getch(); if(getch()==27)exit(0); clearviewport();} void QueenRe(Queen *Q, int y) /* 八皇后的遞歸算法 */ {int x; if(y>7) return; for(x=0;x<8;x++) if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍歷的子樹由狀態(tài)數(shù)確定 */ {Q->Y[y]=x; Q->A[x+7]=1; Q->B[x+y+7]=1; Q->C[x-y+7]=1; if(y==7) PrintQueen(Q); QueenRe(Q,y+1); /* 進(jìn)入下一層遞歸 */ Q->A[x+7]=0; Q->B[x+y+7]=0; Q->C[x-y+7]=0;} } } 3.3函數(shù)調(diào)用圖 3.4項(xiàng)目流程圖 通過編譯連接后，程序基本上把八皇后的92種擺法的都進(jìn)行了演示； 但程 四、調(diào)試分析 序運(yùn)行中也出現(xiàn)了以下缺點(diǎn)： 因?yàn)榘嘶屎蟮谋憩F(xiàn)方法甚多，輸出后雖能全部顯示，但未能使屏幕停留，把一個(gè)一個(gè)的將其顯示出來,但是這樣便使得操作步驟太多,也會(huì)造成不必要的麻煩!所以只畫出了第一種和最后一種的輸出結(jié)果，演示如圖所示： 五、設(shè)計(jì)體會(huì) 該程序在調(diào)試的過程中出現(xiàn)了不少的問題！如數(shù)據(jù)溢出等（是自己過于粗心而造成的）。在調(diào)試的過程中出現(xiàn)的一個(gè)最大的問題就是：在運(yùn)行的時(shí)候出現(xiàn)解的個(gè)數(shù)大于自己所預(yù)計(jì)的。經(jīng)過不斷的查看內(nèi)存變量，操作次數(shù)但還是沒有找出問題的所在。終于在晚上十二點(diǎn)的時(shí)候，決定睡覺！但一關(guān)上電腦，躺在床上的時(shí)候，突然想到了一個(gè)問題：經(jīng)過讀了一些資料，知道八皇后問題有12組實(shí)質(zhì)解，92組全解——這說明在這12組實(shí)質(zhì)解中有其中的一組解是比其它的解要特殊一點(diǎn)的：其它的解經(jīng)過等價(jià)的變換之后都會(huì)產(chǎn)生8組等價(jià)的解，只有這個(gè)特殊的解只有4組等價(jià)的解。說不定我的問題就出在這里！我之前也寫了一些有關(guān)的代碼處理這個(gè)問題，但我之前以為這個(gè)特殊的解是一個(gè)完全中心對(duì)稱的圖形（每轉(zhuǎn)90度得到的圖形就是它自己本身），所以我的在這里的判斷就出現(xiàn)錯(cuò)誤了！后來經(jīng)過相關(guān)代碼的修改，問題終于解決了，程序正確運(yùn)行。 本課程設(shè)計(jì)本人的目的也是通過用WIN-TC程序設(shè)計(jì)平臺(tái)將一個(gè)８＊８的棋盤上放上８個(gè)皇后，使得每一個(gè)皇后既攻擊不到另外七個(gè)皇后，也不被另外七個(gè)皇后所攻擊的92種結(jié)構(gòu)予以實(shí)現(xiàn)．最終將其問題變得一目了然，更加易懂。 六、用戶使用說明 6.1 程序的使用平臺(tái)： 系統(tǒng)要求：windows2000以上操作系統(tǒng)； 語言開發(fā)平臺(tái)：WIN-TC； 6.2 源代碼分析： 首先對(duì)程序中的函數(shù)頭文件進(jìn)行引入，定位；在這個(gè)程序中，與其他C++的程序一樣，都是引入：#include 七、附錄 #include void *buff1,*buff2;typedef struct { int A[21],B[21],C[21],Y[8];} Queen;void SetQueen(Queen *Q) /* 初始化 */ { int i;for(i=0;i<21;i++){ Q->A[i]=0;Q->B[i]=0;Q->C[i]=0;} for(i=0;i<8;i++)Q->Y[i]=-1;} void QueenPic(void) /* 畫皇后圖象，然后存儲(chǔ)到緩沖區(qū) */ { int size, polypoints1[10]={9,1,11,1,20,20,1,20,9,1}, polypoints2[10]={29,1,31,1,40,20,21,20,29,1};setfillstyle(SOLID_FILL,LIGHTBLUE); /* 畫淡藍(lán)色棋格 */ setcolor(LIGHTBLUE);rectangle(1,1,20,20);floodfill(10,10,LIGHTBLUE);setfillstyle(SOLID_FILL,WHITE); /* 畫白色棋格 */ setcolor(WHITE);rectangle(21,1,40,20);floodfill(30,10,WHITE);setfillstyle(SOLID_FILL,DARKGRAY);setcolor(YELLOW);drawpoly(5,polypoints1);drawpoly(5,polypoints2);floodfill(10,10,YELLOW);floodfill(30,10,YELLOW);size=imagesize(1,1,20,20); /* 計(jì)算緩沖區(qū)大小，然后存儲(chǔ) */ buff1=(void *)malloc(size);buff2=(void *)malloc(size);getimage(1,1,20,20,buff1);getimage(21,1,40,20,buff2);cleardevice();} void Checker(void) /* 畫棋盤函數(shù) */ { int i,k; for(k=0;k<8;k++)for(i=0;i<8;i++)if(k%2==0&&i%2==0||k%2!=0&&i%2!=0){ setfillstyle(SOLID_FILL,LIGHTBLUE);setcolor(LIGHTBLUE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,LIGHTBLUE);} else { setfillstyle(SOLID_FILL,WHITE);setcolor(WHITE);rectangle(i*20,20+k*20,(i+1)*20,20+(k+1)*20);floodfill(i*20+10,20+k*20+10,WHITE);} } void PrintQueen(Queen *t) /* 圖形輸出函數(shù) */ {int k;char str[20];static total=0;total++;setviewport(240,80,400,260,1); /* 設(shè)置窗口 */ sprintf(str,“NO.%d”,total);setcolor(GREEN);settextstyle(0,0,1);outtextxy(0,0,str);Checker();for(k=0;k<8;k++)if(k%2==0&&t->Y[k]%2==0||k%2!=0&&t->Y[k]%2!=0)putimage((t->Y[k])*20,20+k*20,buff1,COPY_PUT);if(!Q->A[x+7]&&!Q->B[x+y+7]&&!Q->C[x-y+7])/* 下一棵要遍歷的子樹由狀態(tài)數(shù)確定 */ {Q->Y[y]=x;Q->A[x+7]=1;Q->B[x+y+7]=1;Q->C[x-y+7]=1;if(y==7)PrintQueen(Q);QueenRe(Q,y+1); /* 進(jìn)入下一層遞歸 */ Q->A[x+7]=0;Q->B[x+y+7]=0;Q->C[x-y+7]=0;} } void main(void){ Queen Q;int gdriver=DETECT,gmode;initgraph(&gdriver,&gmode,“D://Win-TC”);SetQueen(&Q);setcolor(YELLOW);QueenPic();cleardevice();setcolor(LIGHTGREEN);settextstyle(0,0,3);outtextxy(180,10,“Eight Queens”);setcolor(WHITE);settextstyle(0,0,1);outtextxy(250,400,“2009.11.8 3:30pm”);QueenRe(&Q,0);getch();closegraph();} //回溯法之N皇后問題 當(dāng)N>10，就有點(diǎn)抽了~~ /*結(jié)果前total行每行均為一種放法，表示第i行擺放皇后的列位置，第total+1行，輸出total*/ #include int n,stack[100]; //存當(dāng)前路徑 int total; //路徑數(shù) void make(int l) //遞歸搜索以stack[l]為初結(jié)點(diǎn)的所有路徑 { int i,j; //子結(jié)點(diǎn)個(gè)數(shù) if(l==n+1) { total=total+1; //路徑數(shù)+1 for(i=1;i<=n;i++) printf(“%-3d”,stack[i]);//輸出第i行皇后的列位置stack[i] printf(“n”); exit; //回溯（若試題僅要求一條路徑，則exit改為halt即可） } for(i=1;i<=n;i++) { stack[l]=i;//算符i作用于生成stack[l-1]產(chǎn)生子狀態(tài)stack[l]; if(!att(l,i)) make(l+1); } //再無算符可用，回溯 } int att(int l,int i){ int k; for(k=1;k if(abs(l-k)==abs(stack[k]-i)||i==stack[k])return 1; return 0;} int main(){ printf(“N=”); scanf(“%d”,&n); total=0;//路徑數(shù)初始化為0 make(1); //從結(jié)點(diǎn)1出發(fā)，遞歸搜索所有的路徑 printf(“%dn”,total); system(“pause”); return 0;} 由回溯法的算法流程可以看出，除非邊界條件設(shè)置不當(dāng)而導(dǎo)致死循環(huán)外，回溯法一般是不會(huì)產(chǎn)生內(nèi)存溢出的。但是，回溯法亦有其致命的弱點(diǎn)——時(shí)間效率比數(shù)學(xué)解析法低。為了改善其時(shí)效，我們可以從下述幾個(gè)方面考慮優(yōu)化： 1、遞歸時(shí)對(duì)尚待搜索的信息進(jìn)行預(yù)處理，減少搜索量； 2、盡可能減少分支（解答樹的次數(shù)）； 3、增加約束條件，使其在保證出解的前提下盡可能“苛刻”； 4、在約束條件中設(shè)置限定搜索層次的檻值。 設(shè)計(jì)題目及要求設(shè)計(jì)題目及要求設(shè)計(jì)題目及要求設(shè)計(jì)題目及要求 1.綜合應(yīng)用實(shí)例——學(xué)生成績管理 編寫一個(gè)菜單驅(qū)動(dòng)的學(xué)生成績管理程序。實(shí)現(xiàn)如下管理功能： （1）能輸入并顯示 n 個(gè)學(xué)生的 m 門考試科目的成績、總分和平均分。 （2）按總分進(jìn)行排序。 （3）按學(xué)號(hào)進(jìn)行排序。 （4）任意輸入一個(gè)學(xué)號(hào)，能顯示該學(xué)生的姓名、各門功課的成績 （5）將輸入的學(xué)生成績數(shù)據(jù)保存到文件中。 （6）從文件中讀出學(xué)生成績數(shù)據(jù)。 具體要求如下：）先用靜態(tài)的數(shù)據(jù)結(jié)構(gòu)（結(jié)構(gòu)體數(shù)組）來存儲(chǔ)和管理 n 個(gè)學(xué)生的學(xué)號(hào)、姓名、成績等信息，進(jìn)行編程。）排序函數(shù)是一個(gè)具有多種排序方式的、通用的、排序程序，即不僅可以實(shí)現(xiàn)成績的升序排序，還可以實(shí)現(xiàn)成績的降序排序。）程序能夠進(jìn)行異常處理，檢查用戶輸入數(shù)據(jù)的有效性，在用戶輸入數(shù)據(jù)有錯(cuò)誤（如類型錯(cuò)誤）或無效時(shí)，不會(huì)中斷程序的執(zhí)行，程序具有一定的健壯性。）輸出菜單形式如下： 1.輸入學(xué)生記錄 2.瀏覽學(xué)生記錄 3.修改學(xué)生記錄 4.排序 0.退出 請(qǐng)選擇（0-4）: 5)排序菜單形式如下： 排序方式：1.按總分升序排序 2.按總分降序排序3.按學(xué)號(hào)排序 0.返回主菜單 請(qǐng)選擇： 二二二二、、、、算法分析及實(shí)現(xiàn)步驟算法分析及實(shí)現(xiàn)步驟算法分析及實(shí)現(xiàn)步驟算法分析及實(shí)現(xiàn)步驟 總體算法分析的思路就是用調(diào)用函數(shù)來實(shí)現(xiàn)每個(gè)小程序的作用，首先是確定頭文件，定義學(xué)生成績結(jié)構(gòu)體類型，用結(jié)構(gòu)體函數(shù)實(shí)現(xiàn)。然后在函數(shù)執(zhí)行過程中調(diào)用主菜單函數(shù)，緊接著被調(diào)用函數(shù)返回一個(gè)值給主函數(shù)，由返回來的值確定主函數(shù)應(yīng)該執(zhí)行下面的哪個(gè)步驟，再用一個(gè)while語句控制下面的幾個(gè)步驟的循環(huán)，里面再嵌套switch語句來控制對(duì)每個(gè)小菜單程序的執(zhí)行。例如：當(dāng)調(diào)用函數(shù)返回“1”時(shí)，經(jīng)過switch語句的判斷之后就會(huì)執(zhí)行相應(yīng)的程序，最后，又會(huì)返回到主菜單程序中。其它的都一樣。當(dāng)調(diào)用函數(shù)返回的值是“4”時(shí)，此時(shí)因?yàn)榕判蚶锩孢€有一個(gè)排序的子菜單，所以此時(shí)這里我又用了一個(gè)switch語句來實(shí)現(xiàn)對(duì)排序程序的控制，也就是說在switch語句里面再嵌套switch語句。對(duì)排序程序進(jìn)行的控制。等到跳出排序程序的時(shí)候，其它的都和之前的選擇那樣。其中，瀏覽每個(gè)學(xué)生信息的函數(shù)先計(jì)算出每個(gè)學(xué)生的平均成績?nèi)缓笥胒or語句來實(shí)現(xiàn)每個(gè)學(xué)生信息的循環(huán)輸入。修改學(xué)生信息的函數(shù)里面也用到了for語句，先找到相同的學(xué)號(hào)，然后在修改后循環(huán)執(zhí)行。后來的排序程序都選用冒泡法來執(zhí)行。當(dāng)然一切程序都是從主函數(shù)開始執(zhí)行。 三三三三、、、、源程序代碼源程序代碼源程序代碼源程序代碼 #include struct student//定義學(xué)生成績結(jié)構(gòu)體類型定義學(xué)生成績結(jié)構(gòu)體類型定義學(xué)生成績結(jié)構(gòu)體類型定義學(xué)生成績結(jié)構(gòu)體類型 { intno;charname[8]; floateng,phy,math,sum,ave;}; int menu(student s[],int n)//主菜單函數(shù)主菜單函數(shù)主菜單函數(shù)主菜單函數(shù) { int k; cout<<“歡迎使用學(xué)生成績管理軟件歡迎使用學(xué)生成績管理軟件歡迎使用學(xué)生成績管理軟件歡迎使用學(xué)生成績管理軟件”< cout<<“"< cout<<”學(xué)生成績管理系統(tǒng)菜單學(xué)生成績管理系統(tǒng)菜單學(xué)生成績管理系統(tǒng)菜單學(xué)生成績管理系統(tǒng)菜單“< cout<<”1.輸入學(xué)生記錄輸入學(xué)生記錄輸入學(xué)生記錄輸入學(xué)生記錄“< cout<<”2.瀏覽學(xué)生記錄瀏覽學(xué)生記錄瀏覽學(xué)生記錄瀏覽學(xué)生記錄“< cout<<”3.修改學(xué)生記錄修改學(xué)生記錄修改學(xué)生記錄修改學(xué)生記錄“< cout<<”4.排序排序排序排序“< cout<<”0.退出退出退出退出“< cout<<”請(qǐng)選擇請(qǐng)選擇請(qǐng)選擇請(qǐng)選擇(0-4):“; cin>>k; returnk;} void Input(student s[],int n)//輸輸輸輸入入入入函數(shù)函數(shù)函數(shù)函數(shù) { int i; cout<<”輸入學(xué)號(hào)輸入學(xué)號(hào)輸入學(xué)號(hào)輸入學(xué)號(hào):“< for(i=0;i { cout<<”第第第第“< void Ave(student s[],int n)//瀏覽每個(gè)學(xué)生瀏覽每個(gè)學(xué)生瀏覽每個(gè)學(xué)生瀏覽每個(gè)學(xué)生信息的信息的信息的信息的函數(shù)函數(shù)函數(shù)函數(shù) { int i;for(i=0;i { s[i].ave=(s[i].eng+s[i].phy+s[i].math)/3;s[i].sum=s[i].eng+s[i].phy+s[i].math; } cout<<”學(xué)號(hào)學(xué)號(hào)學(xué)號(hào)學(xué)號(hào)“<<'t'<<”姓名姓名姓名姓名“<<'t'<<”英語英語英語英語“<<'t'<<”物理物理物理物理“<<'t'<<”數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)“<<'t'<<”總成績總成績總成績總成績“<<'t'<<”平均成績平均成績平均成績平均成績“<<'n'; for(i=0;i cout< } int Sort(student s[],int n)//排序的子菜單排序的子菜單排序的子菜單排序的子菜單函數(shù)函數(shù)函數(shù)函數(shù) { int y; cout<<”排序方式排序方式排序方式排序方式:“< cout<<”1.按總分升序排序按總分升序排序按總分升序排序按總分升序排序“< cout<<”0.返回主菜單返回主菜單返回主菜單返回主菜單“< cout<<”請(qǐng)選擇請(qǐng)選擇請(qǐng)選擇請(qǐng)選擇:“; cin>>y; returny; } void change(student s[],int n)//修改學(xué)生信息的函數(shù)修改學(xué)生信息的函數(shù)修改學(xué)生信息的函數(shù)修改學(xué)生信息的函數(shù) { int i,j; cout<<”請(qǐng)輸入要修改的學(xué)生的學(xué)號(hào)請(qǐng)輸入要修改的學(xué)生的學(xué)號(hào)請(qǐng)輸入要修改的學(xué)生的學(xué)號(hào)請(qǐng)輸入要修改的學(xué)生的學(xué)號(hào):“; cin>>j; for(i=0;i { cout< cout<<”學(xué)生的信息學(xué)生的信息學(xué)生的信息學(xué)生的信息:“< cout<<”請(qǐng)輸入修改的信息請(qǐng)輸入修改的信息請(qǐng)輸入修改的信息請(qǐng)輸入修改的信息“< }} voidzpxs(student s[],int n)// 按總分升序按總分升序按總分升序按總分升序排序排序排序排序的函數(shù)的函數(shù)的函數(shù)的函數(shù) { int i,j;studenttemp;for(i=0;i { s[i].ave=(s[i].eng+s[i].phy+s[i].math)/3;s[i].sum=s[i].eng+s[i].phy+s[i].math;} for(i=0;i { for(j=0;j { temp=s[j];s[j]=s[j+1];s[j+1]=temp; }} cout<<”學(xué)號(hào)學(xué)號(hào)學(xué)號(hào)學(xué)號(hào)“<<'t'<<”姓名姓名姓名姓名“<<'t'<<”英語英語英語英語“<<'t'<<”物理物理物理物理“<<'t'<<”數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)數(shù)學(xué)“<<'t'<<”總成績總成績總成績總成績“<<'t'<<”平均成績平均成績平均成績平均成績“<<'n'; for(i=0;i cout< } voidzpxj(student s[],int n)//按總分降序排序按總分降序排序按總分降序排序按總分降序排序的函數(shù)的函數(shù)的函數(shù)的函數(shù) { int i,j;studenttemp;for(i=0;i {s[i].ave=(s[i].eng+s[i].phy+s[i].math)/3;s[i].sum=s[i].eng+s[i].phy+s[i].math;} for(i=0;i { for(j=0;j for(i=0;i cout< voidxhpxs(student s[],int n)//按學(xué)號(hào)升序排序按學(xué)號(hào)升序排序按學(xué)號(hào)升序排序按學(xué)號(hào)升序排序的函數(shù)的函數(shù)的函數(shù)的函數(shù) {int i,j;studenttemp;for(i=0;i for(i=0;i {for(j=0;j for(i=0;i cout< void main()//主函數(shù)主函數(shù)主函數(shù)主函數(shù) { int i,g;studentstu[3];while(i){i=menu(stu,3);switch(i){case 1:Input(stu,3);cout<<”“< cout<<”“< cout<<”“< cout<<”“< 人工智能課程設(shè)計(jì)報(bào)告 課 程:人工智能課程設(shè)計(jì)報(bào)告 班 級(jí): 姓 名: 學(xué) 號(hào): 指導(dǎo)教師:趙曼 2015年11月 人工智能課程設(shè)計(jì)報(bào)告 人工智能課程設(shè)計(jì)報(bào)告 課程背景 人工智能（Artificial Intelligence），英文縮寫為AI。它是研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它企圖了解智能的實(shí)質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式做出反應(yīng)的智能機(jī)器，該領(lǐng)域的研究包括機(jī)器人、語言識(shí)別、圖像識(shí)別、自然語言處理和專家系統(tǒng)等。人工智能從誕生以來，理論和技術(shù)日益成熟，應(yīng)用領(lǐng)域也不斷擴(kuò)大，可以設(shè)想，未來人工智能帶來的科技產(chǎn)品，將會(huì)是人類智慧的“容器”。 人工智能是對(duì)人的意識(shí)、思維的信息過程的模擬。人工智能不是人的智能，但能像人那樣思考、也可能超過人的智能。 人工智能是一門極富挑戰(zhàn)性的科學(xué)，從事這項(xiàng)工作的人必須懂得計(jì)算機(jī)知識(shí)，心理學(xué)和哲學(xué)。人工智能是包括十分廣泛的科學(xué)，它由不同的領(lǐng)域組成，如機(jī)器學(xué)習(xí)，計(jì)算機(jī)視覺等等，總的說來，人工智能研究的一個(gè)主要目標(biāo)是使機(jī)器能夠勝任一些通常需要人類智能才能完成的復(fù)雜工作。但不同的時(shí)代、不同的人對(duì)這種“復(fù)雜工作”的理解是不同的。 人工智能是計(jì)算機(jī)學(xué)科的一個(gè)分支，二十世紀(jì)七十年代以來被稱為世界三大尖端技術(shù)之一（空間技術(shù)、能源技術(shù)、人工智能）。也被認(rèn)為是二十一世紀(jì)三大尖端技術(shù)（基因工程、納米科學(xué)、人工智能）之一。這是因?yàn)榻陙硭@得了迅速的發(fā)展，在很多學(xué)科領(lǐng)域都獲得了廣泛應(yīng)用，并取得了豐碩的成果，人工智能已逐步成為一個(gè)獨(dú)立的分支，無論在理論和實(shí)踐上都已自成一個(gè)系統(tǒng)。 人工智能是研究使計(jì)算機(jī)來模擬人的某些思維過程和智能行為（如學(xué)習(xí)、推理、思考、規(guī)劃等）的學(xué)科，主要包括計(jì)算機(jī)實(shí)現(xiàn)智能的原理、制造類似于人腦智能的計(jì)算機(jī)，使計(jì)算機(jī)能實(shí)現(xiàn)更高層次的應(yīng)用。人工智能將涉及到計(jì)算機(jī)科學(xué)、心理學(xué)、哲學(xué)和語言學(xué)等學(xué)科?？梢哉f幾乎是自然科學(xué)和社會(huì)科學(xué)的所有學(xué)科，其范圍已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)科學(xué)的范疇，人工智能與思維科學(xué)的關(guān)系是實(shí)踐和理論的關(guān)系，人工智能是處于思維科學(xué)的技術(shù)應(yīng)用層次，是它的一個(gè)應(yīng)用分支。從思維觀點(diǎn)看，人工智能不僅限于邏輯思維，要考慮形象思維、靈感思維才能促進(jìn)人工智能的突破性的發(fā)展，數(shù)學(xué)常被認(rèn)為是多種學(xué)科的基礎(chǔ)科學(xué)，數(shù)學(xué)也進(jìn)入語言、思維領(lǐng)域，人工智能學(xué)科也必須借用數(shù)學(xué)工具，數(shù)學(xué)不僅在標(biāo)準(zhǔn)邏輯、模糊數(shù)學(xué)等范圍發(fā)揮作用，數(shù)學(xué)進(jìn)入人工智能學(xué)科，它們將互相促進(jìn)而更快地發(fā)展。 人工智能課程設(shè)計(jì)報(bào)告 a[] a[i]=0表示第i行上還沒有皇后； b[] b[i]=0表示第i列反斜線/上沒有皇后； c[] c[i]=0表示第i列正斜線上沒有皇后。 棋盤中同一反斜線/上的方格的行號(hào)與列號(hào)相同；同一正斜線上的方格的行號(hào)與列號(hào)之差均相同，這就是判斷斜線的依據(jù)。 初始時(shí)，所有行和斜線上都沒有皇后，從第1列的第1行配置第一個(gè)皇后開始，在第m列，col[m]行放置了一個(gè)合理的皇后，準(zhǔn)備考察第m+1列時(shí)，在數(shù)組a[]，b[]和c[]中為第m列，col[m]行的位置設(shè)定有皇后的標(biāo)志；當(dāng)從第m列回溯到m-1列時(shí)，并準(zhǔn)備調(diào)整第m-1列的皇后配置時(shí)，清除在數(shù)組a[],b[]和c[]對(duì)應(yīng)位置的值都為1來確定。 2)遺傳算法 遺傳算法的基本運(yùn)算過程如下： a)初始化：設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。b)個(gè)體評(píng)價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。遺傳算法 遺傳算法 c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。d)交叉運(yùn)算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。 e)變異運(yùn)算：將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體P(t+1)。 f)終止條件判斷:若t=T,則以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。 3）csp最小沖突法 （1）初始化N個(gè)皇后的一個(gè)放置，允許有沖突 （2）考慮某一行的某個(gè)皇后，她可能與x個(gè)皇后沖突，然后看看將這個(gè)皇后移動(dòng)到這一行的哪個(gè)空位能使得與其沖突的皇后個(gè)數(shù)最少，就移動(dòng)到那里。（也可以考慮列，是等價(jià)的）（3）不斷執(zhí)行（2），直到?jīng)]有沖突為止 2.數(shù)據(jù)結(jié)構(gòu) 使用數(shù)組結(jié)構(gòu)存儲(chǔ)相關(guān)數(shù)據(jù) 一維數(shù)組： t + n] == 1||rd[i + t] == 1)continue; //沒有沖突 ver[i] = 1;ru[i 人工智能課程設(shè)計(jì)報(bào)告 } } //后退處理 rd[i + t] = 0;ru[i1;i++){ } cout << endl;*/ cout << “row:” << i << “ col:” << this->ChromosomeMatrix[i][0] << endl;g = 1;if(DisplayAllAnsures)this->FillArea(k);this->CostMatrix[k] = this->CostFunc(k);bool DisplayAllAnsures=PrintChessBoard;//是否輸出所有棋盤結(jié)果 int g = 0, num = 0; //逐個(gè)檢查第row行的每個(gè)位置，看看是否存在沖突數(shù)更小的位置 for(int i = 0;i < N;i++){ } if(i == cur_col)continue; int conflict = col[i] + pdiag[GetP(row, i)] + cdiag[GetC(row, i)];if(conflict < min_conflict){ } min_conflict = conflict;optimal_col = i;+ cdiag[GetC(row, optimal_col)] 人工智能課程設(shè)計(jì)報(bào)告 } } col[optimal_col]++;pdiag[GetP(row, optimal_col)]++;cdiag[GetC(row, optimal_col)]++;R[row] = optimal_col;if(col[cur_col] == 1 && col[optimal_col] == 1 } && pdiag[GetP(row, optimal_col)] == 1 && cdiag[GetC(row, optimal_col)] == 1){ return Qualify();//qualify相對(duì)更耗時(shí)，所以只在滿足上面基本條件后才檢查 //否則當(dāng)前點(diǎn)就是最佳點(diǎn)，一切都保持不變 return false;//如果都沒變的話，肯定不滿足終止條件，否則上一次就應(yīng)該返回true并終止了 //檢查沖突 bool CSP_Queens::Qualify(){ } //最終用戶調(diào)用函數(shù)，numOfQueens為輸入皇后數(shù)，PrintChessBoard判斷是否輸出棋盤表示 int CSP_Queens::CSPAlgorithms(bool PrintChessBord){ srand((unsigned)time(NULL));Init();if(Qualify()){//運(yùn)氣很好，初始化后就滿足終止條件 } bool end = false;while(!end){ for(int i = 0;i < N;i++){ if(Adjust_row(i)){ end = true;if(PrintChessBord)Print_result();return 0;for(int i = 0;i < N;i++){ } return true;if(col[R[i]]!= 1 || } pdiag[GetP(i, R[i])]!= 1 || cdiag[GetC(i, R[i])]!= 1){ return false; 人工智能課程設(shè)計(jì)報(bào)告 2.遺傳算法 3.CSP最小沖突算法 人工智能課程設(shè)計(jì)報(bào)告 總的來說，回溯在n值很小時(shí)，效率很高，但其求解范圍很小，超過35基本就解不出來，遺傳算法求解范圍適中。在n值很大(>100)時(shí)，前兩者都不能再解決，此時(shí)，CSP最小沖突法的效率最高，且與n值沒有必然的聯(lián)系。 總結(jié) 通過此次課程實(shí)習(xí)不僅大大加深了我對(duì)幾種經(jīng)典搜索算法的理解，而且?guī)椭液芎玫膹?fù)習(xí)了隊(duì)列、堆棧、圖、文件讀寫這幾部分的內(nèi)容，使我對(duì)幾種基本的數(shù)據(jù)結(jié)構(gòu)類型的運(yùn)用更加熟練。在解決這些問題的過程中我不但很好的鞏固了數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，而且提高了編程及程序調(diào)試能力，增強(qiáng)了自己編程的信心。 總之，在這次課程實(shí)習(xí)過程中我是實(shí)實(shí)在在學(xué)到了一些課堂上學(xué)不到的東西，同時(shí)也提高了實(shí)踐能力。同時(shí)在這個(gè)過程中也暴露了自己的不少問題，在今后的學(xué)習(xí)過程成也會(huì)更加有針對(duì)性。最后還要感謝老師的悉心指導(dǎo)，解答我編程過程中的疑問、指出我程序中的不足，及提出可行的解決方法，讓我的程序的功能更加完善。 CSP算法源代碼： //CSPAlgorithms.h #pragma once class CSP_Queens { public: //構(gòu)造函數(shù)，numOfQueens為輸入皇后數(shù)，CSP_Queens(int numOfQueens);~CSP_Queens(); private: //row[i]表示當(dāng)前擺放方式下第i行的皇后數(shù)，int *row;//col[i]表示當(dāng)前擺放方式下第i列的皇后沖突數(shù) int *col;int N;//放置N個(gè)皇后在N*N棋盤上 //從左上到右下的對(duì)角線上row-col值是相同的，但是這個(gè)值有可能是負(fù)值，最小為 12]，2*N-1條，作為對(duì)角線編號(hào) //R[]用來存儲(chǔ)皇后放置位置，R[row] = col表示(row,col)處,即“第row行第col列”//cdiag[i]表示編號(hào)為i的對(duì)角線上的皇后數(shù) int *cdiag;//counter diagonal,副對(duì)角線 有個(gè)皇后 int *R; public: int swap(int &a, int &b); //給定二維矩陣的一個(gè)點(diǎn)坐標(biāo)，返回其對(duì)應(yīng)的左上到右下的對(duì)角線編號(hào) int GetP(int row, int col);//給定二維矩陣的一個(gè)點(diǎn)坐標(biāo)，返回其對(duì)應(yīng)的右上到左下的對(duì)角線編號(hào) int GetC(int row, int col);//返回begin, begin + 1,..., endbegin個(gè)數(shù)中的隨機(jī)的一個(gè) int My_rand(int begin, int end);//左閉右開[begin, end) 人工智能課程設(shè)計(jì)報(bào)告 N = numOfQueens;row = new int[N];col = new int[N];pdiag=new int[2 * N];cdiag=new int[2 * N];R=new int[N];} CSP_Queens::~CSP_Queens(){ if(NULL!= row)delete[]row;if(NULL!= col)delete[]col;if(NULL!= pdiag)delete[]pdiag;if(NULL!= cdiag)delete[]cdiag;if(NULL!= R)delete[]R;} int CSP_Queens::swap(int &a, int &b){ int t = a;a = b;b = t;return 0;} // int CSP_Queens::GetP(int row, int col){ return row1;} int CSP_Queens::GetC(int row, int col){ return row + col;} //返回begin, begin + 1,..., endbegin個(gè)數(shù)中的隨機(jī)的一個(gè) int CSP_Queens::My_rand(int begin, int end)//左閉右開[begin, end){ return rand()%(end 人工智能課程設(shè)計(jì)報(bào)告 { } for(int i = begin;i <= end1;i++){ pdiag[i] = 0;cdiag[i] = 0;} //初始化當(dāng)前棋局的皇后所在位置的各個(gè)沖突數(shù) for(int i = 0;i < N;i++){ col[R[i]]++;pdiag[GetP(i, R[i])]++;cdiag[GetC(i, R[i])]++;} //用最小沖突算法調(diào)整第row行的皇后的位置（初始化時(shí)每行都有一個(gè)皇后，調(diào)整后仍然在第 + cdiag[GetC(row, optimal_col)] 人工智能課程設(shè)計(jì)報(bào)告 } } //當(dāng)前點(diǎn)就是最佳點(diǎn)，一切都保持不變 return false;//如果都沒變的話，肯定不滿足終止條件，否則上一次就應(yīng)該返回true并終止了 } //檢查沖突 bool CSP_Queens::Qualify(){ for(int i = 0;i < N;i++){ if(col[R[i]]!= 1 || pdiag[GetP(i, R[i])]!= 1 || cdiag[GetC(i, R[i])]!= 1){ return false; } } return true;} void CSP_Queens::Print_result(){ } cout << “-------結(jié)果為:” << endl;cout << endl;for(int j = 0;j < N;j++){ for(int k = 0;k < N;k++){ if(R[j] == k) cout << “Q”; else cout << “+”; cout << “ ”;} cout << endl;} //最終用戶調(diào)用函數(shù)，numOfQueens為輸入皇后數(shù)，PrintChessBoard判斷是否輸出棋盤表 人工智能課程設(shè)計(jì)報(bào)告 int N;cin >> N;int time1 = clock();CSP_Queens myQueens(N);myQueens.CSPAlgorithms(end);int time2 = clock();cout << “---” << N << “皇后問題耗時(shí)：” << time2 讀書的好處 1、行萬里路，讀萬卷書。 2、書山有路勤為徑，學(xué)海無涯苦作舟。 3、讀書破萬卷，下筆如有神。 4、我所學(xué)到的任何有價(jià)值的知識(shí)都是由自學(xué)中得來的?！_(dá)爾文 5、少壯不努力，老大徒悲傷。 6、黑發(fā)不知勤學(xué)早，白首方悔讀書遲?！佌媲?/p> 7、寶劍鋒從磨礪出，梅花香自苦寒來。 8、讀書要三到：心到、眼到、口到 9、玉不琢、不成器，人不學(xué)、不知義。 10、一日無書，百事荒廢?！悏?/p> 11、書是人類進(jìn)步的階梯。 12、一日不讀口生，一日不寫手生。 13、我撲在書上，就像饑餓的人撲在面包上。——高爾基 14、書到用時(shí)方恨少、事非經(jīng)過不知難?！懹?/p> 15、讀一本好書，就如同和一個(gè)高尚的人在交談——歌德 16、讀一切好書，就是和許多高尚的人談話?！芽▋?/p> 17、學(xué)習(xí)永遠(yuǎn)不晚?！郀柣?/p> 18、少而好學(xué)，如日出之陽；壯而好學(xué)，如日中之光；志而好學(xué)，如炳燭之光?！?jiǎng)⑾?/p> 19、學(xué)而不思則惘，思而不學(xué)則殆。——孔子 20、讀書給人以快樂、給人以光彩、給人以才干?！喔?/p> 第二篇：數(shù)據(jù)結(jié)構(gòu)八皇后問題實(shí)習(xí)報(bào)告（寫寫幫整理）
第三篇：回溯法之N皇后問題(C語言)
第四篇：C語言編程實(shí)訓(xùn)報(bào)告
第五篇：人工智能課程設(shè)計(jì)報(bào)告-n皇后問題解讀
點(diǎn)擊咨詢 