算法復(fù)習(xí)材料1

1、文檔可能無法思考全面，請瀏覽后下載! 算法復(fù)習(xí)練習(xí)題一計(jì)算題與簡答題1. 用表示函數(shù)f與g之間的關(guān)系。(1) f(n)=10000n g(n)=n-10000(2) f(n)=2n g(n)=3n/n(3) f(n)=n3log2n g(n)=n2log3n(4) f(n)=log2n g(n)=log3n(5) f(n)=100n+n100 g(n)=n!2.估計(jì)下列算法的時(shí)間復(fù)雜性的階。(1)算法A的時(shí)間復(fù)雜性為，(2)算法B的時(shí)間復(fù)雜性為3. 計(jì)算下面算法中count=count+1的執(zhí)行次數(shù)算法1.10 COUNT3 輸入：，k為正整數(shù) 輸出：count=count+1的執(zhí)行次數(shù) co

2、unt=0 for i=1 to n j=2 while j<=n j=j2 count=count+1 end while end for return count end COUNT34. 下面是冒泡排序的算法，該算法的基本運(yùn)算是什么？求該算法最壞情況下的時(shí)間復(fù)雜性。算法 BUBBLESORT輸入：正整數(shù)n,n個(gè)元素的數(shù)組A1.n。輸出：按升序排列的數(shù)組A1.n。i=n;sorted=falsewhile i>1 and not sorted sorted=true for j=2 to i if Aj<Aj-1 then Aj Aj-1 sorted=false end

3、 if end for- 12 - / 12 i=i-1end while end BUBBLESORT5. 用兩種方法證明log n!= (n log n)。(1)用代數(shù)方法(2)用積分方法6. 求解遞推關(guān)系式 f(n)=-6f(n-1)-9f(n-2)。 7. 分治算法由哪些基本步驟組成？分治算法的時(shí)間復(fù)雜性常滿足什么樣的遞歸方程，寫出該方程的一般形式，并指出其中各參數(shù)的意義。8. 算法有哪五個(gè)特性？9. 什么是最優(yōu)子結(jié)構(gòu)？10. 貪心法與動(dòng)態(tài)規(guī)劃有何根本區(qū)別？11. 設(shè)計(jì)回溯算法通常包括哪些步驟？12. 隨機(jī)算法分成那幾類，各有什么特點(diǎn)？三算法填空1. 以下是計(jì)算xm的值的過程power

4、 ( x, m )/計(jì)算xm的值并返回。if m=0 then y=_else y=_ y=y*y if m為奇數(shù) then y=x*yend if_end power2. 以下是關(guān)于矩陣鏈乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1輸入：矩陣鏈長度n, n個(gè)矩陣的階r1.n+1, 其中r1.n為n個(gè)矩陣的行數(shù)，rn+1為第n個(gè)矩陣的列數(shù)。輸出：n個(gè)矩陣相乘的數(shù)量乘法的最小次數(shù)，最優(yōu)順序的信息數(shù)組S1.n, 1.n。for i=1 to n Ci, i=0 /對角線d0置 for d=1 to n-1 /逐條計(jì)算對角線d0dn-1 for i=1 to

5、n-d / 計(jì)算對角線dd的n-d個(gè)元素。 _ Ci, j= for k=i+1 to j x= _ if _ then Ci, j=x; Si, j=k end if end for end for end for return C1, n, Send MATCHAIN1根據(jù)S中的信息遞歸確定最優(yōu)乘法順序。算法 MATCHAIN_PRODUCT輸入：矩陣鏈長度n, n個(gè)矩陣M1, M2, , Mn , 最優(yōu)乘法順序的信息數(shù)組S1.n, 1.n。輸出：按最優(yōu)順序計(jì)算的矩陣鏈乘積M=M1M2Mn 。 M=matchain_product( 1, n ) return Mend MATCHAIN_

6、PRODUCT 過程 matchain_product (i, j) / 求按最優(yōu)順序計(jì)算的矩陣鏈乘積MiMi+1Mj并返回。if _ then return Mi else A=matchain_product _ B=matchain_product _ C=multiply( A , B) /計(jì)算兩個(gè)矩陣乘積C=AB。 return C end ifend matchain_product3. 以下是迷宮問題的算法算法 MAZE 輸入：正整數(shù)m, n，表示迷宮的數(shù)組M0.m+1, 0.n+1 (迷宮數(shù)據(jù)存于M1.m, 1.n中)，迷宮的入口位置(ix, iy),出口位置(ox, oy)。

7、 輸出：迷宮中入口至出口的一條通路，若無通路，則輸出no solution。 M0, 0.n+1=Mm+1, 0.n+1=1 M0.m+1, 0=M0.m+1, n+1=1 /設(shè)置迷宮邊界。 tag1.m, 1.n=0 為dx1.4, dy1.4置值 flag=false /flag表示是否存在通路。 x=ix; y=iy ; tagx, y=1 /進(jìn)入入口, (x, y)表示當(dāng)前位置。 i=1; ki=0 while _ and not flag while _ and not flag _ /試沿著下一個(gè)方向搜索。 x1= x+dxki; y1= y+dyki if Mx1, y1=0 a

8、nd tagx1, y1=0 then /位置(x1,y1)可走 if x1=ox and y1=oy then _ /找到一條通路 else x=x1; y=y1; tagx, y=1 /進(jìn)入新位置。 i=i+1 ； ki= _ /準(zhǔn)備搜索下一個(gè)位置。 end if end if /否則，剪枝 end while_; x=x-dxki; y=y-dyki/回溯 end while if flag then outputroute(k, i) /輸出由k1.i表示的通路。 else output “no solution”/輸出無解end MAZE4. 下面是求一個(gè)序列的多數(shù)元素的遞歸算法算法

9、 MAJORITY輸入：n個(gè)元素的數(shù)組A1.n。輸出：若A1.n存在多數(shù)元素，則輸出；否則輸出none。 c=candidate ( 1 ) / 求A1.n中的候選多數(shù)元素。count=0 /以下驗(yàn)證c是否為A1.n中的多數(shù)元素。 for j=1 to n if Aj=c then count=count+1 end for if _ then return c else return noneend MAJORITY過程 candidate ( m )/求Am.n中的候選多數(shù)元素并返回。j=m; c=Am; count=1while j<n and count>0 j=j+1 i

10、f _ then _ else _ /除去兩個(gè)不同的元素。end whileif j=n then return c /此時(shí)序列已掃描完畢。else return _ end candidate5. 下面是0-1背包問題的算法算法 KNAPSACKREC輸入：物品數(shù)n, n種物品的體積數(shù)組s1.n和價(jià)值數(shù)組v1.n, 背包容量C。輸出：裝入背包物品的最大總價(jià)值，以及最優(yōu)解的信息數(shù)組H0.n, 0.C。 for i=0 to n for j=0 to C Vi, j=-1 maxv=knapsack(n, C) return maxv , Hend KNAPSACKREC過程 knapsack(

11、i, j) /從i種物品中選擇物品裝入容量為j的背包中，求背包中/物品所能達(dá)到的最大總價(jià)值并返回，同時(shí)將最優(yōu)解的相應(yīng)/信息存入數(shù)組H0.n, 0.C。 if Vi, j=-1 then /相應(yīng)的子問題未解過。 if i=0 or j=0 then Vi,j=0 else if si>j then Vi, j= _ Hi, j= _ else a1=_ a2=knapsack(i-1, j) if a1>=a2 then Vi, j=a1; Hi, j= _ else Vi, j=a2; Hi, j=0 end if end if end if end if return _end

12、knapsack算法 KNAPSACK_SOLUTION輸入：物品數(shù)n , 背包容量C, n種物品的體積數(shù)組s1.n, 相應(yīng)的0/1背包問題的最優(yōu)解信息數(shù)組H0.n, 0.C。輸出：相應(yīng)的0/1背包問題的最優(yōu)解X1.n。 y=C / y表示當(dāng)前背包的剩余容量Xn=Hn, Cfor i=n to 2 if Xi=1 then y=_ Xi-1= _end forreturn Xend KNAPSACK_SOLUTION6. 以下是隨機(jī)化的線性選擇算法算法 RANDOMIZEDSELECT輸入：整數(shù)n, k, 1<=k<=n, 以及n個(gè)元素的數(shù)組A1.n。輸出：A中的第k小元素s。 s

13、=rselect ( A , 1, n, k )end RANDOMIZEDSELECT過程 rselect ( A , low, high, k ) /求Alow.high中的第k小元素并返回。 v=random(low, high) mm= _ 將Alow.high分成三個(gè)數(shù)組： A1=a|a<mm，A2=a|a=mm, A3=a|a>mm/以下選擇一個(gè)子問題遞歸或直接解。 case|A1|>=k: return _ /求A1的第k小元素。|A1|+|A2|>=k: return mm /此時(shí)mm為Alow.high的第k小元素。 |A1|+|A2|<k: r

14、eturn rselect _ /求A3的第k-|A1|-|A2|小元素 end caseend rselect7. 以下是歸并排序的分治算法MERGESORT 輸入：n個(gè)元素的數(shù)組A1.n。 輸出：按非降序排序的數(shù)組A1.n。 mergesort(A , 1, n) end MERGESORT 過程 mergersort( A , low, high ) /將Alow.high 按非降序歸并排序。 if low<high then mid=_ /平均分解成兩個(gè)子數(shù)組mergesort_ /分別對兩個(gè)子數(shù)組遞歸mergesort_MERGE (A , low, mid, high) /合

15、并兩個(gè)有序的子數(shù)組 end ifend mergesort8. 以下是分?jǐn)?shù)背包問題的貪心算法算法 GREEDY_KANPSACK輸入：表示背包容量的實(shí)數(shù)C, 物品數(shù)n, 表示n個(gè)物品的體積和價(jià)值的實(shí)數(shù)數(shù)組s1.n和v1.n。輸出：裝入背包物品的最大總價(jià)值maxv和相應(yīng)的最優(yōu)解x1.n。 for i=1 to n yi=vi/si /求n個(gè)物品的單位體積價(jià)值y1.n。 end for /對y1.n按降序地址排序，排序結(jié)果返回到數(shù)組d1.n /中, 使得yd1>=yd2>=>=ydn。 d=sort(y, n) for i=1 to n xi=0 /對x1.n初始化。 i=1;

16、maxv=0; rc=C /以下rc表示當(dāng)前背包的剩余容量。while _ and i<=nj=di / uj為當(dāng)前考慮選擇的物品 if sj<=rc then xj= _; rc= _ /物品uj全部裝入背包。 else xj= _ /選擇物品uj的一部分將背包填滿。 rc=0 end if maxv= _i= _ end while return maxv, x1.nend GREEDY_KNAPSACK9. 以下是子集合問題的回溯算法算法 SUBSETSUM 輸入:正整數(shù)n,正實(shí)數(shù)b,表示含有n個(gè)正實(shí)數(shù)的集合S的數(shù)組a1.n。 輸出:集合S的元素之和等于b的所有子集，若無解，

17、則輸出“no solution”。 for i=1 to n xi=0 /用x1.n表示子集，初始化為空集。 r=0 for i=1 to n r=r+ai flag=subset(0, 0, r)if not flag then output “no solution” end SUBSETSUM 過程：subset(k, sum, r) /在已經(jīng)求出的部分解x1.k固定的情況下，求關(guān)于S, b的/子集和問題的所有解并輸出，有解返回true, 否則返回/false。 / sum= 表示當(dāng)前子集的元素之和，r= 表示剩/余元素之和。 if sum=b then /找到一個(gè)解。output x1

18、.n; t=true /輸出當(dāng)前解。 elseif k<n and sum<b and sum+r>=b then /可繼續(xù)往下搜索。r=_ xk+1=0t1=subset_ /搜索左子樹（對應(yīng)xk+1=0）xk+1= _t2=setsub_ /搜索右子樹t=t1 or t2else t=_end if end if _ return tend subset10. 下面是一個(gè)求n個(gè)元素全排列的算法算法 PERMUTATION 輸入：正整數(shù)n和存儲n個(gè)元素a1 , a2, an的數(shù)組P1.n。輸出：a1 , a2, an的全排列。 perml ( 1 )end PERMUTAT

19、ION過程 perml ( m )/在P1.m-1中元素固定不變的情況下，求Pm.n中元素/的全排列，并輸出P1.n中元素的相應(yīng)排列。if _ then / 此時(shí)只求一個(gè)元素Pn的全排列。 output P1.n; / 輸出P1.n中元素的一個(gè)新排列。else for j=m to n PmPj _ _ end for end if end perml11. 以下是求最長公共子序列的算法算法 LCS 輸入：非負(fù)整數(shù)n、m, 長度分別為n和m的序列A= a1a2an和B=b1b2bn 。 輸出：A和B的最長公共子序列長度Ln, m和存儲最長公共子序列的有關(guān)信息的數(shù)組H1.n, 1.m。 for

20、i=0 to n Li, 0=0 for j=0 to m L0, j=0 for i=1 to n for j=1 to m if ai=bj then Li, j= _ ; Hi, j=0 else if Li-1, j>=Li, j-1 then Li, j= _ ; Hi, j=1 else Li, j=Li, j-1 ; Hi, j= _ end if end if end for end for return Ln, m, H end LCS算法 LCSS輸入：非負(fù)整數(shù)n、m, 長度分別為n和m的序列A和B的最長公共子序列的有關(guān)信息數(shù)組H1.n, 1.m, 序列A= a1a2

21、an 。輸出: 序列A和B的最長公共子序列C 。 C= /表示空序列。 i=n; j=m while i>0 and j>0 if Hi, j=0 then 在C的前面插入ai i=_; j=_ else if Hi, j= _ then i=i-1 else j=j-1 end if end while return C end LCSS12. 以下是0-1背包問題的回溯算法算法 KNAPSACK01輸入: 物品數(shù)n, n種物品的體積數(shù)組s1.n和價(jià)值數(shù)組v1.n,背包容量C。輸出：裝入背包物品的最大總價(jià)值maxv和最優(yōu)解x01.n。 /用x1.n表示選擇的物品子集，初始化為空集

22、。 rv=0; rs=0for i=1 to nrv=rv+vi ; rs=rs+si maxv=0; x01.n=x1.n=0 / x0表示當(dāng)前最優(yōu)解。knapsack01(0, C, 0, rv, rs)output maxv, x01.n end KNAPSACK01 過程：knapsack(k, r, cv, rv, rs) /在已知當(dāng)前最優(yōu)值為maxv且已經(jīng)求出的部分解x1.k固/定的情況下，求 0/1背包問題的最優(yōu)值和最優(yōu)解，并更新/maxv和x0。 r表示當(dāng)前背包的剩余容量, cv表示當(dāng)前背/包中物品的總價(jià)值為，rv= , rs= 。 if r>=0 and cv>m

23、axv then /找到更優(yōu)的解，更新當(dāng)前最優(yōu)值。 maxv=_; x0=x end if if rs<=r then if cv+rv>maxv then maxv=cv+rv; x01.k=x1.k; x0k+1.n=1; end if else if r>0 and cv+rv>maxv then /可繼續(xù)往下搜索。 rv=_; rs=_ xk+1=0 knapsack_ /搜索左子樹（對應(yīng)xk+1=0） xk+1=1 knapsack_ /搜索右子樹end if end if _end knapsack13. 下面是求第k小元素的算法算法 SELECT輸入：整數(shù)

24、n, k, 1<=k<=n, 以及n個(gè)元素的數(shù)組A1.n。輸出：A中的第k小元素s。 s=select ( A , 1, n, k )end SELECT過程 select ( A , low, high, k ) /求Alow.high中的第k小元素并返回。 p=high-low+1 /p為當(dāng)前處理的元素個(gè)數(shù)。 if p<44 then / 當(dāng)元素個(gè)數(shù)<44時(shí)，直接求解。 將Alow.high排序 return(Alow+k-1) end if / 以下分解子問題。 q=；/將Alow.high每5個(gè)分組，剩余的被排除。 將Alow.low+5q-1分為q組, 每組5

25、個(gè)元素； 將q組中的每一組單獨(dú)排序并找出中項(xiàng)，所有的中項(xiàng)存于數(shù)組M1.q中； mm=select(_) /求中項(xiàng)序列M的中項(xiàng)mm 將Alow.high分成三組： A1=a|a<mm, A2=a|a=mm, A3=a|a>mm/以下選擇一個(gè)子問題遞歸或直接解。 case|A1|>=k: return select (_) |A1|+|A2|>=k: return mm |A1|+|A2|<k: return select (_) end caseend select14. 有期限的作業(yè)安排問題算法 JOB_ARRANGEMENT輸入：作業(yè)數(shù)n, 表示n個(gè)作業(yè)的期限和

26、收益的數(shù)組d1.n和p1.n。輸出：最優(yōu)的作業(yè)安排序列J1.k和安排的作業(yè)數(shù)k。/對p1.n按降序地址排序，排序結(jié)果返回到數(shù)組a1.n /中,使得pa1>=pa2>=>=pan。 a=sort(p, n) d0=0; J0=0 /設(shè)一個(gè)虛擬作業(yè)編號為，期限為 J1=a1 /直接安排收益最高的作業(yè)jaik=1 /以下k總是表示當(dāng)前已被安排的作業(yè)數(shù)。for t=2 to ni= _ / ji為當(dāng)前考慮安排的作業(yè)。 r=k while _ and dJr>r _ end whileif dJr<=di and _ then /把i插入到J中的r+1位置上。 for s=

27、k to r+1 Js+1=Js Jr+1= _ k= _end if end for return k, J1.kend JOB_ARRANGEMENT15. 以下是關(guān)于矩陣鏈乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1輸入：矩陣鏈長度n, n個(gè)矩陣的階r1.n+1, 其中r1.n為n個(gè)矩陣的行數(shù)，rn+1為第n個(gè)矩陣的列數(shù)。輸出：n個(gè)矩陣相乘的數(shù)量乘法的最小次數(shù)，最優(yōu)順序的信息數(shù)組S1.n, 1.n。for i=1 to n Ci, i=0 /對角線d0置 for d=1 to n-1 /逐條計(jì)算對角線d0dn-1 for i=1 to n-d / 計(jì)算對角線dd的n-d個(gè)元素。 _ Ci, j= for k=i+1 to j x= _ if _ then Ci, j=x; Si, j=k