算法設(shè)計(jì)與分析習(xí)題

1、算法設(shè)計(jì)與分析習(xí)題第一章算法引論1、 算法的定義？答：算法是指在解決問題時(shí)，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程。通俗講，算法：就是解決問題的方法或過程。2、 算法的特征？答：1）算法有零個(gè)或多個(gè)輸入；2）算法有一個(gè)或多個(gè)輸出；3）確定性；4）有窮性3、 算法的描述方法有幾種？答：自然語言、圖形、偽代碼、計(jì)算機(jī)程序設(shè)計(jì)語言4、 衡量算法的優(yōu)劣從哪幾個(gè)方面？答：（1）算法實(shí)現(xiàn)所耗費(fèi)的時(shí)間（時(shí)間復(fù)雜度）；（2） 算法實(shí)現(xiàn)所所耗費(fèi)的存儲(chǔ)空間（空間復(fù)雜度）；（3） 算法應(yīng)易于理解，易于編碼，易于調(diào)試等等。5、 時(shí)間復(fù)雜度、空間復(fù)雜度定義？答：指的是算法在運(yùn)行過程中所需要的資源（時(shí)間、空間）多

2、少。6、時(shí)間復(fù)雜度計(jì)算：i=1；while（i<=n）i=i*2；答：語句執(zhí)行次數(shù)1次，語句執(zhí)行次數(shù)f（n）,2Af（n）<=n,則f（n）<=log2n;算法執(zhí)行時(shí)間：T（n）=2log2n+1時(shí)間復(fù)雜度：記為O（log2n）；7.遞歸算法的特點(diǎn)？答：每個(gè)遞歸函數(shù)都必須有非遞歸定義的初值；否則，遞歸函數(shù)無法計(jì)算；（遞歸終止條件）遞歸中用較小自變量函數(shù)值來表達(dá)較大自變量函數(shù)值；（遞歸方程式）8、算法設(shè)計(jì)中常用的算法設(shè)計(jì)策略？答：蠻力法;動(dòng)態(tài)規(guī)劃法；倒推法；循環(huán)與遞歸；分治法；貪心法；回溯法；分治限界法9、設(shè)計(jì)算法：遞歸法：漢諾塔問題？兔子序列（上樓梯問題）？整數(shù)劃分問題？蠻力

3、法：百雞百錢問題？倒推法：穿越沙漠問題？答：算法如下：(1)遞歸法漢諾塔問題voidhanoi(intn,inta,intb,intc)if(n>0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);兔子序列(fibonaci數(shù)列)遞歸實(shí)現(xiàn)：IntF(intn)if(n<=2)return1;elsereturnF(n-1)+F(n-2);上樓梯問題IntF(intn)if(n=1)return1if(n=2)return2;elsereturnF(n-1)+F(n-2);整數(shù)劃分問題I動(dòng)罪條件f1n=1,2F(n)F(n-1)+F(n-2)n

4、>2IK.通血方程PfrHW：1；2；3；5s8；13，動(dòng)界條件I1n=1F(n)=,2n=2F(n-1)+F(n-2)rv>2遞歸方程問題描述：將正整數(shù)n表示成一系列正整數(shù)之和，n=n1+n1+n3+將最大加數(shù)不大于m的劃分個(gè)數(shù)，記作q(n,m)。正整數(shù)n的劃分?jǐn)?shù)p(n)=q(n,n)?？梢越(n,m)的如下遞歸關(guān)系:1n1,m1q(n,m)遞歸算法:q(n,n)1q(n,n1)q(n,m1)q(nm,m)Intq(intn,intm)if(n<1|m<1)return0;If(n=1)|(m=1)return1;If(n<m)returnq(n,n);If

5、(n=m)returnq(n,m-1)+1;elsereturnq(n,m-1)+q(n-m,m);( 2) 蠻力法：百雞百錢問題算法設(shè)計(jì)1：設(shè)x，y，z分別為公雞、母雞、小雞的數(shù)量。約束條件：x+y+z=100且5*x+3*y+z/3=100main()intx,y,z;for(x=1;x<=20;x=x+1)for(y=1;y<=34;y=y+1)for(z=1;z<=100;z=z+1)if(100=x+y+zand100=5*x+3*y+z/3)print(thecocknumberis",x)；print(thehennumberis",y)；p

6、rint(thechicknumberis"z);算法分析：以上算法需要枚舉嘗試20*34*100=68000次。算法的效率顯然太低算法設(shè)計(jì)2：在公雞(x)、母雞(y)的數(shù)量確定后，小雞的數(shù)量z就固定為100-x-y,無需再進(jìn)行枚舉了。此時(shí)約束條件只有一個(gè)：5*x+3*y+z/3=100main()intx,y,z;for(x=1;x<=20;x=x+1)for(y=1;y<=33;y=y+1)z=100-x-y;if(zmod3=0and5*x+3*y+z/3=100)print(thecocknumberis",x)；print(thehennumberis

7、",y)；print(thechicknumberis"z);算法分析：以上算法只需要枚舉嘗試20*33=660次。實(shí)現(xiàn)時(shí)約束條件又限定Z能被3整除時(shí)，才會(huì)判斷“5*x+3*y+z/3=100”。這樣省去了z不整除3時(shí)的算術(shù)計(jì)算和條件判斷，進(jìn)一步提高了算法的效率。(3) 倒推法：穿越沙漠問題desert()intdis，k，oil,k;/dis表示距終點(diǎn)的距離，k表示貯油點(diǎn)從后到前的序號(hào)dis=500;k=1;oil=500;/初始化while(dis<1000)print(“storepoint”,k,”distance”,1000-dis,”oilquantity

8、”,oil)/1000-dis則表示距起點(diǎn)的距離，k=k+1;/k表示儲(chǔ)油點(diǎn)從后到前的序號(hào)dis=dis+500/(2*k-1);oil=500*k;print("storepoint”,k,"distance”,dis,"oilquantity”,oil);第二章分治算法1、分治算法基本思想是什么？適合用分治算法解決的問題，一般具有幾個(gè)特征？分治算法基本步驟是什么？答：1)基本思想：將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。2)特征：?該問題的規(guī)模縮小到一定的程度就可以容易解決；?該問題可以分解為若干個(gè)規(guī)模較小的相同子問題

9、，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；?該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。?4)利用該問題分解出子問題解可以合并為該問題解；3)基本步驟：分解、求小問題解、合并2、改寫二分查找算法：設(shè)a1n是一個(gè)已經(jīng)排好序的數(shù)組，改寫二分查找算法：?當(dāng)搜索元素x不在數(shù)組中時(shí)，返回小于x的最大元素位置i,和大于x的最小元素位置j;(即返回x的左、右2個(gè)元素)?當(dāng)搜索元素x在數(shù)組中時(shí)，i和j相同，均為x在數(shù)組中的位置。并計(jì)算其時(shí)間復(fù)雜度？答：intbinaryS&arch(Ta,constT友x,intleft,intright,intii,int,intmiddle;whi

10、le(left<=right)(middle(left+right)/2;1if(xreturn1J."1-if(x>amddle)left=middle+；elseright=middle-1;，:)1 =right;j=iMt：;return0;3、設(shè)計(jì)一個(gè)合并排序的算法？(分治法解)公式，及其求解過程)答：voidMergeSort(intA，intlowintmiddle;if(low<high)middle=(low+high)/2;/MergeSort(A,low,middle);MergeSort(A,middle+1,high);Merge(A,lo

11、w,middle,high);并計(jì)算其時(shí)間復(fù)雜度？(要求寫出遞推inthigh)取中點(diǎn)/合并算法voidMerge(intA，intlow，intmiddle，inthigh)/合并過程描述：inti,j,k;int*B=newinthigh-low+1;i=low;j=middle+1;k=low;while(i<=middle&&j<=high)/兩個(gè)子序列非空if(Ai<=Aj)elsewhile(i<=middle)Bwhile(j<=high)BBk+=Ai+;Bk+=Aj+;Bk+=Ai+;/子序列Alow,middle非空，將A復(fù)制到

12、Bk+=Aj+;/子序列Amiddle+1,high非空，將A復(fù)制到for(i=low;i<=high;i+)Ai+=Bi+;/將合并后的序列復(fù)制回A?合并排序算法運(yùn)行時(shí)間T(n)的遞歸形式為：T(n)=O(1)n=12T(n/2)+O(n)n>1分析該算法時(shí)間復(fù)雜度：令T(n)為元素個(gè)數(shù)為n時(shí)所需比較次數(shù)(時(shí)間)當(dāng)n=1時(shí)，時(shí)間復(fù)雜度記為0(1)。當(dāng)n>1時(shí)，T(n)=2T(n/2)+0(n)=2(2T(n/22)+O(n/2)+O(n)=22T(n/22)+2O(n)=23T(n/23)+3O(n)=2xT(n/2x)+x*O(n)分解到最后只有2個(gè)元素可以求解，n/2x

13、=1,x=logn;故T(n)=n*T(1)+n*logn，故時(shí)間復(fù)雜度記為：O(n*logn)4、金塊問題(求最大最小兀問題)老板有一袋金塊(共n塊)，最優(yōu)秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。假設(shè)有一臺(tái)比較重量的儀器，我們希望用最少的比較次數(shù)找出最重的金塊。要求：1)設(shè)計(jì)一算法求解該問題？(分治法解)2)計(jì)算其時(shí)間復(fù)雜度？(要求寫出遞推公式，及其求解過程)答：遞歸求取最大和最小元素maxmin(inti,intj,float&fmax,float&fmin)intmid;floatImax,Imin,rmax,rmin;if(i=j)fmax=ai;fm

14、in=ai;只有1個(gè)元素elseif(i=j-1)/只有2個(gè)元素if(ai<aj)fmax=aj;fmin=ai;elsefmax=ai;fmin=aj;else/多于2個(gè)元素mid=(i+j)/2;maxmin(i,mid,lmax,lmin);/遞歸調(diào)用算法求最大最小maxmin(mid+1,j,rmax,rmin);/遞歸調(diào)用算法求最大最小if(lmax>rmax)fmax=lmax;/合并取大elsefmax=rmax;if(lmin>rmin)fmin=rmin;/合并取小elsefmin=lmin;分析該算法時(shí)間復(fù)雜度：令T(n)為元素個(gè)數(shù)為n時(shí)所需比較次數(shù)(時(shí)間

15、)：當(dāng)n=2時(shí)，查找查找最大最小元只需要1次比較，T(2)=1;時(shí)間復(fù)雜度記為。(1)。當(dāng)n>2時(shí)，T(n)=2T(n/2)+2T(2)=4T(n/4)+4T(2)+2T(2)=8T(n/8)+8+4+2=2xT(n/2x)+2x+2x-1+-+8+4+2分解到最后只有2個(gè)元素可以求解，n/2x=2,T(n)=2x*1+2x+2x-1-+22+21=2x*1+(2-2x*2)/(1-2)=2x+2x+1-2=3n/2-2故時(shí)間復(fù)雜度記為：O(n)n位大整數(shù)的乘法運(yùn)算?為兩個(gè)n位整數(shù) 為x* y的符號(hào)5、用分治思想設(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)其時(shí)間復(fù)雜度？(要求寫出遞推公式，及其求解過

16、程)答：intmult(intx,inty,intn)x,ys=sign(x)*sign(y);sx=abs(x);y=abs(y);intmul;if(n=1)mul=s*x*y;returnmul;else/計(jì)算XY=ac2n+(a-b)(d-c)+ac+bd)2n/2+bdinta=x左邊n/2位；/移位操作，把X分為2塊intb=x右邊n/2位；intc=y左邊n/2位；/移位操作，把Y分為2塊intd=y右邊n/2位；intm1=mult(a,c,n/2);/a,c還不夠小繼續(xù)分為2塊，直到最后1x1位intm2=mult(a-b,d-c,n/2);intm3=mult(b,d,n/

17、2);mul=s*(m1*2n+(m1+m2+m3)*2'/2+m3);returnmul;該算法舞法需要經(jīng)過3次規(guī)模為W2僮的乘法.以及相應(yīng)的移位加法操作(時(shí)間o(n)、J。竹二13T(h/2)+O()n>1用解遞歸方程的迭代公式法：T(n)=3T(n/2)+0(n)=3(3T(n/4)+0(n/2)+0(n)J=33T(tl/22)+3*0(n/2)H)(n)3=(3T(n/2»)中加/4)卜3*0(n/2)H)(n)=33T<n/2a)(n/22)+3*O(n/2)H)=3kT(n/2k)+3k>*O(n/2k)*3*0(n/2)H)(n)解：分解到最

18、后口/2乂二1：T(n)=3k+(3/2)kU(3/2)k%+3/2+1*0(n)=3*3k-2*O(n)解得:T(n)-3*nloo3-2n故時(shí)間復(fù)雜度記為：0583尸0(口1巧6、設(shè)計(jì)一棋盤覆蓋問題算法（分治法）？并計(jì)算其時(shí)間復(fù)雜度？（要求寫出遞推公式，及其求解過程）在一個(gè)2kx2k個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。（該算法中可能用到的變量：tr:棋盤中左上角方格所在行；tc:棋盤中左上角方格所在列。dr

19、：殘缺方塊所在行；dl:殘缺方塊所在列。size:棋盤的行數(shù)或列數(shù)；用二維數(shù)組board,模擬棋盤。）答：voidchessBoard（inttr,inttc,intdr,intdc,intsize）棋盤行數(shù)型骨牌號(hào)特殊方格在此棋盤中if(size=1)return;/size:intt=tile+,/Ls=size/分割棋盤/覆蓋左上角子棋盤if(dr<tr+s&&dc<tc+s)/chessBoard(tr, tc, dr, dc, s);else /此棋盤中無特殊方格boardtr + s - 1tc + s - 1 = t; / chessBoard(tr,

20、 tc, tr+s-1, tc+s-1, s); /覆蓋右上角子棋盤if (dr < tr + s && dc >= tc + s) / chessBoard(tr, tc+s, dr, dc, s);else /此棋盤中無特殊方格boardtr + s - 1tc + s = t; / chessBoard(tr, tc+s, tr+s-1, tc+s, s); /覆蓋左下角子棋盤if (dr >= tr + s && dc < tc + s) / chessBoard(tr+s, tc, dr, dc, s);else boardtr

21、 + stc + s - 1 = t; /chessBoard(tr+s, tc, tr+s, tc+s-1, s); /覆蓋右下角子棋盤if (dr >= tr + s && dc >= tc + s) / chessBoard(tr+s, tc+s, dr, dc, s);else boardtr + stc + s = t; / chessBoard(tr+s, tc+s, tr+s, tc+s, s);/用t號(hào)L型骨牌覆蓋右下角覆蓋其余方格特殊方格在此棋盤中用t號(hào)L型骨牌覆蓋左下角覆蓋其余方格特殊方格在此棋盤中用t號(hào)L型骨牌覆蓋右上角覆蓋其余方格特殊方格在此

22、棋盤中用t號(hào)L型骨牌覆蓋左上角覆蓋其余方格4,算法時(shí)間復(fù)雜度分析設(shè)丑均是覆蓋一個(gè)臥X2K棋盤所需時(shí)間；則其滿足如下遞歸方程工丁小；0(0k=04T(k-1)+0(】)A>0T(k)=4*T(k-1)+1=42*T(k-2)+4+1/4*(rT(k-2)+1)+1=4l*T(k'3J+4I+4+1=4*T(k-x)+4-U4*.+42+4+1分解到最后解x=。；-43口0)+47+47+4?+4+1=(14*揪14)=(4也邛3故該算法的時(shí)間交雜度記為。(49第三章動(dòng)態(tài)規(guī)劃算法1、動(dòng)態(tài)規(guī)劃算法基本思想？動(dòng)態(tài)規(guī)劃算法與分治算法異同點(diǎn)？適合用動(dòng)態(tài)規(guī)劃算法求解問題的基本要素？動(dòng)態(tài)規(guī)劃算法

23、的基本步驟？答：1)基本思想：將待求解問題分解成若干個(gè)子問題；由于子問題有重疊，動(dòng)態(tài)規(guī)劃算法能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算.2）相同：都是將原問題分解成小問題，通過小問題求解得到原問題解。不同：?用分治法求解時(shí)，分解的子問題是互相獨(dú)立的，且與原問題類型一致。分治算法實(shí)現(xiàn)一般用遞歸；?動(dòng)態(tài)規(guī)劃方法經(jīng)分解得到的子問題往往不是互相獨(dú)立的；動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)一般用循環(huán)；3）基本要素：具有最優(yōu)子結(jié)構(gòu)；子問題具有重疊性4）步驟：1）分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。2） 遞推地定義最優(yōu)值。3） 以自底向上的方式計(jì)算出最優(yōu)值.4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息

24、，構(gòu)造問題的最優(yōu)解2、序列X=X1,X2,Xm和Y=Y1,Y2Yn的最長公共子序列為Z=Z1,Z2,Zk用動(dòng)態(tài)規(guī)劃的方法求序列X和Y的最長公共子序列長度？（要求按照動(dòng)態(tài)規(guī)劃寫出動(dòng)態(tài)規(guī)劃求解問題的步驟分析最優(yōu)子結(jié)構(gòu)寫出遞歸方程算法描述）注：Cmn記錄序列X與Y的最長公共子序列的長度答：最優(yōu)子結(jié)構(gòu)設(shè)序列X=X1,X2,-Xm與序列Y=yi,y2,yn的一個(gè)最長公共子序列Z=zi,Z2,zkI、若xm=yn,則zk=xm=yn,且zi,Z2,zk-i是序列Xm-i與序列Yn-1的最長公共自序列；n、若XmWyn,且XmWZk,則Z是Xm-1與Y的最長公共子序列；出、若XmWyn,且ynWZk,則Z是

25、X與Yn-1的最長公共子序列；由此可見，2個(gè)序列的最長公共子序列包含了這2個(gè)序列的前綴（去掉一個(gè)元素）的最長公共子序列。即，原問題最優(yōu)解，包含子問題最優(yōu)解；因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。寫出遞歸方程/ = 0,/ = 00中5“印-川max印U-1,中I。X.循環(huán)實(shí)現(xiàn),計(jì)算最優(yōu)值Cij,算法描述IntlcsLength(x,y,b)intm=x.length-1;n=y.length-1;for(inti=1;i<m;i+)Ci0=0;/y序列空for(inti=1;i<n;i+)C0i=0;/x序列空for(inti=1;i<=m;i+)/x序列長為m/ y序

26、列長為nO(m*n)for(intj=1;j<=n;j+)if(xi=yj)Cij=Ci-1j-1+1；b皿=1；elseif(ci-1j>=cij-1)Cij=Ci-1j；bij=2；elseCij=Cij-1；bij=3；returnCmn;時(shí)間復(fù)雜度分析：該算法時(shí)間復(fù)雜度:構(gòu)造最長公共子序列，算法描述：voidLCS(charXi,Yj,intb)if(i=0|j=0)return;if(bij=1)LCS(Xi-1,Yj-1,b);system.out.print(xi);elseif(bij=2)LCS(Xi-1,Yj,b);elseif(bij=3)LCS兇i,Yj-1

27、,b);時(shí)間復(fù)雜度分析：此算法每一次遞歸調(diào)用使得i或j減1,因此該算法時(shí)間復(fù)雜度為O(m+n)3、長江游艇俱樂部在長江上設(shè)置了n個(gè)游艇出租站1,2n.游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r（i,j）,其中1<=i<j<=n;試設(shè)計(jì)一個(gè)算法，計(jì)算出游艇從出租站1到出租站n所需最少租金？（見習(xí)題集第三章算法設(shè)計(jì)與計(jì)算題T2）4、掌握動(dòng)態(tài)規(guī)劃方法求解0-1背包問題？答：分析問題的最優(yōu)解結(jié)構(gòu)設(shè)（y1,y2,?。┧o01背包容量為M的解；則，（y2,丫n）相應(yīng)子問題背包容量為M-w的解；（即原問題最優(yōu)解，包含了子問

28、題最優(yōu)解）遞歸定義最優(yōu)值/）=</<nmaxm（z+1J）,m（i+1J-v（j>wtroo，/<w1V/WI村ft計(jì)算最優(yōu)值m(i,j)voidknapsack(intv,intw,intM,intm)intn=v.length;if(M<wn)/i=n時(shí)，只有1個(gè)物品mnM=0;elseif(M>=wn)mnM=vn;M=M-wn;for(inti=n-1;i>=1;i-)/i<n時(shí)，Xixn多個(gè)物品if(M<wi)miM=mi+1M;elseif(M>=wn)miM=math.max(mi+1M,mi+1M-wi+vi);M=M

29、-wi;該算法時(shí)間復(fù)雜度：O(c*n)c常數(shù)構(gòu)造最優(yōu)解voidtrackack(intm,intw,intM,intx)/xi標(biāo)記i是否放入背包intn=w.length;for(inti=1;i<n;i+)/判斷前n-1個(gè)物體是否放入背包if(miM=mi+1M)xi=0;elsexi=1;M=M-wi;xn=(mnM>0)?1:0;/判斷第n個(gè)物體是否放入背包該算法時(shí)間復(fù)雜度：O(n)第4章貪心算法1、貪心算法基本思想？答：從問題的初始解出發(fā)逐步逼近給定的目標(biāo),每一步都做出當(dāng)前看來是最優(yōu)的選擇（貪心選擇），最終得到整個(gè)問題的最優(yōu)解2、貪心算法的基本要素？答：貪心選擇性；最優(yōu)子結(jié)

30、構(gòu)3、貪心算法與動(dòng)態(tài)規(guī)劃算法的異同？答：1）相同點(diǎn)：對于要求解的問題都具有最優(yōu)子結(jié)構(gòu)；2）不同點(diǎn)：算法的基本思想不同；求解問題的類型不同；例：普通背包問題貪心算法求解0-1背包問題動(dòng)態(tài)規(guī)劃算法求解4、設(shè)計(jì)普通背包裝載問題的貪心算法？并分析其時(shí)間復(fù)雜度?答:floatgreedy_knapsack(floatM,floatw,floatp,floatx)/M背包載重x背包問題最優(yōu)解，w物品重量，P物品價(jià)值 int n=w.length;nfloat pp=0;ppfloat mm = M;/mmfor( int i=1;i<=n; i+ ) float ww i= p i / w i；x

31、i=0; /Mergesort (w i , ww i , n ); / for( int i=1; i<=n; i+ )/ if ( w i<=mm )/物品的個(gè)數(shù)計(jì)算當(dāng)前背包總價(jià)值背包剩余載重/計(jì)算物品單位價(jià)值 ww初始化，所有物品沒有放入背包按單位價(jià)值將物品排序，便于貪心選擇貪心選擇，總是選擇價(jià)值最大放入背包 當(dāng)前物品小于背包剩余載重整個(gè)放入背包部分放入背包(合并排序時(shí)間) B j初始化排序；for( j=1, j<=6;j+) S j=0；/A=GZ/B j;/AS j=A;S jGZ=GZ-A*B j; /每求出一種面額所需的張數(shù)后, for(i=1;i<=6

32、;i+)print( B i," -xi=1;mm=mm-wi;pp=pp+pi;/elsexi=mm/wi;pp=pp+xi*pi;break;/ireturnpp;該算法主要包括以下幾部分：?計(jì)算物品單位價(jià)值時(shí)間，其時(shí)間復(fù)雜度O(n);?按照物品單位價(jià)值排序時(shí)間，其時(shí)間復(fù)雜度為O(n*logn);?貪心選擇時(shí)間，其時(shí)間復(fù)雜度為O(n);故該算法的時(shí)間復(fù)雜度為：O(n*logn+2n);記為：O(n*logn)5、設(shè)計(jì)找零問題的貪心算法？并分析其時(shí)間復(fù)雜度？答：voidgreedy_zhaoling(floatGZ,intB,intS)/GZ應(yīng)發(fā)工資/為了貪心選擇，依次選最大幣種初

33、始化Sj表不對應(yīng)j幣種張數(shù)存放對應(yīng)j幣種總張數(shù)一定要把這部分金額減去："，Si);/輸出幣種和對應(yīng)張數(shù)6、設(shè)計(jì)活動(dòng)安排問題的貪心算法？并分析其時(shí)間復(fù)雜度？答：偽代碼：Intgreedyselector(ints,intf,booleana)intn=s.length;/n活動(dòng)的個(gè)數(shù)；a按活動(dòng)結(jié)束時(shí)間遞增排序；便于貪心選擇a1=true;/活動(dòng)1被選中intj=1；/j記錄最近加入活動(dòng)集合A的活動(dòng)jintcount=1;/count存儲(chǔ)相容活動(dòng)個(gè)數(shù)for(inti=2;i<=n;i+)貪心選擇從活動(dòng)j=2-n判是否可加入Aif(活動(dòng)i的開始時(shí)間，大于最近活動(dòng)j的結(jié)束時(shí)間)將活動(dòng)i

34、加入活動(dòng)集合A;j=i;/活動(dòng)i作為最近加入活動(dòng)集合A的最近活動(dòng)count+;else活動(dòng)i不加入活動(dòng)集合A;returncount;程序設(shè)計(jì)語言：Intgreedyselector(ints,intf,booleana) int n=s.length; nMergesort (a ,f , n ); /a1=true; /int j=1;/int count=1; /countfor(int i=2; i<=n; i+) / if( s i>=f j) a i=true; /j=i; /活動(dòng)的個(gè)數(shù)按活動(dòng)結(jié)束時(shí)間排序，便于貪心選擇活動(dòng)1被選中j記錄最近依次加入活動(dòng)集合A的活動(dòng)j存儲(chǔ)

35、相容活動(dòng)個(gè)數(shù)貪心選擇從活動(dòng)i=2n判是否可加入A將活動(dòng)i加入活動(dòng)集合A活動(dòng)i作為最近加入活動(dòng)集合A的最近活動(dòng)else a i=false; / s i<f j,活動(dòng)i不加入活動(dòng)集合Acount+;returncount;該算法主要包括2部分：?按照按活動(dòng)結(jié)束時(shí)間對活動(dòng)排序時(shí)間，其時(shí)間復(fù)雜度為：O(n*logn);?貪心選擇時(shí)間，其需要經(jīng)過n-1次的比較(si>=fj)時(shí)間復(fù)雜度為：O(n-1);故本算法的時(shí)間復(fù)雜度：O(n*logn+n-1);記為：O(n*logn)。7、掌握例dijkstra算法的求單源最短路徑問題。算法設(shè)計(jì)？求解過程?答：voiddijkstra(intv,f

36、loata叩,floatdist口)/v表示源,aij表示邊i到j(luò)的權(quán)值/disti記錄源到頂點(diǎn)i的最短路徑長度/previ記錄頂點(diǎn)i的前一個(gè)點(diǎn)，可以找出最短路徑intn=dist.length;booleans;/si標(biāo)記頂點(diǎn)i是否加入頂點(diǎn)集合sif(v<1|v>n)return;/源點(diǎn)v不存在for(inti=1;i<=n;i+)disti尸avi; / si=false;if(disti=max-value) / previ=0;else previ=v; distv=0; sv=true; /初始化數(shù)組disti 、si源到頂點(diǎn)i沒有邊把源v加入到集合s中for(in

37、t i=1; i<n; i+)/剩下n-1個(gè)頂點(diǎn)，每次選擇一個(gè)加入s中floattemp=max-value;intu=v;for(intj=1;j<=n;j+)/貪心選擇，計(jì)算V-S中頂點(diǎn)的dist值，選擇最小白那個(gè)頂點(diǎn)jif(!sj)&&(distj<temp)u=j;temp=distj;su=true;/源到頂點(diǎn)u的最短路徑已經(jīng)確定，u加入到s中for(intj=2;j<=n;j+)/根據(jù)u重新計(jì)算distif(!sj)&&(auj<max-value)u到j(luò)有邊f(xié)loatnewdist=distu+auj;if(newdi

38、st<distj)distj=newdist;prevj=u;該算法主體有兩重循環(huán)，故該算法的時(shí)間復(fù)雜度記為O(n2)8、P126圖4 8求最小生成樹，寫出其 prim算法？并給出其選邊過程？答：prim算法描述(偽代碼)voidprim(intn,floatc口口)可口存儲(chǔ)邊權(quán)值T=空集；/T表示最小生成樹的邊集合S=1;/S表示最小生成樹包含的頂點(diǎn)集合while(S!=V)選擇邊(i,j),iCS且jCV-S;且權(quán)值c皿最小;/貪心選擇T=TU(i,j);S=SUj;prim算法描述(程序設(shè)計(jì)語言)Voidprim(intn,floatc口口)floatlowcost;floatcl

39、osest;booleans;s1=true;/初始化，頂點(diǎn)1加入生成樹集合sfor(inti=2;i<=n;i+)初始化，計(jì)算與頂點(diǎn)1相鄰頂點(diǎn)邊權(quán)值lowcosti=c1i;colsesti=1;si=false;for(inti=1;i<n;i+)/剩下n-1個(gè)頂點(diǎn)，每次選擇一個(gè)加入s中floatmin=float.max-value;intj=1;for(intk=2;k<=n;k+)/貪心選擇，v-s中找使lowcost最小的頂點(diǎn)kif(lowcostk<min)&&(!sk)min=lowcostk;j=k;sj=true;/把找到的頂點(diǎn)j加入

40、到生成樹集合s中for(intk=2;k<=n;k+)/根據(jù)剛加入的頂點(diǎn)修改lowcost,closestif(cjk<lowcosestk)&&(!sk)lowcostk=c皿k;closest止j;該算法主體有兩重循環(huán)，故該算法的時(shí)間復(fù)雜度記為O(n2)Prim算法執(zhí)行過程：首先，找出V-S中使lowcost值最小白頂點(diǎn)j(距離s最近的頂點(diǎn)j);然后，根據(jù)數(shù)組closest選取邊(j,closestj);最后，將j添加到S中，并對closest和lowcost作必要的修改。選邊過程：9、P126圖48,利用kruskal算法求最小生成樹，給出其選邊過程?答：偽代

41、碼：voidkrustral(intn,floatcc叩存儲(chǔ)邊權(quán)值mergesort(floatc口,T口);/按邊權(quán)值排序T=空集；/T表示最小生成樹的邊集合while(|T|<n-1)/n個(gè)頂點(diǎn)有n-1個(gè)邊選擇最小權(quán)值邊(i,j);/貪心選擇if(i6T1&&jCT2)/邊(i,j)一端i在T1分支，一端j在T2分支union(i,j)；T=TU(i,j)elseT=TU(i,j);選邊過程:第5章回溯算法1、回溯法基本思想？回溯法解題步驟？答：基本思想：在搜索嘗試中找問題的解，當(dāng)不滿足條件就“回溯"返回，嘗試別的路徑。解題步驟：（1）針對所給問題，定義問題

42、的解空間；（2） 并確定易于搜索的解空間結(jié)構(gòu)（排列樹，子集樹）；（3） 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)，剪去無效的枝，避免無效搜索。2、什么叫子集樹？什么叫排列樹？什么叫滿m叉樹？答：1）子集樹：當(dāng)所給問題是在n個(gè)元素的集合S中找出S滿足某種性質(zhì)的子集時(shí)，其相應(yīng)的解空間樹稱作子集樹。2）排列樹：當(dāng)所給問題是在確定的 n個(gè)元素滿足某種性質(zhì)的排列中搜索問題的解時(shí)，相應(yīng)的解空間樹被稱作排列樹。3）滿m叉樹：當(dāng)所給問題的n個(gè)元素中每一個(gè)元素均有 m種選擇，要求確定其中的一種選 擇，使得對這n個(gè)元素的選擇結(jié)果組成的向量滿足某種性質(zhì)，即尋找滿足某種特性的 n個(gè)元素取值的一種組合。這類問

43、題的解空間樹稱為滿m叉樹。3、利用回溯法，求解 01背包問題，要求設(shè)計(jì)出相應(yīng)算法？并分析其時(shí)間復(fù)雜度？答：算法描述（遞歸實(shí)現(xiàn)）double knaspack（double p , double w , double c）/c是背包載重/double cw=0;double cp=0;double bestp=0;backtrack； return bestp;double backtrack( int i) /double n=p.length;if ( i>n )/ i bestp=cp; return bestp; 當(dāng)前重量當(dāng)前價(jià)值當(dāng)前最優(yōu)裝載價(jià)值深度優(yōu)先搜索解空間搜索解空間函數(shù)表示

44、深度(層)，i>n搜索到葉子節(jié)點(diǎn)/否則，進(jìn)入左子樹向下深度搜索elseif(cw+wi<=c)/當(dāng)前物品放入背包不超載cw=cw+wi;cp=cp+pi;c=c-wi;backtrack(i+1);/繼續(xù)向下深度搜索else/超載，則回溯進(jìn)入右子樹if(bound(i+1)>bestp)/通過限界函數(shù)知道右子樹可能包含最優(yōu)解/即，當(dāng)前價(jià)值+剩余物品價(jià)值大于bestp,進(jìn)入右子樹backtrack(i+1);限界函數(shù)計(jì)算當(dāng)前價(jià)值與剩余價(jià)值和/剩余容量當(dāng)前物品價(jià)值doublebound(inti)/doublecleft=c-cw;doubleb=cp;/while(i<=

45、n&&wi<=cleft)/裝載剩下的物品cleft=cleft-wi;b=b+pi;i+;/wi>cleft跳出循環(huán)，背包裝滿，物品部分裝入背包if(i<=n)b+=pi/wi*cleft;returnb;/當(dāng)前物品價(jià)值與剩余物品價(jià)值之和算法分析：該算法計(jì)算上界函數(shù)bound時(shí)間復(fù)雜度為O(n);在最壞的情況下，有2n個(gè)右孩子節(jié)點(diǎn)需要計(jì)算上界；故該算法的時(shí)間復(fù)雜度為O(n*2n)4、利用回溯法，求解n后問題，要求設(shè)計(jì)出相應(yīng)算法，并分析其時(shí)間復(fù)雜度？答：算法描述(遞歸實(shí)現(xiàn))doublenqueen(intnn)intn=nn;intsum=0;/放置皇后的方案

46、數(shù)intxn;/xi表示皇后i放在棋盤的第i行，第xi列for(inti=0;i<=n;i+;)初始化深度優(yōu)先搜索解空間搜索到葉子節(jié)點(diǎn)，方案數(shù)+1, t是層數(shù)xi=0;/backtrack；/returnsum;voidbacktrack(intt)if(t>n)/sum+;elsefor(inti=1;i<=n;i+)/for循環(huán)一一判斷皇后所在列xt=i;/將第t個(gè)皇后放在t行(t不同)，i歹Uif(place(t)/約束函數(shù)，判斷是否有沖突backtrack(t+1);/放下一個(gè)皇后voidplace(intk)/約束函數(shù)for(intj=1;j<k;j+)k之前

47、的皇后k-1是否與k沖突if(math.abs(k-j尸math.abs(xk-xj)|(xk=xj)/k與之前白皇后1k-1不能在同一斜線或同一列returnfalse;elsereturntrue;算法分析：對于n皇后問題的解空間共有n!個(gè)葉子節(jié)點(diǎn)，故排列樹最多有n*n!個(gè)節(jié)點(diǎn)；最壞的情況下每個(gè)節(jié)點(diǎn)都要用place函數(shù)判斷是否可行，每一個(gè)節(jié)點(diǎn)判斷時(shí)間為O(n)；故該算法的時(shí)間復(fù)雜度記為O(n*n*n!)第六章分支限界算法1、分支限界算法的解題步驟？答：1)針對所給問題，定義問題的解空間；2)確定易于搜索的解空間結(jié)構(gòu)(排列樹，子集樹)；3)以廣度優(yōu)先方式搜索問題的解空間;4)在搜索過程中用限

48、界函數(shù)，剪去無效的枝，避免無效搜索。2、常用的兩種分支限界算法？并說明其思想？答：1)隊(duì)列式(FIFO先進(jìn)先出)分支限界算法將活動(dòng)結(jié)點(diǎn)表組織成一個(gè)隊(duì)列，并按照隊(duì)列先進(jìn)先出原則取下一個(gè)結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)基本思想：開始，根結(jié)點(diǎn)是唯一的活結(jié)點(diǎn)，根結(jié)點(diǎn)入隊(duì)列；從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有兒子(分支)，用約束條件檢查(限界)，把所有滿足約束函數(shù)的兒子結(jié)點(diǎn)加入活結(jié)點(diǎn)隊(duì)列中。再從活結(jié)點(diǎn)表中取出隊(duì)首結(jié)點(diǎn)（隊(duì)中最先進(jìn)來的結(jié)點(diǎn)）為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到找到一個(gè)解或活結(jié)點(diǎn)隊(duì)列為空為止。2）優(yōu)先隊(duì)列式分支限界算法將活結(jié)點(diǎn)表組織成一個(gè)優(yōu)先隊(duì)列（堆），并按照優(yōu)先隊(duì)列中規(guī)定

49、的結(jié)點(diǎn)優(yōu)先級(jí)，選取優(yōu)先級(jí)最高的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)?；舅枷耄焊Y(jié)點(diǎn)是唯一的活結(jié)點(diǎn)，根結(jié)點(diǎn)入堆；從活結(jié)點(diǎn)隊(duì)中取出根結(jié)點(diǎn)后，作為當(dāng)前擴(kuò)展結(jié)點(diǎn)。對當(dāng)前擴(kuò)展結(jié)點(diǎn)，先從左到右地產(chǎn)生它的所有兒子節(jié)點(diǎn)；用約束條件檢查（限界），把所有滿足約束函數(shù)的兒子結(jié)點(diǎn)加入活結(jié)點(diǎn)表中（堆），并給每個(gè)結(jié)點(diǎn)設(shè)置優(yōu)先級(jí)。再從活結(jié)點(diǎn)表（堆）中取出堆頂結(jié)點(diǎn)（堆中優(yōu)先級(jí)最高結(jié)點(diǎn)）為當(dāng)前擴(kuò)展結(jié)點(diǎn)，直到活結(jié)點(diǎn)表（堆）為空。3、分支限界算法與回溯法異同？答：相同點(diǎn)：都屬于搜索算法；都需要在問題的解空間中搜索問題的解；不同點(diǎn)：1）求解目標(biāo)不同：回溯法求解目標(biāo)是找出解空間樹中滿足約束條件所有解；分支限界法求解目標(biāo)則是找出滿足約束條件的一個(gè)解，

50、或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹；分支限界法則以廣度優(yōu)先的方式搜索解空間樹。4、利用優(yōu)先隊(duì)列分支限界算法，設(shè)計(jì)0-1背包問題算法?答：隊(duì)列式分支限界算法（無限界函數(shù)）doubleknaspack(doublep,doublew,doublec)doublecw=0;/當(dāng)前重量doublecp=0;/當(dāng)前價(jià)值doublebestp=0;/當(dāng)前最優(yōu)裝載價(jià)值backtrack(l);/分支限界法搜索解空間returnbestp;doublebacktrack(inti)while(true)/隊(duì)列不空/檢查左兒子結(jié)點(diǎn)if(ew+

51、wi<=c)enQueue（ew+wi,i）;/左兒子加入隊(duì)列/進(jìn)入右孩子，右兒子結(jié)點(diǎn)總是可行的，無上界函數(shù)enQueue（ew,i）;/右兒子加入隊(duì)列ew=（Integer）queue.remove（）.intValue（）;取隊(duì)首下一擴(kuò)展結(jié)點(diǎn)if（ew=-1）/同一層尾部標(biāo)記ew=-1:同一層結(jié)點(diǎn)處理結(jié)束if（queue.isEmpty（）returnbestw;判斷隊(duì)列是否為空elsequeue.put(newInteger(-I);/同層結(jié)點(diǎn)尾部標(biāo)志ew=(Integer)queue.remove().intValue();/取下一擴(kuò)展結(jié)點(diǎn)i+;/進(jìn)入下一層隊(duì)列式分支限界法(帶上

52、界函數(shù))doubleknaspack(doublep,doublew,doublec)doublecw=0;/當(dāng)前重量doublecp=0;/當(dāng)前價(jià)值doublebestp=0;/當(dāng)前最優(yōu)裝載價(jià)值backtrack(1);/分支限界法搜索解空間returnbestp;doublebacktrack(inti)while(true)/隊(duì)列不空/檢查左兒子結(jié)點(diǎn)if(ew+wi<=c)enQueue(ew+wi,i);/左兒子加入隊(duì)列/進(jìn)入右孩子，計(jì)算上界函數(shù)，檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)up=Bound(i+1);右子樹可能含最優(yōu)解右兒子結(jié)點(diǎn)加入隊(duì)列取隊(duì)首下一擴(kuò)展結(jié)點(diǎn)ew = -1 :同一層結(jié)點(diǎn)處理結(jié)束if