【正文】 gx(a)。 }2. 快速排序includeincludeincludeincludedefine MAXI 10typedef int KeyType。i++) b[i]=a[i]。 i=s。amp。i++) coutsetw(4)b[i].key。 srand(time(0))。 ()。作出貪心決策的依據(jù)稱為貪心準(zhǔn)則（greedy criterion）。3. 將統(tǒng)計(jì)數(shù)與復(fù)雜性函數(shù)所計(jì)算的比較次數(shù)比較，用表格列出比較結(jié)果，給出文字分析。 ModifyCandidateSet(…)； //根據(jù)新紅點(diǎn)v調(diào)整候選輕邊集 }1. 背包問題貪心算法include struct goodinfo{ float p。j++) { goods[0]=goods[j]。i=n。//確定背包新的剩余容量 } if(i=n) goods[i].X=cu/goods[i].w。 }cout最優(yōu)解為:endl。 int n。 coutendl。 cingoods[i].p。 }}2. Prim算法include include include define INFINITY INT_MAX define MAX_VERTEX_NUM 20 typedef int VRType。 int vexnum, arum。int LocateVex(MGraph G, VerTexType u)。 j 。G){ int weigh。 j 。 coutinputarc(char,char,weigh):endl。 cinweigh。 }}void MiniSpanTree_PRIM(MGraph G,VerTexType u){ int i, j, k = 0。 close[j].adjvex = 39。 cout。 } } }}int LocateVex(MGraph G, VerTexType u){ int k = 0。 close[j1].lowcost != 0) { client = close[j1].lowcost。對于一個多階段過程問題，是否可以分段實(shí)現(xiàn)最優(yōu)決策，依賴于該問題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動態(tài)規(guī)劃的方法，還要看該問題的子問題是否具有重疊性質(zhì)。3. 一般方法1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2） 遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3） 以自底向上的方式計(jì)算出最優(yōu)值；4） 根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。E是邊集，c(i，j)是邊i,j的成本。 //頂點(diǎn)信息 ArcNode *firstArc。 Gvexnum = n。 m = a。 padjvex = h。 qnextarc = p。 while(p) { printf(%d,%d,padjvex,pvalue)。 cost[n] = 0。 //pvalue=c(j,r) r = padjvex。 i = k 1。 int n,a,k。 printf(請輸入多段圖的段數(shù):)。 getch()。1． 編程實(shí)現(xiàn)深度優(yōu)先搜索算法。 procedure DFS_Visit(u)。 //標(biāo)記環(huán)并記錄其個數(shù)int tree=0。||color[k]==39。 //當(dāng)點(diǎn)為死結(jié)點(diǎn)時記為黑色}void main(){ int i,j,k,m。j=n。 cout請輸入指向的點(diǎn):。 } for(i=1。 if(m==n1) cout該圖為一棵樹!endl。算法搜索至解空間樹的任一結(jié)點(diǎn)時，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。 i = 1。 //從當(dāng)前列加1的位置開始搜索 while((X[k] = n)amp。 //不是最后一個,則處理下一個皇后 X[k] = 0。 while(i) { printf(Please input the sum of Queens:\n)。 scanf(%d, amp。 printf(Press 1 to run again\n)。 printf(| edited by Jill Chih |\n)。 printf(\n)。 k = 1。3. 在程序中添加統(tǒng)計(jì)擴(kuò)展節(jié)點(diǎn)數(shù)，估計(jì)算法的復(fù)雜性。2. 理解回溯法的基本思想回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。A[j][i])) tree++。W39。k++) { cout請輸入其始點(diǎn):。i=n。 //訪問鄰接點(diǎn)中一個沒有被訪問的點(diǎn) } } color[i]=39。k++) { if(A[i][k]==1) { if(color[k]==39。 //保存每個點(diǎn)的顏色標(biāo)記int n,A[MAX][MAX]。 repeat for每個頂點(diǎn)u∈G do if color[u]=White then DFS_Visit(G,u)。2． 理解深度優(yōu)先搜索過程中頂點(diǎn)的三種狀態(tài)：還未到達(dá)的頂點(diǎn)，當(dāng)前路徑上經(jīng)過的頂點(diǎn)，深度優(yōu)先在搜索過程中也為結(jié)點(diǎn)著色以表示結(jié)點(diǎn)的狀態(tài)。 print_Graph(g)。 scanf(%d, amp。 w++) printf(%d, path[w])。 path[k] = n。 value = pvalue。 int j, r, i, min, w, value。 i++) { p = Gvertices[i].firstArc。 qnextarc。v)。 Gvertices[m].firstArc = NULL。 node p, q。 //指向下一條弧的指針}ArcNode, *node。4. 驗(yàn)證算法的時間復(fù)雜性。即當(dāng)前最優(yōu)只與上一步有關(guān)。這類問題的解決是多階段的決策過程。) { if (client close[j1].lowcost amp。 j++) { if ([k][j].adj close[j].lowcost) { close[j].adjvex = [k]。 i++) { k = minimum(close)。 close[j].lowcost = [k][j].adj。 k = 0。 cinhand。 i++) cin[i]。 i 。)。 i 。G)。typedef struct{ VerTexType vexs[MAX_VERTEX_NUM]。 coutpress 0 to exitendl。 cingoods[i].w。// cout請輸入背包的最大容量：。 cout||endl。 i。 goods[i].X=1。 int i,j。 for(j=2。通過具體算法理解如何通過局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)，并驗(yàn)證算法的時間復(fù)雜性。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。 (low,high)。 sqlist a1。 } void output() { for(int i=0。 b[i]=b[j]。 } int part(int s,int t) { int i,j。class kuaisu{public: kuaisu(sqlist a,int m):n(m) { for(int i=0。 (b,M)。i++) { a[i].key=rand()%80。 }private: sqlist r。 } output(r2,M)。 for(j=m。 if(k!=i) { rec temp=b[k]。 coutendl。 }。 if pq then j=Partition(p, q+1)。2. 輸入10組相同的數(shù)據(jù)，驗(yàn)證排序結(jié)果和完成排序的比較次數(shù)。p163。那末，對于這類問題分治法是十分有效的。 else m=Divide(p,q)。5. 給出文字分析。 endif end QuickSortprocedure PARTITION(m，p) //退出過程時，p帶著劃分元素所在的下標(biāo)位置。iM。in1。 } } } void merge(int l,int m,int h,sqlist r2) { xuanze(r,l,m)。jh。 k++。 sqlist a,b。 cout排序前數(shù)組:\n。typedef int ElemType。 } void quicksort(int s,int t) { int i。j=t。b[i].key=)