算法設計與分析課后習題解答

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

習題1.1

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

能用到基本的四則運算操作。

算法求1d

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

//金：o

stepl:a=l；

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

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

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

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(1,

0)=1.

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

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

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

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

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,n)=gcd(n,r)

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

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

Hint:

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

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

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

8a對于所有iWm,nW10的輸入,Euclid算法最少要做幾次除法?(1次)

b.對于所有l(wèi)Wm,nW10的輸入,Euclid算法最多要做幾次除法?(5次)

gcd(5,8)

習題1.2

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

PggPwgwPwcwcPwgc

PwgcWcPwCCPgcgPg

P—農(nóng)夫W—狼G—山羊C—白菜

2.(過橋問題)

7,1,227,2,5,105,107,1,2,5,10

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

兒2,5,105,101,5,101力,2

1,2,5,10…分別代表4個人,J手電筒

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

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

算法Quadratic(a,b,c)

〃求方程axA2+bx+c=0的實根的算法

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

〃輸出:實根或者無解信息

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

ifbWOreturn-c/b

else//a=b=0

ifc=0returnunorealnumbersM

elsereturn“norealroots”

5.描述將十進制整數(shù)表達為二進制整數(shù)的標準算法

a.用文字描述

b.用偽代碼描述

解答：

a.將十進制整數(shù)轉(zhuǎn)換為二進制整數(shù)的算法

輸入：一個正整數(shù)n

輸出：正整數(shù)n相應的二進制數(shù)

第一步：用n除以2,余數(shù)賦給Ki(i=0,l,2...),商賦給n

第二步：如果n=0,則到第三步，否則重復第一步

第三步：將Ki按照i從高到低的順序輸出

b.偽代碼

算法DectoBin(n)

〃將十進制整數(shù)n轉(zhuǎn)換為二進制整數(shù)的算法

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

〃輸出：該正整數(shù)相應的二進制數(shù)，該數(shù)存放于數(shù)組Bin[l…川中

i=l

whilen!=0do{

Bin[i]=n%2;

n=(int)n/2;

i++；

)

whilei!=0do{

printBinfi];

i—；

)

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

對這個算法做盡可能多的改進.

算法MinDistance(A[O..n-l])

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

〃輸出:thesmallestdistancedbetweentwoofitselements

dmin*—oo

forz?—0ton—2do

fori+lton—ldo

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

iftemp<dmin

dmin?—temp

returndmin

習題1.3

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

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

forz<—0ton—1do

Count[i]*—0

forz4—0ton—2do

forz+lton—1do

ifA\i]<A\j]

Count[j]Count[j]+1

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

fori*—0ton—1do

S[Count[z]]*—A[i]

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

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

c.該算法在位嗎？

解：

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

Array川0..5]603581981447

InitiallyCount\\000000

Afterpassz=0County301100

Afterpassi=1Count\\12201

Afterpassi=2Count\\4301

Afterpassi=3Count\\501

Afterpassi=4Count\\02

FinalstateCounty314502

Array5[0..5][11|3*476()|Kl~|~前

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

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

4.(古老的七橋問題)

第2章

習題2.1

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

a.如果t(n)e0(g(n),則g(n)GQ(t(n))

b.a>0時,?(ag(n))=@(g(n))

解：

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

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

由t(n)Wc?g(n)foralln2n0,wherec>0

則：(—)z(?)<g(?j)foral1nNnO

b.這個斷言是正確的。只需證明。(空(〃))葭。(8(〃)),。(8(〃))三。(陰(〃))。

設f(n)G?(ag(n)),則有:

/(?)<cag(n)foralln>=nO,c>0

foralln>=nO,cl=ca>0

即：f(n)G@(g(n))

又設f(n)c0(g(n)),則有：f(n)<cg(n)foralln>=n0,c>0

c

/(〃)<—ag(〃)=cag(n)foralln>=nO,cl=c/a>0

a}

即：f(n)G0(ag(n))

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

a.Q符號

b.@符號

證明：

a。weneedtoproofthatift,(n)GQ(gi(n))andt2(n)GQ(g2(n)),thenti(n)+

t2(n)eQ(max{gi(n),g2(n)})o

由tj(n)eQ(g|(n)),

ti(n)^Cigi(n)foralln>=nl,wherecl>0

由t2(n)eQ(g2(n)),

T2(n)2c2g2(n)foralln>=n2,wherec2>0

那么，取c>=min{cl,c2},當n>=max{nl,n2}時:

ti(n)+t2(n)>c,gi(n)+c2g2(n)

2cgi(n)+cg2(n)2c[gi(n)+g2(n)]

2cmax{gi(n),g2(n)}

所以以命題成立。

b.t|(n)+t2(n)G0(max(gl(〃)，g2(〃)))

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

clmax((gl(〃),g2(〃))<〃(“)+t2(n)<max(gl(〃),g2(〃))

由t|(n)e?(gl(n))知，存在非負整數(shù)al,a2和nl使:

al*gl(n)<=t|(n)<=a2*gl(n)-----(1)

由t2(n)W?(g2(n))知，存在非負整數(shù)bl,b2和n2使：

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

(1)+(2):

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

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

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

不失一般性假設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)o

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

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

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

時上述不等式成立。

證畢。

習題2.2

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

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

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

答：c假，其它真。

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

(n-2)!,51g(n+lOO)10,22n,0.001n+3n3+l,In2n,W,3n.

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

(22)n€0(4n),().0()In4+3n3+1€0(n4),In2n€0(log2n),y/n￡

3n€B(3n).Thelistofthesefunctionsorderedinincreasing

orderofgrowthlooksasfollows:

51g(n+100)1°,ln2n,^n,().0()In1+3n3+1,3n,22n,(n-2)!

答：

習題2.3

1.計算下列求和表達式的值。

a.1+3+5+7+...+999

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

c&￡二，e.工/(￡+1)

f.3加g.EM訂h.EM!/￡(￡+1)

答

5UU5005U0

a.1+3+5+7+...+999=￡(2i-l)=￡2i-￡1=2嗎辿-500=250,000.

i=li=li=l

500

(Orbyusingtheformulaforthesumofoddintegers:￡(2￡?1)=5()()2=

250,000.

Orbyusingtheformulaforthesumofthearithmeticprogressionwith

=("管二°

a1=1,an=999,andn=500:=25(),(M)O.)

10io

b.2+4+8+16+.??+l,024=￡2=工2'—1=(2n-1)-1=2,046.

?=0

(Orbyusingtheformulaforthesumofthegeometricserieswitha=2,

(7=2,andn=9:.1=22'7.1=2,046.)

q_12_1

n+l

c.工1=(ri+1)—3+1=n—L

i=3

n-Fln+12.?

&￡i=￡￡_￡i=(葉1'十2)一3=一十1-4

i=3i=Oi=0

n-1n-1n—1n—1

e.￡i(i+l)=E(i2+i)=￡i2+ER-qg)十

i=0i=Oi=0i=O

=-3—-

nnn.」

￡力3>+i=3^3)=3[￡#—1]=-1]=

j=ij=if=o—

nnnnnn

g.=Z￡t=n(中n哽)

i=lt=lJ=1i=l一t=l

n2(n4-l)J

=i-

h.E?=il/?(i+l)=L"=I(7~*)

=(+_*)+(*_+)+…+(土一千)+C—木)=1-K+T=

(Thisisaspecialcaseoftheso-calledtelescopingseries-seeAppaidix

A——at_i)=A-見一1.)

3.考慮下面的算法。

AlgorithmMystery(n)

//Input:Anoimegativeintegern

S-0

fori4-1tondo

S-S+￡*￡

returnS

a.該算法求的是什么？

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

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

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

e.對該算法進行改進，或者設計一個更好的算法，然后指出它們的效率類型。

如果做不到這一點，請試著證明這是不可能做到的。

n

a.ComputesS(n)=￡產(chǎn).

i=l

b.Multiplication(or.ifmultiplicationandadditionareassumedtotake

thesameamountoftime,eitherofthetwo).

n

c.(7(n)=1=n.

i=l

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

andhencen七*C(n)u2“€。(外).

e.Usetheformula￡產(chǎn)=如十中tocomputethesumin0(1)

time(whidiassumesthatthetimeofarithmeticoperationsstayconstant

irrespectiveofthesizeoftheoperations1operands).

9.證明下面的公式：

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

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

數(shù)學歸納法：

71

Hereisaproofbymathematicalinductionthat匯f"貸>forevery

positiveint^ern.

(i)Basisstep:For幾=1,￡￡=￡￡=1and|=1.

/—12

(ii)Inductivestep:Assumethatfforapositiveintegern.

t=i

Weneedtoshowthatthen￡i=(八?】)八一Thisisobtainedasfollows:

i=l

.t.n(n4-l)./..\n(n-Fl)-F2(n-Kl)(n+l)(n+2)

El=Et+(n+1)="S-+(n+1)=■三------

t=l

高斯的方法:

TheyoungGausscomputedthesum

1+2+...+99+100

bynoticingthatitcanbecomputedasthesumof50pairs,eachwiththe

sum101:

1+1()0=2+99=...=50+51=101.

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

anecdoteclaimsthathisteachergavethisassignmenttoaclasstokeep

theclassbusy.)TheGaussideacanbeeasilygeneralizedtoailarbitrary

nbyadding

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

and

S(7l)=71+(71—1)+...+2+1

toobtain

八-/)=(n4-l)nandhenceS(n)=十】).

習題2.4

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

a.r

x(n)=x(n-l)+5當心1時

[MD=O

解：

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

x(n)=1(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

=...

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

b.fx(n)=3x(n-l)當n>i時

<x(l)=4

解:

b.x(n)=—1)forn>1,z(l)=4

x(n)=3x(n-1)

=3[3X(TI-2)]=32z(n—2)

=32[3x(n—3)]=33x(n—3)

—sas

=3lx(n-i)

------?aa

=3n-1x(l)=4.3n-1.

c.x(n)=x(n-1)+nforn>0,x(0)=0

x(n)=x(n-1)4-n

=[z(n-2)+(n—1)]+n=x(n—2)+(n—1)+n

=[j：(n-3)+(n—2)]+(n—1)+n=x(n—3)+(n-2)+(n—1)4-n

=...

=x(n—i)+(n—￡+1)+(n—￡+2)+…+n

-aa.

小、-n(n+1)

=x(0)+1+2+…+n=-------.

d.x(n)=x(n/2)4-nforn>1,z(l)=1(solveforn=2fc)

x(2k)=x(/-1)+2fc

=[x(2*-2)+2*-1]+2fc=2(/-2)+2k~1+/

=忸(沙々)+2k~2]+2fc-1+2*=x(2fc-3)+沙-2+2&-1+2k

-...

=x(/-<)4-2fc-<+1+2^~i+2+...+2k

=...

=h(/f)+21+22+...+2*=1+21+22+...+2*

=2*+：-1=2-2fc-1=271-1.

ex(n)=x(n/3)+1forn>1,x(l)=1(solveforn=3fe)

x(3fc)=x(3fc-1)+1

=[x(3fc-2)+1]+1=X(3*-2)+2

=[x(3fc-3)+1]+2=x(3fc-3)+3

=...

=x(3^-1)+i

=...

=x(3kk)+fc=x(l)+fc=1+logan.

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—i)+￡=...=(7(0)+n=14-n.

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

算法S(n)

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

〃輸出：前n個立方的和

ifn=lreturn1

elsereturnS(n-l)+n*n*n

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

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

解：

a.LetAf(n)bethenumberofmultiplicationsmadebythealgorithm.

Wehavethefollowingrecurrencerelationforit:

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

Wecansolveitbybackwardsubstitutions:

Af(n)=M(n-1)+2

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

=\M(n-3)+2]+2+2=M(n-3)+2+2+2

=...

=M(n-￡)+2i

=...

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

7.a.請基于公式2三2叔+2南，設計一個遞歸算法。當n是任意非負整數(shù)的時候,

該算法能夠計算2n的值。

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

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

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

解：a.算法power(n)

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

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

〃輸出：2"的值

Ifn=0return1

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

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

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

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

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

------a??

=2,4n-￡)+2*T+2*.+…+i

------a??

=2"40)+2"T+2n-2+...+1=2nT+2n-2+...4-1=2n-1.

C(〃)=力2'=2n+l-1

/=0

8.考慮下面的算法

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

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

Ifn=lreturnA[0]

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

Iftemp〈A[nT]returntemp

ElsereturnA[n-1]

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

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

解：

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

fC(n-l)+lforalln>l

b.C(〃)=%n=l

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

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

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

Ifl=rreturnA[l]

Elsetempl*-Min2(A[l..O.+r)/2])

Temp2*-Min2(A[l..(l+r)/2]+l..r)

IftempiWtemp2returntempi

Elsereturntemp2

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

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

解：a.

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

Solvingitforn—2kbybackwardsul)st.it.ut.ioiisyicklsthefollowuig:

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

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

=22[2C(2fc-3)+1]+2+1=23C(2fc-3)4-22+24-1

-???

=2*C(2fc-*)+2*-1+2<-2+...+1

=2fcC(2fe-fe)+2fc-1+2k-2+...4-1=2fc-1=n-1.

習題2.5

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

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

a.int類型b.long類型

a.ThequestionistofindthesmallestvalueofnsuchthatF(n)>231—1.

UsingtheformulaF(n)=力0nroundedtothenearestintege*.weget

(approximately)thefollowinginequality:

-U0n>231-1or0n>-1).

v5

Aftertakingnaturallogarithmsofbotlihandsides,weobtain

皿西科-1))

n>x46.3.

ln°

Thus,theanswerisn=47.

b.Similarly,wehavetofindthesmallestvalueofnsuchtliatF(n)>

X3—1.1im-.

親0n>2s3一1,or0n>述(28一1)

or.aftertakingnaturallogarithmsofbothhandsides.

、皿門(嚴-1)).

n>-------------------p9n2.o4.

In。

Thus,theanswerisn=93.

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

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

1-2和2-1)o

LetW(n)bethenumberofdifferentwaystoclimbann-stairstaircase.

W(n—1)ofthemstartwithaone-stairclimbandW(n-2)ofthemstart

withatwo-stairclimb.Thus,

W(n)=W(n-1)4-W(n-2)forn>3,W(l)=1,W'(2)=2.

Solvingthisrecurrenceeither"fromscratclrorbetteryetnoticingthat

thesolutionrunsonestepaheadofthecanonicalFibonaccisequenceF(n).

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

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

AlgorithmFib2(n)

//Computesthen-thFibonaccinumberusingjusttwovariables

//Input:Anonnegativeintegern

//Output:Then-thFibonaccinumber

u0;r—1

forz4-2tondo

vv+u

u—r-u

ifn=0return0

elsereturnv

7.證明等式:

F(n-1)F(n)01,I

forn>1.

F(n)F(n+1)11

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

(i)Thevalidityoftheequalityforn=1followsimmediatelyfromthe

definitionoftheFibonaccisequence.

(ii)Assumethat

-1)B

forapositiveint^ern.

F(n)F(n+1)

Weneedtoshowthatthen

n+1

尸(n)F(n+1)01l

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

F(n)F(n)F(n+1)

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

習題2.6

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

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

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

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

count*-0

foriTton-1do

v-A[i]

j-iT

whilej>0andA[j]>vdo

count-count+1

A[j+1]-A[j]

j-j+1

A[j+1]-v

returncount

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

解:應改為：

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

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

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

count-0

fori*-lton-1do

v-A[i]

whilej>0andA[j]>vdo

count-count+1

A[j+1]<-A[j]

j-j+1

ifj>=0count=count+l

A[j+1]*-v

returncount

習題3.1

4.a,設計一個蠻力算法,對于給定的x°,計算下面多項式的值：

P(x)=anx"+an-ix"'+...+aix+ao

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

b.如果你設計的算法屬于?(n>,請你為該算法設計一個線性的算法.

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

解：

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

〃由高幕到低幕用蠻力法計算多項式P在給定點x的值

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

〃輸出：多項式P在給定點x的值

p=0.0

fori=nto0do

power=l

forj=1toido

power=power*x

p=p+P[i]*power

returnp

算法效率分析：

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

M(〃)==---)

i=0j=\i=02

b.thaabovealgorithmsisveryinefficient,becausewerecomputepowersofx

againandagainasiftherewerenorelationshipamongthem.Infact,wecanmove

fromthelowesttermtothehighestandcomputex'byusingx".

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

〃由高累到低幕用蠻力法計算多項式p在給定點x的值

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

〃輸出：多項式P在給定點x的值

P=P[OJ

power=1

fori<—1tondo

powen—power*x

p<—p+P[i]*power

returnp

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

M(n)=Z2=2"e0(n)

>=i

c.不行.因為計算任意--個多項式在任意點x的值,都必須處理它的n+1個系數(shù).

例如：(x=l,p(x)=an+ae+..+a,+ao,至少要做n次加法運算)

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

EXAMp￡

E

XEMp￡

E

ylEXMp,

ylLE

EEMpL

ylA

EELpMX

八X

EELMp

X

EELMP

71IX

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

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

Yes.Bothoperation—findingthesmallestelementandswappingit-canbedoneas

efficientlywiththelinkedlistaswithanarray.

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

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

?

EXsAMPLE

EAX工MPLE

EAMX二PLE

EAMPX』?LE

EAMPLX工E

EAMPLEI*

,,

EAMPLE

?

AEM工P工LE

AEMLP」,E

AEMLE\P

,,

A4—>EM4LE

AELM工E

AELE|A/

?7

ASESL3E

AEE\L

??

AEE二L

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

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

b.結(jié)合所做的改進,為冒泡排序?qū)懸?，段偽代碼.

c.請證明改進的算法最差效率也是平方級的.

Hints:

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

?

4(),…,4/…,4?！?W|4八—4W???SAn—i

intheirfinalpositions

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

4)W4W???W4s4+iW…W4一i-i,

b.AlgorithmsBetterBubblesort(A[0..n-lJ)

〃用改進的冒泡算法對數(shù)組A[0..nT]排序

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

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

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

flag-true〃交換標志

whileflagdo

flag—false

fori=0tocount-1do

ifA[i+l]<A[i]

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

flag-true

count-count-1

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

排序.

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

習題3.2

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

a.在最差情況下

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

Hints:

a.CWOrst(n)=n+l

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

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

1

Ccv3(n)=[1,—'2,—I...4i1—...~Fn1—+(nI1)-(1p)

nnnn

——[1-I2+...4-i+...4n]i(n41)(1p)

=A(-)=(2-P)”l).

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

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

Hints:

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

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

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

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

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

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

〃蠻力字符匹配'

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

〃輸出:在文本中匹配成功的子串數(shù)量

count-0

fori<—0ton-mdo

J-0

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

j-j+1

ifj=m

count*—count+l

returncount

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

算法來利用這個信息.

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

符的比較.

習題3.4

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

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

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

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

型為0(n!(n-l))o

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

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

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

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

1c9-n2(n2+1)

S7i=l+2+...+n,i.e.,sn=-------------

2

由上式可得：

n(n2+1)

2

習題4.1

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

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

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

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

解：a.

AlgorithmsMaxlndex(A[Z..r]){

Input:AportionofarrayA[0..n-l]betweenindicesIandr(/<r)

Output:TheindexofthelargestelementinA[/..r]

ifl=rreturn1

網(wǎng)血+力周)

elsetemp1Maxlndexi

temp2<—MaxIndex(A[|(/+r)/2.r])

ifA[templ]>A[temp2]returntemp1

elsereturntemp2

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

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

C(n)=C([n/2])+C(|n/2|)+lforn>l

C(l)=0

設n=2\C(2k)=2C(2kU)+l

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

=2[22C(2k