算法設(shè)計與分析第二版課后習(xí)題及解答

算法設(shè)計與分析基礎(chǔ)課后練習(xí)答案

習(xí)題1.1

4.設(shè)計一個計算的算法，n是任意正整數(shù)。除了賦值和比較運(yùn)算，該算法只

能用到基本的四則運(yùn)算操作。

算法求IE」

〃輸入：一個正整數(shù)/2

〃輸出：。

stepl:a=l;

step2:若a*a<n轉(zhuǎn)step3,否則輸出a;

step3:a=a+l轉(zhuǎn)step2;

5.a.用歐幾里德算法求gcd(31415,14142k

b.用歐幾里德算法求gcd(31415,14142),比檢查min{m,n)和gcd(m,

n)間連續(xù)整數(shù)的算法快多少倍？請估算一下。

a.gcd(31415,14142)=gcd(14142,3131)=gcd(3131,1618)=gcd(1618,1513)=gcd(1513,

105)=gcd(1513,105)=gcd(105,43)=gcd(43,19)=gcd(19,5)=gcd(5,4)=gcd(4,1)

=gcd(l,0)=1.

b.有a可知計算gcd(31415,14142)歐幾里德算法做了11次除法。

連續(xù)整數(shù)檢測算法在14142每次迭代過程中或者做了一次除法，或者兩次除法，

因此這個算法做除法的次數(shù)鑒于1-14142和2?14142之間，所以歐幾里德算法

比此算法快1?14142/11=1300與2?14142/11?2600倍之間。

6.證明等式gcd(m,n)=gcd(n,mmodn)對每一對正整數(shù)m,n都成立.

Hint:

根據(jù)除法的定義不難證明：

?如果d整除u和v,那么d一定能整除u土v;

?如果d整除u,那么d也能夠整除u的任何整數(shù)倍ku.

對于任意一對正整數(shù)m,n,若d能整除m和n,那么d一定能整除n和r=mmod

n=m-qn;顯然，若d能整除n和r,也一定能整除m=r+qn和n。

數(shù)對(m,n)和(n,r)具有相同的公約數(shù)的有限非空集，其中也包括了最大公約

數(shù)。故gcd(m,故=gcd(n,r)

7.對于第一個數(shù)小于第二個數(shù)的一對數(shù)字，歐幾里得算法將會如何處理?該算法

在處理這種輸入的過程中，上述情況最多會發(fā)生幾次？

Hint:

對于任何形如0<=m<n的一對數(shù)字,Euclid算法在第一次疊代時交換m和n,即

gcd(m,n)=gcd(n,m)

并且這種交換處理只發(fā)生一次.

8.2.對于所有1401,11410的輸入，Euclid算法最少要做幾次除法？(1次)

b.對于所有14m,n410的輸入，Euclid算法最多要做幾次除法？(5次)

gcd(5,8)

習(xí)題1.2

1.(農(nóng)夫過河)

PggPwgwPwcwcPwgc

PwgcwcPwccpgcgpg

p—農(nóng)夫W—狼G一山羊c—白菜

2.(過橋問題)

川,22/,2,5,105,107,1,2,5,10

(0)(2)(3)(13)(15)(17)

7,1,2,5,105,107,1,5,101兒2

1,2,5,10--分別代表4個人，f一手電筒

4.對于任意實(shí)系數(shù)a,b,c,某個算法能求方程axA2+bx+c=0的實(shí)根，寫出上述算

法的偽代碼(可以假設(shè)sqrt(x)是求平方根的函數(shù))

算法Quadratic(a,b,c)

〃求方程axA2+bx+c=0的實(shí)根的算法

//輸入:實(shí)系數(shù)a,b,c

〃輸出：實(shí)根或者無解信息

Ifa*0

D*-b*b-4*a*c

IfD>0

temp-2*a

xl-(-b+sqrt(D))/temp

x2—(-b-sqrt(D))/temp

returnxl,x2

elseifD=0return-b/(2*a)

elsereturn“norealroots”

else//a=0

ifbw0return-c/b

else//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ù)的算法

輸入：一個正整數(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[l...n]中

i=l

whilen!=0do{

Bin[i]=n%2;

n=(int)n/2;

i++;

)

whilei!=0do{

printBin[i];

i—；

)

9.考慮下面這個算法，它求的是數(shù)組中大小相差最小的兩個元素的差.(算法略)

對這個算法做盡可能多的改進(jìn).

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

//輸入:數(shù)組A[0..n-1]

//輸出：thesmallestdistancedbetweentwoofitselements

dmin<—oo

fori0ton—2do

forji+lton—Ido

temp*—|A[i]—A\j]\

iftemp<dmin

dmin4—temp

returndmin

習(xí)題1.3

1.考慮這樣一個排序算法,該算法對于待排序的數(shù)組中的每一個元素，計算比它

小的元素個數(shù)，然后利用這個信息，將各個元素放到有序數(shù)組的相應(yīng)位置上

去.

forz?—0ton—1do

Count[i]*—0

fori0ton—2do

forz+lton—1do

ifA\i]<A[j]

Count[j]-Count[j]+1

elseCount[i]*—Count[i]+1

for2-0tori-1do

S[Count[i]]—A[i\

a.應(yīng)用該算法對列表”60,35,81,98,14,47”排序

b.該算法穩(wěn)定嗎？

c.該算法在位嗎？

解：

a.該算法對列表”60,35,81,98,14,47”排序的過程如下所示:

ArrayA[0..5]3581981447

InitiallyCount\]000000

Afterpassi=0County301100

Afterpassi=1Count[\12201

Afterpassi=2Count\\4301

Afterpassi=3Count\]501

Afterpassi=4Count\\02

FinalstateCount\\314502

ArrayS[0..5]|14|35|47|6()|817^

b.該算法不穩(wěn)定.比如對列表”2,2*”排序

c.該算法不在位.額外空間forSandCount[]

4.(古老的七橋問題)

第2章

習(xí)題2.1

7.對下列斷言進(jìn)行證明：(如果是錯誤的，請舉例)

a.如果t(n)€0(g(n),則g(n)EQ(t(n))

b.a>0時，O(ag(n))=0(g(n))

解：

a.這個斷言是正確的。它指出如果t(n)的增長率小于或等于g(n)的增長率，

那么g(n)的增長率大于或等于t(n)的增長率

由t(n)Wc?g(n)foral1n》nO,wherec>0

則：(-)z(n)<g(n)foralln>nO

c

b.這個斷言是正確的。只需證明e(ag(〃))=0(g(〃)),設(shè)(g(〃))=0(ag(〃))。

設(shè)f(n)￡?(ag(n)),則有:

/(n)<cagin')foralln>=nO,c>0

f(n)<cig(n)foralln>=nO,cl=ca>0

即：f(n)￡?(g(n))

又設(shè)f(n)￡€)(g(n)),則有:/(n)<cg(n)foralln>=n0,c>0

Q

f(n)<—ag(n)=cag(n)foral1n>=n0,cl=c/a>0

at

即：f(n)￡€)(ag(n))

8.證明本節(jié)定理對于下列符號也成立：

a.Q符號

b.。符號

證明：

a.weneedtoproofthatifti(n)€Q(gt(n))andt2(n)€￡2(g2(n)),then

ti(n)+tz(n)￡Q(max?(n),g2(n)})o

由3(n)￡Q(gi(n)),

ti(n)>c,gi(n)foral1n>=nl,wherecl>0

由tz(n)￡。(g2(n)),

T2(n)>c2g；(n)foral1n>=n2,wherec2>0

那么，取c>=min{cl,c2),當(dāng)n>=max{nl,n2)時：

ti(n)+t2(n)》ggi(n)+c2g2(n)

>cgj(n)+cg2(n)>c[g!(n)+g2(n)]

>cmax{g,(n),g2(n)}

所以以命題成立。

b.ti(n)+t2(n)￡€)(max(gl(〃),g2(〃)))

證明：由大?的定義知，必須確定常數(shù)cl、c2和nO,使得對于所有n>=nO,有:

clmax((gl(〃),g2(〃))</l(n)+r2(n)<max(gl(〃),g2(〃))

由3(n)￡0(gl(n))知，存在非負(fù)整數(shù)al,a2和nl使：

al*gl(n)<=ti(n)<=a2*gl(n)-----(1)

由t?(n)€0(g2(n))知，存在非負(fù)整數(shù)bl,b2和n2使：

bl*g2(n)<=t2(n)<=b2*g2(n)-----(2)

(1)+(2):

al*gl(n)+bl*g2(n)<=tl(n)+t2(n)<=a2*gl(n)+b2*g2(n)

令cl=min(al,bl),c2=max(a2,b2),則

Cl*(gl+g2)<=ti(n)+t2(n)<=c2(gl+g2)-----(3)

不失一般性假設(shè)max(gl(n),g2(n))=gl(n).

顯然,gl(n)+g2(n)<2gl(n),即gl+g2<2max(gl,g2)

又g2(n)>0,gl(n)+g2(n)>gl(n),即gl+g2>max(gl,g2).

則(3)式轉(zhuǎn)換為：

Cl*max(gl,g2)<=t,(n)+t2(n)<=c2*2max(gl,g2)

所以當(dāng)cl=min(al,bl),c2=2c2=2max(cl,c2),nO=max(nl,n2)時，當(dāng)n>=n0

時上述不等式成立。

證畢。

習(xí)題2.2

2.請用66。的非正式定義來判斷下列斷言是真還是假。

a.n(n+1)/2￡0(n3)b.n(n+1)/260(n2)

c.n(n+1)/2￡0(n3)d.n(n+1)/2￡。(n)

答：c假，其它真。

5.按照下列函數(shù)的增長次數(shù)對它們進(jìn)行排列(按照從低到高的順序)

(n-2)!,51g(n+lOO)10,22n,0.001n4+3n；+l,In2n,，3n.

(n-2)!€e((n-2)!),51g(n+1OO)10=501g(n+100)€0(logn),*二

淳尸€9(4”),0.0()In*+3n3+1€6(n4),In2n€0(log2n),>/n€

0(n^),3n€0(3n).Thelistofthesefunctionsorderedinincreasing

orderofgrowthlooksasfbllows:

51g(n+100)10,ln2n,y/n,0.00In4+3n:1+1,3n,22n,(n-2)!

答：

習(xí)題2.3

1.計算下列求和表達(dá)式的值。

a.1+3+54-7+...+999

b.2+4+8+16+…+1024

1&￡二ie.江】Hi+0

3"g-￡屋iJ工￡二1/*(*+1)

答

500500500

a1+3+5+7+...+999=匯(2￡-1)=￡1=2叫亞?500=250,00().

?=1G1?=1

500

(Orbyusingtheformulaforthesumofoddintegers:￡(2，-l)=50()，=

i=l

250,000.

Orbyusingtheformulaforthesumofthearitlnneticprogressionwith

5n

缶=1,a”=999,andn=5()0:=。+挈o=25()(XH))

1010

b.2+4+8+16+.??+1,024=￡h=匯2?一1=(211-1)-1=2,(M6.

i=li^)

(Orbyusingtheformulaforthesumofthegeometricserieswitha=2,

q=2,andn=9:M7=2^-^-=2,046.)

n+1

c￡l=(n+l)—3+l=n-L

i=3

n-kln+12z_x/

d.￡i=￡，-￡i=伊十】X葉&-3=a

i=3i=0i=0

n—1n—1n—1n—1

(八1)八

e.￡￡(￡+l)=￡(/+￡)=￡5+￡?=5=。驊工以+2

i=Oi=0i=0i=0

(n--l)n

nn

'―-11=3〃=9

f.2力+i=3￡3>=3[f#-1]=3[曰3-1」2

j二】j=lf=。

nnnnn

[)-n(n+

g.￡=與0=)乙/=?,>

i=lt=li-1~

yv(n+】>

h.￡屋i/￡(￡+i)=￡LG-米)

=(+—+)+(/_/)+…+(+-n)+(n-H+T)=1-^+T=^+T-

(Thisisaspecialcaseoftheso-calledtelescopingseries-seeAppendix

A—￡:,(七—%_i)=A-四一1?)

3.考慮下面的算法。

AlgorithmMysteryfn)

//Input:Anoniiegativeintegern

S-0

fori4-1tondo

S—S+￡*f

returnS

a.該算法求的是什么？

b.它的基本操作是什么？

C.該基本操作執(zhí)行了多少次？

d.該算法的效率類型是什么？

e.對該算法進(jìn)行改進(jìn)，或者設(shè)計一個更好的算法，然后指出它們的效率類

型。如果做不到這一點(diǎn)，請試著證明這是不可能做到的。

n

a.ComputesS(n)=￡9.

i=l

b.Multiplication(or.ifmultiplicationandadditionareassumedtotake

thesameamountoftime,eitherofthetwo).

c.C(n)=1=n.

d.C(n)=n€0(n).Sincethenumberofbitsb=[log2nJ+1%log2n

andhencen七*C(n)%26€。(沙).

e.Usetheformula￡產(chǎn)=“皆tocomputethesumin0(1)

t=i

time(whichassumesthatthetimeofarithmeticoperationsstayconstant

irrespectiveofthesizeoftheoperations'operands).

9.證明下面的公式：

可以使用數(shù)學(xué)歸納法，也可以像10歲的高斯一樣，用洞察力來解決該問題。這

個小學(xué)生長大以后成為有史以來最偉大的數(shù)學(xué)家之一。

數(shù)學(xué)歸納法:

Hereisaproofbymathematicalinductionthat￡i=叢等?forevery

positiveint^ern.

(i)Basisstep:Forn=l,￡￡=￡2=1andI=乂〒)=1.

i=li=lI21

n/八

(ii)Inductivestep:Assumethat匯i=1forapositiveintegern.

Weneedtoshowtliattheni=1n+十〃Thisisobtainedasfollows:

i=l

歲：玄￡+(71+1)=+(n+l)=中+】-26+】)(n+l)(n+2)

高斯的方法：

TheyoungGausscomputedthesum

1+2+...+99+100

bynoticingthatitcanbecomputedasthesumof50pairs,eachwiththe

sum101:

1+1(X)=2+99=…=50+51=101.

Hencetheentiresumisequalto50-101=5,()5().(Thewell-knownhistoric

anecdoteclaimsthathisteachergavethisassignmenttoaclasstokeep

theclassbusy.)TheGaussideacanbeeasilygeneralizedtoanarbitrary

nbyadding

=1+2+…+(7i—1)+n

and

5(x1)=+(n—1)+…+2+1

toobtain

25(n)=(n+l)nandhenceS(n)=?

習(xí)題2.4

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

a?Jx(〃)=x(〃一l)+5當(dāng)n>l時

'x(l)=0

解：

a.x(n)=x(n-1)+5forn>1,x(l)=0

x(n)=x(n-1)+5

=[x(n-2)+5]+5=x(n-2)+5?2

=\x(n-3)+5]+5-2=x(n-3)+5?3

=...

=x(n-i)+5-i

=...

=x(l)+5-(n—1)=5(n—1).

b.(x(n)=3x(n-l)當(dāng)口>1時

、⑴=4

Z?3o[+1=4+([)]=++GT￡)X=

?+(1￡)工=

???—

￡+(￡_或)工=5+[I+(￡_器)對=

z+Q_#)￡=i+k+Q-F)H]=

1+(1-￡)工=(和)工

(共=UJCJaA[os)I=(i)x4I<UjcgI+(￡/u)工=(u)工

I一真=1-水々=1-1+#=

必+…+/+R+I=/+…+/+R+0_/)工=

水+…+Z+L#+1+L/+Q-彳)工=

???

水+1Tz+l彳+(￡_我)]=*+廣式+Q.我+(￡-彳)同=

/+[_/+(]⑶工=水+]1_我+。_聲閉=

病+Q一必用=(/)工

(1=UJOJ3AJOS)[=⑴1*1<UJOJU+(z/u)工=(u)xp

,7-=?+-+Z+T+⑹工=

(I+u)u

,??_

U+…+億+)比)+(I+?-U)+(?-u)x=

???_

u+(1-u)+(g-u)+(g-u)r=u+(1-u)+[(g-□)+(￡-u)x]=

W+(I-U)+(g-u)x=u+[(I-U)+(z-u)x]=

〃+(1-U)N=(U)X

0=(o)x4o<uIOJ〃+(1-u)x=(u)xp

?LU￡*=⑴2i-u￡=

???—

(?一叫￡=

???_

(g-U)xeg=[(g-u)a?g]zg=

Uw

(2-)^ZS=[(2-)^e]E=

(I~口)穌=(u)x

I=(l)x4i<uJOJ(1-葭)”：=(u)xq

:樨

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

解：

2.C(n)=C(n-1)+1,C(0)=1(thereisacallbutnomultiplications

whenn=0).

C(n)=C(n—1)+1=[C(n-2)+1]+1=C(n—2)+2=...

=C(n—，)+￡=.??=(7(0)+ri=1+n.

3.考慮下列遞歸算法，該算法用來計算前n個立方的和：S(n)=13+23+…+n3。

算法S(n)

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

//輸出：前n個立方的和

ifn=lreturn1

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

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

b.如果將這個算法和直截了當(dāng)?shù)姆沁f歸算法比，你做何評價？

解：

a.LetAf(n)bethenumberofmultiplicationsmadebythealgorithm.

Wehavethefollowingrecurrencerelationforit:

Af(n)=M(n-1)+2,Af(l)=0.

\Vecansolveitbybackwardsubstitutions:

Af(n)=Af(n—1)+2

=\M(n-2)+2]+2=A/(n-2)+2+2

=[Af(n-3)+2]+2+2=Af(n-3)+2+2+2

—aaa

=M(n-i)+2i

-???

=M(l)+2(n-l)=2(n-1).

7.a.請基于公式2"=2e+21,設(shè)計一個遞歸算法。當(dāng)n是任意非負(fù)整數(shù)的時候,

該算法能夠計算20的值。

b.建立該算法所做的加法運(yùn)算次數(shù)的遞推關(guān)系并求解

c.為該算法構(gòu)造一棵遞歸調(diào)用樹，然后計算它所做的遞歸調(diào)用次數(shù)。

d.對于該問題的求解來說，這是一個好的算法嗎？

解:a.算法power(n)

〃基于公式2"=2"-'+2"-1,計算2"

//輸入:非負(fù)整數(shù)n

〃輸出:2"的值

Ifn=0return1

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

b.4(n)=24n-1)+1,A(0)=0.

4(n)=24(n-l)+l

=2[2A(n-2)4-1]4-1=22A(n-2)4-2+1

=22\2A(n-3)+1]+2+1=234n-3)+22+2+1

---?.?

=2U(n-i)+2i-1+2*-2+...+1

???

=2nA(0)+2n-1+2nt+...+1=2nt+2n7+...+1=2n—1.

c.

。(〃)=支2'=2n+[-1

/=0

8.考慮下面的算法

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

〃輸入:包含n個實(shí)數(shù)的數(shù)組A[0..n-1]

Ifn=lreturnA[0]

Elsetemp"-Mini(A[0..n-2])

Iftemp<A[n-1]returntemp

ElsereturnA[n-1]

a.該算法計算的是什么？

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

解：

a.計算的給定數(shù)組的最小值

fC(n-l)+lforalln>l

n=l

9.考慮用于解決第8題問題的另一個算法，該算法遞歸地將數(shù)組分成兩半.我們

將它稱為Min2(A[0..n-l])

算法Min(A[r..1])

Ifl=rreturnA[1]

Elsetempi*-Min2[1..Ll+r)/2l)

Temp2-Min2(A[1..^(1+r)川+1??r)

Iftempi<temp2returntempi

Elsereturntemp2

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

b.算法Mini和Min2哪個更快?有其他更好的算法嗎？

解：a.

C(n)=C([n/21)+C([n/2J)+1forn>1,C(l)=0.

Solvingitforn—2kbybackwardsul)stit.iit.ioiisyicklsthefollowing:

C(2fe)=2C(2fc-1)+1

=2[2C(2fc-2)+1]+1=22C(2fc-2)+2+1

=22[2C(2fe-3)+1]+2+1=23C(2fe-3)+224-2+1

—???

=2七(2*-*)+2,7+2*t+…+i

--???

=2fcC(2fc-fc)+2fc-1+2kt+...+l=2fc-l=n-l.

習(xí)題2.5

3.java的基本數(shù)據(jù)類型int和long的最大值分別是當(dāng)

n最小為多少的時候，第n個斐波那契數(shù)能夠使下面的類型溢出。

a.int類型b.long類型

a.ThequestionistofindthesmallestvalueofnsuchthatF(n)>231—1.

UsingtheformulaF(n)=roundedtothenearestintego-.weget

(approximately)thefollowinginequality:

-Upn>231-1or<t>n>西川-1).

V5

Aftertakingnaturallogarithmsofbotlihandsides,weobtain

w>If))”

In。

Thus,theanswerisn=47.

b.Similarly,wehavetofindthesmallestvalueofnsuditliatF(n)>

2^3-1.Thus,

力。”>2s3—1,or6>與2s3-1)

or.aftertakingnaturallogarithmsofbothhandsides,

In(兩嚴(yán)-1))心，

n>--------：------------x924

Thus,theanswerisn=93.

4.爬梯子假設(shè)每一步可以爬一個或兩格梯子，爬一部n格梯子一共可以用幾

種的不同方法？(例如，一部3格的梯子可以用三種不同的方法爬：1-1-1,

1-2和2-1)o

LetW(n}bethenumberofdifferentwaystoclimbann-stairstaircase.

IV(n-1)ofthemstartwithaone-stairclimbandW(n-2)ofthemstart

withatwo-stairclimb.Thus.

W(n)=W(n-1)+W(n-2)forn>3,卬(1)=1,W(2)=2.

Solvingthisrecurrenceeither“fromscratch**orbetteryetnoticingthat

thesolutionrunsonestepaheadofthecanonicalFibonaccisequenceF(n),

weobtainW(n)=F(n+1)forn>1.

6.改進(jìn)算法Fib,使它只需要e(1)的額外空間。

AlgorithmFib2(n)

//Computesthen-thFibonacciniunberusingjusttwovariables

//Input:Anonnegativeintegern

//Output:Then-thFibonaccinumber

u—0;”—1

fori—2tondo

vv+u

uv-u

ifn=0return0

elsereturnv

7.證明等式:

F(n—1)F(n)01,

forn>1.

F(n)F(n+1)11

答：數(shù)學(xué)歸納法證明

(i)Thevalidityoftheequalityforn=1followsimmediatelyfromthe

definitionoftheFibonaccisequence.

(ii)Assumethat

F(n—1)F(n)

forapositiveintegern.

F(n)F(n+1)

Weneedtoshowthatthen

.F(n)F(n+1)n+l

F(n+1)F(n+2)11

Indeed.

n+1n

01'01,,01

111111

?01'.F(n-1)F(n)F(n+1)'

11F(n)F(n+1)F(n+1)F(n+2)

習(xí)題2.6

1.考慮下面的排序算法，其中插入了一個計數(shù)器來對關(guān)鍵比較次數(shù)進(jìn)行計數(shù).

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

//input:包含n個可排序元素的一個數(shù)組A[0..n-1]

//output:所做的關(guān)鍵比較的總次數(shù)

count-0

fori-1ton-1do

v-A[i]

j-iT

whilej>0andA[j]>vdo

count—count+l

A[j+1]-A[j]

j-j+l

A[j+1]-v

returncount

比較計數(shù)器是否插在了正確的位置?如果不對，請改正.

解:應(yīng)改為：

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

//input:包含n個可排序元素的一個數(shù)組A[0..n-1]

“output:所做的關(guān)鍵比較的總次數(shù)

count-0

fori-1ton-1do

v—A[i]

j-i-1

whilej>0andA[j]>vdo

count*-count+l

A[j+1]-A[j]

j-j+1

ifj>=0count=count+l

A[j+1]~v

returncount

習(xí)題3.1

4.a.設(shè)計一個蠻力算法,對于給定的x°,計算下面多項(xiàng)式的值：

nn_1

P(x)=anx+an-iX+...+aiX+ao

并確定該算法的最差效率類型.

b.如果你設(shè)計的算法屬于O"),請你為該算法設(shè)計一個線性的算法.

C.對于該問題來說，能不能設(shè)計一個比線性效率還要好的算法呢？

解：

a.AlgorithmsBruteForcePolynomialEvaluation(P[0..n],x)

〃由高累到低累用蠻力法計算多項(xiàng)式P在給定點(diǎn)x的值

〃輸入:P[0..n]是多項(xiàng)式按低累到高惠的常系數(shù)，以及定值x

〃輸出：多項(xiàng)式P在給定點(diǎn)x的值

p=0.0

fori=nto0do

power=l

forj=ltoido

power=power*x

p=p+P⑴*power

returnp

算法效率分析：

基本操作：兩個數(shù)相乘，且M(n)僅依賴于多項(xiàng)式的階n

A“、?"(幾+1)C/2\

/=oj=\/=o2

b.thaabovealgorithmsisveryinefficient,becausewerecomputepowers

ofxagainandagainasiftherewerenorelationshipamongthem.In

fact,wecanmovefromthelowesttermtothehighestandcomputex'

byusingx7

AlgorithmsBetterBruteForcePolynomialEvalnation(P[0..n],x)

〃由高嘉到低量用蠻力法計算多項(xiàng)式p在給定點(diǎn)X的值

〃輸入:P[0..n]是多項(xiàng)式按低累到高暴的常系數(shù)，以及定值x

〃輸出：多項(xiàng)式P在給定點(diǎn)x的值

P=P[0]

power=l

fori—1tondo

power4-power*x

p-p+P[i]*power

returnp

基本操作乘法運(yùn)算總次數(shù)M(n):

M(〃)=E2=2ne。(〃)

>=i

C.不行.因?yàn)橛嬎闳我庖粋€多項(xiàng)式在任意點(diǎn)X的值，都必須處理它的n+1個系數(shù).

例如：(x=l,p(x)=a?+a?.1+..+a,+a0,至少要做n次加法運(yùn)算)

5.應(yīng)用選擇排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.

IEXAAfPLE

A|\XEMPLE

AE|MPLE

AEE|MPLX

AEEL|PMX

AEELM|PX

AEELMP

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

7.用鏈表實(shí)現(xiàn)選擇排序的話，能不能獲得和數(shù)組版相同的€)(n2)效率？

Yes.Bothoperation一findingthesmallestelementandswappingit-canbe

doneasefficientlywiththe1inkedlistaswithanarray.

8.應(yīng)用冒泡排序?qū)π蛄蠩,X,A,M,P,L,E按照字母順序排序.

E,X,A,M,P,L,E

?

EIX4—?AA/PLE

?

EAXIMPLE

EAMX二PLE

EAMPX」?LE

EAMPLX工E

EAMPLEn

?

E二AMPLE

?

AEMpXLE

AEMLP」?E

AEMLE1尸

??

AsE二MLE

AELM4E

AELE加

???

AIESLIE

AEE\L

?7?

AIEEIL

9.a.請證明，如果對列表比較一遍之后沒有交換元素的位置，那么這個表已經(jīng)排

好序了，算法可以停止了.

b.結(jié)合所做的改進(jìn),為冒泡排序?qū)懸欢蝹未a.

c.請證明改進(jìn)的算法最差效率也是平方級的.

Hints:

a.第i趟冒泡可以表示為：

.Ady.AjAji-i—iAji-iW...S4n-1

intheirfinalpositions

如果沒有發(fā)生交換位置,那么：

力oS41W…WA?’W力j+iW…W

b.AlgorithmsBetterBubblesort(A[0..n-1])

〃用改進(jìn)的冒泡算法對數(shù)組A[0..n-1]排序

〃輸入:數(shù)組A[0..n-1]

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

count-n-1〃進(jìn)行比較的相鄰元素對的數(shù)目

flag-true〃交換標(biāo)志

whileflagdo

flag—false

fori=0tocount-1do

ifA[i+l]<A[i]

swap(A[i],A[i+l])

flag-true

count*-count-1

C最差情況是數(shù)組是嚴(yán)格遞減的，那么此時改進(jìn)的冒泡排序會蛻化為原來的冒泡

排序.

10.冒泡排序是穩(wěn)定的嗎？(穩(wěn)定)

習(xí)題3.2

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

a.在最差情況下

b.在平均情況下.假設(shè)成功查找的概率是p(0<=p〈=l)

Hints:

a.C??rst(n)=n+l

b.在成功查找下，對于任意的I,第一次匹配發(fā)生在第i個位置的可能性是

p/n,比較次數(shù)是i.在查找不成功時，比較次數(shù)是n+1,可能性是1-p.

Ca?g(n)—[1,—+2?—I...+1-—+...4711—1+(71+1)-(1p)

nnnn

="[1+2+*...+i+...4n+(n+1)(1p)

n

=?*3+(n+I)("p)=")”l).

6.給出一個長度為n的文本和長度為m的模式構(gòu)成的實(shí)例，它是蠻力字符串匹配

算法的一個最差輸入.并指出，對于這樣的輸入需要做多少次字符比較運(yùn)算.

Hints:

文本：由n個0組成的文本

模式：前m-1個是0,最后一個字符是1

比較次數(shù)：m(n-m+l)

7.為蠻力字符匹配算法寫一個偽代碼，對于給定的模式，它能夠返回給定的文本

中所有匹配子串的數(shù)量.

AlgorithmsBFStringmatch(T[0..n-1],P[0..m-1])

〃蠻力字符匹配

//輸入:數(shù)組長度為n的文本，數(shù)組P[0..m-1]—長度為m的模式

〃輸出：在文本中匹配成功的子串?dāng)?shù)量

count-0

fori-0ton-mdo

j-o

whilej<mandP[j]=T[i+j]

j~j+l

ifj=m

count-count+1

returncount

8.如果所要搜索的模式包含一些英語中較少見的字符,我們應(yīng)該如何修改該蠻力

算法來利用這個信息.

Hint:每次都從這些少見字符開始比較，如果匹配，則向左邊和右邊進(jìn)行其它字

符的比較.

習(xí)題3.4

8.解釋一下如何對排序問題應(yīng)用窮舉查找，并確定這種算法的效率類型。

答：生成給定元素的一個排列，通過連續(xù)比較它們之間的元素，檢查他們是否符

合排序的要求。如果符合就停止，否則重新生成新的排列。

最差情況生成排列的個數(shù)是n!,每趟連續(xù)元素比較次數(shù)為n-1次。所以效率類

型為0(n!(n-1)).

9.幻方一個n階幻方是把從1到I?的整數(shù)填入一個n階方陣，每個整數(shù)只出現(xiàn)

一次，使得每一行，每一列，每一條主對角線的和都相等。

a.證明：如果一個n階幻方存在的話，所討論的和一定等于n(n?+l)/2。

答：令s為n階幻方的每一行的和。則把從1到n，的整數(shù)求和可得如下式子

n2(n2+1)

sn=1+2+…+〃，i.e.,sn=

2

由上式可得：

n(n2+1)

8=2

習(xí)題4.1

La.為一個分治算法編寫偽代碼，該算法求一個n個元素數(shù)組中最大元素的位置.

b.如果數(shù)組中的若干個元素都具有最大值,該算法的輸出是怎樣的呢？

c.建立該算法的鍵值比較次數(shù)的遞推關(guān)系式并求解.

d.請拿該算法與解同樣問題的蠻力算法做一個比較

解:a.

AlgorithmsMaxIndex(A[/..r]){

Input:AportionofarrayA[0..n-1]betweenindices1and

r(/<r)

Output:TheindexofthelargestelementinA[/..r]

ifl=rreturn1

elsetempi*-Maxindex(A[T.(T+f)/2])

ifA[tempi]>A[temp2]returntempi

elsereturntemp2

)

b.返回數(shù)組中位于最左邊的最大元素的序號.

c.鍵值比較次數(shù)的遞推關(guān)系式：

C(n)=C(Ln/b)+口1/2)+1forn>l

C(l)=0

設(shè)n=2k,C(2k)=2C(2k-1)+l

=2[2C(2k-2)+l]+l=22C(2k-2)+2+l

=2[22C(2*+l]+2+l=23C(2k-3)+22+2+l

=2((21)+2i-i+2i-2+…+2+1

=2kC(2k'k)+2k-1+2I+...+2+1=2=l=n-l

可以證明C(n)=n-1對所有n>l的情況都成立(n是偶數(shù)或奇數(shù))

d.比較的次數(shù)相同，但蠻力算法不用遞歸調(diào)用。

2、a.為一個分治算法編寫偽代碼，該算法同時求出一個n元數(shù)組的最大元素和最

小元素的值。

b.請拿該算法與解同樣問題的蠻力算法做一個比較。

c.請拿該算法與解同樣問題的蠻力算法做一個比較。

解答：

a.同時求出最大值和最小值，只需要將原數(shù)組一分為二，再使用相