【正文】 w，mid，high) //A(low：high)是一個(gè)全程數(shù)組// //輔助數(shù)組B(low；high)// integer h，i，j，k； h←low；i←low；j←mid+1； while h≤mid and j≤high do //當(dāng)兩個(gè)集合都沒(méi)取盡時(shí)// if A(h)≤A(j) then B(i) ←A(h)；h←h+1 else B(i) ←A(j)；j←j+1 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。// integer m，p，i；global A(m：p1) v←A(m)；i←m //A(m)是劃分元素// loop loop i←i+1 until A(i)≥v repeat //i由左向右移// loop p←p1 until A(p)≤v repeat //p由右向左移// if ip then call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)換位// else exit endif repeat A(m) ←A(p)；A(p) ←v //劃分元素在位置p// End PARTITION1. 歸并排序includeincludeincludeincludedefine M 11typedef int KeyType。i++) r[i]=b[i]。i++) { k=i。 xuanze(r,m,h)。k++) { if(r[i].key=r[j].key) { r2[k]=r[i]。 } while(i=m) { r2[k]=r[i]。 int i,j=0,k=M/2,n=M。 (a,M)。struct rec{ KeyType key。 if(st){ i=part(s,t)。p=b[s]。 b[j]=b[i]。 }private: sqlist b。in。}1. 歸并排序2. 快速排序?qū)嶒?yàn)二 貪心法1. 優(yōu)化問(wèn)題 有n個(gè)輸入，而它的解就由這n個(gè)輸入滿足某些事先給定的約束條件的某個(gè)子集組成，而把滿足約束條件的子集稱為該問(wèn)題的可行解。2）按這種量度標(biāo)準(zhǔn)對(duì)這n個(gè)輸入排序3）依次選擇輸入量加入部分解中。M是背包的容量大小，而x(1：n)是解向量 real P(1：n)，W(1：n)，X(1：n)，M，cu； integer i，n；X←0 //將解向量初始化為零 cu←M //cu是背包剩余容量 for i←1 to n do if W(i)cu then exit endif X(i) ←1 cu←cuW(i) repeat if i≤n then X(i) ←cu/ W(i) endif end GREEDYKNAPSACKprocedure prim(G,)status←“unseen” // T為空 status[1]←“tree node” // 將1放入Tfor each edge(1,w) do status[w]←“fringe” // 找到T的鄰接點(diǎn) dad[w] ←1。 for(k=0；kn1；k++){ //求T的n1條樹(shù)邊 //物品重量 float X。 while (goods[0].pgoods[i].p) { goods[i+1]=goods[i]。 cu=M。j=n。i=n。 goodinfo *goods。 for(i=1。//得出物品的效益，重量比 coutendl。typedef char VerTexType。typedef struct{ VerTexType adjvex。void main( void ){ int i, j。 cout 。 char hand, tide。 } coutendl。 k = 0。 while (tide != [k]) k++。 k = LocateVex ( G, u )。 close[k].lowcost = 0。 coutclose[k].lowcostendl。 return 0。 } j1++。子問(wèn)題重疊性質(zhì)：每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。// real COST(n)，integerD(n一1)，P(k)，r，j，k，n COST(n)← 0 for j←n1to 1by－1do //計(jì)算COST(j)// 　設(shè)r是一個(gè)這樣的結(jié)點(diǎn)，(j，r)206。typedef struct Graph{ AdjList vertices。 Garum = a。 printf(輸入第%d條弧:, m)。 pnextarc = NULL。}void print_Graph(ALGraph G){ //打印鄰接表 ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode))。 } printf(\n)。 j = 1。 } p = pnextarc。 printf(最小成本為:%d\n,cost[1])。 printf(請(qǐng)輸入多段圖節(jié)點(diǎn)數(shù)目:)。k)。在深度優(yōu)先搜索中，對(duì)于最新發(fā)現(xiàn)的頂點(diǎn)v，如果邊(v,w)是還未探測(cè)的邊，則沿(v,w)繼續(xù)搜索下去。3． 修改算法使之可以判斷圖是否為一棵樹(shù)。 for (u,w)∈E do //探尋邊(u,w) if color[w]=White then DFS_Visit(w)。 color[i]=39。) //當(dāng)該點(diǎn)的鄰接點(diǎn)中有已被訪問(wèn)的點(diǎn)時(shí)存在環(huán) loop++。 cinn。 //將矩陣初始化為0 color[i]=39。 A[i][j]=1。i++) for(j=1。 cout該圖不是一棵樹(shù)!endl。否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。 i++。(!place(k, X))) //當(dāng)前列位置是否滿足條件 X[k] = X[k] + 1。 //當(dāng)前行復(fù)位為0 k = k 1。n)。 }}33。 printf(The solutions are:\n)。 int *X。i = n。}void Nqueens(int n, int *X){//k表示所處理的是第k行的皇后，X[k]表示第k行皇后的列位置 int k。 while (k0) do if Tk (x1，x2，…， x k1)的值還未取遍 then {xk←Tk (x1，x2，…， x k1)中未取遍過(guò)的值；if Bk (x1，x2，…， x k) then{(x1，x2，…， x k)被激活；if k ==n then 輸出(x1，x2，…， x n)；else k =k+1； // 深度擴(kuò)展搜索 } } else k = k 1 // 試探完了所有的x k，回溯 end BACAKTRACE1. 編程實(shí)現(xiàn)n皇后算法。Si,i=1,2,…n}，給定關(guān)于n元組中的分量的一個(gè)約束集D，求滿足D的全部約束條件的所有n元組。j++) { if(!(A[i][j]amp。i=n。 //所有頂點(diǎn)顏色初始化為白色 } } for(k=1。 cinm。W39。 //已訪問(wèn)頂點(diǎn)記為灰色 for(k=1。