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

本文格式為Word版，下載可任意編輯——算法設(shè)計(jì)與分析基礎(chǔ)課后習(xí)題答案（中文版）Program算法設(shè)計(jì)與分析基礎(chǔ)中文版答案

習(xí)題1.1

5..證明等式gcd(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ì)于任何形如00

temp←2*a

x1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturnx1,x2

elseifD=0return–b/(2*a)elsereturn“norealroots〞else//a=0

ifb≠0return–c/belse//a=b=0

ifc=0return“norealnumbers〞elsereturn“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ù)賦給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=1

whilen!=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

2

習(xí)題1.3

1.考慮這樣一個(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.該算法不在位.額外空間forSandCount[]4.(古老的七橋問(wèn)題)

3

習(xí)題1.4

1.請(qǐng)分別描述一下應(yīng)當(dāng)如何實(shí)現(xiàn)以下對(duì)數(shù)組的操作,使得操作時(shí)間不依靠數(shù)組的長(zhǎng)度.a.刪除數(shù)組的第i個(gè)元素(10時(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,wherec>0

1則：()t(n)?g(n)foralln≥n0

cb.這個(gè)斷言是正確的。只需證明?(?g(n))??(g(n)),?(g(n))??(?g(n))。設(shè)f(n)∈Θ(αg(n)),則有：

f(n)?c?g(n)foralln>=n0,c>0f(n)?c1g(n)foralln>=n0,c1=cα>0

即：f(n)∈Θ(g(n))

又設(shè)f(n)∈Θ(g(n)),則有：f(n)?cg(n)foralln>=n0,c>0

4

f(n)?c??g(n)?c1?g(n)foralln>=n0,c1=c/α>0

即：f(n)∈Θ(αg(n))

8．證明本節(jié)定理對(duì)于以下符號(hào)也成立：a.Ω符號(hào)b.Θ符號(hào)證明：

a。weneedtoproofthatift1(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,wherec1>0由t2(n)∈Ω(g2(n))，

T2(n)≥c2g2(n)foralln>=n2,wherec2>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)∈Θ(max(g1(n),g2(n)))

證明：由大?的定義知，必需確定常數(shù)c1、c2和n0，使得對(duì)于所有n>=n0，有：

c1max((g1(n),g2(n))?t1(n)?t2(n)?max(g1(n),g2(n))

由t1(n)∈Θ(g1(n))知，存在非負(fù)整數(shù)a1,a2和n1使：a1*g1(n)0，g1(n)+g2(n)>g1(n),即g1+g2>max(g1,g2)。則（3）式轉(zhuǎn)換為：

C1*max(g1,g2)=n0時(shí)上述不等式成立。證畢。

習(xí)題2.4

1.解以下遞推關(guān)系（做a,b）a.

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

5

b.??x(n)?3x(n?1)當(dāng)n>1時(shí)

?x(1)?4解：

2.對(duì)于計(jì)算n!的遞歸算法F(n)，建立其遞歸調(diào)用次數(shù)的遞推關(guān)系并求解。解：

3.考慮以下遞歸算法，該算法用來(lái)計(jì)算前n個(gè)立方的和：S(n)=13+23+…+n3。算法S(n)

//輸入：正整數(shù)n

//輸出：前n個(gè)立方的和ifn=1return1

elsereturnS(n-1)+n*n*n

a.建立該算法的基本操作次數(shù)的遞推關(guān)系并求解

b.假使將這個(gè)算法和直截了當(dāng)?shù)姆沁f歸算法比，你做何評(píng)價(jià)？解：a.

6

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.算法power(n)

//基于公式2n=2n-1+2n-1,計(jì)算2n//輸入:非負(fù)整數(shù)n//輸出:2n的值Ifn=0return1

Elsereturnpower(n-1)+power(n-1)

c.

7

C(n)??2i?2n?1?1ni?08.考慮下面的算法算法Min1(A[0..n-1])//輸入:包含n個(gè)實(shí)數(shù)的數(shù)組A[0..n-1]Ifn=1returnA[0]Elsetemp←Min1(A[0..n-2])Iftemp≤A[n-1]returntempElsereturnA[n-1]a.該算法計(jì)算的是什么?b.建立該算法所做的基本操作次數(shù)的遞推關(guān)系并求解解:a.計(jì)算的給定數(shù)組的最小值b.C(n)??C(n?1)?1foralln>1??0n=19.考慮用于解決第8題問(wèn)題的另一個(gè)算法,該算法遞歸地將數(shù)組分成兩半.我們將它稱為Min2(A[0..n-1])算法Min(A[r..l])Ifl=rreturnA[l]Elsetemp1←Min2(A[l..(l+r)/2])Temp2←Min2(A[l..(l+r)/2]+1..r)Iftemp1≤temp2returntemp1Elsereturntemp2a.建立該算法所做的的操作次數(shù)的遞推關(guān)系并求解b.算法Min1和Min2哪個(gè)更快?有其他更好的算法嗎?解:a.8

習(xí)題2.6

1.考慮下面的排序算法,其中插入了一個(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←0

fori←1ton-1dov←A[i]j←i-1

whilej>0andA[j]>vdocount←count+1A[j+1]←A[j]j←j+1A[j+1]←vreturncount

比較計(jì)數(shù)器是否插在了正確的位置?假使不對(duì),請(qǐng)改正.解:應(yīng)改為:

算法SortAnalysis(A[0..n-1])

//input:包含n個(gè)可排序元素的一個(gè)數(shù)組A[0..n-1]//output:所做的關(guān)鍵比較的總次數(shù)count←0

fori←1ton-1dov←A[i]j←i-1

whilej>0andA[j]>vdocount←count+1A[j+1]←A[j]j←j+1

ifj>=0count=count+1A[j+1]←vreturncount

9

習(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è)比線性效率還要好的算法呢?解:a.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)???1??i?i?0j?1i?0ninn(n?1)??(n2)2b.thaabovealgorithmsisveryinefficient,becausewerecomputepowersofxagainandagainasiftherewerenorelationshipamongthem.Infact,wecanmovefromthelowesttermtothehighestandcomputexibyusingxi-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)??2?2n??(n)i?1nc.不行.由于計(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ū)π蛄衑xample依照字母順序排序.10

6.選擇排序是穩(wěn)定的嗎?(不穩(wěn)定)

7.用鏈表實(shí)現(xiàn)選擇排序的話,能不能獲得和數(shù)組版一致的Θ(n2)效率?

Yes.Bothoperation—findingthesmallestelementandswappingit–canbedoneasefficientlywiththelinkedlistaswithanarray.

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]排序//輸入:數(shù)組A[0..n-1]

//輸出:升序排列的數(shù)組A[0..n-1]

count←n-1//進(jìn)行比較的相鄰元素對(duì)的數(shù)目flag←true//交換標(biāo)志whileflagdoflag←false

fori=0tocount-1doifA[i+1]swap(A[i],A[i+1])flag←truecount←count-1

c最差狀況是數(shù)組是嚴(yán)格遞減的,那么此時(shí)改進(jìn)的冒泡排序會(huì)蛻化為原來(lái)的冒泡排序.10.冒泡排序是穩(wěn)定的嗎?(穩(wěn)定)習(xí)題3.2

1.對(duì)限位器版的順序查找算法的比較次數(shù):

a.在最差狀況下

b.在平均狀況下.假設(shè)成功查找的概率是p(01C(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)題的最大值和最小值。算法MaxMin(A[l..r],Max,Min)//該算法利用分治技術(shù)得到數(shù)組A中的最大值和最小值//輸入：數(shù)值數(shù)組A[l..r]//輸出：最大值Max和最小值Minif(r=l)Max←A[l]；Min←A[l];//只有一個(gè)元素時(shí)

13

else

ifr－l=1//有兩個(gè)元素時(shí)

ifA[l]≤A[r]

Max←A[r];Min←A[l]

else

Max←A[l];Min←A[r]

else//r－l>1

MaxMin(A[l,(l+r)/2],Max1,Min1);//遞歸解決前一部分MaxMin(A[(l+r/)2..r],Max2,Min2);//遞歸解決后一部分

ifMax1＜Max2Max=Max2//從兩部分的兩個(gè)最大值中選擇大值ifMin22C(1)=0,C(2)=1

C(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－2

b.蠻力法的算法如下：算法simpleMaxMin(A[l..r])

//用蠻力法得到數(shù)組A的最大值和最小值//輸入：數(shù)值數(shù)組A[l..r]

//輸出：最大值Max和最小值MinMax=Min=A[l];fori=l+1tordo

ifA[i]>MaxMax←A[i];elseifA[i]1(n=2k)Cbest(1)=015

c.鍵值比較次數(shù)M(n)

M(n)=2M(n)+2nforn>1M(1)=0習(xí)題4.2

1.應(yīng)用快速排序?qū)π蛄蠩,X,A,M,P,L,E按字母順序排序

16

4.請(qǐng)舉一個(gè)n個(gè)元素?cái)?shù)組的例子,使得我們有必需對(duì)它使用本節(jié)提到的〞限位器〞.限位器的值應(yīng)是多少

年來(lái)?為什么一個(gè)限位器就能滿足所有的輸入呢?Hints:

Withthepivotbeingtheleftmostelement,theleft-to-rightscanwillgetoutofboundsifandonlyifthepivotislargerthantheotherelements.

Appendingasentinel(限位器)ofvalueequalA[0](orlargerthanA[0])afterthearray’slastelement,thequicksortalgorithmswillstoptheindexoftheleft-to-rightscanofA[0..n-1]fromgoingbeyondpositionn.

8.設(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-1Whilei1時(shí),Cw(n)=Cw(n/2)+1,Cw(1)=1(略)4.假使對(duì)于一個(gè)100000個(gè)元素的數(shù)組成功查找的話,使用折半查找比順序查找要快多少倍?6．如何將折半查找應(yīng)用于范圍查找?范圍查找就是對(duì)于一個(gè)有序數(shù)組,找出位于給定值L、U之間（包含L、U）的所有元素，Lrreturn-1elsem←(l+r)/2ifK=A[m]returnmelseifKA[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-1whilel

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.(題略)21

習(xí)題5.1

2.a.設(shè)計(jì)一個(gè)遞歸的減一算法,求n個(gè)實(shí)數(shù)構(gòu)成的數(shù)組中最小元素的位置.b.確定該算法的時(shí)間效率,然后把它與該問(wèn)題的蠻力算法作比較

AlgorithmsMinLocation(A[0..n-1])

//findthelocationofthesmallestelementinagivenarray//anarrayA[0..n-1]ofrealnumbers

//AnindexofthesmallestelementinA[0..n-1]ifn=1return0

elsetemp←MinLocation(A[0..n-2])

ifA[temp]時(shí)間效率分析見(jiàn)習(xí)題2.4中8C(n)=C(n-1)+1forn>1C(1)=0

4.應(yīng)用插入排序?qū)π蛄衑xample依照字母順序排序

5.a.對(duì)于插入排序來(lái)說(shuō),為了避免在內(nèi)部循環(huán)的每次迭代時(shí)判斷邊界條件j>=0,應(yīng)當(dāng)在待排序數(shù)組的第一個(gè)元素前放一個(gè)什么樣的限位器?

b.帶限位器版本和原版本的效率類型一致嗎?

解:a.應(yīng)當(dāng)在待排序數(shù)組的第一個(gè)元素前放-∞或者小于等于最小元素值的元素.b.效率類型一致.對(duì)于最差狀況(數(shù)組是嚴(yán)格遞減):

7.算法InsertSort2(A[0..n-1])fori←1ton-1do

j←i-1

whilej>=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í)間的比率是(3ca+cd)/(ca+cd)

22

習(xí)題5.21.a.(略)b.

4.

習(xí)題5.31.

DFS的棧狀態(tài):

退棧順序:efgbcad拓?fù)渑判?dacbgfeb.

23

這是一個(gè)有環(huán)有向圖.DFS從a出發(fā),?,遇到一條從e到a的回邊.

4.能否利用頂點(diǎn)進(jìn)入DFS棧的順序(代替它們從棧中退出的順序)來(lái)解決拓?fù)渑判騿?wèn)題?Hints:不能.

5.對(duì)第1題中的有向圖應(yīng)用源刪除算法.

拓?fù)湫蛄?dabcgef

24

習(xí)題5.4

4.下面是生成排列的B.Heap算法.算法HeapPermute(n)

//實(shí)現(xiàn)生成排列的Heap算法

//輸入:一個(gè)正整數(shù)n和一個(gè)全局?jǐn)?shù)組A[1..n]//輸出:A中元素的全排列

Ifn=1WriteAElse

Fori←1tondoHeapPermute(n-1)Ifnisodd