第一篇：回溯法之N皇后問題(C語言)
//回溯法之N皇后問題
當N>10，就有點抽了~~ /*結果前total行每行均為一種放法，表示第i行擺放皇后的列位置，第total+1行，輸出total*/ #include
int n,stack[100];
//存當前路徑 int total;
//路徑數
void make(int l)
//遞歸搜索以stack[l]為初結點的所有路徑 {
int i,j;
//子結點個數
if(l==n+1)
{
total=total+1;
//路徑數+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]產生子狀態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;//路徑數初始化為0 make(1); //從結點1出發，遞歸搜索所有的路徑 printf(“%dn”,total); system(“pause”); return 0;} 由回溯法的算法流程可以看出，除非邊界條件設置不當而導致死循環外，回溯法一般是不會產生內存溢出的。但是，回溯法亦有其致命的弱點——時間效率比數學解析法低。為了改善其時效，我們可以從下述幾個方面考慮優化： 1、遞歸時對尚待搜索的信息進行預處理，減少搜索量； 2、盡可能減少分支（解答樹的次數）； 3、增加約束條件，使其在保證出解的前提下盡可能“苛刻”； 4、在約束條件中設置限定搜索層次的檻值。 人工智能課程設計報告 課 程:人工智能課程設計報告 班 級: 姓 名: 學 號: 指導教師:趙曼 2015年11月 人工智能課程設計報告 人工智能課程設計報告 課程背景 人工智能（Artificial Intelligence），英文縮寫為AI。它是研究、開發用于模擬、延伸和擴展人的智能的理論、方法、技術及應用系統的一門新的技術科學。人工智能是計算機科學的一個分支，它企圖了解智能的實質，并生產出一種新的能以人類智能相似的方式做出反應的智能機器，該領域的研究包括機器人、語言識別、圖像識別、自然語言處理和專家系統等。人工智能從誕生以來，理論和技術日益成熟，應用領域也不斷擴大，可以設想，未來人工智能帶來的科技產品，將會是人類智慧的“容器”。 人工智能是對人的意識、思維的信息過程的模擬。人工智能不是人的智能，但能像人那樣思考、也可能超過人的智能。 人工智能是一門極富挑戰性的科學，從事這項工作的人必須懂得計算機知識，心理學和哲學。人工智能是包括十分廣泛的科學，它由不同的領域組成，如機器學習，計算機視覺等等，總的說來，人工智能研究的一個主要目標是使機器能夠勝任一些通常需要人類智能才能完成的復雜工作。但不同的時代、不同的人對這種“復雜工作”的理解是不同的。 人工智能是計算機學科的一個分支，二十世紀七十年代以來被稱為世界三大尖端技術之一（空間技術、能源技術、人工智能）。也被認為是二十一世紀三大尖端技術（基因工程、納米科學、人工智能）之一。這是因為近三十年來它獲得了迅速的發展，在很多學科領域都獲得了廣泛應用，并取得了豐碩的成果，人工智能已逐步成為一個獨立的分支，無論在理論和實踐上都已自成一個系統。 人工智能是研究使計算機來模擬人的某些思維過程和智能行為（如學習、推理、思考、規劃等）的學科，主要包括計算機實現智能的原理、制造類似于人腦智能的計算機，使計算機能實現更高層次的應用。人工智能將涉及到計算機科學、心理學、哲學和語言學等學科。可以說幾乎是自然科學和社會科學的所有學科，其范圍已遠遠超出了計算機科學的范疇，人工智能與思維科學的關系是實踐和理論的關系，人工智能是處于思維科學的技術應用層次，是它的一個應用分支。從思維觀點看，人工智能不僅限于邏輯思維，要考慮形象思維、靈感思維才能促進人工智能的突破性的發展，數學常被認為是多種學科的基礎科學，數學也進入語言、思維領域，人工智能學科也必須借用數學工具，數學不僅在標準邏輯、模糊數學等范圍發揮作用，數學進入人工智能學科，它們將互相促進而更快地發展。 人工智能課程設計報告 a[] a[i]=0表示第i行上還沒有皇后； b[] b[i]=0表示第i列反斜線/上沒有皇后； c[] c[i]=0表示第i列正斜線上沒有皇后。 棋盤中同一反斜線/上的方格的行號與列號相同；同一正斜線上的方格的行號與列號之差均相同，這就是判斷斜線的依據。 初始時，所有行和斜線上都沒有皇后，從第1列的第1行配置第一個皇后開始，在第m列，col[m]行放置了一個合理的皇后，準備考察第m+1列時，在數組a[]，b[]和c[]中為第m列，col[m]行的位置設定有皇后的標志；當從第m列回溯到m-1列時，并準備調整第m-1列的皇后配置時，清除在數組a[],b[]和c[]對應位置的值都為1來確定。 2)遺傳算法 遺傳算法的基本運算過程如下： a)初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。b)個體評價：計算群體P(t)中各個個體的適應度。遺傳算法 遺傳算法 c)選擇運算:將選擇算子作用于群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。d)交叉運算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。 e)變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經過選擇、交叉、變異運算之后得到下一代群體P(t+1)。 f)終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。 3）csp最小沖突法 （1）初始化N個皇后的一個放置，允許有沖突 （2）考慮某一行的某個皇后，她可能與x個皇后沖突，然后看看將這個皇后移動到這一行的哪個空位能使得與其沖突的皇后個數最少，就移動到那里。（也可以考慮列，是等價的）（3）不斷執行（2），直到沒有沖突為止 2.數據結構 使用數組結構存儲相關數據 一維數組： t + n] == 1||rd[i + t] == 1)continue; //沒有沖突 ver[i] = 1;ru[i 人工智能課程設計報告 } } //后退處理 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;//是否輸出所有棋盤結果 int g = 0, num = 0; //逐個檢查第row行的每個位置，看看是否存在沖突數更小的位置 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)] 人工智能課程設計報告 } } 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相對更耗時，所以只在滿足上面基本條件后才檢查 //否則當前點就是最佳點，一切都保持不變 return false;//如果都沒變的話，肯定不滿足終止條件，否則上一次就應該返回true并終止了 //檢查沖突 bool CSP_Queens::Qualify(){ } //最終用戶調用函數，numOfQueens為輸入皇后數，PrintChessBoard判斷是否輸出棋盤表示 int CSP_Queens::CSPAlgorithms(bool PrintChessBord){ srand((unsigned)time(NULL));Init();if(Qualify()){//運氣很好，初始化后就滿足終止條件 } 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; 人工智能課程設計報告 2.遺傳算法 3.CSP最小沖突算法 人工智能課程設計報告 總的來說，回溯在n值很小時，效率很高，但其求解范圍很小，超過35基本就解不出來，遺傳算法求解范圍適中。在n值很大(>100)時，前兩者都不能再解決，此時，CSP最小沖突法的效率最高，且與n值沒有必然的聯系。 總結 通過此次課程實習不僅大大加深了我對幾種經典搜索算法的理解，而且幫助我很好的復習了隊列、堆棧、圖、文件讀寫這幾部分的內容，使我對幾種基本的數據結構類型的運用更加熟練。在解決這些問題的過程中我不但很好的鞏固了數據結構的相關知識，而且提高了編程及程序調試能力，增強了自己編程的信心。 總之，在這次課程實習過程中我是實實在在學到了一些課堂上學不到的東西，同時也提高了實踐能力。同時在這個過程中也暴露了自己的不少問題，在今后的學習過程成也會更加有針對性。最后還要感謝老師的悉心指導，解答我編程過程中的疑問、指出我程序中的不足，及提出可行的解決方法，讓我的程序的功能更加完善。 CSP算法源代碼： //CSPAlgorithms.h #pragma once class CSP_Queens { public: //構造函數，numOfQueens為輸入皇后數，CSP_Queens(int numOfQueens);~CSP_Queens(); private: //row[i]表示當前擺放方式下第i行的皇后數，int *row;//col[i]表示當前擺放方式下第i列的皇后沖突數 int *col;int N;//放置N個皇后在N*N棋盤上 //從左上到右下的對角線上row-col值是相同的，但是這個值有可能是負值，最小為 12]，2*N-1條，作為對角線編號 //R[]用來存儲皇后放置位置，R[row] = col表示(row,col)處,即“第row行第col列”//cdiag[i]表示編號為i的對角線上的皇后數 int *cdiag;//counter diagonal,副對角線 有個皇后 int *R; public: int swap(int &a, int &b); //給定二維矩陣的一個點坐標，返回其對應的左上到右下的對角線編號 int GetP(int row, int col);//給定二維矩陣的一個點坐標，返回其對應的右上到左下的對角線編號 int GetC(int row, int col);//返回begin, begin + 1,..., endbegin個數中的隨機的一個 int My_rand(int begin, int end);//左閉右開[begin, end) 人工智能課程設計報告 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個數中的隨機的一個 int CSP_Queens::My_rand(int begin, int end)//左閉右開[begin, end){ return rand()%(end 人工智能課程設計報告 { } for(int i = begin;i <= end1;i++){ pdiag[i] = 0;cdiag[i] = 0;} //初始化當前棋局的皇后所在位置的各個沖突數 for(int i = 0;i < N;i++){ col[R[i]]++;pdiag[GetP(i, R[i])]++;cdiag[GetC(i, R[i])]++;} //用最小沖突算法調整第row行的皇后的位置（初始化時每行都有一個皇后，調整后仍然在第 + cdiag[GetC(row, optimal_col)] 人工智能課程設計報告 } } //當前點就是最佳點，一切都保持不變 return false;//如果都沒變的話，肯定不滿足終止條件，否則上一次就應該返回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 << “-------結果為:” << 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;} //最終用戶調用函數，numOfQueens為輸入皇后數，PrintChessBoard判斷是否輸出棋盤表 人工智能課程設計報告 int N;cin >> N;int time1 = clock();CSP_Queens myQueens(N);myQueens.CSPAlgorithms(end);int time2 = clock();cout << “---” << N << “皇后問題耗時：” << time2 讀書的好處 1、行萬里路，讀萬卷書。 2、書山有路勤為徑，學海無涯苦作舟。 3、讀書破萬卷，下筆如有神。 4、我所學到的任何有價值的知識都是由自學中得來的。——達爾文 5、少壯不努力，老大徒悲傷。 6、黑發不知勤學早，白首方悔讀書遲。——顏真卿 7、寶劍鋒從磨礪出，梅花香自苦寒來。 8、讀書要三到：心到、眼到、口到 9、玉不琢、不成器，人不學、不知義。 10、一日無書，百事荒廢。——陳壽 11、書是人類進步的階梯。 12、一日不讀口生，一日不寫手生。 13、我撲在書上，就像饑餓的人撲在面包上。——高爾基 14、書到用時方恨少、事非經過不知難。——陸游 15、讀一本好書，就如同和一個高尚的人在交談——歌德 16、讀一切好書，就是和許多高尚的人談話。——笛卡兒 17、學習永遠不晚。——高爾基 18、少而好學，如日出之陽；壯而好學，如日中之光；志而好學，如炳燭之光。——劉向 19、學而不思則惘，思而不學則殆。——孔子 20、讀書給人以快樂、給人以光彩、給人以才干。——培根 關于c語言編程中八皇后問題的設計報告 一、課題的來源及意義 八皇后問題是一個古老而著名的問題，該問題是十九世紀著名的數學家高斯1850年提出的。 在國際象棋中，皇后是最有權利的一個棋子；只要別的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時，它就能把對方棋子吃掉。所以高斯提出了一個問題：在8*8的格的國際象棋上擺放八個皇后，使其不能相互攻擊，即任意兩個皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法。 到了現代，隨著計算機技術的飛速發展，這一古老而有趣的數學游戲問題也自然而然的被搬到了計算機上。運用所學計算機知識來試著解決這個問題是個鍛煉和提高我自己編程能力和獨立解決問題能力的好機會，可以使我增強信心，為我以后的編程開個好頭，故我選擇了這個有趣的課題。 二、面對的問題 1）解決沖突問題：這個問題包括了行，列，兩條對角線； 列：規定每一列放一個皇后，不會造成列上的沖突； 行：當第I行被某個皇后占領后，則同一行上的所有空格都不能再放皇后，要把以I為下標的標記置為被占領狀態； 2）使用數據結構的知識，用遞歸法解決問題。 三、需求分析 1、涉及到的知識 本次設計中，用到的主要知識有：遞歸法的運用，for語句的靈活運用，數據結構中樹知識的靈活運用、棧及數組的掌握。 2、軟硬件的需求 1)系統要求：winxp以上操作系統； 2)語言平臺：tc++或vc++6.0； 3、功能需求 當運行程序時，在屏幕上顯示每一種方法八個皇后的相對位置，要用比較直觀 的界面顯示。 四、概要設計 我的思想是用循環遞歸循環來實現的，分別一一測試了每一種擺法，并把它擁有的92種變化表現出來。在這個程序中，我的主要思路以及思想是這樣的： 1）解決沖突問題： 這個問題包括了行，列，兩條對角線； 列：規定每一列放一個皇后，不會造成列上的沖突； 行：當第I行被某個皇后占領后，則同一行上的所有空格都不能再放皇后，要把以I為下標的標記置為被占領狀態； 對角線：對角線有兩個方向。在這我把這兩條對角線稱為：主對角線和從對角線。在同一對角線上的所有點（設下標為(i,j)），要么(i+j)是常數，要么(i-j)是常數。因此，當第I個皇后占領了第J列后，要同時把以(i+j)、(i-j)為下標的標記置為被占領狀態。 2）數據結構的實現 而對于數據結構的實現，學生則是著重于: 數組a[I]：a [I]表示第I個皇后放置的列；I的范圍：1..8;對角線數組：b[j](主對角線),c[j]（從對角線），根據程序的運行，去決定主從對角線是否放入皇后； 五、詳細設計和實現 1、算法描述 A、數據初始化。 B、從n列開始擺放第n個皇后（因為這樣便可以符合每一豎列一個皇后的要求），先測試當前位置（n，m）是否等于0（未被占領）。如果是，擺放第n個皇后，并宣布占領（記得姚橫列豎列斜列一起設置），接著進行遞歸；如果不是，測試下一個位置（n，m+1），但是如果當n<=8，m=8時，發現此時已無法擺放時，便要進行回溯。從問題的某一種可能出發，搜索從這種情況能出發，繼續搜索，這種不斷“回溯”的尋找解的方法，稱為“回溯法”。 C、使用數組實現回溯法的思想。D、當n>8時，便打印出結果。 E、輸出函數我使用printf輸出，運行形式為：第m種方法為：* * * * * * * * 2、算法流程圖 六、代碼編寫及詳細注釋 #include void main()/*----------------------------Main：主函數。----------------------------*/ { system(“title 葉青--遞歸算法八皇后問題 ”);cout<<“ ”<<“八皇后的解法：”< { 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個皇后放上去之后，是否合法，即是否無沖突。------*/ { int i;for(i = 0;i < n;i++)//!將第n個皇后的位置依次于前面n－1個皇后的位置比較。 { if(Site[i] == Site[n])//!兩個皇后在同一列上，返回0。return 0;if(abs(Site[i]i))//!兩個皇后在同一對角線上，返回0。return 0;} return 1;//!沒有沖突，返回1。} void Output()/*------------Output：輸出一個解，即一種沒有沖突的放置方案。------------*/ { int i;printf(“No.%-5d” , ++iCount);//!輸出序號。 for(i = 0;i < QUEENS;i++)//!依次輸出各個行上的皇后的位置，即所在的列數。printf(“%d ” , Site[i]);printf(“n”);} 七、程序調試 調試過程、步驟及遇到的問題 在完整程序調試時遇到幾個小問題，后經細心改正后才把調試工作做完。 例如:當用printf輸出時,出現了一些錯誤,幾經調試后,發現原來是缺少了stdio.h這樣一個頭文件,添加了頭文件后, 還出現了一些問題,邏輯錯誤導致程序死循環或不循環或循環一小部分,但是編譯時卻沒有錯誤,就是沒有正確的輸出答案,一開始我也不知道是怎么回事,通過和同學的交流,發現是邏輯錯誤,經過改正后,程序終于可以運行了.八、運行與測試 運行演示 九、總結 在這次的程序設計，我從中得到了許多的經驗以及軟件設計的一些新的思路；從這個八皇后問題設計以及分析中，本人從中理解到了數據結構對于計算機軟件設計的重要性，它的使用，可以改變一個軟件的運行周期，也可以將軟件的思路從繁化簡，并且都能夠通過數據結構的相關引導，將本身以前編程思想進行擴充，發展；這也是在這次課程設計中我所掌握得到的。 但由于我的基本知識還不是那么扎實，也缺乏對軟件設計的經驗，在這過程中也出現了一些問題，如，八皇后在變成初期由于沒真正體會到數據結構中“樹”在里面的運用，將程序往大一時c語言的方向發展，不自覺的采用了非遞歸的算法，結果大大增加了程序的復雜程度。并且也讓整個程序的時間復雜度變得更大；在后來學生對數據結構的第六章進行了比較深入的研讀，才發現了數據結構樹的實際運用的空間是相當的大，并且，通過了重溫樹的回溯，以及二叉樹的遍歷，最終將程序進行了一次較大的改造。并且通過思考，再將以前的數組知識加以運用才最終解決了這個問題，整個程序的算法的可看性也有了相當的改進。 以前對數據結構的學習還是具有相當大的意義，它從一個程度上改變了我們的編程思想，如何將一個程序快速而又準備的進行編寫，進行編譯，都成為了我們思考的重點，也通過這一門課的學習，我們將數據結構的思想帶入到了我們以后的編程學習中去。在這個階段，我也明白了，好的思想，不能提留于字面上的認知，還需要的是平時多練多寫一些相關的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關鍵。 我覺得還可以考慮開發N皇后問題,在主界面中添加一個 int型的變量,程序一開始要求輸入一個數(確定是幾皇后問題),輸入后按下 enter 后,輸出各種解.主程序與八皇后的求解大體相同.十、參考文獻 [1]蘇仕華,數據結構課程設計.-北京:機械工業出版社,2005.5 [2]于永彥,趙建洋.課程設計指導書.淮安：江蘇淮陰工學院 計算機工程系,2006 [3]劉振安,劉燕君，孫忱.C++語言課程設計.北京：高等教育出版社,2003 [4]陳志泊, 張海燕, 王春玲.Visual C++程序設計.中國鐵道出版社 ,2005 [5]呂鳳哲,C++語言程序設計（第二版）.北京：電子工業出版社,2005 [6]殷人昆，陶永雷等.數據結構（用面向對象方法與C++）.北京:清華大學出版社，1999 [7]嚴蔚敏，吳偉民，數據結構．北京：清華大學出版社，1997 [8]李春葆.數據結構—考研指導.北京:清華大學出版社,2002 [9]陳慧南．數據結構—C++語言描述．北京：人民郵電出版社，2005．03 計算： （1）1+2+3+4+5+6+7+8=？ （2）1*1+2*2+3*3+4*4+5*5+6*6+7*7+8*8=? （3）1*1*1+2*2*2+3*3*3+4*4*4+5*5*5+6*6*6+7*7*7+8*8*8=? 程序如下： #include 模型的推廣： 計算： 1+2+…+n=? … … 1*1*1*…1+…+n*n*n*…n=? 程序如下： #include 題目計算器軟件設計 一、設計要求 用C語言設計出模擬計算器軟件，實現計算器的功能。 二、設計內容 1．基本要求： （1）圖形顯示方式，在DOS環境下畫出計算器的圖形，能夠用鼠標實現操作，能夠進行簡單的數學計算。 2．提高要求： （1）能夠實現鍵盤和鼠標兩種輸入方式。 （2）能夠保存計算結果。 （3）能夠處理括號等運算符。 （4）學生可自動增加新功能模塊（視情況可另外加分）。 3．設計報告： 1）寫出主要設計思路，圖形方式和文本方式的工作原理； 2）畫出程序流程圖； 3）調試出現的問題及解決方法； 4）提交程序清單。 三、編程重點、難點提示 1．DOS環境下的圖形初始化。 2．DOS環境下鼠標的使用方法。1．MOUSE.COM文件； 2．鼠標初始化； 擊。 聯系方式：譚順華 電話：6088222,***(V網：61025) QQ：182986843．數字的顯示方法。3．鼠標事件的獲取，包括鼠標的位置（X，Y），左鍵或右件，單擊或雙第二篇：人工智能課程設計報告-n皇后問題解讀
第三篇：關于c語言編程中八皇后問題的設計報告
第四篇：C語言關于自然數的和以及自然數n次方的和
第五篇：C語言之計算器軟件設計
點擊咨詢 