算法設(shè)計(jì)與分析基礎(chǔ)習(xí)題參考答案

習(xí)題1.15..證明等式g?cd(m,n)=gcd(n,mmodn)對(duì)每一對(duì)正?整數(shù)m,n都成立.Hint:根據(jù)除法的?定義不難證?明:如果d整除?u和v,那么d一定?能整除u±v;如果d整除?u,那么d也能?夠整除u的?任何整數(shù)倍?ku.對(duì)于任意一?對(duì)正整數(shù)m?,n,若d能整除?m和n,那么d一定?能整除n和?r=mmodn=m-qn；顯然，若d能整除?n和r，也一定能整?除m=r+qn和n。數(shù)對(duì)(m,n)和(n,r)具有相同的?公約數(shù)的有?限非空集，其中也包括?了最大公約?數(shù)。故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ù)?字,Eucli?d算法在第?一次疊代時(shí)?交換m和n?,即gcd(m,n)=gcd(n,m)并且這種交?換處理只發(fā)?生一次.7.a.對(duì)于所有1?≤m,n≤10的輸入?,Eucli?d算法最少?要做幾次除?法?(1次)b.對(duì)于所有1?≤m,n≤10的輸入?,Eucli?d算法最多?要做幾次除?法?(5次)gcd(5,8)習(xí)題1.21.(農(nóng)夫過(guò)河)P—農(nóng)夫W—狼G—山羊C—白菜2.(過(guò)橋問(wèn)題)1,2,5,10---分別代表4?個(gè)人,f—手電筒4.對(duì)于任意實(shí)?系數(shù)a,b,c,某個(gè)算法能?求方程ax?^2+bx+c=0的實(shí)根,寫出上述算?法的偽代碼?(可以假設(shè)s?qrt(x)是求平方根?的函數(shù))算法Qua?drati?c(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))/tempretur?nx1,x2elseifD=0retur?n–b/(2*a)elseretur?n“norealroots?”else//a=0ifb≠0retur?n–c/belse//a=b=0ifc=0retur?n“norealnumbe?rs”elseretur?n“norealroots?”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ù)第一步：用n除以2?，余數(shù)賦給K?i(i=0,1,2...)，商賦給n第二步：如果n=0，則到第三步?，否則重復(fù)第?一步第三步：將Ki按照?i從高到低?的順序輸出?b.偽代碼算法Decto?Bin(n)//將十進(jìn)制整?數(shù)n轉(zhuǎn)換為?二進(jìn)制整數(shù)?的算法//輸入：正整數(shù)n//輸出：該正整數(shù)相?應(yīng)的二進(jìn)制?數(shù)，該數(shù)存放于?數(shù)組Bin?[1...n]中i=1while?n!=0do{Bin[i]=n%2;n=(int)n/2;i++;}while?i!=0do{print?Bin[i];i--;}9.考慮下面這?個(gè)算法,它求的是數(shù)?組中大小相?差最小的兩?個(gè)元素的差?.(算法略)對(duì)這個(gè)算法?做盡可能多?的改進(jìn).算法MinDi?stanc?e(A[0..n-1])//輸入:數(shù)組A[0..n-1]//輸出:thesmall?estdista?ncedbetwe?entwoofitseleme?nts習(xí)題1.3考慮這樣一?個(gè)排序算法?,該算法對(duì)于?待排序的數(shù)?組中的每一?個(gè)元素,計(jì)算比它小?的元素個(gè)數(shù)?,然后利用這?個(gè)信息,將各個(gè)元素?放到有序數(shù)?組的相應(yīng)位?置上去.a.應(yīng)用該算法?對(duì)列表”60,35,81,98,14,47”排序b.該算法穩(wěn)定?嗎?c.該算法在位?嗎?解:a.該算法對(duì)列?表”60,35,81,98,14,47”排序的過(guò)程?如下所示:b.該算法不穩(wěn)?定.比如對(duì)列表?”2,2*”排序c.該算法不在?位.額外空間f?orSandCount?[]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?:a.Repla?cetheitheleme?ntwiththelasteleme?ntanddecre?asethearray?sizeof1b.Repla?cetheitheleme?ntwithaspeci?alsymbo?lthatcanno?tbeavalue?ofthearray?’seleme?nt(e.g.,0foranarray?ofposit?ivenumbe?rs)tomarktheithposit?ionisempty?.(“l(fā)azydelet?ion”)第2章習(xí)題2.17.對(duì)下列斷言?進(jìn)行證明:(如果是錯(cuò)誤?的,請(qǐng)舉例)a.如果t(n)∈O(g(n),則g(n)∈Ω(t(n))b.α>0時(shí),Θ(αg(n))=Θ(g(n))解:a.這個(gè)斷言是?正確的。它指出如果?t(n)的增長(zhǎng)率小?于或等于g?(n)的增長(zhǎng)率，那么g(n)的增長(zhǎng)率大?于或等于t?(n)的增長(zhǎng)率由t(n)≤c·g(n)foralln≥n0,where?c>0則：foralln≥n0b.這個(gè)斷言是?正確的。只需證明。設(shè)f(n)∈Θ(αg(n)),則有：foralln>=n0,c>0foralln>=n0,c1=cα>0即：f(n)∈Θ(g(n))又設(shè)f(n)∈Θ(g(n)),則有：foralln>=n0,c>0foralln>=n0,c1=c/α>0即：f(n)∈Θ(αg(n))8．證明本節(jié)定?理對(duì)于下列?符號(hào)也成立?：a.Ω符號(hào)b.Θ符號(hào)證明：a。weneedtoproof?thatift1(n)∈Ω(g1(n))andt2(n)∈Ω(g2(n)),thent1(n)+t2(n)∈Ω(max{g1(n),g2(n)})。由t1(n)∈Ω(g1(n))，t1(n)≥c1g1(n)foralln>=n1,where?c1>0由t2(n)∈Ω(g2(n))，T2(n)≥c2g2(n)foralln>=n2,where?c2>0那么，取c>=min{c1,c2},當(dāng)n>=max{n1,n2}時(shí)：t1(n)+t2(n)≥c1g1(n)+c2g2(n)≥cg1(n)+cg2(n)≥c[g1(n)+g2(n)]≥cmax{g1(n),g2(n)}所以以命題?成立。b.t1(n)+t2(n)∈Θ(證明：由大?的定義知，必須確定常?數(shù)c1、c2和n0?，使得對(duì)于所?有n>=n0，有： 由t1(n)∈Θ(g1(n))知，存在非負(fù)整?數(shù)a1,a2和n1?使：a1*g1(n)<=t1(n)<=a2*g1(n)-----(1)由t2(n)∈Θ(g2(n))知，存在非負(fù)整?數(shù)b1,b2和n2?使：b1*g2(n)<=t2(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)<=t1(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)<=t1(n)+t2(n)<=c2*2max(g1,g2)所以當(dāng)c1?＝min(a1,b1),c2＝2c2=2max(c1,c2)，n0＝max(n1,n2)時(shí)，當(dāng)n>=n0時(shí)上述?不等式成立?。證畢。習(xí)題2.4解下列遞推?關(guān)系（做a,b）當(dāng)n>1時(shí)a.當(dāng)n>1時(shí)解：當(dāng)n>1時(shí)b.當(dāng)n>1時(shí)解：對(duì)于計(jì)算n?!的遞歸算法?F(n)，建立其遞歸?調(diào)用次數(shù)的?遞推關(guān)系并?求解。解：考慮下列遞?歸算法，該算法用來(lái)?計(jì)算前n個(gè)?立方的和：S(n)=13+23+…+n3。算法S(n)//輸入：正整數(shù)n//輸出：前n個(gè)立方?的和ifn=1retur?n1elseretur?nS(n-1)+n*n*na.建立該算法?的基本操作?次數(shù)的遞推?關(guān)系并求解?b.如果將這個(gè)?算法和直截?了當(dāng)?shù)姆沁f?歸算法比，你做何評(píng)價(jià)?？解：a.7.a.請(qǐng)基于公式?2n=2n-1+2n-1，設(shè)計(jì)一個(gè)遞?歸算法。當(dāng)n是任意?非負(fù)整數(shù)的?時(shí)候，該算法能夠?計(jì)算2n的?值。b.建立該算法?所做的加法?運(yùn)算次數(shù)的?遞推關(guān)系并?求解c.為該算法構(gòu)?造一棵遞歸?調(diào)用樹，然后計(jì)算它?所做的遞歸?調(diào)用次數(shù)。d.對(duì)于該問(wèn)題?的求解來(lái)說(shuō)?，這是一個(gè)好?的算法嗎？解:a.算法pow?er(n)//基于公式2?n=2n-1+2n-1,計(jì)算2n//輸入:非負(fù)整數(shù)n?//輸出:2n的值Ifn=0retur?n1Elseretur?npower?(n-1)+power?(n-1)c.8.考慮下面的?算法算法Min1(A[0..n-1])//輸入:包含n個(gè)實(shí)?數(shù)的數(shù)組A?[0..n-1]Ifn=1retur?nA[0]Elsetemp←Min1(A[0..n-2])Iftemp≤A[n-1]retur?ntempElseretur?nA[n-1]a.該算法計(jì)算?的是什么?b.建立該算法?所做的基本?操作次數(shù)的?遞推關(guān)系并?求解解:a.計(jì)算的給定?數(shù)組的最小?值foralln>1nforalln>1n=19.考慮用于解?決第8題問(wèn)?題的另一個(gè)?算法,該算法遞歸?地將數(shù)組分?成兩半.我們將它稱?為Min2?(A[0..n-1])算法Min(A[r..l])Ifl=rretur?nA[l]Elsetemp1?←Min2(A[l..(l+r)/2])Temp2?←Min2(A[l..(l+r)/2]+1..r)Iftemp1?≤temp2?retur?ntemp1?Elseretur?ntemp2?a.建立該算法?所做的的操?作次數(shù)的遞?推關(guān)系并求?解b.算法Min?1和Min?2哪個(gè)更快??有其他更好?的算法嗎?解:a.習(xí)題2.6考慮下面的?排序算法,其中插入了?一個(gè)計(jì)數(shù)器?來(lái)對(duì)關(guān)鍵比?較次數(shù)進(jìn)行?計(jì)數(shù).算法Sor?tAnal?ysis(A[0..n-1])//input?:包含n個(gè)可?排序元素的?一個(gè)數(shù)組A?[0..n-1]//outpu?t:所做的關(guān)鍵?比較的總次?數(shù)count?←0fori←1ton-1dov←A[i]j←i-1while?j>0andA[j]>vdocount?←count?+1A[j+1]←A[j]j←j+1A[j+1]←vretur?ncount?比較計(jì)數(shù)器?是否插在了?正確的位置??如果不對(duì),請(qǐng)改正.解:應(yīng)改為:算法Sor?tAnal?ysis(A[0..n-1])//input?:包含n個(gè)可?排序元素的?一個(gè)數(shù)組A?[0..n-1]//outpu?t:所做的關(guān)鍵?比較的總次?數(shù)count?←0fori←1ton-1dov←A[i]j←i-1while?j>0andA[j]>vdocount?←count?+1A[j+1]←A[j]j←j+1ifj>=0count?=count?+1A[j+1]←vretur?ncount?習(xí)題3.14.a.設(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è)比線性?效率還要好?的算法呢?解:Algor?ithms?Brute?Force?Polyn?omial?Evalu?ation?(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]*power?retur?np算法效率分?析:基本操作:兩個(gè)數(shù)相乘?,且M(n)僅依賴于多?項(xiàng)式的階n?thaabove?algor?ithms?isveryineff?icien?t,becau?sewerecom?putepower?sofxagain?andagain?asifthere?werenorelat?ionsh?ipamong?them.Infact,wecanmovefromthelowes?ttermtothehighe?standcompu?texibyusing?xi-1.Algor?ithms?Bette?rBrut?eForc?ePoly?nomia?lEval?uatio?n(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]*power?retur?np基本操作乘?法運(yùn)算總次?數(shù)M(n):c.不行.因?yàn)橛?jì)算任?意一個(gè)多項(xiàng)?式在任意點(diǎn)?x的值,都必須處理?它的n+1個(gè)系數(shù).例如:(x=1,p(x)=an+an-1+..+a1+a0,至少要做n?次加法運(yùn)算?)5.應(yīng)用選擇排?序?qū)π蛄衑?xampl?e按照字母?順序排序.6.選擇排序是?穩(wěn)定的嗎?(不穩(wěn)定)7.用鏈表實(shí)現(xiàn)?選擇排序的?話,能不能獲得?和數(shù)組版相?同的Θ(n2)效率?Yes.Bothopera?tion—findi?ngthesmall?esteleme?ntandswapp?ingit–canbedoneaseffic?ientl?ywiththelinke?dlistaswithanarray?.9.a.請(qǐng)證明,如果對(duì)列表?比較一遍之?后沒(méi)有交換?元素的位置?,那么這個(gè)表?已經(jīng)排好序?了,算法可以停?止了.b.結(jié)合所做的?改進(jìn),為冒泡排序?寫一段偽代?碼.c.請(qǐng)證明改進(jìn)?的算法最差?效率也是平?方級(jí)的.Hints?:第i趟冒泡?可以表示為?:如果沒(méi)有發(fā)?生交換位置?,那么:b.Algor?ithms?Bette?rBubb?lesor?t(A[0..n-1])//用改進(jìn)的冒?泡算法對(duì)數(shù)?組A[0..n-1]排序//輸入:數(shù)組A[0..n-1]//輸出:升序排列的?數(shù)組A[0..n-1]count?←n-1//進(jìn)行比較的?相鄰元素對(duì)?的數(shù)目flag←true//交換標(biāo)志while?flagdoflag←false?fori=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è)成功查?找的概率是?p(0<=p<=1)Hints?:Cwors?t(n)=n+1在成功查找?下,對(duì)于任意的?I,第一次匹配?發(fā)生在第i?個(gè)位置的可?能性是p/n,比較次數(shù)是?i.在查找不成?功時(shí),比較次數(shù)是?n+1,可能性是1?-p.6.給出一個(gè)長(zhǎng)?度為n的文?本和長(zhǎng)度為?m的模式構(gòu)?成的實(shí)例,它是蠻力字?符串匹配算?法的一個(gè)最?差輸入.并指出,對(duì)于這樣的?輸入需要做?多少次字符?比較運(yùn)算.Hints?:文本:由n個(gè)0組?成的文本模式:前m-1個(gè)是0,最后一個(gè)字?符是1比較次數(shù):m(n-m+1)7.為蠻力字符?匹配算法寫?一個(gè)偽代碼?,對(duì)于給定的?模式,它能夠返回?給定的文本?中所有匹配?子串的數(shù)量?.Algor?ithms?BFStr?ingma?tch(T[0..n-1],P[0..m-1])//蠻力字符匹?配//輸入:數(shù)組T[0..n-1]—長(zhǎng)度為n的?文本,數(shù)組P[0..m-1]—長(zhǎng)度為m的?模式//輸出:在文本中匹?配成功的子?串?dāng)?shù)量count?←0fori←0ton-mdoj←0while?j<mandP[j]=T[i+j]j←j+1ifj=mcount?←count?+1retur?ncount?8.如果所要搜?索的模式包?含一些英語(yǔ)?中較少見(jiàn)的?字符,我們應(yīng)該如?何修改該蠻?力算法來(lái)利?用這個(gè)信息?.Hint:每次都從這?些少見(jiàn)字符?開始比較,如果匹配,則向左邊和?右邊進(jìn)行其?它字符的比?較.習(xí)題4.11.a.為一個(gè)分治?算法編寫偽?代碼,該算法求一?個(gè)n個(gè)元素?數(shù)組中最大?元素的位置?.b.如果數(shù)組中?的若干個(gè)元?素都具有最?大值,該算法的輸?出是怎樣的?呢?c.建立該算法?的鍵值比較?次數(shù)的遞推?關(guān)系式并求?解.d.請(qǐng)拿該算法?與解同樣問(wèn)?題的蠻力算?法做一個(gè)比?較解:a.Algor?ithms?MaxIn?dex(A[l..r]){Input?:Aporti?onofarray?A[0..n-1]betwe?enindic?eslandr(l≤r)Outpu?t:Theindex?ofthelarge?steleme?ntinA[l..r]ifl=rretur?nlelsetemp1?←MaxIn?dex(A[l..(l+r)/2])temp2?←MaxIn?dex(A[(l+r)/2..r])ifA[temp1?]≥A[temp2?]retur?ntemp1?elseretur?ntemp2?}b.返回?cái)?shù)組中?位于最左邊?的最大元素?的序號(hào).c.鍵值比較次?數(shù)的遞推關(guān)?系式:C(n)=C(n/2)+C(n/2)+1forn>1C(1)=0設(shè)n=2k，C(2k)=2C(2k-1)+1=2[2C(2k-2)+1]+1=22C(2k-2)+2+1=2[22C(2k-3)+1]+2+1=23C(2k-3)+22+2+1=...=2iC(2k-i)+2i-1+2i-2+...+2+1=...=2kC(2k-k)+2k-1+2k-2+...+2+1=2k－1=n-1可以證明C?(n)=n-1對(duì)所有n?>1的情況都?成立（n是偶數(shù)或?奇數(shù)）d.比較的次數(shù)?相同，但蠻力算法?不用遞歸調(diào)?用。2、a.為一個(gè)分治?算法編寫偽?代碼，該算法同時(shí)?求出一個(gè)n?元數(shù)組的最?大元素和最?小元素的值?。b.請(qǐng)拿該算法?與解同樣問(wèn)?題的蠻力算?法做一個(gè)比?較。c.請(qǐng)拿該算法?與解同樣問(wèn)?題的蠻力算?法做一個(gè)比?較。解答：a.同時(shí)求出最?大值和最小?值，只需要將原?數(shù)組一分為?二，再使用相同?的方法找出?這兩個(gè)部分?中的最大值?和最小值，然后經(jīng)過(guò)比?較就可以得?到整個(gè)問(wèn)題?的最大值和?最小值。算法MaxMi?n(A[l..r],Max,Min)//該算法利用?分治技術(shù)得?到數(shù)組A中?的最大值和?最小值//輸入：數(shù)值數(shù)組A?[l..r]//輸出：最大值Ma?x和最小值?Minif(r=l)Max←A[l]；Min←A[l];//只有一個(gè)元?素時(shí)elseifr－l=1//有兩個(gè)元素?時(shí)ifA[l]≤A[r]Max←A[r];Min←A[l] elseMax←A[l];Min←A[r] else//r－l>1MaxMi?n(A[l,(l+r)/2],Max1,Min1);//遞歸解決前?一部分MaxMi?n(A[(l+r/)2..r],Max2,Min2);//遞歸解決后?一部分ifMax1＜Max2Max=Max2//從兩部分的?兩個(gè)最大值?中選擇大值?ifMin2<Min1Min=Min2;//從兩部分的?兩個(gè)最小值?中選擇小值?}b.假設(shè)n=2k,比較次數(shù)的?遞推關(guān)系式?:C(n)=2C(n/2)+2forn>2C(1)=0,C(2)=1C(n)=C(2k)=2C(2k-1)+2=2[2C(2k-2)+2]+2=22C(2k-2)+22+2=22[2C(2k-3)+2]+22+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,2k=n=n/2+n-2=3n/2－2b.蠻力法的算?法如下：算法simpl?eMaxM?in(A[l..r])//用蠻力法得?到數(shù)組A的?最大值和最?小值//輸入：數(shù)值數(shù)組A?[l..r]//輸出：最大值Ma?x和最小值?MinMax=Min=A[l];fori=l+1tordoifA[i]>MaxMax←A[i];elseifA[i]<MinMin←A[i]retur?nMax,Min}時(shí)間復(fù)雜度?t(n)=2(n-1)算法Max?Min的時(shí)?間復(fù)雜度為?3n/2-2，simpl?eMaxM?in的時(shí)間?復(fù)雜度為2?n-2，都屬于Θ(n)，但比較一下?發(fā)現(xiàn)，MaxMi?n的速度要?比simp?leMax?Min的快?一些。6.應(yīng)用合并排?序?qū)π蛄蠩?,X,A,M,P,L,E按字母順?序排序.3213218.a.對(duì)合并排序?的最差鍵值?比較次數(shù)的?遞推關(guān)系式?求解.(forn=2k)b.建立合并排?序的最優(yōu)鍵?值比較次數(shù)?的遞推關(guān)系?式求解.(forn=2k)c.對(duì)于4.1節(jié)給出的?合并排序算?法,建立它的鍵?值移動(dòng)次數(shù)?的遞推關(guān)系?式.考慮了該算?法的鍵值移?動(dòng)次數(shù)之后?,是否會(huì)影響?它的效率類?型呢?解:遞推關(guān)系式?見(jiàn)4.1節(jié).最好情況(列表升序或?降序)下:Cbest?(n)=2Cbes?t(n/2)+n/2forn>1(n=2k)Cbest?(1)=0鍵值比較次?數(shù)M(n)M(n)=2M(n)+2nforn>1M(1)=0習(xí)題4.21.應(yīng)用快速排?序?qū)π蛄蠩?,X,A,M,P,L,E按字母順?序排序請(qǐng)舉一個(gè)n?個(gè)元素?cái)?shù)組?的例子,使得我們有?必須對(duì)它使?用本節(jié)提到?的”限位器”.限位器的值?應(yīng)是多少年?來(lái)?為什么一個(gè)?限位器就能?滿足所有的?輸入呢?Hints?:Withthepivot?being?theleftm?osteleme?nt,theleft-to-right?scanwillgetoutofbound?sifandonlyifthepivot?islarge?rthantheother?eleme?nts.Appen?dingasenti?nel(限位器)ofvalue?equal?A[0](orlarge?rthanA[0])after?thearray?’slasteleme?nt,thequick?sortalgor?ithms?willstoptheindex?oftheleft-to-right?scanofA[0..n-1]fromgoing?beyon?dposit?ionn.8.設(shè)計(jì)一個(gè)算?法對(duì)n個(gè)實(shí)?數(shù)組成的數(shù)?組進(jìn)行重新?排列,使得其中所?有的負(fù)元素?都位于正元?素之前.這個(gè)算法需?要兼顧空間?和時(shí)間效率?.Algor?ithms?netbe?forep?os(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-1While?i<jdo While?A[i]≤0do i←i+1 while?A[j]≥0do j←j-1 swapA[i]andA[j]swapA[i]andA[j]//undothelastswap當(dāng)全是非負(fù)?數(shù)或全是非?正數(shù)時(shí)需要?限位器.習(xí)題4.31.(題略)解:a.由公式4.4得:4次b.二分查找判?定樹:所以,14,31,42,74,85,98需要比?較4次c.d.當(dāng)n=2k時(shí),用反向替換?法求下面的?遞推方程:當(dāng)n>1時(shí),Cw(n)=Cw(n/2)+1,Cw(1)=1(略)4.如果對(duì)于一?個(gè)1000?00個(gè)元素?的數(shù)組成功?查找的話,使用折半查?找比順序查?找要快多少?倍?如何將折半?查找應(yīng)用于?范圍查找?范圍查找就?是對(duì)于一個(gè)?有序數(shù)組,找出位于給?定值L、U之間（包含L、U）的所有元素?，L<=U。該算法的最?差效率是多?少？Hints?:Step1?:檢查A[0]≤L，A[n-1]≥U是否成立?，若不成立，則無(wú)解。否則進(jìn)入s?tep2Step2?:在數(shù)組A中?用二分查找?法查找值L?，如果查找成?功，則返回?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和h?igh是s?tep2和?step3?的值。）為折半查找?寫遞歸的偽?代碼。Algor?ithms?BSR(A[o..n-1],K)//折半查找遞?歸算法//有序子數(shù)組?A[l..r]和查找鍵值?K//查找成功則?輸出其下標(biāo)?，否則輸出-1ifl>rretur?n-1elsem←(l+r)/2 ifK=A[m]retur?nm elseifK<A[m]retur?nBSR(A[l..m-1],K) elseifK>A[m]retur?nBSR(A[m+1,r],K)8.設(shè)計(jì)一個(gè)只?使用兩路比?較的折半查?找算法，即只用≤和=,或者只用≥和=.Algor?ithms?TwoWa?ysBin?arySe?arch(A[o..n-1],K)//二路比較的?折半查找//有序子數(shù)組?A[l..r]和查找鍵值?K//查找成功則?輸出其下標(biāo)?，否則輸出-1l←0,r←n-1while?l<rdom←(l+r)/2 ifK≤A[m]r←m elsel←m+1ifK=A[l]retur?nlelseretur?n-1習(xí)題4.4設(shè)計(jì)一個(gè)分?治算法來(lái)計(jì)?算二叉樹的?層數(shù).(空樹返回0?,單頂點(diǎn)樹返?回1),并分析效率?類型.Algor?ithms?Level?(TreeT)//遞歸計(jì)算二?叉樹的層數(shù)?//輸入:二叉樹T//輸出:二叉樹T的?層數(shù)IfT=NULLretur?n0Elseretur?nmax{Level?(TL),Level?(TR)}+1算法效率類?型是Θ(n)(同4.4節(jié)算法h?eight?(T))2.選擇一個(gè)二?叉樹的經(jīng)典?遍歷算法(前\中\(zhòng)后序),寫出它的遞?歸偽代碼,并求它的遞?歸調(diào)用次數(shù)?.Algor?ithms?preor?der(T)//先序遍歷二?叉樹T//輸入:二叉樹T//輸出:先序遍歷的?結(jié)點(diǎn)序列表?IfT≠NULLVisit?T’srootPreor?der(TL)Preor?der(TR)遞歸調(diào)用次?數(shù)C(n)=擴(kuò)展樹中內(nèi)?部結(jié)點(diǎn)+外部結(jié)點(diǎn)=n+(n+1)=2n+17.設(shè)計(jì)一個(gè)算?法計(jì)算有根?有序樹的高?度.Algor?ithms?heigh?t(T)//遞歸計(jì)算有?根有序樹的?高度//輸入:一棵有根有?序樹的高度?T//輸出:T的高度i=NumCh?ildre?n(T)//根的孩子個(gè)?數(shù)ifi=0retur?n0elseretur?nmax{heigh?t(T1),heigh?t(T2),…,heigh?t(Ti)}+18.下面的算法?試圖計(jì)算一?棵二叉樹中?葉子的數(shù)量?Algor?ithms?LeafC?ount(T)//遞歸計(jì)算二?叉樹中葉子?的數(shù)量//輸入:一棵二叉樹?//輸出:T中葉子的?數(shù)量ifT=NULLretur?n0elseretur?nLeafC?ount(TL)+LeafC?ount(TR)應(yīng)為:ifT=NULLretur?n0//empty?treeelseifTL=NULLANDTR=NULLretur?n1//singl?e-nodetreeelseretur?nLeafC?ount(TL)+LeafC?ount(TR)//gener?alcase習(xí)題4.61.a.為最近對(duì)問(wèn)?題的一維版?本設(shè)計(jì)一個(gè)?直接基于分?治技術(shù)的算?法,并確定它的?效率類型b.對(duì)于這個(gè)問(wèn)?題,它是一個(gè)好?算法嗎?解:Algor?ithms?Close?stNum?ber(A[l..r])//分治計(jì)算最?近對(duì)問(wèn)題的?一維版本//輸入:升序排列的?實(shí)數(shù)子數(shù)組?A[l..r]//輸出:最近數(shù)對(duì)的?距離Ifr=lretur?n∞Elseifr－l=1retur?nA[r]－A[l]Elseretur?nmin{Close?stNum?ber(A[l…(l+r)/2]), Close?stNum?ber(A[(l+r)/2...r]) A[(l+r)/2+1]－A[(l+r)/2]}設(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ù)組?中最小元素?的位置.b.確定該算法?的時(shí)間效率?,然后把它與?該問(wèn)題的蠻?力算法作比?較Algor?ithms?MinLo?catio?n(A[0..n-1])//findthelocat?ionofthesmall?esteleme?ntinagiven?array?//anarray?A[0..n-1]ofrealnumbe?rs//Anindex?ofthesmall?esteleme?ntinA[0..n-1]ifn=1retur?n0elsetemp←MinLo?catio?n(A[0..n-2])ifA[temp]<A[n-1]retur?ntempelseretur?nn-1時(shí)間效率分?析見(jiàn)習(xí)題2?.4中8C(n)=C(n-1)+1forn>1C(1)=04.應(yīng)用插入排?序?qū)π蛄衑?xampl?e按照字母?順序排序5.a.對(duì)于插入排?序來(lái)說(shuō),為了避免在?內(nèi)部循環(huán)的?每次迭代時(shí)?判斷邊界條?件j>=0,應(yīng)該在待排?序數(shù)組的第?一個(gè)元素前?放一個(gè)什么?樣的限位器??b.帶限位器版?本和原版本?的效率類型?相同嗎?解:a.應(yīng)該在待排?序數(shù)組的第?一個(gè)元素前?放-∞或者小于等?于最小元素?值的元素.效率類型相?同.對(duì)于最差情?況(數(shù)組是嚴(yán)格?遞減):7.算法Ins?ertSo?rt2(A[0..n-1])fori←1ton-1doj←i-1while?j>=0andA[j]>A[j+1]doswap(A[j],A[j+1])j←j+1分析:在教材中算?法Inse?rtSor?t的內(nèi)層循?環(huán)包括一次?鍵值賦值和?一次序號(hào)遞?減,而算法In?sertS?ort2的?內(nèi)層循環(huán)包?括一次鍵值?交換和一次?序號(hào)遞減,設(shè)一次賦值?和一次序號(hào)?遞減的時(shí)間?分別為ca?和cd,那么算法I?nsert?Sort2?和算法In?sertS?ort運(yùn)行?時(shí)間的比率?是(3ca+cd)/(ca+cd)習(xí)題5.21.a.(略)b.4.習(xí)題5.31.DFS的棧?狀態(tài):退棧順序:efgbc?ad拓?fù)渑判?dacbg?feb.這是一個(gè)有?環(huán)有向圖.DFS從a出發(fā),…,遇到一條從?e到a的回?邊.4.能否利用頂?點(diǎn)進(jìn)入DF?S棧的順序?(代替它們從?棧中退出的?順序)來(lái)解決拓?fù)?排序問(wèn)題?Hints?:不能.對(duì)第1題中?的有向圖應(yīng)?用源刪除算?法.拓?fù)湫蛄?dabcg?ef習(xí)題5.44.下面是生成?排列的B.Heap算?法.算法Hea?pPerm?ute(n)//實(shí)現(xiàn)生成排?列的Hea?p算法//輸入:一個(gè)正整數(shù)?n和一個(gè)全?局?jǐn)?shù)組A[1..n]//輸出:A中元素的?全排列Ifn=1Write?AElseFori←1tondoHeapP?ermut?e(n-1)IfnisoddSwapA[1]andA[n]ElseswapA[i]andA[n]對(duì)于n=2,3,4的情況,手工跟蹤該?算法.解:對(duì)于n=2fori=1

doheapp?ermut?e(1）{write?A即12}這時(shí)nnotodd,sodoA[1]與A[2]互換，A=21fori=2doheapp?ermut?e(1）{write?A即21}對(duì)于n=3Fori=1doHeapp?ermut?e(2){heapp?ermut?e(1)write?A即123這時(shí)2notodd,so,doA[1]與A[2]互換，A=213heapp?ermut?e(1)write?A即213這時(shí)2notodd,doA[2]與A[2]互換，A=213}由于3isodd,sodoA[1]與A[3]互換,A=312Fori=2doHeapp?ermut?e(2){heapp?ermut?e(1)write?A即312這時(shí)2notodd,so,doA[1]與A[2]互換，A=132heapp?ermut?e(1)write?A即132這時(shí)2notodd,doA[2]與A[2]互換，A=231}由于3isodd,sodoA[1]與A[3]互換,A=231Fori=3doHeapp?ermut?e(2){heapp?ermut?e(1)write?A即231這時(shí)2notodd,so,doA[1]與A[2]互換，A=321heapp?ermut?e(1)write?A即321這時(shí)2notodd,doA[2]與A[2]互換，A=321}由于3isodd,sodoA[1]與A[3]互換,A=123n=4的的情況?:習(xí)題5.52.Hints?:減常因子c.d.折半查找在?最壞情況下?的查找效率?是log2?n+1.而習(xí)題6.1hintsortthelistandthensimpl?yretur?nthen/2theleme?ntsofthesorte?dlist.效率:假設(shè)排序算?法的效率是?O(nlogn?),那么該算法?的效率是O?(nlogn?)+Θ(1)=O(nlogn?)3.hinta.初始化C=A∩B=Φforevery?eleme?ntaiinAdo(1<=i<=n)forevery?eleme?ntbjinB(1<=j<=m)Ifai=bjaddaitoCdelet?ebjfromB最差情況:C為空,比較的次數(shù)?是nm.b.方法一:排序集合A?Forevery?eleme?ntbjinB用二分查找?的辦法在A?中查找與b?j相匹配的?元素aIf查找成功AddatoC效率分析:假設(shè)排序的?效率是O(nlogn?),則該算法效?率O(nlogn?)+mO(logn)=(n+m)O(logn)方法二:首先對(duì)A和?B都分別排?序.然后對(duì)A和?B應(yīng)用合并?排序,只輸出它們?的公有元素?.效率分析:假設(shè)排序的?效率是O(nlogn?),則該算法效?率O(nlogn?)+O(mlogm?)+Θ(n+m)=O(slogs?)where?s=max{n,m}方法三:首先將A和?B合并為L(zhǎng)?排序L從左至右成?對(duì)掃描LIfLi=Li+1AddLitoCi←i+2效率分析:假設(shè)排序的?效率是O(nlogn?),則該算法效?率O((n+m)logn))+Θ(n+m)=O(slogs?)where?s=max{n,m}4.hinta.排序數(shù)組,然后返回它?的第一和最?后元素.假設(shè)排序的?效率是O(nlogn?),則該算法效?率O(nlogn?)+Θ(1)+Θ(1)=O(nlogn?)b.蠻力和分治?都是線性的?,所以優(yōu)于基?于預(yù)排序的?算法習(xí)題6.32.b.4.a.5.a.二叉查找樹?中最大值和?最小值分別?是樹中最右?邊和最左邊?的結(jié)點(diǎn).因此,從根開始,沿著向左的?路徑一直走?到這樣的結(jié)?點(diǎn):它的左孩子?為空.這個(gè)結(jié)點(diǎn)里?的值就是最?小值.同理,可以找到最?大值.最后,這兩個(gè)值做?一次減法運(yùn)?算即可.算法的效率?:Θ(logn)+Θ(logn)+Θ(1)=Θ(logn)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}5.a.設(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ì).效率分析:查找:Θ(n)交換并刪除?:Θ(1)+Θ(1)調(diào)整為堆:O(logn)b.設(shè)計(jì)一個(gè)算?法,在給定的堆?H中尋找并?刪除一個(gè)包?含給定值v?的元素,然后確定其?時(shí)間效率.Hints?:在H中順序?查找滿足條?件的第一個(gè)?元素H[i].H[i]與H[n]互換.刪除最后元?素堆規(guī)模降1?調(diào)整元素H?[n]使其滿足雙?親優(yōu)勢(shì)效率分析:查找:Θ(n)交換并刪除?:Θ(1)+Θ(1)調(diào)整為堆:O(logn)習(xí)題6.51.乘法總次數(shù)?M(n)加法總次數(shù)?A(n)習(xí)題7.13.假設(shè)列表的?可能值屬于?集合{a,b,c,d},用分布計(jì)數(shù)?算法對(duì)下面?的列表按照?字母順序排?序.b,c,d,c,b,a,a,b解:輸入A:b,c,d,c,b,a,a,b頻率:分布值:4.分布計(jì)數(shù)算?法是穩(wěn)定的?嗎?是穩(wěn)定的.因?yàn)樗惴◤?右至左掃描?輸入,等值元素也?是被從右至?左地放入排?序好的數(shù)組?里.習(xí)題7.2應(yīng)用Hor?spool?算法在下面?的文本中查?找模式BA?OBAB:BESS_?KNEW_?ABOUT?_BAOB?ABS解:字符移動(dòng)表?:匹配過(guò)程:4.用Hors?pool算?法在一個(gè)長(zhǎng)?度為n的文?本中查找一