【正文】 printf(Press 0 to exit\n)。 printf(||\n\n)。 } else { k = k + 1。 while(k 0) { X[k] = X[k] + 1。n皇后算法procedure NQUEENS(n)X(1)←0；k←1 //k是當(dāng)前行；X(k)是當(dāng)前列//While k0 do //對所有的行執(zhí)行以下語句//{ X(k)←X(k)+1 //移到下一列//While X(k)≤n and not PLACE(k) do X(k)←X(k)十l if X(k)≤n //找到一個位置// then if k=n //是一個完整的解嗎// then print(X) //是，打印這個數(shù)組// else {k←k+1；X(k)←0；} else k←k－1 //回溯//}end NQUEENSinclude include /*檢查可不可以放置一個新的皇后*/bool place(int k, int *X){ int i。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。 } if(loop==0) { cout該圖中無環(huán)!endl。) DFS(i)。 cini。i++) { for(j=1。B39。G39。 //頂點數(shù)和矩陣int loop=0。end。每個頂點開始均為白色，搜索中被發(fā)現(xiàn)時置為灰色，當(dāng)其鄰接表被完全檢索之后又被置成黑色。 fgraph(g, k, n)。a)。}void main(){ ALGraph g。 for(i = 2。 while(p != NULL) { //r是一個的這樣的結(jié)點，權(quán)值c(j,r)+cost[r]取最小值 if((pvalue + cost[padjvex]) min) { min = pvalue + cost[padjvex]。 node p。 printf([%d],i)。 q = qnextarc)。 p = (ArcNode*)malloc(sizeof(ArcNode))。 } for(m = 1。 if(n 0) return printf(ERROR)。typedef struct VNode{ int data。多段圖算法procedure FGRAPH(E，k，n，P) //輸入是按段的順序給結(jié)點編號的，有n個結(jié)點 的k段圖。us 初始值，uj第j段的最優(yōu)值。在50年代，貝爾曼（Richard Bellman）等人提出了解決這類問題的“最優(yōu)化原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法－動態(tài)規(guī)劃。amp。 close[j].lowcost = [k][j].adj。 coutclose[k].adjvex。 } } close[j].lowcost = 88。 coutendl。 cintide。 coutendl。 i++) { for(j = 0。}void CreateGraph(MGraph amp。 i++) { for(j = 0。void MiniSpanTree_PRIM(MGraph G, VerTexType u)。 AdjMatrix arcs。 cinj。 cout請輸入第i件物品的效益:。 cinM。 int j。 } goods[i+1]=goods[0]。 cu=cugoods[i].w。 for(i=1。j=n。 InitCandidateSet(…)；//初始化：設(shè)置初始的輕邊候選集，并置T=({r}，￠)2. 輸入5個的圖的鄰接矩陣，程序加入統(tǒng)計prim算法訪問圖的節(jié)點數(shù)和邊數(shù)的語句。決策一旦作出，就不可再更改。 cout排序后數(shù)組:\n。 int i,n=MAXI,low=0,high=9。in。 while(ijamp。 rec p。in。 ()。b[i].key=0。 }。 } while(jh) { r2[k]=r[j]。imamp。 b[k]=b[i]。 } void xuanze(sqlist b,int m,int n) { int i,j,k。typedef rec sqlist[M]。 // 劃分后j成為劃分元素的位置 QuickSort(p,j1)。3. 與復(fù)雜性函數(shù)所計算的比較次數(shù)比較。q163。算法設(shè)計與分析實驗報告 指導(dǎo)老師：沙莎學(xué) 院：信息科學(xué)與工程學(xué)院班 級：計科0508姓 名：戚婕學(xué) 號：10完成日期：2007年12月目 錄實驗一 分治法 ………………………………………………………………………… 2 實驗要求 ……………………………………………………………………… 2 實驗內(nèi)容 ……………………………………………………………………… 2 核心算法 ……………………………………………………………………… 2 程序代碼 ……………………………………………………………………… 4 實驗結(jié)果 ……………………………………………………………………… 8實驗二 貪心法 ……………………………………………………………………… 10 實驗要求 …………………………………………………………………… 10 實驗內(nèi)容 …………………………………………………………………… 10 核心算法 …………………………………………………………………… 10 程序代碼 …………………………………………………………………… 12 實驗結(jié)果 …………………………………………………………………… 18實驗三 動態(tài)規(guī)劃 ………………………………………………………………… 20 實驗要求 …………………………………………………………………… 20 實驗內(nèi)容 …………………………………………………………………… 20 核心算法 …………………………………………………………………… 20 程序代碼 …………………………………………………………………… 21 實驗結(jié)果 …………………………………………………………………… 24實驗四 深度優(yōu)先搜索 …………………………………………………………… 26 實驗要求 …………………………………………………………………… 26 實驗內(nèi)容 …………………………………………………………………… 26 核心算法 …………………………………………………………………… 26 程序代碼 …………………………………………………………………… 27 實驗結(jié)果 …………………………………………………………………… 28實驗五 回溯法 ……………………………………………………………………… 30 實驗要求 …………………………………………………………………… 30 實驗內(nèi)容 …………………………………………………………………… 30 核心算法 …………………………………………………………………… 30 程序代碼 …………………………………………………………………… 31 實驗結(jié)果 …………………………………………………………………… 33實驗一 分治法1. 了解用分治法求解的問題：當(dāng)要求解一個輸入規(guī)模為n，且n的取值相當(dāng)大的問題時，如果問題可以分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中1k≤n，而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。n if Small(p,q) then return G(p,q)。4. 用表格列出比較結(jié)果。 QuickSort(j+1,q)。class guibing{public: guibing(sqlist b) { for(int i=0。 for(i=m。 b[i]=temp。amp。 j++。 void main() { coutguibingfa1運行結(jié)果:\n。 } guibing