武漢理工大學(xué)算法設(shè)計(jì)題(考試專用)

武漢理工大學(xué)算法設(shè)計(jì)題(考試專用)武漢理工大學(xué)算法設(shè)計(jì)題(考試專用)武漢理工大學(xué)算法設(shè)計(jì)題(考試專用)武漢理工大學(xué)算法設(shè)計(jì)題(考試專用)編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:算法2.3二分檢索//給定一個(gè)按非降次序排列的元素?cái)?shù)組A(1:n),n≥1,判 斷x是否出現(xiàn)。若是，置j，使得x=A(j),若非，j=0//BINSEARCH(A,n,x) 1low12highnwhilelow<=high//如果low>high，數(shù)組A中沒(méi)有找到x，返回j＝04do5{6//取處于low和high之間的中間值7ifx==A[mid]//找到值為x的元素，mid即為其下標(biāo)，返回mid8then returnmid9elseifx<A[mid]//如果x<A[mid]，則x可能位于low與mid之間，10 //否則x可能位于mid與high之間11 thenhighmid-112 elselowmid+113}14retrun0一種二分檢索的變形BINSEARCH1。BINSEARCH1(A,n,x,j)1low12highn+13whilelow<high4 do5 {6 mid(low+high)/27 if(x<A[mid]) //在循環(huán)中只比較一次8 thenhighmid9 elselowmid10 }11ifx==A[low]12thenjlow //x出現(xiàn)13elsej=0 //x不出現(xiàn)14returnj算法2.5直接找最大和最小元素maxmin(A,n)//將A(1:n)中的最大元素置于max，最小元素置于min//1maxA[1]2minA[1];

3fori2ton4 do5 {6 ifmax<A[i]5 thenmaxA[i]6ifmin>A[i]7 thenminA[i]8 }用下面的語(yǔ)句代替for循環(huán)中的語(yǔ)句：ifA(i)>maxthenmaxA(i)elseifA(i)<minthenminA(i) endifendif最好情況將在元素按遞增次序排列時(shí)出現(xiàn)，元素比較數(shù)是n-1；最壞情況將在遞減次序時(shí)出現(xiàn)，元素比較是2（n-1）；至于在平均情況下,A(i)將有一半的時(shí)間比max大，因此平均比較數(shù)是3/2(n-1)。算法２.６遞歸求取最大和最小元素floatA[n];maxmin（i,j,fmax,fmin）//最大和最小元素賦給fmax和fmin1ifi==j2 then3 {4 fmaxA[i];5 fminA[i];6}7elseifi==j-18 thenifA[i]<A[j]9 then10 {11 fmaxA[j]；12 fminA[i]13 }14 else15 {16 fmaxA[i];17 fminA[j];18 }19 else20 {21 mid(i+j)/2;

22 maxmin(i，mid，lmax，lmin)23 maxmin(mid+1，j，rmax，rmin）24 iflmax>rmax25 thenfmaxlmax;26elsefmaxrmax27iflmin>rmin28 thenfminrmin;29elsefminlmin;30 }算法3.3背包問(wèn)題的貪心算法Knapsack(ElemtypeWp[n],ElemtypePw[n],floaty[n],ElemtypeWC,intn)//p[n]和w[n]分別含有按p[i]／w[i]，p[i＋1]／w[i+1]排序的n件物品的效益值和容量。M是背包的容量大小，而y[n]是解向量//1fori←1ton2doy[i]←0; //將解向量初始化為0；3cu←C; //cu是背包中剩余的空間；4fori←1ton5do{ //依次考察下一個(gè)物品是否可以放入背包；6ifw[i]>cubreak;//物品i無(wú)法全部放入背包,退出for循環(huán)；7elsey[i]←1;8cu←cu-w[i];9}10ifi≤n11theny[i]←cu/w[i];//不能完全裝入的物品的部分裝入量算法3.4帶有限期和效益的單位時(shí)間的作業(yè)排序貪心算法GreedyJob(intn,intd[],int&J[])//d[1],…,d[n]是期限值。n≥1。作業(yè)已按p1≥p2≥…pn被排序。J[i]是最優(yōu)解中的第i個(gè)作業(yè)，1≤i≤k。終止時(shí)，d[J[i]]≤d[J[i+1]]，1≤i＜k//1 k←1;2 d[0]←0;3 J[0]←0;4 J[1]←1; //首先將作業(yè)1插入第一個(gè)位置；5 fori←2ton//按p的非增次序依次考慮剩下的作業(yè)；6 do{7 r←k;8 whiled[J[r]]>d[i]andd[J[r]]≠r 9 do{//while循環(huán)用來(lái)確定正在考慮的作業(yè)可能要插入的位置；10 r←r-1; 11}12 ifd[J[r]]≤d[i]andd[i]>r//判斷此作業(yè)是否可以插入J；13 then{14 forj←ktor+1//j是遞減的 15 do{//將第k到第r+1個(gè)作業(yè)依次后移一位以插入新的作業(yè)；16 J[j+1]←J[j];17 }18 J[r+1]←i; //將作業(yè)插入位置r+1；19 k←k+1; //記入J的作業(yè)數(shù)加1;20 }21 }22 returnk; //返回記入J中的作業(yè)數(shù)。算法JS所需要的總時(shí)間是O（sn）。由于s≤n(s為包含在解中的作業(yè)數(shù))，因此JS的最壞計(jì)算時(shí)間為O（n2）。算法4.1多段圖的向前處理算法FGRAPH(ElemtypeE[],intk,intn,ElemtypeP[k])//輸入是按段的順序給結(jié)點(diǎn)編號(hào)的，有n個(gè)結(jié)點(diǎn)的k段圖。E是邊集，c[i][j]是邊<i,j>的成本。P[k]是最小成本路徑//輸入：多段圖的頂點(diǎn)編號(hào)表，各頂點(diǎn)的邊表和各邊的成本函數(shù)c(i，j)的表。輸出：從s到t的一條最小成本路徑上的各頂點(diǎn)以及成本COST(l，s)。1COST[n]0;2forjn-1to1by-1//計(jì)算COST[j]；3do{設(shè)r是這樣一個(gè)結(jié)點(diǎn)，<j,r>且使c[j][r]+COST[r]取最小值；4COST[j]c[j][r]+COST[r];5D[j]r;6}//找一條最小成本路徑；7P[1]1；P[k]n;8forj2tok-1//找路徑上的第j個(gè)結(jié)點(diǎn)。9do{10P[j]D[P[j-1]];11}第3-6行的for循環(huán)的時(shí)間是(n+e)，第9-11行的for循環(huán)時(shí)間是。總的計(jì)算時(shí)間在以內(nèi)。算法6.1回溯的一般方法BackTrack(n)//這是對(duì)回溯法控制流程的抽象描述。每個(gè)解都在X[n]中生成，一個(gè)解一經(jīng)確定就立即打印出。在X[1]，…,X[k-1]已被選定的情況下，R（X[1]，…,X[k-1]）給出X[k]的所有可能的取值。限界函數(shù)C（X[1]，…,X[k]）判斷哪些元素X[k]滿足隱式約束條件//1k←1//變量k用來(lái)記錄樹(shù)的層數(shù)，初始化為12whilek>0do3{4if還剩有沒(méi)檢驗(yàn)過(guò)的X[k]使得5X[k]∈R(X[1],…,X[k-1])andC(X[1],…,X[k])=true6then{if(X[1],…,X[k])是一條抵達(dá)一答案結(jié)點(diǎn)的路徑7thenprint(X[1],…,X[k]);8kk+1;9}10elsekk-1;//說(shuō)明不剩沒(méi)有檢驗(yàn)的X(k)或Ck(X(1)..X(k))=false11}算法6.2遞歸回溯算法RBackTrack(k)//此算法是對(duì)回溯算法的抽象遞歸描述。進(jìn)入算法時(shí)，解向量X[n]的前k-1個(gè)分量X[1],…X[k-1]已賦值//while滿足下式的每個(gè)X(k)X[k]∈R(X[1],…,X[k-1])andC(X[1],…,X[k])=truedo{if(X[1],…,X[k])是一條已抵達(dá)一答案結(jié)點(diǎn)的路徑thenprint(X[1],…,X[k]);RBackTrack(k+1)}算法6.4可以放置一個(gè)新皇后嗎？以下函數(shù)Place(k)，用來(lái)判定將皇后k放在棋盤的第xk列是否可行，如果皇后k可以放在第xk列，那么Place(k)的返回值為真，否則返回值為假，顯然，在進(jìn)入該函數(shù)前，前k-1皇后已經(jīng)放置好，即x[n]已確定k-1個(gè)值。Place(intk)1i←1; //設(shè)置i值；2whilei<k //把第k行皇后的位置與前k-1行的皇后的位置進(jìn)行比較；3do{4ifx[i]=x[k]orabs(k-i)=abs(x[k]–x[i]) //若皇后i和k相互攻擊，5 thenreturnFALSE;//返回FALSE6 i←i+1 //準(zhǔn)備與下一行的皇后進(jìn)行比較；7 }8 returntrue;算法6.5n-皇后問(wèn)題的所有解//此過(guò)程使用回溯法求出在一個(gè)n*n棋盤上放置n個(gè)皇后，使其不能互相攻擊的所有可能位置//nQueens(intn)1x[1]←0;2k←1;3whilek>04do{5x[k]←x[k]+1; //將第k行的皇后k后移一列；6whilex[k]≤nandPlace(k)=FALSE//確定皇后k的列數(shù)x[k]；7 dox[k]←x[k]+1;8 ifx[k]≤n9 then{10 ifk=n //n個(gè)皇后的位置都已經(jīng)確定，輸出；11 thenfori←1ton 12 doprint（x[i]）; 13 else{//n個(gè)皇后的位置還沒(méi)全確定，考慮下一個(gè)皇后的位置；14 k←k+1;15 x[k]←0;}16 }//x[k]≤n17 else//當(dāng)前行皇后無(wú)位置放，將上一行的皇后的位置重新安排；18k←k–1; //回溯//19}//while算法6.6子集和數(shù)問(wèn)題的遞歸回溯算法SumOfSub(ints,intk,intr) //找W(1:n)中和數(shù)為M的所有子集。進(jìn)入此過(guò)程時(shí)X(1),…,X(k-1)的值已確定。且。這些W(j)按非降次序排列。假定W(1)≤M，//生成左兒子。注意，由于Bk-1=true,因此s+W(k)≤M// 1x[k]←1; //將第k個(gè)正數(shù)計(jì)入解向量；2 if(s+w[k])=M//將第k個(gè)正數(shù)計(jì)入解向量后，得到一個(gè)可行解；3 thenfori←1tok4 doprint(x[i]); //輸出這個(gè)可行解；5 else{//第k個(gè)正數(shù)可以計(jì)入解向量，遞歸調(diào)用SumOfSub()算法；6 if(s+w[k]+w[k+1])≤M)7thenSumOfSub(s+w[k],k+1,r–w[k]);}//以下生成右兒子和計(jì)算Bk的值8if(s+r–w[k])≥Mand(s+w[k+1])≤M)then{//第k個(gè)正數(shù)不可以計(jì)入解向量，遞歸調(diào)用SumOfSub()算法。 x[k]←0;SumOfSub(s,k+1,r-w[k]);}LC-檢索算法LC(ElemtypeT，Elemtypec[])的描述LC(ElemtypeT，Elemtypec[])//為找一個(gè)答案結(jié)點(diǎn)檢索T；//書上的算法有錯(cuò)，請(qǐng)修改LC(ElemtypeT，Elemtypec[])1 if(T是答案結(jié)點(diǎn))2 then{輸出