算法設計與分析基礎課后習題答案(中文版)參考范本

精品精品感謝下載載感謝下載載Program 算法設計與分析基礎中文版答案習題1.15..證明等式gcd(m,n)=gcd(n,mmodn) 對每一對正整數(shù) m,n都成立Hint:根據除法的定義不難證明 :duv,d一定能整除udud也能夠整除u的任何整數(shù)倍ku.對于任意一對正整數(shù) m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn ；然，若d能整除n和r，也一定能整除m=r+qn 和n。(m,n)(n,r)gcd(m,n)=gcd(n,r)6.對于第一個數(shù)小于第二個數(shù)的一對數(shù)字 歐幾里得算法將會如何處理 該算法在處理這種輸入的過中上述情況最多會發(fā)生幾次 ?Hint:對于任何形如0<=m<n 的一對數(shù)字,Euclid 算法在第一次疊代時交換 m和n,即gcd(m,n)=gcd(n,m)并且這種交換處理只發(fā)生一次 .7.a.對于所有1的輸入,Euclid 算法最少要做幾次除法?(1次)b.對于所有的輸入,Euclid 算法最多要做幾次除法?(5次gcd(5,8)習題1.21.(農夫過河)PP—農夫WG—山羊C—白菜2.()1,2,5,10--- 分別代表4個人,f4.對于任意實系數(shù) a,b,c, 某個算法能求方程 ax^2+bx+c=0 的實根寫出上述算法的偽代碼 (可以設sqrt(x)是求平方根的函數(shù))算法Quadratic(a,b,c)//求方程ax^2+bx+c=0 的實根的算法//輸入:實系數(shù)a,b,c//輸出:實根或者無解信息Ifa≠0D←b*b-4*a*cIfD>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturnx1,x2elseifD=0return–b/(2*a)elsereturn“norealrootselse //a=0ifbreturn –else //a=b=0ifc=0return “norealnumbers ”elsereturn “norealroots ”5.5.描述將十進制整數(shù)表達為二進制整數(shù)的標準算法a.用文字描述b用偽代碼描述解答：a將十進制整數(shù)轉換為二進制整數(shù)的算法輸入：一個正整數(shù) n輸出：正整數(shù) n相應的二進制數(shù)第一步：用n2，余數(shù)賦給Ki(i=0,1,2...)，商賦給n第二步：如果 n=0，則到第三步，否則重復第一步第三步：將Ki按照i從高到低的順序輸出b.偽代碼算法 DectoBin(n)//將十進制整數(shù) n轉換為二進制整數(shù)的算法//輸入：正整數(shù) n//輸出：該正整數(shù)相應的二進制數(shù)，該數(shù)存放于數(shù)組 Bin[1...n]中i=1whilen!=0do{Bin[i]=n%2;n=(int)n/2;i++;}whilei!=0do{printBin[i];i--;}9.考慮下面這個算法,它求的是數(shù)組中大小相差最小的兩個元素的差 算法略)對這個算法做盡可能多的改進 .算法MinDistance(A[0..n-1])//輸入:數(shù)組A[0..n-1]//輸出:thesmallestdistancedbetweentwoofitselements習題1.31. 考慮這樣一個排序算法 ,該算法對于待排序的數(shù)組中的每一個元素 計算比它小的元素個數(shù) ,然后用這個信息將各個元素放到有序數(shù)組的相應位置上去 .應用該算法對列表7 排序b?c.該算法在位嗎?解:.該算法對列表7 排序的過程如下所示:.*c.該算法不在位.額外空間forSandCount[]4.(古老的七橋問題)習題1.41.請分別描述一下應該如何實現(xiàn)下列對數(shù)組的操作 使得操作時間不依賴數(shù)組的長度 a.刪除數(shù)組的第i個元素(1<=i<=n)b.刪除有序數(shù)組的第 i個元素(依然有序hints:Replacethe ithelementwiththelastelementanddecreasethearraysizeof1e the h t h aspecial symbol that cannot e avalue f the yelement(e.g.,0foranarrayofpositivenumbers)tomarkthe ithpositionisempty.(yn )第2章習題2.17.對下列斷言進行證明:(如果是錯誤的,請舉例)a.t(n)∈O(g(n),g(n)b.時解:這個斷言是正確的。它指出如果 t(n)的增長率小于或等于 g(n)的增長率，那么 g(n)的增長率于或等于t(n)的增長率由 t(n)c)forln ,ec>01(n)c

g(

foralln 這個斷言是正確的。只需證明

( g(n))

(g(

(g(n))

( gn。設f(n)∈Θ(αg(n)),則有：f(n)

c g(n)

foralln>=n0,c>0f(n)

c1g(n)

foralln>=n0,c1=c 即：f(n)∈Θ(g(n))f(n)∈Θ(g(n)),

f(n)

cg(n)

foralln>=n0,c>0f(

cg(

g(

foralln>=n0,c1=c/ 即：f(n)8a.Ω符號b.Θ符號證明：aweneedtoproofthatift 1(n)1(n))andt2(n)2(n)),thent 1(n)+t2(n)∈Ω(max{g1g2(n)})。由t1(n)1(n))，t1(n)1(n) foralln>=n1,wherec1>0由t2(n)2(n))，T2(n)2(n) foralln>=n2,wherec2>0那么，取c>=min{c1,c2}, 當n>=max{n1,n2} 時：t1(n)+t2(n)≥c1g1(n)+c2g2(n)g1(n)+cg 2(n)1(n)+g2(n)]≥cmax{g1(n),g2(n)}所以以命題成立。b.t1(n)+t2(n) max(g1(n),gn)))證明：由大?的定義知，必須確定常數(shù) c1、c2和n0，使得對于所有n>=n0 ，有：max((g2(n))

t1(n)

t2(n)

max(g1(n),g由t1(n)知，存在非負整數(shù) a1,a2和n1使：a1*g1(n)<=t 1(n)<=a2*g1(n) (1)由t2(n)知，存在非負整數(shù) b1,b2 和n2使：b1*g2(n)<=t 2(n)<=b2*g2(n) (2)(1)+(2):a1*g1(n)+b1*g2(n)<=t1(n)+t2(n)<=a2*g1(n)+b2*g2(n)令c1=min(a1,b1),c2=max(a2,b2) ，則C1*(g1+g2)<=t 1(n)+t2(n)<=c2(g1+g2) (3)不失一般性假設 max(g1(n),g2(n))=g1(n).顯然，g1(n)+g2(n)<2g1(n) ，即g1+g2<2max(g1,g2)又g2(n)>0 ，g1(n)+g2(n)>g1(n), 即g1+g2>max(g1,g2) 則（3）式轉換為：C1*max(g1,g2)<=t 1(n)+t2(n)<=c2*2max(g1,g2)所以當c1＝min(a1,b1),c2 ＝2c2=2max(c1,c2) ＝max(n1,n2) 時當n>=n0 時上述不等成立。證畢。習題2.41. 解下列遞推關系 （做a,b）x(n)x(1)解：

x(n 50

當n>1時x(n)解：

3x(n 4

當n>1時2.2. 對于計算的遞歸算法F(n)，建立其遞歸調用次數(shù)的遞推關系并求解。解：考慮下列遞歸算法，該算法用來計算前 n個立方的和：S(n)=13+23+ ?+n3算法S(n)//輸入：正整數(shù)n//輸出：前n個立方的和ifn=1return1elsereturnS(n-1)+n*n*n建立該算法的基本操作次數(shù)的遞推關系并求解解：a.a. 請基于公式2n=2n-1+2n-1，設計一個遞歸算法。當 n是任意非負整數(shù)的時候，該算法能夠計算2n的值。建立該算法所做的加法運算次數(shù)的遞推關系并求解為該算法構造一棵遞歸調用樹，然后計算它所做的遞歸調用次數(shù)。對于該問題的求解來說，這是一個好的算法嗎？解:a.算法power(n)//基于公式2n=2n-1+2n-12n//輸入:非負整數(shù)n//輸出:2n的值Ifn=0return1Elsereturnpower(n-1)+power(n-1)c.nC(2ii0

2n1 1考慮下面的算法算法Min1(A[0..n-1])//輸入:包含n個實數(shù)的數(shù)組A[0..n-1]Ifn=1returnA[0]Elsetemp←Min1(A[0..n-2])Iftemp returnElsereturnA[n-1]該算法計算的是什么?解:計算的給定數(shù)組的最小值C(n)

C(n 10

foralln>1n=1考慮用于解決第 8題問題的另一個算法該算法遞歸地將數(shù)組分成兩半 .我們將它稱Min2(A[0..n-1])算法 Min(A[r..l])Ifl=rreturnElsetemp1 ←Min2(A[l..(l+r)/2])Temp2←Min2(A[l..(l+r)/2]+1..r)Iftemp1 returntemp1Elsereturntemp2建立該算法所做的的操作次數(shù)的遞推關系并求解算法Min1 和Min2 哪個更快?有其他更好的算法嗎?解:a.習題2.61. 考慮下面的排序算法其中插入了一個計數(shù)器來對關鍵比較次數(shù)進行計數(shù) .算法SortAnalysis(A[0..n-1])//input: 包含n個可排序元素的一個數(shù)組 A[0..n-1]//output: 所做的關鍵比較的總次數(shù)count←0fori←1ton-1dov←A[i]j←i-1whilej>0andA[j]>vdocount←count+1A[j+1] ←A[j]j←j+1A[j+1] ←vreturncount比較計數(shù)器是否插在了正確的位置 如果不對,請改正.解:算法SortAnalysis(A[0..n-1])//input://input: 包含n個可排序元素的一個數(shù)組 A[0..n-1]//output: 所做的關鍵比較的總次數(shù)count←0fori←1ton-1dov←A[i]j←i-1whilej>0andA[j]>vdocount←count+1A[j+1] ←A[j]j←j+1ifj>=0count=count+1A[j+1] ←vreturncount習題3.1a設計一個蠻力算法,對于給定的x0,計算下面多項式的值:P(x)=anxn+an-1xn-1+?+a1x+a0并確定該算法的最差效率類型 .b.如果你設計的算法屬于Θ(n2),請你為該算法設計一個線性的算法 .C.對于該問題來說能不能設計一個比線性效率還要好的算法呢 ?解:AlgorithmsBruteForcePolynomialEvaluation(P[0..n],x)//由高冪到低冪用蠻力法計算多項式 p在給定點x的值//輸入:P[0..n]是多項式按低冪到高冪的常系數(shù) 以及定值x//輸出:多項式p在給定點x的值p=0.0fori=nto0dopower=1forj=1toidopower=power*xp=p+P[i]*powerreturnp算法效率分析:基本操作兩個數(shù)相乘,且M(n)僅依賴于多項式的階 nM(n)

n i n1 i0j1 i0

n(n 2

(n2)thaabovealgorithmsisveryinefficient,becausewerecompute powersofxagainandagainasiftherewerenorelationshipamongthem.Infact,wecanmovefromthelowesttermtothehighestandcomputex ibyusingx i-1.AlgorithmsBetterBruteForcePolynomialEvaluation(P[0..n],x)//由高冪到低冪用蠻力法計算多項式 p在給定點x的值//輸入:P[0..n]是多項式按低冪到高冪的常系數(shù) 以及定值x//輸出:多項式p在給定點x的值P=P[0]power=1fori←1tondopower←power*xp←p+P[i]*powerreturnp基本操作乘法運算總次數(shù) M(n):M(n)

n2 2ni1

(n)不行.因為計算任意一個多項式在任意點 x 的值,都必須處理它的 n+1 個系數(shù).例如(x=1,p(x)=a n+an-1+..+a1+a0,至少要做n次加法運算)應用選擇排序對序列 example 按照字母順序排序.選擇排序是穩(wěn)定的嗎?()用鏈表實現(xiàn)選擇排序的話 ,能不能獲得和數(shù)組版相同的Θ(n2)效率?Yes.Both n —finding the smallest t d swapping t can e e efficientlywiththelinkedlistaswithanarray.9.a.請證明,如果對列表比較一遍之后沒有交換元素的位置 那么這個表已經排好序了 ,算法可以停止了.b.結合所做的改進,為冒泡排序寫一段偽代碼 c.請證明改進的算法最差效率也是平方級的 .Hints:a. i趟冒泡可以表示為:如果沒有發(fā)生交換位置 那么:b.AlgorithmsBetterBubblesort(A[0..n-1])//用改進的冒泡算法對數(shù)組 A[0..n-1] 排序//輸入A[0..n-1]//輸出升序排列的數(shù)組 A[0..n-1]count←n-1 //進行比較的相鄰元素對的數(shù)目flag←true //交換標志whileflagdoflag←falsefori=0tocount-1doifA[i+1]<A[i]swap(A[i],A[i+1])flag←truecount←count-1c最差情況是數(shù)組是嚴格遞減的 ,那么此時改進的冒泡排序會蛻化為原來的冒泡排序 .10.冒泡排序是穩(wěn)定的嗎?(穩(wěn)定)習題3.2對限位器版的順序查找算法的比較次數(shù) :在最差情況下在平均情況下假設成功查找的概率是 Hints:Cworst(n)=n+1在成功查找下對于任意的I,第一次匹配發(fā)生在第 i個位置的可能性是 p/n,比較次數(shù)是i.在找不成功時比較次數(shù)是n+1,可能性是1-p.給出一個長度為 n的文本和長度為m的模式構成的實例,它是蠻力字符串匹配算法的一個最差輸入 .并指出,對于這樣的輸入需要做多少次字符比較運算 .Hints:文本n0組成的文本模式前m-1 個是0,最后一個字符是1比較次數(shù):m(n-m+1)為蠻力字符匹配算法寫一個偽代碼 對于給定的模式它能夠返回給定的文本中所有匹配子串的數(shù)量 AlgorithmsBFStringmatch(T[0..n-1],P[0..m-1])//蠻力字符匹配////輸入T[0..n-1]n的文本,P[0..m-1]—長度為m的模式//輸出:在文本中匹配成功的子串數(shù)量count←0fori←0ton-mdoj←0whilej<mandP[j]=T[i+j]j←j+1ifj=mcount←count+1returncount8.如果所要搜索的模式包含一些英語中較少見的字符,我們應該如何修改該蠻力算法來利用這個信息.Hint:每次都從這些少見字符開始比較 ,如果匹配,則向左邊和右邊進行其它字符的比較.習題4.11.a.為一個分治算法編寫偽代碼 ,該算法求一個 n個元素數(shù)組中最大元素的位置 .b.如果數(shù)組中的若干個元素都具有最大值 該算法的輸出是怎樣的呢 c.建立該算法的鍵值比較次數(shù)的遞推關系式并求解 .d.請拿該算法與解同樣問題的蠻力算法做一個比較解:a.AlgorithmsMaxIndex(A[ l..r]){Input:AnfyA[0..n-1]ns ld r(lrOutput:TheindexofthelargestelementinA[ l..r]ifl=rreturnlelsetemp1 ←MaxIndex(A[ l..(l+rtemp2 ←MaxIndex(A[( l+r)/2..r])ifA[temp1] returntemp1elsereturntemp2}b.返回數(shù)組中位于最左邊的最大元素的序號 鍵值比較次數(shù)的遞推關系式 :C(n)=C(n/2)+C(n/2)+1 forn>1C(1)=0設n=2k，C(2k)=2C(2 k-1)+1=2[2C(2 k-2)+1]+1=2 2C(2k-2)+2+1=2[2 2C(2k-3)+1]+2+1=2 3C(2k-3)+22+2+1=...=2iC(2k-i)+2i-1+2 i-2 +...+2+1=...=2kC(2k-k)+2k-1+2 k-2 +...+2+1=2 k－1=n-1可以證明C(n)=n-1 對所有n>1 的情況都成立（n是偶數(shù)或奇數(shù)）d.比較的次數(shù)相同，但蠻力算法不用遞歸調用。2、a.為一個分治算法編寫偽代碼，該算法同時求出一個 n元數(shù)組的最大元素和最小元素的值。bc.請拿該算法與解同樣問題的蠻力算法做一個比較。解答：同時求出最大值和最小值，只需要將原數(shù)組一分為二，再使用相同的方法找出這兩個部分中的最大值和最小值，然后經過比較就可以得到整個問題的最大值和最小值算法 MaxMin(A[ l..r],Max,Min)//該算法利用分治技術得到數(shù)組 A中的最大值和最小值//輸入：數(shù)值數(shù)組 A[l..r]//輸出：最大值 Max 和最小值Minifrl)Max←A[l]Min←A[l];//只有一個元素時elseifrl=1 //有兩個元素時fA[l]A[r]Max←A[r]; Min←A[l]elseMax←A[l]; Min←A[r]else //r－l>1MaxMin(A[ l,(l+r)/2],Max1,Min1);// 遞歸解決前一部分MaxMin(A[( l+r/)2..r],Max2,Min2);// 遞歸解決后一部分ifMax1 Max2 Max=Max2 //從兩部分的兩個最大值中選擇大值ifMin2<Min1 Min=Min2;// 從兩部分的兩個最小值中選擇小值}n=2比較次數(shù)的遞推關系式:C(n)=2C(n/2)+2 forC(1)=0, C(2)=1C(n)=C(2k)=2C(2k-1)+2=2[2C(2 k-2)+2]+2=22C(2k-2)+22+2=22[2C(2k-3)+2]+2 2+2=23C(2k-3)+23+22+2...=2k-1C(2)+2k-1+2k-2+...+2 //C(2)=1=2k-1+2k-1+2k-2+...+2// 后面部分為等比數(shù)列求和=2k-1+2k-2 //2(k-1)=n/2,2 k=n=n/2+n-2=3n/2 －2b.蠻力法的算法如下：算法 simpleMaxMin(A[ l..r])//用蠻力法得到數(shù)組 A的最大值和最小值//輸入：數(shù)值數(shù)組 A[l..r]//輸出：最大值 Max 和最小值Max=Min=A[ l];fori= l+1tordoifA[i]>Max Max←A[i];elseifA[i]<MinMin ←A[i]returnMax,Min}時間復雜度t(n)=2(n-1)算法MaxMin 的時間復雜度為 3n/2-2 ，simpleMaxMin 的時間復雜度為 2n-2，都屬于，但較一下發(fā)現(xiàn)，MaxMin 的速度要比 simpleMaxMin 的快一些。6.應用合并排序對序列 E,X,A,M,P,L,E按字母順序排序.1238.a.對合并排序的最差鍵值比較次數(shù)的遞推關系式求解 .(forn=2 k)b.建立合并排序的最優(yōu)鍵值比較次數(shù)的遞推關系式求解 .(forn=2 k)對于4.1節(jié)給出的合并排序算法 ,建立它的鍵值移動次數(shù)的遞推關系式 .考慮了該算法的鍵值移動次數(shù)后是否會影響它的效率類型呢 ?解:遞推關系式見 4.1節(jié).(列表升序或降序)下:Cbest(n)=2Cbest(n/2)+n/2 forn>1(n=2 k)Cbest(1)=0鍵值比較次數(shù) M(n)M(n)=2M(n)+2n forM(1)=0習題4.21.應用快速排序對序列 E,X,A,M,P,L,E按字母順序排序4. 請舉一個n個元素數(shù)組的例子 使得我們有必須對它使用本節(jié)提到的 限位器限位器的值應是多少年來為什么一個限位器就能滿足所有的輸入呢 ?精品Hints:Withthepivotbeingtheleftmostelement,theleft-to-rightscanwillgetoutofboundsifandonlyifthepivotislargerthantheotherelements.Appendingasentinel( 限位器)fvaluelA[0](orrthanA[0])rthey selement,thequicksortalgorithmswillstoptheindexoftheleft-to-rightscanofA[0..n-1]fromgoingbeyondpositionn.設計一個算法對 n個實數(shù)組成的數(shù)組進行重新排列 ,使得其中所有的負元素都位于正元素之前 .這個算需要兼顧空間和時間效率 .Algorithmsnetbeforepos(A[0..n-1])//使所有負元素位于正元素之前//輸入實數(shù)組A[0..n-1]//輸出所有負元素位于于正元素之前的實數(shù)組 A[0..n-1]A[-1]-1;A[n] 1//限位器i←0;j←n-1Whilei<jdoWhileA[i] i←i+1whileA[j] j←j-1swapA[i]andA[j]swapA[i]andA[j] //undothelastswap當全是非負數(shù)或全是非正數(shù)時需要限位器 .4.31.(題略)感謝下載載精品解:由公式4.4得:4次二分查找判定樹:所以,14,31,42,74,85,98 需要比較4次c.CyesavgC

1 1113

1 2 213

1 3 413

1 4 613

41 13d.CnoavgC

1 3214

1 412 5414 14

3.92. 當n=2k時,用反向替換法求下面的遞推方程 :當n>1 時,Cw(n)=Cw(n/2)+1, (1)=1(略)4.如果對于一個 100000 個元素的數(shù)組成功查找的話 使用折半查找比順序查找要快多少倍 ?．如何將折半查找應用于范圍查找 范圍查找就是對于一個有序數(shù)組 找出位于給定值 L、U之間（包含、U）的所有元素，L<=U 。該算法的最差效率是多少？感謝下載載精品Hints:Step1: 檢查A[0]是否成立，若不成立，則無解。否則進入 step2Step2:在數(shù)組A中用二分查找法查找值 如果查找成功，則返回數(shù)組下標 m否則l二分查找結束時值.Step3: 在數(shù)組A中用二分查找法查找值 U，如果查找成功，則返回數(shù)組下標 m，否則r為二分查找結束時的值.最后，結果就是在數(shù)組序號范圍在 low和high（包含low,high ）之間的范圍。（low 和high 是step2和step3 的值。）． 為折半查找寫遞歸的偽代碼。AlgorithmsBSR(A[o..n-1],K)//折半查找遞歸算法//有序子數(shù)組A[l..r]和查找鍵值K//查找成功則輸出其下標，否則輸出 if l>rreturn-1else m←(l+r)/2ifK=A[m]returnmelseifK<A[m]returnBSR(A[ l..m-1],K)elseifK>A[m]returnBSR(A[m+1,r],K)8.設計一個只使用兩路比較的折半查找算法，即只用≤和 =, 或者只用≥和=.AlgorithmsTwoWaysBinarySearch(A[o..n-1],K)//二路比較的折半查找//有序子數(shù)組A[l..r]和查找鍵值K//查找成功則輸出其下標，否則輸出 -1l←0,r←n-1while l<rm←(l+r)/2ifK≤A[m]r←melsel←m+1ifK=A[ l] return l感謝下載載精品精品感謝下載載感謝下載載elsereturn-1習題4.4設計一個分治算法來計算二叉樹的層數(shù) .(空樹返回0,單頂點樹返回 1),并分析效率類型 .AlgorithmsLevel(TreeT)//遞歸計算二叉樹的層數(shù)//輸入:二叉樹T//輸出二叉樹T的層If T=NULL return0Elsereturnmax{Level(T L),Level(TR)}+1算法效率類型是Θ(n)(4.4height(T))選擇一個二叉樹的經典遍歷算法 (前中后序),寫出它的遞歸偽代碼 ,并求它的遞歸調用次數(shù) .Algorithmspreorder(T)//先序遍歷二叉樹 T//輸入:二叉樹T//輸出先序遍歷的結點序列表IfT≠NULLVisitTsrootPreorder(T L)Preorder(T R)遞歸調用次數(shù) C(n)=擴展樹中內部結點+外部結點=n+(n+1)=2n+1設計一個算法計算有根有序樹的高度 .Algorithmsheight(T)//遞歸計算有根有序樹的高度//輸入一棵有根有序樹的高度 T//輸出:T的高度i=NumChildren(T) //根的孩子個數(shù)if i=0return0elsereturnmax{height(T 1),height(T 2),?,height(T i)}+1下面的算法試圖計算一棵二叉樹中葉子的數(shù)量AlgorithmsLeafCount(T)//遞歸計算二叉樹中葉子的數(shù)量//輸入一棵二叉樹//輸出:T中葉子的數(shù)量ifT=NULLreturn0elsereturnLeafCount(T L)+LeafCount(TR)應為:ifT=NULLreturn0 //emptytreeelseifTL=NULLANDT R=NULLreturn1//single-nodetreeelsereturnLeafCount(T L)+LeafCount(TR)//generalcase習題4.61.a.為最近對問題的一維版本設計一個直接基于分治技術的算法 并確定它的效率類型b.對于這個問題它是一個好算法嗎 ?解:AlgorithmsClosestNumber(A[ l..r])//分治計算最近對問題的一維版本//輸入升序排列的實數(shù)子數(shù)組 A[l..r]//輸出最近數(shù)對的距Ifr=lreturn ∞Elseifr－l=1returnA[r] －A[l]Elsereturnmin{ClosestNumber(A[ l?(l+r)/2]),ClosestNumber(A[( l+r)/2...r])A[(l+r)/2+1] －A[(l+r)/2]}設遞歸的時間效率為設遞歸的時間效率為 T(n):對n=2k, 則:T(n)=2T(n/2)+c利用主定理求解.T(n)=Θ(n)2.(題略)習題5.12.a.設計一個遞歸的減一算法 ,求n個實數(shù)構成的數(shù)組中最小元素的位置 .確定該算法的時間效率 然后把它與該問題的蠻力算法作比較AlgorithmsMinLocation(A[ 0..n-1])//findthelocationofthesmallestelementinagivenarray//anarrayA[0..n-1]ofrealnumbers//AnindexofthesmallestelementinA[ 0..n-1if n=1return0else temp ←MinLocation(A[ 0..n-2])if A[temp]<A[ n-1] return else return n-1時間效率分析見習題 2.4中8C(n)=C(n-1)+1 for n>1 C(1)=04.應用插入排序對序列 example 按照字母順序排序5.a.對于插入排序來說 為了避免在內部循環(huán)的每次迭代時判斷邊界條件 j>=0, 應該在待排序數(shù)組的第個元素前放一個什么樣的限位器 ?b.帶限位器版本和原版本的效率類型相同嗎 ?解:a.應該在待排序數(shù)組的第一個元素前放 -∞或者小于等于最小元素值的元素 .b. 效率類型相同.(數(shù)組是嚴格遞減):7.算法InsertSort2(A[0..n-1])fori←1ton-1doj←i-1whilej>=0andA[j]>A[j+1]doswap(A[j],A[j+1])j←j+1分析:在教材中算法InsertSort 的內層循環(huán)包括一次鍵值賦值和一次序號遞減 ,而算InsertSort2 的內層循環(huán)包括一次鍵值交換和一次序號遞減 ,設一次賦值和一次序號遞減的時間分別為 ca和cd,那么算法InsertSort2 和算法InsertSort 運行時間的比率是(3cd)/(ca+cd)習題5.21.a.(略)b.4.習題5.31.DFS的棧狀態(tài):退棧順序:efgbcad 拓撲排序:dacbgfeb.這是一個有環(huán)有向圖 .DFS從a出發(fā),?,遇到一條從 e到a的回邊.能否利用頂點進入 DFS棧的順序(代替它們從棧中退出的順序 )來解決拓撲排序問題 Hints:不能.對第1題中的有向圖應用源刪除算法 .dabcgef習題5.44.下面是生成排列的 B.Heap 算法.算法HeapPermute(n)//實現(xiàn)生成排列的 Heap算法//輸入一個正整數(shù) n和一個全局數(shù)組 A[1..n]//輸出:A中元素的全排列Ifn=1WriteAElseFori←1tondoHeapPermute(n-1)IfnisoddSwapA[1]andA[n]ElseswapA[i]andA[n]對于n=2,3,4 的情況,手工跟蹤該算法.解n=2fori=1 doheappermute(1 ）{writeA 12}這時nnotodd,sodoA[1] 與A[2]互換，fori=2doheappermute(1 ）{writeA 21}對于n=3Fori=1doHeappermute(2){heappermute(1writeA 即123這時2notodd,so,doA[1]與A[2]heappermute(1)writeA即213這時2notodd,doA[2]與A[2]互換，A=213}由于3isodd,sodoA[1]A[3]互換,A=312Fori=2doHeappermute(2){heappermute(1writeA 即312這時2notodd,so,doA[1]與A[2]互換，A=132heappermute(1)writeA即132這時2notodd,doA[2]與A[2]互換，A=231}由于3isodd,sodoA[1]A[3]互換,A=231Fori=3doHeappermute(2){heappermute(1writeA 2312notodd,so,doA[1]A[2]A=321heappermute(1)writeA即321這時2notodd,doA[2]與A[2]互換，A=321}由于3isodd,sodoA[1]A[3]互換,A=123n=4 :習題5.52.Hints:減常因子b.c.c.折半查找在最壞情況下的查找效率是log2n+1.而習題6.11. hintsortthelistandthensimplyreturnthe n/2thelementsofthesortedlist.效率:假設排序算法的效率是 O(nlogn), 那么該算法的效率是 O(nlogn)+ O(nlogn)3.hinta.初始化C=A∩B=Φforeveryelementa iinAdo(1<=i<=n)foreveryelementb jinB(1<=j<=m)Ifai=bjaddaitoCdeleteb jfrom最差情況:C為空,比較的次數(shù)是 nm.方法一:排序集合AForeveryelementb jinB用二分查找的辦法在 A中查找與bj相匹配的元素 If 查找成功AddatoC效率分析:假設排序的效率是 O(nlogn), 則該算法效率O(nlogn)+mO(logn)=(n+m)O(logn)方法二:首先對AB.然后對A和B應用合并排序只輸出它們的公有元素 .效率分析:假設排序的效率是 O(nlogn), 則該算法效率O(nlogn)+O(mlogm)+ wheres=max{n,m}方法三:首先將A和B合并為L排序L從左至右成對掃描 IfLi=Li+1AddLitoi←i+2效率分析:假設排序的效率是 O(nlogn), 則該算法效率O((n+m)logn))+ =O(slogs)wheres=max{n,m}4.hint排序數(shù)組然后返回它的第一和最后元素 .假設排序的效率是 O(nlogn), 則該算法效率 O(nlogn)+ O(nlogn)蠻力和分治都是線性的 所以優(yōu)于基于預排序的算習題6.32.b.4.a.5.a.二叉查找樹中最大值和最小值分別是樹中最右邊和最左邊的結點 .因此,從根開始,沿著向左的路徑一直走到這樣的結點它的左孩子為空這個結點里的值就是最小值 .同理,可以找到最大值.最后,這兩個值做一次法運算即可.算法的效率:b.錯誤.8.不成立.例如列表{A,B},查找A,二分查找只做 1次比較而在2-3樹中查找則要做 2次比習題6.41.a.b.c.錯誤.對于列表{1,2,3}按自頂向下:{3,1,2}自底向上:{3,2,1}設計一個算法尋找并刪除堆中最小元素 然后確定其時間效Hints: 最小元素一定在堆的葉子中 .在堆H[1..n]的后半部分,(H[n/2+1], ?,H[n])中查找最小元素,并與最后的元素 H[n]互換刪除最后的元素堆規(guī)模降1,如果必要的話,調整元素H[n],使其滿足雙親優(yōu)勢 .:查找交換并刪除:調整為堆:O(logn)b.設計一個算法在給定的堆 H中尋找并刪除一個包含給定值 v的元素,然后確定其時間效率 .Hints:在H中順序查找滿足條件的第一個元素 H[i]與H[n]互換.刪除最后元素堆規(guī)模降1調整元素H[n]:查找交換并刪除:調整為堆:O(logn)習題6.51.精品乘法總次數(shù) M(n)加法總次數(shù) A(n)感謝下載載精品精品感謝下載載感謝下載載精品1 總則1.1 為了加強公司的環(huán)境衛(wèi)生管理，創(chuàng)造一個整潔、文明、溫馨的購物、辦公環(huán)境，根據《公共場所衛(wèi)生管理條例》的要求，特制定本制度。1.2 集團公司的衛(wèi)生管理部門設在企管部，并負責將集團公司的衛(wèi)生區(qū)域詳細劃分到各部室，各分公司所轄區(qū)域衛(wèi)生由分公司客服部負責劃分，確保無遺漏。2 衛(wèi)生標準2.1 室內衛(wèi)生標準2.1.1 地面、墻面：無灰塵、無紙屑、無痰跡、無泡泡糖等粘合物、無積水，墻角無灰吊、無蜘蛛網。2.1.2 門、窗、玻璃、鏡子、柱子、電梯、樓梯、燈具等，做到明亮、無灰塵、無污跡、無粘合物，特別是玻璃，要求兩面明亮。2.1.3 柜臺、貨架：清潔干凈，貨架、柜臺底層及周圍無亂堆亂放現(xiàn)象、無灰塵、無粘合物，貨架頂部、背部和底部干凈，不存放雜物和私人物品。2.1.4 購物車（筐）、直接接觸食品的售貨工具（包括刀、叉等）：做到內外潔凈，無污垢和粘合物等。購物車（筐）要求每天營業(yè)前簡單清理，周五全面清理消毒；售貨工具要求每天消毒，并做好記錄。2.1.5 商品及包裝：商品及外包裝清潔無灰塵（外包裝破損的或破舊的不得陳列）。2.1.6 收款臺、服務臺、辦公櫥、存包柜：保持清潔、無灰塵，臺面和側面無灰塵、無灰吊和蜘蛛網。桌面上不得亂貼、亂畫、亂堆放物品，用具擺放有序且干凈，除當班的購物小票收款聯(lián)外，其它單據不得存放在桌面上。2.1.7 垃圾桶：桶內外干凈，要求營業(yè)時間隨時清理，不得溢出，每天下班前徹底清理，不得留有垃圾過夜。2.1.8 窗簾：定期進行清理，要求干凈、無污漬。2.1.9 吊飾：屋頂?shù)牡躏椧鬅o灰塵、無蜘蛛網，短期內不適用的吊飾及時清理徹底。2.1.10 內、外倉庫：半年徹底清理一次，無垃圾、無積塵、無蜘蛛網等。2.1.11 室內其他附屬物及工作用具均以整潔為準，要求無灰塵、無粘合物等污垢。2.2 室外衛(wèi)生標準2.2.1 門前衛(wèi)生：地面每天班前清理，平時每一小時清理一次，每周四營業(yè)結束后有條件的用水沖洗地面（冬季可根據情況適當清理），墻面干凈且無亂貼亂畫。2.2.2 院落衛(wèi)生：院內地面衛(wèi)生全天保潔，果皮箱、消防器械、護欄及配電箱等設施每周清理干凈。垃圾池周邊衛(wèi)生清理徹底，不得有垃圾溢出。2.2.3 綠化區(qū)衛(wèi)生：做到無雜物、無紙屑、無塑料袋等垃圾。3 清理程序3.1 室內和門前院落等區(qū)域衛(wèi)生：每天營業(yè)前提前10分鐘把所管轄區(qū)域內衛(wèi)生清理完畢，營業(yè)期間隨時保潔。下班后5-10分鐘清理桌面及衛(wèi)生區(qū)域。3.2 綠化區(qū)衛(wèi)生：每周徹底清理一遍，隨時保持清潔無垃圾。4 管理考核4.1 實行百分制考核，每月一次（四個分公司由客服部分別考核、集團職4.2 集團堅持定期檢查和不定期抽查的方式監(jiān)督各分公司、部門的衛(wèi)生工作。每周五為衛(wèi)生檢查日，集團檢查結果考核至各分公司，各分公司客服部的檢查結果考核至各部門。4.3 集團公司每年不定期組織衛(wèi)生大檢查活動，活動期間的考核以通知為準。5 監(jiān)督考核部門：企管部、分公司客服部。!歡迎您的下載，資料僅供參考Program 算法設計與分析基礎中文版答案習題1.15..證明等式gcd(m,n)=gcd(n,mmodn) 對每一對正整數(shù) m,n都成立Hint:根據除法的定義不難證明 :duv,d一定能整除udud也能夠整除u的任何整數(shù)倍ku.對于任意一對正整數(shù) m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn ；然，若d能整除n和r，也一定能整除m=r+qn 和n。(m,n)(n,r)gcd(m,n)=gcd(n,r)6.對于第一個數(shù)小于第二個數(shù)的一對數(shù)字 歐幾里得算法將會如何處理 該算法在處理這種輸入的過中上述情況最多會發(fā)生幾次 ?Hint:對于任何形如0<=m<n 的一對數(shù)字,Euclid 算法在第一次疊代時交換 m和n,即gcd(m,n)=gcd(n,m)并且這種交換處理只發(fā)生一次 .7.a.對于所有1的輸入,Euclid 算法最少要做幾次除法?(1次)b.對于所有的輸入,Euclid 算法最多要做幾次除法?(5次gcd(5,8)習題1.21.(農夫過河)PP—農夫WG—山羊C—白菜2.()1,2,5,10--- 分別代表4個人,f4.對于任意實系數(shù) a,b,c, 某個算法能求方程 ax^2+bx+c=0 的實根寫出上述算法的偽代碼 (可以設sqrt(x)是求平方根的函數(shù))算法Quadratic(a,b,c)//求方程ax^2+bx+c=0 的實根的算法//輸入:實系數(shù)a,b,c//輸出:實根或者無解信息Ifa≠0D←b*b-4*a*cIfD>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturnx1,x2elseifD=0return–b/(2*a)elsereturn“norealrootselse //a=0ifbreturn –else //a=b=0ifc=0return “norealnumbers ”elsereturn “norealroots ”5.5.描述將十進制整數(shù)表達為二進制整數(shù)的標準算法a.用文字描述b用偽代碼描述解答：a將十進制整數(shù)轉換為二進制整數(shù)的算法輸入：一個正整數(shù) n輸出：正整數(shù) n相應的二進制數(shù)第一步：用n2，余數(shù)賦給Ki(i=0,1,2...)，商賦給n第二步：如果 n=0，則到第三步，否則重復第一步第三步：將Ki按照i從高到低的順序輸出b.偽代碼算法 DectoBin(n)//將十進制整數(shù) n轉換為二進制整數(shù)的算法//輸入：正整數(shù) n//輸出：該正整數(shù)相應的二進制數(shù)，該數(shù)存放于數(shù)組 Bin[1...n]中i=1whilen!=0do{Bin[i]=n%2;n=(int)n/2;i++;}whilei!=0do{printBin[i];i--;}9.考慮下面這個算法,它求的是數(shù)組中大小相差最小的兩個元素的差 算法略)對這個算法做盡可能多的改進 .算法MinDistance(A[0..n-1])//輸入:數(shù)組A[0..n-1]//輸出:thesmallestdistancedbetweentwoofitselements習題1.31. 考慮這樣一個排序算法 ,該算法對于待排序的數(shù)組中的每一個元素 計算比它小的元素個數(shù) ,然后用這個信息將各個元素放到有序數(shù)組的相應位置上去 .應用該算法對列表7 排序b?c.該算法在位嗎?解:.該算法對列表7 排序的過程如下所示:.*c.該算法不在位.額外空間forSandCount[]4.(古老的七橋問題)習題1.41.請分別描述一下應該如何實現(xiàn)下列對數(shù)組的操作 使得操作時間不依賴數(shù)組的長度 a.刪除數(shù)組的第i個元素(1<=i<=n)b.刪除有序數(shù)組的第 i個元素(依然有序hints:Replacethe ithelementwiththelastelementanddecreasethearraysizeof1e the h t h aspecial symbol that cannot e avalue f the yelement(e.g.,0foranarrayofpositivenumbers)tomarkthe ithpositionisempty.(yn )第2章習題2.17.對下列斷言進行證明:(如果是錯誤的,請舉例)a.t(n)∈O(g(n),g(n)b.時解:這個斷言是正確的。它指出如果 t(n)的增長率小于或等于 g(n)的增長率，那么 g(n)的增長率于或等于t(n)的增長率由 t(n)c)forln ,ec>01(n)c

g(

foralln 這個斷言是正確的。只需證明

( g(n))

(g(

(g(n))

( gn。設f(n)∈Θ(αg(n)),則有：f(n)

c g(n)

foralln>=n0,c>0f(n)

c1g(n)

foralln>=n0,c1=c 即：f(n)∈Θ(g(n))f(n)∈Θ(g(n)),

f(n)

cg(n)

foralln>=n0,c>0f(

cg(

g(

foralln>=n0,c1=c/ 即：f(n)8a.Ω符號b.Θ符號證明：aweneedtoproofthatift 1(n)1(n))andt2(n)2(n)),thent 1(n)+t2(n)∈Ω(max{g1g2(n)})。由t1(n)1(n))，t1(n)1(n) foralln>=n1,wherec1>0由t2(n)2(n))，T2(n)2(n) foralln>=n2,wherec2>0那么，取c>=min{c1,c2}, 當n>=max{n1,n2} 時：t1(n)+t2(n)≥c1g1(n)+c2g2(n)g1(n)+cg 2(n)1(n)+g2(n)]≥cmax{g1(n),g2(n)}所以以命題成立。b.t1(n)+t2(n) max(g1(n),gn)))證明：由大?的定義知，必須確定常數(shù) c1、c2和n0，使得對于所有n>=n0 ，有：max((g2(n))

t1(n)

t2(n)

max(g1(n),g由t1(n)知，存在非負整數(shù) a1,a2和n1使：a1*g1(n)<=t 1(n)<=a2*g1(n) (1)由t2(n)知，存在非負整數(shù) b1,b2 和n2使：b1*g2(n)<=t 2(n)<=b2*g2(n) (2)(1)+(2):a1*g1(n)+b1*g2(n)<=t1(n)+t2(n)<=a2*g1(n)+b2*g2(n)令c1=min(a1,b1),c2=max(a2,b2) ，則C1*(g1+g2)<=t 1(n)+t2(n)<=c2(g1+g2) (3)不失一般性假設 max(g1(n),g2(n))=g1(n).顯然，g1(n)+g2(n)<2g1(n) ，即g1+g2<2max(g1,g2)又g2(n)>0 ，g1(n)+g2(n)>g1(n), 即g1+g2>max(g1,g2) 則（3）式轉換為：C1*max(g1,g2)<=t 1(n)+t2(n)<=c2*2max(g1,g2)所以當c1＝min(a1,b1),c2 ＝2c2=2max(c1,c2) ＝max(n1,n2) 時當n>=n0 時上述不等成立。證畢。習題2.41. 解下列遞推關系 （做a,b）x(n)x(1)解：

x(n 50

當n>1時x(n)解：

3x(n 4

當n>1時2.2. 對于計算的遞歸算法F(n)，建立其遞歸調用次數(shù)的遞推關系并求解。解：考慮下列遞歸算法，該算法用來計算前 n個立方的和：S(n)=13+23+ ?+n3算法S(n)//輸入：正整數(shù)n//輸出：前n個立方的和ifn=1return1elsereturnS(n-1)+n*n*n建立該算法的基本操作次數(shù)的遞推關系并求解解：a.a. 請基于公式2n=2n-1+2n-1，設計一個遞歸算法。當 n是任意非負整數(shù)的時候，該算法能夠計算2n的值。建立該算法所做的加法運算次數(shù)的遞推關系并求解為該算法構造一棵遞歸調用樹，然后計算它所做的遞歸調用次數(shù)。對于該問題的求解來說，這是一個好的算法嗎？解:a.算法power(n)//基于公式2n=2n-1+2n-12n//輸入:非負整數(shù)n//輸出:2n的值Ifn=0return1Elsereturnpower(n-1)+power(n-1)c.nC(2ii0

2n1 1考慮下面的算法算法Min1(A[0..n-1])//輸入:包含n個實數(shù)的數(shù)組A[0..n-1]Ifn=1returnA[0]Elsetemp←Min1(A[0..n-2])Iftemp returnElsereturnA[n-1]該算法計算的是什么?解:計算的給定數(shù)組的最小值C(n)

C(n 10

foralln>1n=1考慮用于解決第 8題問題的另一個算法該算法遞歸地將數(shù)組分成兩半 .我們將它稱Min2(A[0..n-1])算法 Min(A[r..l])Ifl=rreturnElsetemp1 ←Min2(A[l..(l+r)/2])Temp2←Min2(A[l..(l+r)/2]+1..r)Iftemp1 returntemp1Elsereturntemp2建立該算法所做的的操作次數(shù)的遞推關系并求解算法Min1 和Min2 哪個更快?有其他更好的算法嗎?解:a.習題2.61. 考慮下面的排序算法其中插入了一個計數(shù)器來對關鍵比較次數(shù)進行計數(shù) .算法SortAnalysis(A[0..n-1])//input: 包含n個可排序元素的一個數(shù)組 A[0..n-1]//output: 所做的關鍵比較的總次數(shù)count←0fori←1ton-1dov←A[i]j←i-1whilej>0andA[j]>vdocount←count+1A[j+1] ←A[j]j←j+1A[j+1] ←vreturncount比較計數(shù)器是否插在了正確的位置 如果不對,請改正.解:算法SortAnalysis(A[0..n-1])//input://input: 包含n個可排序元素的一個數(shù)組 A[0..n-1]//output: 所做的關鍵比較的總次數(shù)count←0fori←1ton-1dov←A[i]j←i-1whilej>0andA[j]>vdocount←count+1A[j+1] ←A[j]j←j+1ifj>=0count=count+1A[j+1] ←vreturncount習題3.1a設計一個蠻力算法,對于給定的x0,計算下面多項式的值:P(x)=anxn+an-1xn-1+?+a1x+a0并確定該算法的最差效率類型 .b.如果你設計的算法屬于Θ(n2),請你為該算法設計一個線性的算法 .C.對于該問題來說能不能設計一個比線性效率還要好的算法呢 ?解:AlgorithmsBruteForcePolynomialEvaluation(P[0..n],x)//由高冪到低冪用蠻力法計算多項式 p在給定點x的值//輸入:P[0..n]是多項式按低冪到高冪的常系數(shù) 以及定值x//輸出:多項式p在給定點x的值p=0.0fori=nto0dopower=1forj=1toidopower=power*xp=p+P[i]*powerreturnp算法效率分析:基本操作兩個數(shù)相乘,且M(n)僅依賴于多項式的階 nM(n)

n i n1 i0j1 i0

n(n 2

(n2)thaabovealgorithmsisveryinefficient,becausewerecompute powersofxagainandagainasiftherewerenorelationshipamongthem.Infact,wecanmovefromthelowesttermtothehighestandcomputex ibyusingx i-1.AlgorithmsBetterBruteForcePolynomialEvaluation(P[0..n],x)//由高冪到低冪用蠻力法計算多項式 p在給定點x的值//輸入:P[0..n]是多項式按低冪到高冪的常系數(shù) 以及定值x//輸出:多項式p在給定點x的值P=P[0]power=1fori←1tondopower←power*xp←p+P[i]*powerreturnp基本操作乘法運算總次數(shù) M(n):M(n)

n2 2ni1

(n)不行.因為計算任意一個多項式在任意點 x 的值,都必須處理它的 n+1 個系數(shù).例如(x=1,p(x)=a n+an-1+..+a1+a0,至少要做n次加法運算)應用選擇排序對序列 example 按照字母順序排序.選擇排序是穩(wěn)定的嗎?()用鏈表實現(xiàn)選擇排序的話 ,能不能獲得和數(shù)組版相同的Θ(n2)效率?Yes.Both n —finding the smallest t d swapping t can e e efficientlywiththelinkedlistaswithanarray.9.a.請證明,如果對列表比較一遍之后沒有交換元素的位置 那么這個表已經排好序了 ,算法可以停止了.b.結合所做的改進,為冒泡排序寫一段偽代碼 c.請證明改進的算法最差效率也是平方級的 .Hints:a. i趟冒泡可以表示為:如果沒有發(fā)生交換位置 那么:b.AlgorithmsBetterBubblesort(A[0..n-1])//用改進的冒泡算法對數(shù)組 A[0..n-1] 排序//輸入A[0..n-1]//輸出升序排列的數(shù)組 A[0..n-1]count←n-1 //進行比較的相鄰元素對的數(shù)目flag←true //交換標志whileflagdoflag←falsefori=0tocount-1doifA[i+1]<A[i]swap(A[i],A[i+1])flag←truecount←count-1c最差情況是數(shù)組是嚴格遞減的 ,那么此時改進的冒泡排序會蛻化為原來的冒泡排序 .10.冒泡排序是穩(wěn)定的嗎?(穩(wěn)定)習題3.2對限位器版的順序查找算法的比較次數(shù) :在最差情況下在平均情況下假設成功查找的概率是 Hints:Cworst(n)=n+1在成功查找下對于任意的I,第一次匹配發(fā)生在第 i個位置的可能性是 p/n,比較次數(shù)是i.在找不成功時比較次數(shù)是n+1,可能性是1-p.給出一個長度為 n的文本和長度為m的模式構成的實例,它是蠻力字符串匹配算法的一個最差輸入 .并指出,對于這樣的輸入需要做多少次字符比較運算 .Hints:文本n0組成的文本模式前m-1 個是0,最后一個字符是1比較次數(shù):m(n-m+1)為蠻力字符匹配算法寫一個偽代碼 對于給定的模式它能夠返回給定的文本中所有匹配子串的數(shù)量 AlgorithmsBFStringmatch(T[0..n-1],P[0..m-1])//蠻力字符匹配////輸入T[0..n-1]n的文本,P[0..m-1]—長度為m的模式//輸出:在文本中匹配成功的子串數(shù)量count←0fori←0ton-mdoj←0whilej<mandP[j]=T[i+j]j←j+1ifj=mcount←count+1returncount8.如果所要搜索的模式包含一些英語中較少見的字符,我們應該如何修改該蠻力算法來利用這個信息.Hint:每次都從這些少見字符開始比較 ,如果匹配,則向左邊和右邊進行其它字符的比較.習題4.11.a.為一個分治算法編寫偽代碼 ,該算法求一個 n個元素數(shù)組中最大元素的位置 .b.如果數(shù)組中的若干個元素都具有最大值 該算法的輸出是怎樣的呢 c.建立該算法的鍵值比較次數(shù)的遞推關系式并求解 .d.請拿該算法與解同樣問題的蠻力算法做一個比較解:a.AlgorithmsMaxIndex(A[ l..r]){Input:AnfyA[0..n-1]ns ld r(lrOutput:TheindexofthelargestelementinA[ l..r]ifl=rreturnlelsetemp1 ←MaxIndex(A[ l..(l+rtemp2 ←MaxIndex(A[( l+r)/2..r])ifA[temp1] returntemp1elsereturntemp2}b.返回數(shù)組中位于最左邊的最大元素的序號 鍵值比較次數(shù)的遞推關系式 :C(n)=C(n/2)+C(n/2)+1 forn>1C(1)=0設n=2k，C(2k)=2C(2 k-1)+1=2[2C(2 k-2)+1]+1=2 2C(2k-2)+2+1=2[2 2C(2k-3)+1]+2+1=2 3C(2k-3)+22+2+1=...=2iC(2k-i)+2i-1+2 i-2 +...+2+1=...=2kC(2k-k)+2k-1+2 k-2 +...+2+1=2 k－1=n-1可以證明C(n)=n-1 對所有n>1 的情況都成立（n是偶數(shù)或奇數(shù)）d.比較的次數(shù)相同，但蠻力算法不用遞歸調用。2、a.為一個分治算法編寫偽代碼，該算法同時求出一個 n元數(shù)組的最大元素和最小元素的值。bc.請拿該算法與解同樣問題的蠻力算法做一個比較。解答：同時求出最大值和最小值，只需要將原數(shù)組一分為二，再使用相同的方法找出這兩個部分中的最大值和最小值，然后經過比較就可以得到整個問題的最大值和最小值算法 MaxMin(A[ l..r],Max,Min)//該算法利用分治技術得到數(shù)組 A中的最大值和最小值//輸入：數(shù)值數(shù)組 A[l..r]//輸出：最大值 Max 和最小值Minifrl)Max←A[l]Min←A[l];//只有一個元素時elseifrl=1 //有兩個元素時fA[l]A[r]Max←A[r]; Min←A[l]elseMax←A[l]; Min←A[r]else //r－l>1MaxMin(A[ l,(l+r)/2],Max1,Min1);// 遞歸解決前一部分MaxMin(A[( l+r/)2..r],Max2,Min2);// 遞歸解決后一部分ifMax1 Max2 Max=Max2 //從兩部分的兩個最大值中選擇大值ifMin2<Min1 Min=Min2;// 從兩部分的兩個最小值中選擇小值}n=2比較次數(shù)的遞推關系式:C(n)=2C(n/2)+2 forC(1)=0, C(2)=1C(n)=C(2k)=2C(2k-1)+2=2[2C(2 k-2)+2]+2=22C(2k-2)+22+2=22[2C(2k-3)+2]+2 2+2=23C(2k-3)+23+22+2...=2k-1C(2)+2k-1+2k-2+...+2 //C(2)=1=2k-1+2k-1+2k-2+...+2// 后面部分為等比數(shù)列求和=2k-1+2k-2 //2(k-1)=n/2,2 k=n=n/2+n-2=3n/2 －2b.蠻力法的算法如下：算法 simpleMaxMin(A[ l..r])//用蠻力法得到數(shù)組 A的最大值和最小值//輸入：數(shù)值數(shù)組 A[l..r]//輸出：最大值 Max 和最小值Max=Min=A[ l];fori= l+1tordoifA[i]>Max Max←A[i];elseifA[i]<MinMin ←A[i]returnMax,Min}時間復雜度t(n)=2(n-1)算法MaxMin 的時間復雜度為 3n/2-2 ，simpleMaxMin 的時間復雜度為 2n-2，都屬于，但較一下發(fā)現(xiàn)，MaxMin 的速度要比 simpleMaxMin 的快一些。6.應用合并排序對序列 E,X,A,M,P,L,E按字母順序排序.1238.a.對合并排序的最差鍵值比較次數(shù)的遞推關系式求解 .(forn=2 k)b.建立合并排序的最優(yōu)鍵值比較次數(shù)的遞推關系式求解 .(forn=2 k)對于4.1節(jié)給出的合并排序算法 ,建立它的鍵值移動次數(shù)的遞推關系式 .考慮了該算法的鍵值移動次數(shù)后是否會影響它的效率類型呢 ?解:遞推關系式見 4.1節(jié).(列表升序或降序)下:Cbest(n)=2Cbest(n/2)+n/2 forn>1(n=2 k)Cbest(1)=0鍵值比較次數(shù) M(n)M(n)=2M(n)+2n forM(1)=0習題4.21.應用快速排序對序列 E,X,A,M,P,L,E按字母順序排序4. 請舉一個n個元素數(shù)組的例子 使得我們有必須對它使用本節(jié)提到的 限位器限位器的值應是多少年來為什么一個限位器就能滿足所有的輸入呢 ?精品Hints:Withthepivotbeingtheleftmostelement,theleft-to-rightscanwillgetoutofboundsifandonlyifthepivotislargerthantheotherelements.Appendingasentinel( 限位器)fvaluelA[0](orrthanA[0])rthey selement,thequicksortalgorithmswillstoptheindexoftheleft-to-rightscanofA[0..n-1]fromgoingbeyondpositionn.設計一個算法對 n個實數(shù)組成的數(shù)組進行重新排列 ,使得其中所有的負元素都位于正元素之前 .這個算需要兼顧空間和時間效率 .Algorithmsnetbeforepos(A[0..n-1])//使所有負元素位于正元素之前//輸入實數(shù)組A[0..n-1]//輸出所有負元素位于于正元素之前的實數(shù)組 A[0..n-1]A[-1]-1;A[n] 1//限位器i←0;j←n-1Whilei<jdoWhileA[i] i←i+1whileA[j] j←j-1swapA[i]andA[j]swapA[i]andA[j] //undothelastswap當全是非負數(shù)或全是非正數(shù)時需要限位器 .4.31.(題略)感謝下載載精品解:由公式4.4得:4次二分查找判定樹:所以,14,31,42,74,85,98 需要比較4次c.CyesavgC

1 1113

1 2 213

1 3 413

1 4 613

41 13d.CnoavgC

1 3214

1 412 5414 14

3.92. 當n=2k時,用反向替換法求下面的遞推方程 :當n>1 時,Cw(n)=Cw(n/2)+1, (1)=1(略)4.如果對于一個 100000 個元素的數(shù)組成功查找的話 使用折半查找比順序查找要快多少倍 ?．如何將折半查找應用于范圍查找 范圍查找就是對于一個有序數(shù)組 找出位于給定值 L、U之間（包含、U）的所有元素，L<=U 。該算法的最差效率是多少？感謝下載載精品Hints:Step1: 檢查A[0]是否成立，若不成立，則無解。否則進入 step2Step2:在數(shù)組A中用二分查找法查找值 如果查找成功，則返回數(shù)組下標 m否則l二分查找結束時值.Step3: 在數(shù)組A中用二分查找法查找值 U，如果查找成功，則返回數(shù)組下標 m，否則r為二分查找結束時的值.最后，結果就是在數(shù)組序號范圍在 low和high（包含low,high ）之間的范圍。（low 和high 是step2和step3 的值。）． 為折半查找寫遞歸的偽代碼。AlgorithmsBSR(A[o.