湖南大學(xué)深刻復(fù)習(xí)算法分析期末答案解析大題

.一、 解答題1.機(jī)器調(diào)度問題。問題描述：現(xiàn)在有n件任務(wù)和無限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時(shí)間為si，完成時(shí)間為fi，si<fi。[si，fi]為處理任務(wù)精品文檔放心下載i的時(shí)間范圍。兩個(gè)任務(wù)i，j重疊指兩個(gè)任務(wù)的時(shí)間范圍區(qū)間有重疊，而并非指i，j的起點(diǎn)或終點(diǎn)重合。例如：區(qū)間[1，4]與區(qū)間[2，4]重疊，而與[4，7]不重疊。一個(gè)可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù)分配給同一臺(tái)機(jī)器。因此，在可行的分配中每臺(tái)機(jī)器在任何時(shí)刻最多只處理一個(gè)任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。感謝閱讀問題實(shí)例：若任務(wù)占用的時(shí)間范圍是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，則按時(shí)完成所有任務(wù)最少需要幾臺(tái)機(jī)器？（提示：使用貪心算法）謝謝閱讀畫出工作在對應(yīng)的機(jī)器上的分配情況。3.單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖（如下圖所示）G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。感謝閱讀解法：現(xiàn)采用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑。請將此過程填入下表中。謝謝閱讀.迭代

S

u

dist[2]

dist[3]

dist[4]

dist[5]初始

{1}

-

10 maxint

30

1001237.最長公共子序列問題：給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找感謝閱讀4X和Y的最長公共子序列。由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。謝謝閱讀c[i][j]記錄序列Xi和Yj的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；謝謝閱讀Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長公共子序列。故此時(shí)C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：感謝閱讀0i0,j0c[i1][j1]1i,j0;xyc[i][j]max{c[i][j1],c[i1][j]}iji,j0;xyij在程序中，b[i][j]記錄C[i][j]的值是由哪一個(gè)子問題的解得到的。精品文檔放心下載三、算法理解1、寫出多段圖最短路經(jīng)動(dòng)態(tài)規(guī)劃算法求解下列實(shí)例的過程，并求出最優(yōu)值。謝謝閱讀.2 51 3 6 84 7各邊的代價(jià)如下：C(1,2)=3，C(1,3)=5，C(1,4)=2精品文檔放心下載C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1感謝閱讀C(5,8)=4，C(6,8)=5，C(7,8)=6謝謝閱讀解：Cost(4,8)=0Cost(3,7)=C(7,8)+0=6，D[5]=8謝謝閱讀Cost(3,6)=C(6，8)+0=5,D[6]=8謝謝閱讀Cost(3,5)=C(5，8)+0=4 D[7]=8精品文檔放心下載Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}精品文檔放心下載=min{1+5,2+4}=6 D[4]=6Cost(2,3)=min{C(3，6)+Cost(3,6)}謝謝閱讀=min{4+5}=9 D[3]=5Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}感謝閱讀.=min{8+5,4+6}=10 D[2]=7Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}謝謝閱讀=min{3+10,5+9,2+6}=8D[1]=41→4→6→82、寫出maxmin算法對下列實(shí)例中找最大數(shù)和最小數(shù)的過程。精品文檔放心下載數(shù)組A=(48,12,61,3,5,19,32,7)謝謝閱讀解：寫出maxmin算法對下列實(shí)例中找最大數(shù)和最小數(shù)的過程。感謝閱讀數(shù)組A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48～61,12～319～32，5～74、61～323～55、6131、快速排序算法對下列實(shí)例排序，算法執(zhí)行過程中，寫出數(shù)組A第一次被分割的過程。謝謝閱讀A=(65,70,75,80,85,55,50,2)精品文檔放心下載解：第一個(gè)分割元素為65(1)(2)(3)(4)(5)(6)(7)(8)ip65707580855550228652758085555070376525080855575704665250558580757046557075808565502.2、歸并排序算法對下列實(shí)例排序，寫出算法執(zhí)行過程。精品文檔放心下載A=(48,12,61,3,5,19,32,7)解：48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323,12,48,615,7,19，323,5,7,12，19，32，48,613、寫出圖著色問題的回溯算法的判斷X[k]是否合理的過程。精品文檔放心下載解：i←0whilei<kdoifG[k,i]=1andX[k]=X[i]then謝謝閱讀returnfalsei←i+1repeatifi=kthenreturntrue.4、對于下圖，寫出圖著色算法得出一種著色方案的過程。精品文檔放心下載2314解：K←1X[1]←1,返回trueX[2]←1,返回false;X[2]←X[2]+1=2,返回true感謝閱讀X[3]←1,返回false;X[3]←X[3]+1=2,返回false;X[3]←X[3]+1=3,返回true感謝閱讀X[4]←1,返回false;X[4]←X[4]+1=2,返回false;X[4]←X[4]+1=3,返回true精品文檔放心下載找到一個(gè)解（1，2，3，3）5、寫出第7題的狀態(tài)空間樹。解：X[1]=1.X[2]=2X[3]=3X[4]=38、寫出歸并排序算法對下列實(shí)例排序的過程。(6,2,9,3,5,1,8,7)解：調(diào)用第一層次6,2,9,35,1,8,7分成兩個(gè)子問題調(diào)用第二層次6,29,35,18,7分成四個(gè)子問題調(diào)用第三層次62935187分成八個(gè)子問題調(diào)用第四層次只有一個(gè)元素返回上一層第三層歸并2,63,91,57,8返回上一層第二層歸并2,3,6,91,5,7,8返回上一層第一層歸并1,2,3,5,6,7,8,9排序結(jié)束，返回主函數(shù)9、寫出用背包問題貪心算法解決下列實(shí)例的過程。P=(18,12,4,1)W=(12,10,8,3).M=25解:實(shí)例符合P(i)/W(i)≥P(i+1)/W(i+1)的順序。謝謝閱讀CU←25,X←0W[1]<CU: x[1]←1;CU←CU-W[1]=13;精品文檔放心下載W[2]<CU: x[2]←1;CU←CU-W[2]=3;謝謝閱讀W[3]>CU: x[3]←CU/W[3]=3/8;感謝閱讀實(shí)例的解為：（1，1，3/8，0）11、有一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)精品文檔放心下載使用二分查找值為82的結(jié)點(diǎn)時(shí)，經(jīng)過多少次比較后查找成功并給出過程。精品文檔放心下載解：有一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)使用謝謝閱讀二分查找值為82的結(jié)點(diǎn)時(shí)，經(jīng)過多少次比較后查找成功并給出過程。感謝閱讀一共要要執(zhí)行四次才能找到值為82的數(shù)。12、使用prim算法構(gòu)造出如下圖G的一棵最小生成樹。感謝閱讀.12 435

6dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;謝謝閱讀dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6感謝閱讀解：使用普里姆算法構(gòu)造出如下圖G的一棵最小生成樹。感謝閱讀12 435

6dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;精品文檔放心下載dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6感謝閱讀.1 1 14333661124243365613、有如下函數(shù)說明int f(intx,inty){f=xMody+1;}已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c))后，k的值是多少并寫出詳細(xì)過程。感謝閱讀解：有如下函數(shù)說明int f(intx,inty){f=xMody+1;}已知a=10,b=4,c=5則執(zhí)行k=f(f(a+c,b),f(b,c))后，k的值是多少并寫出詳細(xì)過程。精品文檔放心下載.}K的值是5四、設(shè)計(jì)算法設(shè)有n項(xiàng)獨(dú)立的作業(yè){1,2,…,n},由m臺(tái)相同的機(jī)器加工處理。作業(yè)i所需要的處理時(shí)間為ti。約定：任何一項(xiàng)作業(yè)可在任何一臺(tái)機(jī)器上處理，但未完工前不準(zhǔn)中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。謝謝閱讀多機(jī)調(diào)度問題要求給出一種調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)感謝閱讀機(jī)器處理完。設(shè)計(jì)算法，并討論是否可獲最優(yōu)解。解：對于處理機(jī)j，用S[j]表示處理機(jī)j已有的作業(yè)數(shù)，用P[j,k]表示處理機(jī)j的第k感謝閱讀個(gè)作業(yè)的序號(hào)。1）將作業(yè)按照t[1]≥t[2]≥……≥t[n]排序精品文檔放心下載2）S[1:m]清零j←0 //從第一個(gè)處理機(jī)開始安排謝謝閱讀3)fori←1tondo //安排n個(gè)作業(yè)精品文檔放心下載j←jmodm+1 //選下一個(gè)處理機(jī)S[j]←S[j]+1;P[j,S[j]]←i；Repeat設(shè)有n種面值為:d1≥d2≥……≥dn的錢幣，需要找零錢M，如何選擇錢幣dk，的數(shù)目Xk，滿足謝謝閱讀.d1×Xi＋……dn×XnM，使得Xi＋……Xn最小請選擇貪心策略，并設(shè)計(jì)貪心算法。解：貪心原則：每次選擇最大面值硬幣。CU←M;i←1;X←0 //X為解向量WhileCU≠0doX[i]←CUdivd[i] //X[i]為第i中硬幣數(shù)精品文檔放心下載CU←CU-d[i]*X[i]i←i+1;repeat有n個(gè)物品，已知n=7,利潤為P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容積M=15,物品只能選擇全部裝入背包或不裝入背包，設(shè)計(jì)貪心算法，并討論是否可獲最優(yōu)解。精品文檔放心下載解：定義結(jié)構(gòu)體數(shù)組G，將物品編號(hào)、利潤、重量作為一個(gè)結(jié)構(gòu)體：例如G[k]={1,10,2}謝謝閱讀求最優(yōu)解，按利潤/重量的遞減序，有{5,6,1,6}{1,10,2,5}{6,18,4,9/2}{3,15,5,3}{7,3,1,3}{2,5,3,5/3} {4,7,7,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件物品的效益值感謝閱讀和重量。M是背包的容量大小，而x(1：n)是解向量//感謝閱讀.realP(1：n)，W(1：n)，X(1：n)，M，cu；謝謝閱讀integeri，n；X←0 //將解向量初始化為零//cu←M //cu是背包剩余容量//fori←1tondoif W(i)>cu then exit endif精品文檔放心下載X(i)←1cu←cu-W(i)repeatendGREEDY-KNAPSACK根據(jù)算法得出的解：X=（1,1,1,1,1,0,0）獲利潤52，而解感謝閱讀（1,1,1,1,0,1,0）可獲利潤54因此貪心法不一定獲得最優(yōu)解。1、對于下列各組函數(shù) f(n)和g(n)，確定 f(n)=O(g(n))或f(n)(g(n))或感謝閱讀(n)(g(n))，并簡述理由。（12分）精品文檔放心下載f(n)logn2;g(n)logn5;感謝閱讀f(n)2n;g(n)100n2;感謝閱讀f(n)2n;g(n)3n;解：簡答如下：（1）logn2(logn5)，（2）2n(100n2)，（3）2n(3n)謝謝閱讀.《算法設(shè)計(jì)與分析》考試試卷一、排序和查找是經(jīng)常遇到的問題。按照要求完成以下各題：（20分）（1）對數(shù)組A={15，29，135，18，32，1，27，25，5}，用快速排序方法將其排成遞減序。（2）請描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法。（3）給出上述算法的遞歸算法。（4）使用上述算法對（1）所得到的結(jié)果搜索如下元素，并給出搜索過程：18，31，135。答案：（1）第一步：15291351832127255第二步：29135183227251515【1分】第三步：13532291827251551【1分】第四步：13532292725181551【1分】n進(jìn)行比較，如果vAn，（2）基本思想：首先將待搜索元素v與數(shù)組的中間元素A22則在前半部分元素中搜索v；若vAn，則搜索成功；否則在后半部分?jǐn)?shù)組中搜索v。2謝謝閱讀【2分】非遞歸算法：輸入：遞減數(shù)組A[left:right]，待搜索元素v。【1分】謝謝閱讀輸出：v在A中的位置pos，或者不在A中的消息（-1）?！?分】感謝閱讀步驟：【3分】intBinarySearch(intA[],intleft,intright,intv)精品文檔放心下載.{intmid;while(left<=right){mid=int((left+right)/2);if(v==A[mid])returnmid;感謝閱讀elseif(v>A[mid])right=mid-1;精品文檔放心下載elseleft=mid+1;}return-1;}（3）遞歸算法：輸入：遞減數(shù)組A[left:right]，待搜索元素v?！?分】謝謝閱讀輸出：v在A中的位置pos，或者不在A中的消息（-1）?！?分】精品文檔放心下載步驟：【3分】intBinarySearch(intA[],intleft,intright,intv)感謝閱讀{intmid;if(left<=right){mid=int((left+right)/2);if(v==A[mid])returnmid;感謝閱讀.elseif(v>A[mid])returnBinarySearch(A,left,mid-1,v);感謝閱讀elsereturnBinarySearch(A,mid+1,right,v);感謝閱讀}elsereturn-1;}（4）搜索18：首先與27比較，18<27，在后半部分搜索；再次與18比較，搜索到，返謝謝閱讀回5。【1分】搜索31：首先與27比較，31>27，在前半部分搜索；再次32比較，31<32，在后謝謝閱讀半部分搜索，與29比較，31>29，此時(shí)只有一個(gè)元素，未找到，返回-1。【2分】感謝閱讀搜索135：首先與27比較，135>27，在前半部分搜索；再次32比較，135>32，謝謝閱讀在前半部分搜索；與135比較，相同，返回0?！?分】感謝閱讀二、 對于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。（20分）。感謝閱讀be2g122ad233218cf2h答案：用V1表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與V1中某個(gè)頂點(diǎn)相鄰接且不在V1中的感謝閱讀頂點(diǎn)；E1表示加入到最短路徑中的邊，E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑。【1精品文檔放心下載分】步驟 V1 V2 E1 E2.1.{a}{}{ab}2.{a,b}2donvi8{ab}{bd}3.{a,b,d}{c,f}{ab,bd}{dc,df}4.{a,b,d,c}{f}{ab,bd}{df}5.{a,b,c,d,f}{e}{ab,bd,dc,df}{fe}6.{a,b,c,d,e,f}{g}{ab,bd,dc,df,fe}{eg}7.{a,b,c,d,e,f,g}{h}{ab,bd,dc,df,fe,eg}{gh}8.{a,b,c,d,e,f,g,h}{}{ab,bd,de,df,fe,eg,gh}{}【以上每步2分】結(jié)果：從a到h的最短路徑為abdfegh，權(quán)值為18?！?分】謝謝閱讀三、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹（20分）。物品ABCDEFG3365412重量50000051435343價(jià)值0000500答案：求所有頂點(diǎn)對之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點(diǎn)從a循環(huán)謝謝閱讀到h，每次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對之間的最短路徑。謝謝閱讀【2分】三、按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA。將它們的序號(hào)分別記為1～精品文檔放心下載7。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過如下方式求得：【排感謝閱讀.序1分】x11ax0aj11213

a

x 02ix1ax03x0a4dex0x1x0454behx 1x05x0eg65c0x06f7Q1【狀態(tài)空間搜索樹及其計(jì)算過程17分，每個(gè)節(jié)點(diǎn)1分】a．4040305035150115190.625(1,1,1,1,7,0,0)4084040305030150115177.5(1,1,1,1,0,7,0)精品文檔放心下載6012c．4040305010170(1,1,1,1,0,0,1)d.4040303530150105167.5360(1,1,1,0,1,4,0)e.4040503530150130175160(1,1,0,1,1,3,0)f.4040503510150130170.714)35(1,1,0,1,1,0,7g.40405030160(1,1,0,1,0,1,0)h.4040353010150140146.85235(1,1,0,0,1,1,7)4030503530150125167.5(1,0,1,1,1,5,0)謝謝閱讀6012j.1501451403050353060157.5(0,1,1,1,1,12,0)在Q處獲得該問題的最優(yōu)解為(1,1,1,1,0,0,1)，背包效益為170。即在背包中裝入物品F、1B、G、D、A時(shí)達(dá)到最大效益，為170，重量為150。【結(jié)論2分】四、已知A(a(k))，k=1，2，3，4，5，6，r=5，r=10，r=3，r=12，r=5，kijri*ri112345.r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序。（要求：給出計(jì)算步驟）謝謝閱讀（20分）答案：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：【每個(gè)矩陣18分】12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘積序列為（A1A2）（（A3A4）（A5A6）），共執(zhí)行乘法2010次。【結(jié)論2分】謝謝閱讀五、算法理解題（本題5分）設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行循環(huán)賽，現(xiàn)設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：感謝閱讀①每個(gè)選手必須與其他n-1名選手比賽各一次；②每個(gè)選手一天至多只能賽一次；③循環(huán)賽要在最短時(shí)間內(nèi)完成。.（1）如果n=2k，循環(huán)賽最少需要進(jìn)行幾天；（2）當(dāng)n=23=8時(shí)，請畫出循環(huán)賽日程表。六、算法設(shè)計(jì)題（本題15分）分別用貪心算法、動(dòng)態(tài)規(guī)劃法、回溯法設(shè)計(jì)0-1背包問題。要求：說明所使用的算法精品文檔放心下載策略；寫出算法實(shí)現(xiàn)的主要步驟；分析算法的時(shí)間。七、算法設(shè)計(jì)題（本題10分）通過鍵盤輸入一個(gè)高精度的正整數(shù)n(n的有效位數(shù)≤240)，去掉其中任意s個(gè)數(shù)字后，精品文檔放心下載剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對給定的n和s，尋找一種方案，謝謝閱讀使得剩下的數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13五、（1）8天（2分）；（2）當(dāng)n=23=8時(shí)，循環(huán)賽日程表（3分）。謝謝閱讀

1234567821436587341278564321876556781234658721437856341287654321六、算法設(shè)計(jì)題（本題15分）（1）貪心算法O（nlog（n））首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品謝謝閱讀.總重量未超過C，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。依此策謝謝閱讀略一直地進(jìn)行下去，直到背包裝滿為止。（2）動(dòng)態(tài)規(guī)劃法 O(nc)m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時(shí)0-1背包問題的最優(yōu)值。由0-1感謝閱讀背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。精品文檔放心下載max{m(i1,j),m(i1,jw)v}jwm(i,j)iiim(i1,j)0jwivjwm(n,j)nn00jwn（3）回溯法O(2n)cw:當(dāng)前重量cp:當(dāng)前價(jià)值bestp：當(dāng)前最優(yōu)值voidbacktrack(inti)//回溯法i初值1{if(i>n)//到達(dá)葉結(jié)點(diǎn){bestp=cp; return; }if(cw+w[i]<=c)//搜索左子樹感謝閱讀{cw+=w[i];cp+=p[i];backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp).//搜索右子樹backtrack(i+1);}七、算法設(shè)計(jì)題（本題10分）為了盡可能地逼近目標(biāo)，我們選取的貪心策略為：每一步總是選擇一個(gè)使剩下的數(shù)最小精品文檔放心下載的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個(gè)數(shù)字，否則刪謝謝閱讀除第一個(gè)遞減區(qū)間的首字符。然后回到串首，按上述規(guī)則再刪除下一個(gè)數(shù)字。重復(fù)以上過程謝謝閱讀次，剩下的數(shù)字串便是問題的解了。具體算法如下：輸入s,n;while（s>0）{ i=1; //從串首開始找while(i<length(n))&&(n[i]<n[i+1])精品文檔放心下載{i++;}delete(n,i,1);//刪除字符串n的第i個(gè)字符精品文檔放心下載s--;}while(length(n)>1)&&(n[1]=‘0’)精品文檔放心下載delete(n,1,1);//刪去串首可能產(chǎn)生的無用零精品文檔放心下載輸出n;.二．計(jì)算題和簡答題（每小題7分，共21分）1．用O、、表示函數(shù)f與g之間階的關(guān)系，并分別指出下列函數(shù)中階最低感謝閱讀和最高的函數(shù)：f(n)=100f(n)=6n+nlognf(n)=n/logn-1f(n)=2nn2f(n)=log3n階的關(guān)系：f(n)=O(g(n))f(n)=(g(n))f(n)=(g(n))f(n)=O(g(n))f(n)=(g(n))階最低的函數(shù)是：100階最高的函數(shù)是：3n

g(n)=100ng(n)=3ng(n)=2 ng(n)=3ng(n)=logn2四．算法設(shè)計(jì)題（15分）1.一個(gè)旅行者要駕車從A地到B地，A、B兩地間距離為s。A、B兩地之間有n個(gè)加油站，已知第i個(gè)加油站離起點(diǎn)A的距離為d公里，感謝閱讀i0=ddds，車加滿油后可行駛m公里，出發(fā)之前汽車油箱為空。精品文檔放心下載1 2 n.應(yīng)如何加油使得從A地到B地沿途加油次數(shù)最少？給出用貪心法求解該最優(yōu)感謝閱讀化問題的貪心選擇策略，寫出求該最優(yōu)化問題的最優(yōu)值和最優(yōu)解的貪心算法，感謝閱讀并分析算法的時(shí)間復(fù)雜性。算法設(shè)計(jì)題：貪心選擇策略：從起點(diǎn)的加油站起每次加滿油后不加油行駛盡可能遠(yuǎn)，直至油箱中的油耗盡前所能到達(dá)的最遠(yuǎn)的油站為止，在該油站再加滿油。謝謝閱讀算法MINSTOPS輸入：A、B兩地間的距離s，A、B兩地間的加油站數(shù)n，車加滿油后可行駛的公里數(shù)謝謝閱讀m，存儲(chǔ)各加油站離起點(diǎn)A的距離的數(shù)組d[1..n]。感謝閱讀輸出：從A地到B地的最少加油次數(shù)k以及最優(yōu)解x[1..k]（x[i]表示第i次加油的加油站序號(hào)），若問題無解，則輸出nosolution。感謝閱讀d[n+1]=s;//設(shè)置虛擬加油站第n+1站。fori=1ton謝謝閱讀ifd[i+1]-d[i]>mthenoutput“nosolution”;return//無解，返回感謝閱讀endifendfork=1;x[k]=1 //在第1站加滿油。s1=m //s1為用汽車的當(dāng)前油量可行駛至的地點(diǎn)與A點(diǎn)的距離感謝閱讀i=2whiles1<sifd[i+1]>s1then //以汽車的當(dāng)前油量無法到達(dá)第i+1站。精品文檔放心下載.k=k+1;x[k]=i //在第i站加滿油。精品文檔放心下載s1=d[i]+m //刷新s1的值endifi=i+1endwhileoutputk,x[1..k]MINSTOPS最壞情況下的時(shí)間復(fù)雜性：Θ(n)二、簡答題：2.簡述回溯法解題的主要步驟?；厮莘ń忸}的主要步驟包括：1）針對所給問題，定義問題的解空間；2）確定易于搜索的解空間結(jié)構(gòu)；3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。謝謝閱讀3.簡述動(dòng)態(tài)規(guī)劃算法求解的基本要素。動(dòng)態(tài)規(guī)劃算法求解的基本要素包括：1）最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提；2）動(dòng)態(tài)規(guī)劃算法，對每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡單地用常數(shù)時(shí)間查看一下結(jié)果，即重疊子問題。感謝閱讀4.簡述回溯法的基本思想?；厮莘ǖ幕咀龇ㄊ撬阉鳎趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。謝謝閱讀5.簡要分析在遞歸算法中消除遞歸調(diào)用，將遞歸算法轉(zhuǎn)化為非遞歸算法的方法。精品文檔放心下載將遞歸算法轉(zhuǎn)化為非遞歸算法的方法主要有：1）采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。謝謝閱讀2）用遞推來實(shí)現(xiàn)遞歸函數(shù)。3）通過Cooper變換、反演變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。精品文檔放心下載后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。感謝閱讀.6.簡要分析分支限界法與回溯法的異同。1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。謝謝閱讀2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。感謝閱讀7.簡述算法復(fù)雜性的概念，算法復(fù)雜性度量主要指哪兩個(gè)方面？精品文檔放心下載算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。謝謝閱讀算法復(fù)雜性度量主要包括算法的時(shí)間復(fù)雜性和算法的空間復(fù)雜性。感謝閱讀8.貪心算法求解的問題主要具有哪些性質(zhì)？簡述之。貪心算法求解的問題一般具有二個(gè)重要的性質(zhì)：一是貪心選擇性質(zhì)，這是貪心算法可行的第一個(gè)基本要素；感謝閱讀另一個(gè)是最優(yōu)子結(jié)構(gòu)性質(zhì)，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。感謝閱讀9.分治法的基本思想是什么？合并排序的基本思想是什么？請分別簡述之。謝謝閱讀分治法的基本思想：將n個(gè)輸入分成k個(gè)不同子集合，得到k個(gè)不同的可獨(dú)立求解的子問題，其中1<k≤n，而且子問題與原問題性質(zhì)相同，原問題的解可由這些子問題的解合并得出。精品文檔放心下載合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。感謝閱讀10.簡述分析貪心算法與動(dòng)態(tài)規(guī)劃算法的異同。貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是兩類算法的一個(gè)共同點(diǎn)。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。感謝閱讀三、算法編寫及算法應(yīng)用分析題：1.已知有3個(gè)物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容積M=20，根據(jù)0-1背包動(dòng)態(tài)規(guī)劃的遞推式求出最優(yōu)解。謝謝閱讀解：根據(jù)遞推式fi（X）＝max{fi-1(X)，fi-l(X—wi)+pi |X≥wi}感謝閱讀從i=1開始，最后得到fn（M）f1(1)~f1(11)=0f1(12)~f1(20)=p1=15f2(1)~f2(9)=0.f2(10)~f2(11)=max{f1(10)，f1(10–w2)+p2}=13精品文檔放心下載f2(12)~f2(20)=max{f1(12)，f1(12–w2)+p2}=15感謝閱讀f3(20)=max{f2(20)，f2(20–w3)+p3}=f2(20–6)+10=25精品文檔放心下載可獲得的最大利潤為25，最優(yōu)解為：（1，0，1）2.按要求完成以下關(guān)于排序和查找的問題。（1） 對數(shù)組A={15，29，135，18，32，1，27，25，5}，用快速排序方法將其排精品文檔放心下載成遞減序。（2） 請描述遞減數(shù)組進(jìn)行二分搜索的基本思想，并給出非遞歸算法。精品文檔放心下載（3） 給出上述算法的遞歸算法。（4） 使用上述算法對（1）所得到的結(jié)果搜索如下元素，并給出搜索過程：18，31，感謝閱讀135。解：（1）第一步：15291351832127255精品文檔放心下載第二步：29135183227251515謝謝閱讀第三步：13532291827251551感謝閱讀第四步：13532292725181551精品文檔放心下載（2）基本思想：首先將待搜索元素v與數(shù)組的中間元素An進(jìn)行比較，如果vAn，22則在前半部分元素中搜索v；若vAn，則搜索成功；否則在后半部分?jǐn)?shù)組中搜索v。2感謝閱讀非遞歸算法：輸入：遞減數(shù)組A[left:right]，待搜索元素v。謝謝閱讀輸出：v在A中的位置pos，或者不在A中的消息（-1）。謝謝閱讀步驟：【3分】intBinarySearch(intA[],intleft,intright,intv)精品文檔放心下載.{intmid;while(left<=right){mid=int((left+right)/2);if(v==A[mid])returnmid;精品文檔放心下載elseif(v>A[mid])right=mid-1;感謝閱讀elseleft=mid+1;}return-1;}（3）遞歸算法：輸入：遞減數(shù)組A[left:right]，待搜索元素v。精品文檔放心下載輸出：v在A中的位置pos，或者不在A中的消息（-1）。感謝閱讀步驟：intBinarySearch(intA[],intleft,intright,intv)精品文檔放心下載{intmid;if(left<=right){mid=int((left+right)/2);if(v==A[mid])returnmid;謝謝閱讀.elseif(v>A[mid])returnBinarySearch(A,left,mid-1,v);精品文檔放心下載elsereturnBinarySearch(A,mid+1,right,v);謝謝閱讀}elsereturn-1;}（4）搜索18：首先與27比較，18<27，在后半部分搜索；再次與18比較，搜索到，返精品文檔放心下載5。搜索31：首先與27比較，31>27，在前半部分搜索；再次32比較，31<32，在后感謝閱讀半部分搜索，與29比較，31>29，此時(shí)只有一個(gè)元素，未找到，返回-1。精品文檔放心下載搜索135：首先與27比較，135>27，在前半部分搜索；再次32比較，135>32，感謝閱讀在前半部分搜索；與135比較，相同，返回0。3.已知A(a(k))r*r，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，kijii1r6=50，r7=6，求矩陣鏈積A1×A2×A3×A4×A5×A6的最佳求積順序（要求給出計(jì)算步驟）。精品文檔放心下載解：使用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：123456101503304051655201020360330243019503018093017704030001860501500.60123456101224220222230344404450560因此，最佳乘積序列為（A1A2）（（A3A4）（A5A6）），共執(zhí)行乘法2010次。謝謝閱讀根據(jù)分枝限界算法基本過程，求解0-1背包問題。已知，n=3，M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。謝謝閱讀解：用x(i)表示第i步選擇的物品號(hào)，x(1)=1，c(２)＝0，U(2)＝23;x(1)=2，c(3)＝15，U(3)＝25,x(1)=3，c(4)＝28，U(4)＝28,謝謝閱讀U=min{23,25,28}=23,由于c(4)＝28>U所以節(jié)點(diǎn)４刪除?；罟?jié)點(diǎn)表Ｌ={2,3}，取最小謝謝閱讀代價(jià)估值節(jié)點(diǎn)２作為擴(kuò)展節(jié)點(diǎn)：x(2)=2，w1+w2>M，節(jié)點(diǎn)5是不合理節(jié)點(diǎn)；感謝閱讀x(2)=3，這是答案節(jié)點(diǎn)c(6)=13，即找到了代價(jià)為13的解，修改U＝13，感謝閱讀由于活節(jié)點(diǎn)表中的節(jié)點(diǎn)3有c(3)＝25，所以節(jié)點(diǎn)3可以刪除。精品文檔放心下載.這時(shí)L＝｛ ｝，算法結(jié)束。最優(yōu)解X={1,3}搜索產(chǎn)生的狀態(tài)空間樹如下圖：X1=111X1=323X1=225284U=2302315X2=2X2=352313615013157節(jié)點(diǎn)6是答案節(jié)點(diǎn)5、試用貪心算法求解汽車加油問題：已知一輛汽車加滿油后可行駛n公里，而旅途中有若干個(gè)加油站。試設(shè)計(jì)一個(gè)有效算法，指出應(yīng)在哪些加油站?？考佑?，使加油次數(shù)最少，請寫出該算法。精品文檔放心下載解：intgreedy(vecter<int>x,intn)謝謝閱讀{int sum=0,k=x.size();for(intj=0;j<k;j++)if(x[j]>n){cout<<”Nosolution”<<endl;感謝閱讀.return-1;}for(inti=0,s=0;i<k;i++){s+=x[i];if(s>n){sum++;s=x[i];}}return sum;}6、試用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)下列問題：設(shè)A和B是兩個(gè)字符串。我們要用最少的字符操作，將字符串A轉(zhuǎn)換為字符串B，這里所說的字符操作包括：感謝閱讀(1)刪除一個(gè)字符。(2)插入一個(gè)字符。(3)將一個(gè)字符改為另一個(gè)字符。請寫出該算法。解：此題用動(dòng)態(tài)規(guī)劃算法求解：intdist(){intm=a.size();intn=b.size();vector<int>d(n+1,0);for(inti=1;i<=n;i++)d[i]=i;精品文檔放心下載for(i=1;i<=m;i++){inty=i-1;for(intj=1;j<=n;j++){.intx=y;y=d[j];intz=j>1?d[j-1]:i;intdel=a[i-1]==b[j-1]?0:1;謝謝閱讀d[j]=min(x+del,y+1,z+1);}}returnd[n];}7、對于下圖使用Dijkstra算法求由頂點(diǎn)a到頂點(diǎn)h的最短路徑。感謝閱讀be2g122ad233218cf2h解：用V1表示已經(jīng)找到最短路徑的頂點(diǎn)，V2表示與V1中某個(gè)頂點(diǎn)相鄰接且不在V1中的頂點(diǎn)；E1表示加入到最短路徑中的邊，E2為與V1中的頂點(diǎn)相鄰接且距離最短的路徑。感謝閱讀步驟V1V2E1E21.{a}{}{ab}2.{a,b}ihmts1g{ab}{bd}3.{a,b,d}{c,f}{ab,bd}{dc,df}4. {a,b,d,c} {f} {ab,bd} {df}謝謝閱讀.5.{a,b,c,d,f}{e}{ab,bd,dc,df}{fe}6.{a,b,c,d,e,f}{g}{ab,bd,dc,df,fe}{eg}7.{a,b,c,d,e,f,g}{h}{ab,bd,dc,df,fe,eg}{gh}8.{a,b,c,d,e,f,g,h}{}{ab,bd,de,df,fe,eg,gh}{}結(jié)果：從a到h的最短路徑為abdfegh，權(quán)值為18。謝謝閱讀求所有頂點(diǎn)對之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點(diǎn)從a循環(huán)到h，每精品文檔放心下載次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對之間的最短路徑。精品文檔放心下載8、試寫出用分治法對數(shù)組A[n]實(shí)現(xiàn)快速排序的算法。謝謝閱讀解：用分治法求解的算法代碼如下：int partition(floatA[],intp,intr)感謝閱讀{int i=p,j=r+1;float x=a[p];while(1){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;a[i]a[j];};a[p]=a[j];a[j]=x;return j;}.void Quicksort(float a[], int p,int r)精品文檔放心下載{if(p<r){int q=partition(a,p,r);Quicksort(a,p,q-1);Quicksort(a,q+1,r);}};Quicksort(a,0,n-1);9、有n個(gè)活動(dòng)爭用一個(gè)活動(dòng)室。已知活動(dòng)i占用的時(shí)間區(qū)域?yàn)閇si，fi]，活動(dòng)i,j相容的條感謝閱讀件是：sj≥fi，問題的解表示為(xi|xi=1，2…，n,)，xi表示順序?yàn)閕的活動(dòng)編號(hào)活動(dòng)，求一感謝閱讀個(gè)相容的活動(dòng)子集，且安排的活動(dòng)數(shù)目最多。解：解決這個(gè)問題的基本思路是在安排時(shí)應(yīng)該將結(jié)束時(shí)間早的活動(dòng)盡量往前安排，好給精品文檔放心下載后面的活動(dòng)安排留出更多的空間，從而達(dá)到安排最多活動(dòng)的目標(biāo)。據(jù)此，貪心準(zhǔn)則應(yīng)當(dāng)是：謝謝閱讀在未安排的活動(dòng)中挑選結(jié)束時(shí)間最早的活動(dòng)安排。在貪心算法中，將各項(xiàng)活動(dòng)的開始時(shí)間和感謝閱讀結(jié)束時(shí)間分別用兩個(gè)數(shù)組s和f存儲(chǔ)，并使得數(shù)組中元素的順序按結(jié)束時(shí)間非減排列：精品文檔放心下載f1f2…fn。算法如下：GreedyAction(s,f，n)//s[1:n]、f[1:n]分別代表n項(xiàng)活動(dòng)的起始謝謝閱讀//時(shí)間和結(jié)束時(shí)間,并且滿足f[1]f[2]…f[n]感謝閱讀j=1;solution={1};//解向量初始化為空集精品文檔放心下載fori←2tondoif sifj then.solution=solution{j}; //將j加入解中精品文檔放心下載j=i;endifendforreturn(solution);endGreedy10、設(shè)x1、x2、x3是一個(gè)三角形的三條邊，而且x1+x2+x3=14。請問有多少種不同的三角精品文檔放心下載形？給出解答過程。解：由于x1、x2、x3是三角形的三條邊，從而xi+xj>xk，|xi-xj|<xk，（i,j,k=1,2,3），謝謝閱讀根據(jù)x1+x2+x3=14可知1<xi<7（i=1,2,3）。利用回溯法求解得到：感謝閱讀x1=6 5×x2=65435××x3=2344????即有4個(gè)可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。感謝閱讀11、設(shè)數(shù)組A有n個(gè)元素，需要找出其中的最大最小值。謝謝閱讀（1） 請給出一個(gè)解決方法，并分析其復(fù)雜性。（2） 把n個(gè)元素等分為兩組A1和A2，分別求這兩組的最大值和最小值，然后分別謝謝閱讀將這兩組的最大值和最小值相比較，求出全部元素的最大值和最小值。如果A1感謝閱讀和A2中的元素多于兩個(gè)，則再用上述方法各分為兩個(gè)子集。直至子集中元素精品文檔放心下載至多兩個(gè)元素為止。這是什么方法的思想？請給出該方法的算法描述，并分析感謝閱讀.其復(fù)雜性。解：（1）基本思想：從頭到尾逐個(gè)掃描，紀(jì)錄最大和最小元素。謝謝閱讀輸入：具有n個(gè)元素的數(shù)組輸出：最大值和最小值步驟：voidFindMaxMin(intA[],intn,intmax,intmin)精品文檔放心下載{max=min=A[0];for(i=1;i<n;i++){if(A[i]>max)max=A[i];if(A[i]<min)min=A[i];}}復(fù)雜性分析：由于是從頭到尾掃描各個(gè)元素，而每個(gè)元素都要與max和min比較一遍，從謝謝閱讀而時(shí)間復(fù)雜性為：O(n)。（2）voidFindMaxMin(intleft,intright,intmax,intmin) {謝謝閱讀if(left==right)max=min=A[left];精品文檔放心下載elseif(left=right-1) {max=(A[left]<A[right]?A[right]:A[left]);謝謝閱讀min=(A[left]<A[right]?A[left]:A[right]);精品文檔放心下載}.else{mid=(left+right)/2;FindMaxMin(left,mid,gmax,gmin);感謝閱讀FindMaxMin(mid+1,right,hmax,hmin);精品文檔放心下載max=(gmax<hmax?hmax:gmax);感謝閱讀min=(gmin<hmin?gmin:hmin]);感謝閱讀}}12、有n個(gè)程序和長度為L的磁帶，程序i的長度為ai，已知naiL，求最優(yōu)解(xi，x2，...，謝謝閱讀i1xi，…，xn)，xi=0，1,xi=1，表示程序i存入磁帶，xi=0，表示程序i不存入磁帶，滿足nxaL，且存放的程序數(shù)目最多。精品文檔放心下載i i1解：由于目標(biāo)是存放的程序數(shù)目最多，所以最優(yōu)量度應(yīng)該是精品文檔放心下載min{ai|ai為程序i的長度}，即每次選入的程序都是當(dāng)前最短的。我們可以將n個(gè)程序按a[1]≤a[2]≤…≤a[n]順序排精品文檔放心下載序，然后從i=1開始依次選擇。算法如下：procedureprogramming(L,n,a,x)感謝閱讀begin//n個(gè)程序按a[1]≤a[2]≤…≤a[n]順序排序謝謝閱讀x←0;i=1;while(a[i]≤Land i≤n)do感謝閱讀.{x[i]←1;L←L-a[i]；i←i+1;精品文檔放心下載}end.18、假設(shè)有7個(gè)物品，它們的重量和價(jià)值如下表所示。若這些物品均不能被分割，且背包感謝閱讀容量M＝150，使用回溯方法求解此背包問題，請寫出狀態(tài)空間搜索樹。精品文檔放心下載物品ABCDEFG3365412重量50000051435343價(jià)值0000500解：按照單位效益從大到小依次排列這7個(gè)物品為：FBGDECA。將它們的序號(hào)分別記為1～精品文檔放心下載7。則可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個(gè)節(jié)點(diǎn)處的限界函數(shù)值通過如下方式求得：精品文檔放心下載x11ax0aj11213

a

x 02ix1ax03x0a4dex0x1x0454behx1x05x0eg65c0x06f7Q1a．4040305035150115190.625(1,1,1,1,7,0,0)4084040305030150115177.5(1,1,1,1,0,7,0)謝謝閱讀6012.c．4040305010170(1,1,1,1,0,0,1)d.4040303530150105167.5360(1,1,1,0,1,4,0)e.4040503530150130175160(1,1,0,1,1,3,0)f.4040503510150130170