【正文】 endif i←i+1 repeat if hmid then for k←j to high do //處理剩余的元素// B(i) ←A(k)；i←i+1 repeat else for k←h to mid do B(i) ←A(k)；i←i+1 repeat endif 將已歸并的集合復(fù)制到A end MERGE2. 快速排序算法QuickSort(p,q) //將數(shù)組A[1:n]中的元素 A[p], A[p+1], 188。2. 掌握分治法的一般控制流程。1. 編程實(shí)現(xiàn)歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計(jì)數(shù)功能，輸出排序結(jié)果和比較次數(shù)。 ElemType data。j++) if(b[k].keyb[j].key) k=j。 j++。iM。typedef rec sqlist[MAXI]。b[j].key=)j。void main(){ cout:\n。2. 貪心法求優(yōu)化問題算法思想：在貪心算法中采用逐步構(gòu)造最優(yōu)解的方法。 } }}//按物品效益，重量比值做升序排列void bag(goodinfo goods[],float M,int n){ float cu。 while (goods[0].flaggoods[i].flag) { goods[i+1]=goods[i]。 goods=new struct goodinfo [n+1]。 coutpress 1 to run agianendl。void CreateGraph(MGraph amp。a39。 i 。 j = 0。 i 。\039。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加上這段長度。 //該結(jié)點(diǎn)與鄰接結(jié)點(diǎn)間的代價(jià) struct ArcNode *nextarc。 m++) { Gvertices[m].data = m。 else { //若當(dāng)前結(jié)點(diǎn)有后繼節(jié)點(diǎn)則后移 for(q = Gvertices[i].firstArc。 int path[100]。 //決策階段，各結(jié)點(diǎn)到終點(diǎn)最小代價(jià)路徑上前方頂點(diǎn)的編號(hào) } path[1] = 1。 printf(請(qǐng)輸入多段圖邊的數(shù)目:)。如果還存在未被發(fā)現(xiàn)的頂點(diǎn)，則選擇其中一個(gè)作為源結(jié)點(diǎn)并重復(fù)以上過程，整個(gè)進(jìn)程反復(fù)進(jìn)行直到所有結(jié)點(diǎn)都被發(fā)現(xiàn)為止。includedefine MAX 50 //能夠處理的最多頂點(diǎn)數(shù) char color[MAX]。) DFS(k)。k=m。amp。2. 用圖形輸出中間過程。i++) //輸出各行皇后的列位置 printf(%d , X[i])。 Nqueens(n, X)。 scanf(%d, amp。amp。如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。i=n。j++) { A[i][j]=0。B39。 color[u]←Gray。}多段圖問題實(shí)驗(yàn)四 深度優(yōu)先搜索1． 理解深度優(yōu)先搜索策略：深度優(yōu)先搜索策略是盡可能“深”地搜索圖。 g = (ALGraph)malloc(sizeof(ALGraph))。 value = pvalue。//第i個(gè)結(jié)點(diǎn)的鄰接結(jié)點(diǎn)信息 p = pnextarc。 pvalue = v。 //圖的頂點(diǎn)數(shù) if(a 0) return printf(ERROR)。 P(1：k)是最小成本路徑。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。 while([k++] == u) return k1。\039。 while (hand != [j]) j++。 j++) [i][j].adj = 88。 j++) { cout[i][j].adj。 }MGraph。 goods[i].p=goods[i].p/goods[i].w。 float M。//該物品所要放的量for(j=2。 i=j1。 (u，v)=SelectLiShtEdge(…)；//選取輕邊(u，v)；1. 背包問題的貪心算法 procedure KNAPSACK(P，W，M，X，n) //P(1：n)和W(1；n)分別含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。 ()。 coutendl。j=t。typedef int ElemType。 sqlist a,b。jh。in1。 endif end QuickSortprocedure PARTITION(m，p) //退出過程時(shí)，p帶著劃分元素所在的下標(biāo)位置。 else m=Divide(p,q)。p163。 if pq then j=Partition(p, q+1)。 coutendl。 for(j=m。 }private: sqlist r。 (b,M)。 } int part(int s,int t) { int i,j。 } void output() { for(int i=0。 (low,high)。通過具體算法理解如何通過局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)，并驗(yàn)證算法的時(shí)間復(fù)雜性。 for(j=2。 goods[i].X=1。 cout||endl。 cingoods[i].w。typedef struct{ VerTexType vexs[MAX_VERTEX_NUM]。 i 。 i 。 cinhand。 close[j].lowcost = [k][j].adj。 j++) { if ([k][j].adj close[j].lowcost) { close[j].adjvex = [k]。這類問題的解決是多階段的決策過程。4. 驗(yàn)證算法的時(shí)間復(fù)雜性。 node p, q。v)。 i++) { p = Gvertices[i].firstArc。 value = pvalue。 w++) printf(%d, path[w])。 print_Graph(g)。 repeat for每個(gè)頂點(diǎn)u∈G do if color[u]=White then DFS_Visit(G,u)。k++) { if(A[i][k]==1) { if(color[k]==39。i=n。W39。2. 理解回溯法的基本思想回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。 k = 1。 printf(| edited by Jill Chih |\n)。 scanf(%d, amp。 //不是最后一個(gè),則處理下一個(gè)皇后 X[k] = 0。 i = 1。 if(m==n1) cout該圖為一棵樹!endl。 cout請(qǐng)輸入指向的點(diǎn):。 //當(dāng)點(diǎn)為死結(jié)點(diǎn)時(shí)記為黑色}void main(){ int i,j,k,m。 //標(biāo)記環(huán)并記錄其個(gè)數(shù)int tree=0。1． 編程實(shí)現(xiàn)深度優(yōu)先搜索算法。 printf(請(qǐng)輸入多段圖的段數(shù):)。 i = k 1。 cost[n] = 0。 qnextarc = p。 m = a。 //頂點(diǎn)信息 ArcNode *firstArc。3. 一般方法1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2） 遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）；3） 以自底向上的方式計(jì)算出最優(yōu)值；4） 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。 close[j1].lowcost != 0) { client = close[j1].lowcost。 cout。 }}void MiniSpanTree_PRIM(MGraph G,VerTexType u){ int i, j, k = 0。 coutinputarc(char,char,weigh):endl。G){ int weigh。int LocateVex(MGraph G, VerTexType u)。 }}2. Prim算法include include include define INFINITY INT_MAX define MAX_VERTEX_NUM 20 typedef int VRType。