【正文】 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 將已歸并的集合復制到A end MERGE2. 快速排序算法QuickSort(p,q) //將數(shù)組A[1:n]中的元素 A[p], A[p+1], 188。2. 掌握分治法的一般控制流程。1. 編程實現(xiàn)歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計數(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)化問題算法思想：在貪心算法中采用逐步構造最優(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。每一點最優(yōu)都是上一點最優(yōu)加上這段長度。 //該結(jié)點與鄰接結(jié)點間的代價 struct ArcNode *nextarc。 m++) { Gvertices[m].data = m。 else { //若當前結(jié)點有后繼節(jié)點則后移 for(q = Gvertices[i].firstArc。 int path[100]。 //決策階段，各結(jié)點到終點最小代價路徑上前方頂點的編號 } path[1] = 1。 printf(請輸入多段圖邊的數(shù)目:)。如果還存在未被發(fā)現(xiàn)的頂點，則選擇其中一個作為源結(jié)點并重復以上過程，整個進程反復進行直到所有結(jié)點都被發(fā)現(xiàn)為止。includedefine MAX 50 //能夠處理的最多頂點數(shù) char color[MAX]。) DFS(k)。k=m。amp。2. 用圖形輸出中間過程。i++) //輸出各行皇后的列位置 printf(%d , X[i])。 Nqueens(n, X)。 scanf(%d, amp。amp。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。i=n。j++) { A[i][j]=0。B39。 color[u]←Gray。}多段圖問題實驗四 深度優(yōu)先搜索1． 理解深度優(yōu)先搜索策略：深度優(yōu)先搜索策略是盡可能“深”地搜索圖。 g = (ALGraph)malloc(sizeof(ALGraph))。 value = pvalue。//第i個結(jié)點的鄰接結(jié)點信息 p = pnextarc。 pvalue = v。 //圖的頂點數(shù) if(a 0) return printf(ERROR)。 P(1：k)是最小成本路徑。最優(yōu)子結(jié)構性質(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) //退出過程時，p帶著劃分元素所在的下標位置。 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)實現(xiàn)全局最優(yōu)，并驗證算法的時間復雜性。 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. 驗證算法的時間復雜性。 node p, q。v)。 i++) { p = Gvertices[i].firstArc。 value = pvalue。 w++) printf(%d, path[w])。 print_Graph(g)。 repeat for每個頂點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. 理解回溯法的基本思想回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法。 k = 1。 printf(| edited by Jill Chih |\n)。 scanf(%d, amp。 //不是最后一個,則處理下一個皇后 X[k] = 0。 i = 1。 if(m==n1) cout該圖為一棵樹!endl。 cout請輸入指向的點:。 //當點為死結(jié)點時記為黑色}void main(){ int i,j,k,m。 //標記環(huán)并記錄其個數(shù)int tree=0。1． 編程實現(xiàn)深度優(yōu)先搜索算法。 printf(請輸入多段圖的段數(shù):)。 i = k 1。 cost[n] = 0。 qnextarc = p。 m = a。 //頂點信息 ArcNode *firstArc。3. 一般方法1） 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構特征；2） 遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）；3） 以自底向上的方式計算出最優(yōu)值；4） 根據(jù)計算最優(yōu)值時得到的信息，構造一個最優(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。