算法設(shè)計(jì)與分析基礎(chǔ)課后習(xí)題答案(中文版)參考范本

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

g(

foralln 這個(gè)斷言是正確的。只需證明

( g(n))

(g(

(g(n))

( gn。設(shè)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.Ω符號(hào)b.Θ符號(hào)證明：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}, 當(dāng)n>=max{n1,n2} 時(shí)：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，使得對(duì)于所有n>=n0 ，有：max((g2(n))

t1(n)

t2(n)

max(g1(n),g由t1(n)知，存在非負(fù)整數(shù) a1,a2和n1使：a1*g1(n)<=t 1(n)<=a2*g1(n) (1)由t2(n)知，存在非負(fù)整數(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)不失一般性假設(shè) 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）式轉(zhuǎn)換為：C1*max(g1,g2)<=t 1(n)+t2(n)<=c2*2max(g1,g2)所以當(dāng)c1＝min(a1,b1),c2 ＝2c2=2max(c1,c2) ＝max(n1,n2) 時(shí)當(dāng)n>=n0 時(shí)上述不等成立。證畢。習(xí)題2.41. 解下列遞推關(guān)系 （做a,b）x(n)x(1)解：

x(n 50

當(dāng)n>1時(shí)x(n)解：

3x(n 4

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

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

C(n 10

foralln>1n=1考慮用于解決第 8題問(wèn)題的另一個(gè)算法該算法遞歸地將數(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ù)的遞推關(guān)系并求解算法Min1 和Min2 哪個(gè)更快?有其他更好的算法嗎?解:a.習(xí)題2.61. 考慮下面的排序算法其中插入了一個(gè)計(jì)數(shù)器來(lái)對(duì)關(guān)鍵比較次數(shù)進(jìn)行計(jì)數(shù) .算法SortAnalysis(A[0..n-1])//input: 包含n個(gè)可排序元素的一個(gè)數(shù)組 A[0..n-1]//output: 所做的關(guān)鍵比較的總次數(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比較計(jì)數(shù)器是否插在了正確的位置 如果不對(duì),請(qǐng)改正.解:算法SortAnalysis(A[0..n-1])//input://input: 包含n個(gè)可排序元素的一個(gè)數(shù)組 A[0..n-1]//output: 所做的關(guān)鍵比較的總次數(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習(xí)題3.1a設(shè)計(jì)一個(gè)蠻力算法,對(duì)于給定的x0,計(jì)算下面多項(xiàng)式的值:P(x)=anxn+an-1xn-1+?+a1x+a0并確定該算法的最差效率類型 .b.如果你設(shè)計(jì)的算法屬于Θ(n2),請(qǐng)你為該算法設(shè)計(jì)一個(gè)線性的算法 .C.對(duì)于該問(wèn)題來(lái)說(shuō)能不能設(shè)計(jì)一個(gè)比線性效率還要好的算法呢 ?解:AlgorithmsBruteForcePolynomialEvaluation(P[0..n],x)//由高冪到低冪用蠻力法計(jì)算多項(xiàng)式 p在給定點(diǎn)x的值//輸入:P[0..n]是多項(xiàng)式按低冪到高冪的常系數(shù) 以及定值x//輸出:多項(xiàng)式p在給定點(diǎn)x的值p=0.0fori=nto0dopower=1forj=1toidopower=power*xp=p+P[i]*powerreturnp算法效率分析:基本操作兩個(gè)數(shù)相乘,且M(n)僅依賴于多項(xiàng)式的階 nM(n)

n i n1 i0j1 i0

n(n 2

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

n2 2ni1

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

g(

foralln 這個(gè)斷言是正確的。只需證明

( g(n))

(g(

(g(n))

( gn。設(shè)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.Ω符號(hào)b.Θ符號(hào)證明：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}, 當(dāng)n>=max{n1,n2} 時(shí)：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，使得對(duì)于所有n>=n0 ，有：max((g2(n))

t1(n)

t2(n)

max(g1(n),g由t1(n)知，存在非負(fù)整數(shù) a1,a2和n1使：a1*g1(n)<=t 1(n)<=a2*g1(n) (1)由t2(n)知，存在非負(fù)整數(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)不失一般性假設(shè) 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）式轉(zhuǎn)換為：C1*max(g1,g2)<=t 1(n)+t2(n)<=c2*2max(g1,g2)所以當(dāng)c1＝min(a1,b1),c2 ＝2c2=2max(c1,c2) ＝max(n1,n2) 時(shí)當(dāng)n>=n0 時(shí)上述不等成立。證畢。習(xí)題2.41. 解下列遞推關(guān)系 （做a,b）x(n)x(1)解：

x(n 50

當(dāng)n>1時(shí)x(n)解：

3x(n 4

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

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

C(n 10

foralln>1n=1考慮用于解決第 8題問(wèn)題的另一個(gè)算法該算法遞歸地將數(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ù)的遞推關(guān)系并求解算法Min1 和Min2 哪個(gè)更快?有其他更好的算法嗎?解:a.習(xí)題2.61. 考慮下面的排序算法其中插入了一個(gè)計(jì)數(shù)器來(lái)對(duì)關(guān)鍵比較次數(shù)進(jìn)行計(jì)數(shù) .算法SortAnalysis(A[0..n-1])//input: 包含n個(gè)可排序元素的一個(gè)數(shù)組 A[0..n-1]//output: 所做的關(guān)鍵比較的總次數(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比較計(jì)數(shù)器是否插在了正確的位置 如果不對(duì),請(qǐng)改正.解:算法SortAnalysis(A[0..n-1])//input://input: 包含n個(gè)可排序元素的一個(gè)數(shù)組 A[0..n-1]//output: 所做的關(guān)鍵比較的總次數(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習(xí)題3.1a設(shè)計(jì)一個(gè)蠻力算法,對(duì)于給定的x0,計(jì)算下面多項(xiàng)式的值:P(x)=anxn+an-1xn-1+?+a1x+a0并確定該算法的最差效率類型 .b.如果你設(shè)計(jì)的算法屬于Θ(n2),請(qǐng)你為該算法設(shè)計(jì)一個(gè)線性的算法 .C.對(duì)于該問(wèn)題來(lái)說(shuō)能不能設(shè)計(jì)一個(gè)比線性效率還要好的算法呢 ?解:AlgorithmsBruteForcePolynomialEvaluation(P[0..n],x)//由高冪到低冪用蠻力法計(jì)算多項(xiàng)式 p在給定點(diǎn)x的值//輸入:P[0..n]是多項(xiàng)式按低冪到高冪的常系數(shù) 以及定值x//輸出:多項(xiàng)式p在給定點(diǎn)x的值p=0.0fori=nto0dopower=1forj=1toidopower=power*xp=p+P[i]*powerreturnp算法效率分析:基本操作兩個(gè)數(shù)相乘,且M(n)僅依賴于多項(xiàng)式的階 nM(n)

n i n1 i0j1 i0

n(n 2

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

n2 2ni1

(n)不行.因?yàn)橛?jì)算任意一個(gè)多項(xiàng)式在任意點(diǎn) x 的值,都必須處理它的 n+1 個(gè)系數(shù).例如(x=1,p(x)=a n+an-1+..+a1+a0,至少要做n次加法運(yùn)算)應(yīng)用選擇排序?qū)π蛄?example 按照字母順序排序.選擇排序是穩(wěn)定的嗎?()用鏈表實(shí)現(xiàn)選擇排序的話 ,能不能獲得和數(shù)組版相同的Θ(n2)效率?Yes.Both n —finding the smallest t d swapping t can e e efficientlywiththelinkedlistaswithanarray.9.a.請(qǐng)證明,如果對(duì)列表比較一遍之后沒(méi)有交換元素的位置 那么這個(gè)表已經(jīng)排好序了 ,算法可以停止了.b.結(jié)合所做的改進(jìn),為冒泡排序?qū)懸欢蝹未a c.請(qǐng)證明改進(jìn)的算法最差效率也是平方級(jí)的 .Hints:a. i趟冒泡可以表示為:如果沒(méi)有發(fā)生交換位置 那么:b.AlgorithmsBetterBubblesort(A[0..n-1])//用改進(jìn)的冒泡算法對(duì)數(shù)組 A[0..n-1] 排序//輸入A[0..n-1]//輸出升序排列的數(shù)組 A[0..n-1]count←n-1 //進(jìn)行比較的相鄰元素對(duì)的數(shù)目flag←true //交換標(biāo)志whileflagdoflag←falsefori=0tocount-1doifA[i+1]<A[i]swap(A[i],A[i+1])flag←truecount←count-1c最差情況是數(shù)組是嚴(yán)格遞減的 ,那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原來(lái)的冒泡排序 .10.冒泡排序是穩(wěn)定的嗎?(穩(wěn)定)習(xí)題3.2對(duì)限位器版的順序查找算法的比較次數(shù) :在最差情況下在平均情況下假設(shè)成功查找的概率是 Hints:Cworst(n)=n+1在成功查找下對(duì)于任意的I,第一次匹配發(fā)生在第 i個(gè)位置的可能性是 p/n,比較次數(shù)是i.在找不成功時(shí)比較次數(shù)是n+1,可能性是1-p.給出一個(gè)長(zhǎng)度為 n的文本和長(zhǎng)度為m的模式構(gòu)成的實(shí)例,它是蠻力字符串匹配算法的一個(gè)最差輸入 .并指出,對(duì)于這樣的輸入需要做多少次字符比較運(yùn)算 .Hints:文本n0組成的文本模式前m-1 個(gè)是0,最后一個(gè)字符是1比較次數(shù):m(n-m+1)為蠻力字符匹配算法寫一個(gè)偽代碼 對(duì)于給定的模式它能夠返回給定的文本中所有匹配子串的數(shù)量 AlgorithmsBFStringmatch(T[0..n-1],P[0..m-1])//蠻力字符匹配////輸入T[0..n-1]n的文本,P[0..m-1]—長(zhǎng)度為m的模式//輸出:在文本中匹配成功的子串?dāng)?shù)量count←0fori←0ton-mdoj←0whilej<mandP[j]=T[i+j]j←j+1ifj=mcount←count+1returncount8.如果所要搜索的模式包含一些英語(yǔ)中較少見的字符,我們應(yīng)該如何修改該蠻力算法來(lái)利用這個(gè)信息.Hint:每次都從這些少見字符開始比較 ,如果匹配,則向左邊和右邊進(jìn)行其它字符的比較.習(xí)題4.11.a.為一個(gè)分治算法編寫偽代碼 ,該算法求一個(gè) n個(gè)元素?cái)?shù)組中最大元素的位置 .b.如果數(shù)組中的若干個(gè)元素都具有最大值 該算法的輸出是怎樣的呢 c.建立該算法的鍵值比較次數(shù)的遞推關(guān)系式并求解 .d.請(qǐng)拿該算法與解同樣問(wèn)題的蠻力算法做一個(gè)比較解: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.返回?cái)?shù)組中位于最左邊的最大元素的序號(hào) 鍵值比較次數(shù)的遞推關(guān)系式 :C(n)=C(n/2)+C(n/2)+1 forn>1C(1)=0設(shè)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 對(duì)所有n>1 的情況都成立（n是偶數(shù)或奇數(shù)）d.比較的次數(shù)相同，但蠻力算法不用遞歸調(diào)用。2、a.為一個(gè)分治算法編寫偽代碼，該算法同時(shí)求出一個(gè) n元數(shù)組的最大元素和最小元素的值。bc.請(qǐng)拿該算法與解同樣問(wèn)題的蠻力算法做一個(gè)比較。解答：同時(shí)求出最大值和最小值，只需要將原數(shù)組一分為二，再使用相同的方法找出這兩個(gè)部分中的最大值和最小值，然后經(jīng)過(guò)比較就可以得到整個(gè)問(wèn)題的最大值和最小值算法 MaxMin(A[ l..r],Max,Min)//該算法利用分治技術(shù)得到數(shù)組 A中的最大值和最小值//輸入：數(shù)值數(shù)組 A[l..r]//輸出：最大值 Max 和最小值Minifrl)Max←A[l]Min←A[l];//只有一個(gè)元素時(shí)elseifrl=1 //有兩個(gè)元素時(shí)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 //從兩部分的兩個(gè)最大值中選擇大值ifMin2<Min1 Min=Min2;// 從兩部分的兩個(gè)最小值中選擇小值}n=2比較次數(shù)的遞推關(guān)系式: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}時(shí)間復(fù)雜度t(n)=2(n-1)算法MaxMin 的時(shí)間復(fù)雜度為 3n/2-2 ，simpleMaxMin 的時(shí)間復(fù)雜度為 2n-2，都屬于，但較一下發(fā)現(xiàn)，MaxMin 的速度要比 simpleMaxMin 的快一些。6.應(yīng)用合并排序?qū)π蛄?E,X,A,M,P,L,E按字母順序排序.1238.a.對(duì)合并排序的最差鍵值比較次數(shù)的遞推關(guān)系式求解 .(forn=2 k)b.建立合并排序的最優(yōu)鍵值比較次數(shù)的遞推關(guān)系式求解 .(forn=2 k)對(duì)于4.1節(jié)給出的合并排序算法 ,建立它的鍵值移動(dòng)次數(shù)的遞推關(guān)系式 .考慮了該算法的鍵值移動(dòng)次數(shù)后是否會(huì)影響它的效率類型呢 ?解:遞推關(guān)系式見 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習(xí)題4.21.應(yīng)用快速排序?qū)π蛄?E,X,A,M,P,L,E按字母順序排序4. 請(qǐng)舉一個(gè)n個(gè)元素?cái)?shù)組的例子 使得我們有必須對(duì)它使用本節(jié)提到的 限位器限位器的值應(yīng)是多少年來(lái)為什么一個(gè)限位器就能滿足所有的輸入呢 ?精品Hints:Withthepivotbeingtheleftmostelement,theleft-to-rightscanwillgetoutofboundsifandonlyifthepivotislargerthantheotherelements.Appendingasentinel( 限位器)fvaluelA[0](orrthanA[0])rthey selement,thequicksortalgorithmswillstoptheindexoftheleft-to-rightscanofA[0..n-1]fromgoingbeyondpositionn.設(shè)計(jì)一個(gè)算法對(duì) n個(gè)實(shí)數(shù)組成的數(shù)組進(jìn)行重新排列 ,使得其中所有的負(fù)元素都位于正元素之前 .這個(gè)算需要兼顧空間和時(shí)間效率 .Algorithmsnetbeforepos(A[0..n-1])//使所有負(fù)元素位于正元素之前//輸入實(shí)數(shù)組A[0..n-1]//輸出所有負(fù)元素位于于正元素之前的實(shí)數(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當(dāng)全是非負(fù)數(shù)或全是非正數(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. 當(dāng)n=2k時(shí),用反向替換法求下面的遞推方程 :當(dāng)n>1 時(shí),Cw(n)=Cw(n/2)+1, (1)=1(略)4.如果對(duì)于一個(gè) 100000 個(gè)元素的數(shù)組成功查找的話 使用折半查找比順序查找要快多少倍 ?．如何將折半查找應(yīng)用于范圍查找 范圍查找就是對(duì)于一個(gè)有序數(shù)組 找出位于給定值 L、U之間（包含、U）的所有元素，L<=U 。該算法的最差效率是多少？感謝下載載精品Hints:Step1: 檢查A[0]是否成立，若不成立，則無(wú)解。否則進(jìn)入 step2Step2:在數(shù)組A中用二分查找法查找值 如果查找成功，則返回?cái)?shù)組下標(biāo) m否則l二分查找結(jié)束時(shí)值.Step3: 在數(shù)組A中用二分查找法查找值 U，如果查找成功，則返回?cái)?shù)組下標(biāo) m，否則r為二分查找結(jié)束時(shí)的值.最后，結(jié)果就是在數(shù)組序號(hào)范圍在 low和high（包含low,high ）之間的范圍。（low 和high 是step2和step3 的值。）． 為折半查找寫遞歸的偽代碼。AlgorithmsBSR(A[o.