算法設(shè)計與分析課后答案+田翠華著

參考答案

第1章

一、選擇題

1.C2.A3.C4.CADB5.B6.B

7.D8.B9.B10.Bll.D12.B

二、填空題

1.輸入；輸出；確定性；可行性；有窮性

2.程序；有窮性

3.算法復(fù)雜度

4.時間復(fù)雜度；空間復(fù)雜度

5.正確性；簡明性；高效性；最優(yōu)性

6.精確算法；啟發(fā)式算法

7.復(fù)雜性盡可能低的算法；其中復(fù)雜性最低者

8.最好性態(tài)；最壞性態(tài)；平均性態(tài)

9.基本運算

10.原地工作

三、簡答題

1.高級程序設(shè)計語言的主要好處是：

(1)高級語言更接近算法語言，易學(xué)、易掌握，一般工程技

術(shù)人員只需要兒周時間的培訓(xùn)就可以勝任程序員的工作；

(2)高級語言為程序員提供了結(jié)構(gòu)化程序設(shè)計的環(huán)境和工

具，使得設(shè)計出來的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；

(3)高級語言不依賴于機(jī)器語言，與具體的計算機(jī)硬件關(guān)系

不大，因而所寫出來的程序可移植性好、重用率高；

(4)把復(fù)雜瑣碎的事務(wù)交給編譯程序，所以自動化程度高，

發(fā)用周期短，程序員可以集中集中時間和精力從事更重要的創(chuàng)造

性勞動，提高程序質(zhì)量。

2.使用抽象數(shù)據(jù)類型帶給算法設(shè)計的好處主要有：

(1)算法頂層設(shè)計與底層實現(xiàn)分離，使得在進(jìn)行頂層設(shè)計時

不考慮它所用到的數(shù)據(jù)，運算表示和實現(xiàn)；反過來，在表示數(shù)據(jù)

和實現(xiàn)底層運算時，只要定義清楚抽象數(shù)據(jù)類型而不必考慮在什

么場合引用它。這樣做使算法設(shè)計的復(fù)雜性降低了，條理性增強(qiáng)

了，既有助于迅速開發(fā)出程序原型，又使開發(fā)過程少出差錯，程

序可靠性高。

(2)算法設(shè)計與數(shù)據(jù)結(jié)構(gòu)設(shè)計隔開，允許數(shù)據(jù)結(jié)構(gòu)自由選擇,

從中比較，優(yōu)化算法效率。

(3)數(shù)據(jù)模型和該模型上的運算統(tǒng)一在抽象數(shù)據(jù)類型中，反

映它們之間內(nèi)在的互相依賴和互相制約的關(guān)系，便于空間和時間

耗費的折衷，靈活地滿足用戶要求。

(4)由于頂層設(shè)計和底層實現(xiàn)局部化，在設(shè)計中出現(xiàn)的差錯

也是局部的，因而容易查找也容易糾正，在設(shè)計中常常要做的增、

刪、改也都是局部的，因而也都容易進(jìn)行。因此，用抽象數(shù)據(jù)類

型表述的算法具有很好的可維護(hù)性。

(5)算法自然呈現(xiàn)模塊化，抽象數(shù)據(jù)類型的表示和實現(xiàn)可以

封裝，便于移植和重用。

(6)為自頂向下逐步求精和模塊化提供有效途徑和工具。

(7)算法結(jié)構(gòu)清晰，層次分明，便于算法正確的證明和復(fù)雜

性的分析。

3.算法的復(fù)雜度是算法運行所需要的計算機(jī)資源的量。

4.當(dāng)問題的規(guī)模遞增時，將復(fù)雜度的極限稱為漸進(jìn)復(fù)雜度。

5.采用復(fù)雜性漸近性態(tài)替代算法復(fù)雜度，使得在數(shù)量級上

估計一個算法的執(zhí)行時間成為可能。

四、計算題

1.驗證下面的關(guān)系：

0(1)<0(logZ7)^0(77)<0(/?log/7)<0(Z?2)

及0(2")<0(A!)〈06)o

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

證明2：反證法。

證明3：定義證明

令&(〃)=0(1),/(A)=0(log/?),￡(〃)=0(n),/(〃)=

0(7?log77),￡?=0(，)。

根據(jù)|f(〃)I=|0(g(M)I定義，可知一定存在兩個正的常數(shù)C

和使得對所有的為，有以〃)WCg(玲o

那么，就有￡(〃)WC，乙(力WGlog/?,￡(加WG〃，

/(〃)Wanlogn,￡(〃)Wa*

所以，0(g(〃))之間的比較可以通過/(〃)之間的比較得以實

現(xiàn)。

而當(dāng)〃N〃()時，Ci<Glog水Qn<&Hog水C5萬成立。

再根據(jù)0(g(N))表示所有f(/V)增長的階不超過gQN)的

函數(shù)的集合，它用以表達(dá)一個算法運行時間的上界。

則￡(〃)的上界〈分5)的上界<△(〃)的上界〈尤(而的上界〈

△5)的上界

那么就驗證了

0(1)<0(logz?)<0(77)<0(nlog77)<0(772)0

同理，有:0(2")<0(〃!)<03)。

證明4：極限法(通常使用羅比塔法則)。

2.找出下述證明中的錯誤：因為A=0(A),2n=05),…，

故:

解答：概念不清。

止0(〃)，2/7=0(〃)，…，是集合，是說〃，2n,-??,的階是

力不是數(shù)值上相等。

是數(shù)值求和，即首項為〃的〃項等差為〃的數(shù)列求和

所以，。應(yīng)該是：

=1z?+2/?+37?+...+nn=z?(zz+l)z?/2,而

=O(max(1,2,3,4,n))//根據(jù)性質(zhì)0(/*)十0(g)

=0(max(f,g))

=05)〃集合操作，上界的并取最大者

3.求以下各式的漸進(jìn)表達(dá)式：

5

56+8n,36/11+3",56+3/〃，log/?,6log4%

解答：

5/?2+877=0(曲；1

34/11+3"=0(3");

56+3//?=0(1)//0(1)表示常數(shù)；

10g〃”=0(10g/7);

6log4n-0(7?)O

4.按照漸進(jìn)階從低到高的順序排列下列表達(dá)式：

ri,log/?,3",45n,6,3n\n\o

解答：

1

log/?,45n,3n',5n,3”,n!0

5.確定關(guān)系：對于下列各組函數(shù)f(〃)和g(加，確定f

(7?)=0或/'(/?)=Q(g(〃))或/'(〃)=。(g(7?)),

并簡述理由。

(1)f(z?)=logd,g(/7)=logz?+7；

(2)f(z?)=logn,g(〃)=n

(3)f(加=n,g(〃)=log?n；

(4)f(〃)=nlogn+n,g(〃)=log〃；

(5)f(77)=11,g(77)=Og11;

(6)f(z?)=log2n,g(7?)=logn；

(7)f(〃)=2",g(〃)=100if；

n

(8)f(z?)=2",g(〃)=30

解答:

(1)f(z?)=log〃2=。(log〃+7)=。(g(/?))；

(2)f(〃)=log/?2=0(/?'2)=0(g(n))；

(3)f(7?)=72=Q(log2n)=Q(g(n))；

(4)f(z?)=nlogn-\-n=Q(logn)=Q(g(/?))；

(5)f(〃)=11=0(log11)=0(g(〃))；

(6)f(n)=log2n=Q(log/?)=Q(g(〃))；

(7)f(77)=2"=。(100T?)=Q(g(〃))；

(8)f(〃)=2〃=0(3")=0(g(/7))o

6.證明：n\=0(/7")o

證明:

7.證明：如果一個算法在平均情況下的計算時間復(fù)雜度是。

(f(n)),則該算法在最壞情況下所需的計算時間是。(f(n))o

證明：

8.硬件廠商XYZ公司宣稱他們最新研制的微處理器運行速

度為其競爭對手ABC公司同類產(chǎn)品的100倍。對于計算復(fù)雜性分

別為mn2,i?和加的各算法，若用ABC公司的計算機(jī)在1小時

內(nèi)能解輸入規(guī)模為〃的問題，那么用XYZ公司的計算機(jī)在1小時內(nèi)

分別能解輸入規(guī)模為多大的問題？

解答：

n=100/7；

n2=100T72,/.n=10zz;

n3=100/?\n=107377=4.64/?;

n!=100z?!,/.n</?+logl00=/?+6.64o

9.

(1)假設(shè)某算法在輸入規(guī)模為免時的計算時間為T(77)=3

X2"。在某臺計算機(jī)上實現(xiàn)并完成該算法的時間為1秒。現(xiàn)有另一

臺計算機(jī)，其運行速度為第一臺的64倍，那么在這臺新機(jī)器上用

同一算法在力秒內(nèi)能解輸入規(guī)模為多大的問題？

(2)若上述算法的計算時間改進(jìn)為T(n)=4,其他條件不

變，則在新機(jī)器上用Z秒時間能解輸入規(guī)模為多大的問題？

(3)若上述算法的計算時間進(jìn)一步改進(jìn)為7(加=8,其他

條件不變，那么我們在新機(jī)器上用力秒時間能解輸入規(guī)模為多大

的問題？

解答：

(1)設(shè)新機(jī)器用同一算法在t秒內(nèi)能解輸入規(guī)模為n'的問

題,則有

7(〃)=3X2"=3義2"'/64,得〃'=〃+6；

(2)n2=64z?2,得〃'=8〃；

(3)由于7(加=8為常數(shù)，因此算法可以為解任意規(guī)模的

問題。

五、上機(jī)題

二分檢索是指在一個已經(jīng)排序的數(shù)組中查找一個指定的數(shù)據(jù)

是否存在的問題。進(jìn)一步說，假定一個具有4個元素的整型數(shù)組a

和一個整數(shù)x,數(shù)組a的元素已經(jīng)按由小到大的順序排序，希望查

找X在數(shù)組a中是否出現(xiàn)。若出現(xiàn)，輸出對應(yīng)的數(shù)組元素下標(biāo)，

否則，輸出不存在信息。

編程時具體的實現(xiàn)方法是：將?x與a的中間元素a\_N/2]比

較，如果相等則結(jié)束。否則，若xVa[N/2],由于a是有序的，

可以肯定x只可能出現(xiàn)在前半個數(shù)組中；若x>a[N/2],則x

只可能出現(xiàn)在后半個數(shù)組中。然后，將得到的半個數(shù)組看成原來

的數(shù)組，繼續(xù)重復(fù)上述過程直到數(shù)組的所有元素比較完畢或發(fā)現(xiàn)

一個相等的元素為止。

在進(jìn)行程序設(shè)計時，力是數(shù)組大小的上限，實際的元素個數(shù)由

鍵盤輸人。

#include<stdio.h>.

ttdefneN50

intbsearch(int*a,intn,intx)〃參數(shù)為數(shù)組、元素

個數(shù)和被查找的值

{intk=0,m=n-l,mid;//k,m,mid為被查找區(qū)間的最小、

最大和中間元素下標(biāo)

while(k<=m)〃若最小下標(biāo)超過最大下標(biāo)則終止循

環(huán)，說明不存在

{mid=(k+m)/2;〃取中間下標(biāo)，注意整數(shù)相除取整

if(x==a[mid];

returnmid;〃相等時綺束，返回元求下標(biāo)

else

if(x<a[mid])

m=mid-1;〃x應(yīng)在前半個數(shù)組中，最大下標(biāo)凋

整

else

k=mid+1;〃x應(yīng)在后半個數(shù)組中，最小下標(biāo)調(diào)

整

)

return-1;〃執(zhí)行此語句時，必有k>m,即x不存在，

返回-1作標(biāo)志

)

voidrnain()

{inta[N],x,n,rt,k;

printf(uinputcount(<=50):");〃輸人數(shù)組元素

個數(shù)

scanf("%d",&n);

printf(“'Inputal1elermnts:'');

for(k=0;k<n;k++);

scanf("d”，&a[k]);〃輸人數(shù)組元素，元素可

用空格分隔

printf(inputdatasearched");

scanf("%d",&x);〃輸人被查找的值x

rt=bsearch(a,n,x);〃執(zhí)行查找

(rt==-l)?printf("\nNot

found."):printf("\nFound:%d.”,rt);}//顯示查找結(jié)果

第2章

一、選擇題

1.C2.C

二、填空題

1.遞推法；生成函數(shù)法；特征方程法；數(shù)學(xué)歸納法；不規(guī)

則法

2.遞歸消除有利于提高算法的時空性能；研究遞歸消除有

利于透徹理解遞歸機(jī)制

三、簡答題

1.人們在解決一些復(fù)雜問題時，為了降低問題的復(fù)雜程度

(如問題的規(guī)模等)，一般總是將問題逐層分解，最后歸結(jié)為一些

最簡單的問題。這種將問題逐層分解的過程，實際上并沒有對問

題進(jìn)行求解，而只是在解決了最后那些最簡單的問題后，再沿著

原來分解的逆過程逐步進(jìn)行綜合，這就是遞歸的基本思想。

2.假定所求解遞歸方程的解(系列)是某個函數(shù)(如G(x))

展開成無窮級數(shù)后的系數(shù)，于是，可以先利用遞歸方程求出G(x)

的解析表達(dá)式，然后，再將G(x)展成無窮級數(shù)，其/項的系數(shù)

自然就是遞歸方程的通解形式。

四、計算題

1.求和：

(1)

(2)

解答：

(1)設(shè)和為S,則有

5=a+2a2+3a+'''+na①

等式兩邊同乘a,得

aS=a2+2/+…+〃an+l②

①-②得：

(1-a)S=a+a~+a+,,,+an-na"”

整理得：

S=a(l-a")/(『a)2-na[/(l-a)

(2)設(shè)和為S,則有

當(dāng)n為偶數(shù)時，

當(dāng)n為奇數(shù)時，

2.設(shè)回〃都是整數(shù)，計算

（1）（加勿）/2」+（77-研1）/2」

（2）「（77+%）/21+「（77-研1）/21

解答：

（1）因為勿，〃都是整數(shù)，所以加加與止"同時為奇數(shù)或偶數(shù)。

當(dāng)加必與77-%同時為奇數(shù)時，原式=（/?+獷1）/2+（ZT研1）/2=

n

當(dāng)〃+/與77-必同時為偶數(shù)時，原式=（72+血/2+（77-%）/2=n

（2）同理，",〃都是整數(shù)，所以力R與k勿同時為奇數(shù)或偶

數(shù)。

當(dāng)??+勿與ZT?必同時為奇數(shù)時，原式=（77+研1）/2+（77-研1）/2=

n+\

當(dāng)n+m與n-m同時為偶數(shù)時，原式=（〃+%）/2+^n-ni）/2+1=n+\

3.判斷下述等式的真?zhèn)危?/p>

（1）（LX」差=2」

⑵「（「x[）"2]=「

（3）r（LJ）1/21=「一1

解答：（1）當(dāng)后代k為整數(shù)時，原等式成立。

當(dāng)為整數(shù)時，原等式不成立。此時左端不一定為整數(shù)，

而右端為整數(shù)。

（2）等式成立。

（3）當(dāng)尸〃，k為整數(shù)時，原等式成立。

當(dāng)xa4為整數(shù)時，原等式不成立。此時，（Lx」）i/2<rx

〕叱所以左端小于右端。

4.求證：

（1）l_x」+l_y」Wx+y

(2)「x[+「y12「x+y~\

(3)「log(z?+l)1=Llog/?」+1

(4)L(x+勿)/〃」=L(l_x」+m)/n\

(5)

證明：

(1)當(dāng)x,y為整數(shù)時，原等式成立。

當(dāng)x,y不為整數(shù)時，令x=I.x」+\x,y=LyJ+Ay,其

中0<Ax,\yW1o則有

x+y=|_x」+Ax+|_y」+zV=|_x」+|_y」+Z\x+

△y

因為0cAx,Ay<1,所以0<\x+\y<2

貝I」l_x」+l_y」+Ax+Ay〉l_x」+l_y」，即有：x+y

>l_x」+!_『」

所以，原不等式Lx」+Ly」Wx+y成立。

(2)當(dāng)x,y為整數(shù)時，原不等式成立。

當(dāng)x,y不為整數(shù)時，令*=「才]—^x,y=「y]—Ay,其

中0<,Ay<1o則有：

「x+y〕=「「x\—△*+「y]—Ay1=「「/]+「y]—(A

x+Ay)1

因為0W△*,Ay<1,所以有0WA^+Ay<2。因此，

「x+y]W「「x[+「y[1=「x]+「y]。

所以，原不等式「x1+「yl2「x+y1成立。

(3)當(dāng)A為2"時，「log(/zH)1=A+1,而Llogz?J+1=A+l,

所以，原等式成立。

當(dāng)A不為2"時,則2yA<27此處A=l_log〃」，那么2"+10

+1W2叱則有：

Flog(/?+l)l=A+1,Llog/?J+1=A+1,所以，原等式成立。

(4)若要使原等式成立，必有

,這里x=l_x」+\x,0WAx<1

左”而二右”而

所以，原等式成立。

(5)當(dāng)爐2研1時，歷0,1,2,3,…，那么

左端=0+1+1+2+2+3+3+…+研ZZF2*(1+R)+而

右端=L(2研1)2/4」=|_(4/+4研1)/4」=/(1+勿)=左端

所以，原等式成立。

當(dāng)爐2〃時，爐0,1,2,3,…，那么

左端=0+1+1+2+2+3+3+…+(/n~l)+m

2*(l+/?rl)(獷1)/2+/=zz/2

右端=L(2%)74」=/n=/=左端

所以，原等式成立。

5.設(shè)x,y為任意實數(shù)，定義：

{xmody-x-y\_x/yJ,當(dāng)yW0

xmod0=x

依據(jù)上述定義：

(1)若尸-1,計算xmod28o

(2)若xmod3=2,xmod5=3,求xmod150

解答：

(1)當(dāng)下T時一，xmod28=(-l)mod28=(-1)-28L(T)/28」

=-1-28*(-1)「1/281=27

(2)

①當(dāng)xmod3=2,xmod5=3,那么有命題xmod(2/7-1)=/?

成立，此時x>0。

用數(shù)學(xué)歸納法證明命題：當(dāng)上2時，有xmod3=2,成立。

當(dāng)/7=3時，有xmod5=3,成立。

假設(shè)當(dāng)〃=A時，有Amod(2A-1)=k

成立，

然后證明當(dāng)爐〃+1成立。所以，命題成立。

即有：xmod(2(A+1)T)=A+l0

根據(jù)命題Jmod(2zrl)=〃，有在Amod(2zrl)=Amodl5中，

2/7-1=15,則77=8o

所以，Amodl5=8o

②

xmod3=2,xmod5=3,此時x>0,否則不滿足定義

.??存在整數(shù)%,使得：x=3左+2,同時，x=5L+3,

即有：3左+2=5%+3,得左=(5左+1)/3=5(&-1)

/3+2

k、,人為整數(shù).??存在整數(shù)A,使得：k=(&-1)/3,即

有：k2=3k+1

：.x=5左+3=5(34+1)+3=154+8

Amodl5=8o

6.求序列2,5,13,35,…2"+3〃的生成函數(shù)。

解答：根據(jù)題義，得

〃(0)=2,77=0

〃(n)=2"+3",〃=1,2,3,…

設(shè)生成函數(shù)為，將，(〃)=2"+3”代入，得

將上式展開并整理，得

G(x)=[2-5戶(2/2+3〃)(3*2"42*3"|)x"2]/[(1一2才)(1一3才)]

7.給定a0=l,a=1,a^2=an+i+6a?,試求出劣的非遞歸形式的表

達(dá)式。

解答：原方程所對應(yīng)的特征方程為：

(a2-a-6=0

為齊次方程，則齊次解：S=3,0=-2,重數(shù)均為1。

記通解的形式為：a尸四"+為233"+B(-2)〃

將a=1,4=1代入上式，得

{A+B=l

34-2廬1

解得：2=3/5,廬2/5

從而，得當(dāng)?shù)姆沁f歸形式的表達(dá)式為:4=(3"-/5。

8.設(shè)有國,=0,品=1,a=T和a=-a^i+16五2-20a^,當(dāng)〃

N3。求出a”的表達(dá)式。

解答：原遞歸方程所對應(yīng)的特征方程為：

/+/-16^-20=0

解得特征方程的根：＜7.=-5,/=2,重數(shù)分別為1和2。

記通解的形式為：a尸(/+物)6"+。芯=(4+物)*2n+a(-5)"

將a=0,ai=l,殳=-1代入上式，得

4+俏0

2G4+而-5C=1

4(4+20+(-5)2^=-1

解得：1=5/49,廬1/7,小-5/49

從而，得當(dāng)?shù)姆沁f歸形式的表達(dá)式為：/=(5/49W7)*2"

+(-5)ntl/49o

9.設(shè)a=1,為=5,4=436區(qū)-2,當(dāng)〃22。求出劣的解析表達(dá)

式。

解答：原遞推方程的特征方程為

*-獷6=0,則齊次特征方程為

齊次特征的解為：s=3,0=-2,重數(shù)均為1。

記通解的形式為：an=Aq，+Bq2"=A3"+B(—2)n

將a0=l,句=5代入上式，得

'/+B=1

3/-2廬5

解得：4=7/5,廬-2/5

fl+I

記通解的形式為：4=幽/+/2”=(7*3"+(-2))/5

10.求解方程：

T(2)=1,n=l

75)=〃々但/2)+，力2,且有A,使得

解答：由遞歸方程，遞推得

7(〃)=/7l/2T(/71/2)+n

=小[(小)"270+小]+〃

=nl/2/"(〃")+n+n

=/n1/4[(H)1/27((Z71/4)1/2)+/]+2n

=4〃〃"n"T但/8)+3〃

令，則有

T{n)=/7(1/2+log(log/?))

11.求證方程

的解是X(n+1)=Cn2n/(n+1)

證明：根據(jù)遞歸方程，遞推得

x(2)=x(1)x(1)=1=C)2

2

x(3)=x(1)x(2)+x(2)x(1)=1+1=2=C4/3

x(4)-x(1)x(3)+x(2)x(2)+x(3)x(l)=5=

x(5)=x(1)x(4)+x(2)x(3)+x(3)x(2)+

x(4)x(l)=14=C\/5

*(〃)=。)2(叱1)/〃

^(TTi-l)=<72fl/(72+l)

12.求證遞歸方程

{7(1)=0

7(/7)=T(L"2」)+T(「A/21)+〃-1,A>1

riognl

的解是T(〃)=〃「log〃1-2+lo

證明：

(1)當(dāng)〃=2時，由遞歸方程和初值，推得

T(2)=T(1)+T(1)+27=0+0+2-1=1

由方程的解，得T(2)=2-2+l=lo所以，結(jié)論成立。

(2)假設(shè)當(dāng)4時.成立，既有7(〃)=A「log〃]-2hogAl+1

是原遞歸方程的解。

那么當(dāng)斤4+1時，下面證明T(A+1)=(A+l)「log(A+l)〕-2r

logU+1)1+l是原遞歸方程的解。

當(dāng)〃WA時，7(|_—/2」)+7(「A-/21)+A-l=k「log*-2「卜囚

+1

當(dāng)爐A+1且A為奇數(shù)時，有

AL(A+l)/2j)+T(F(A+D/21)U+l-1

=T(l_A/2」+l)+7(「02])+k

=2T(「%/21)+A

=2[「A/2]?「log「A/211-25「"211+i]+4

=(〃+l)?「log「4/211-2M“211”+2+A

=(A+1)(「log(A+l)/2+1])-2「"g<…21+i

=U+1)「log(A+l)-1+11-2riog(k+1)1+1

=(A+1)「log(4+1)]-2riog(k+1)1+1

=T(A+1)

當(dāng)上〃+1且A為偶數(shù)時，有

7((m4)/2」)+7(「(-1)/21)+A+1-1

=7(4/2)+T(A/2+l)+k

=(A/2)「log(A/2)1—2「w"2)1+i+[(A/2+1)「log(A/2+l)1

_2「3(k/2+D1+]]+k

=(A/2+A/2+l)「log(4/2)]-(2riog(k/2)1+2riog(k/2+1)1)+2+k

=(A+1)「log(A/2)1-2r，og(k/2)1+,+2+k

=T(k+l)

即當(dāng)n=k+l時;命題成立。

所以，原命題成立。

五、上機(jī)題

1.計算Hermite多項式

Voidmain()

(

Printf(“\n%f“，H(2,2.0));//輸出結(jié)果76.000000

}

DobuleH(intn,floatx)

(

Switch(n)

(

Case0:return1;

Case1:2*x;

)

Return2*x*H(nT,x)-2*(n-l)*H(n-2,x)

}

2.求解漢諾塔問題

漢諾塔問題：設(shè)4B、。是三根金針。開始時，在金針4上

有〃只紙盤，這些紙盤自下而上，由大到小地疊放一起，各紙盤

從小到大編號為1,2,…，n,如圖A-1所示?，F(xiàn)要求將金針A

上的這一疊紙盤移到金針臺上，并仍按同樣順序疊置。

圖AT漢諾塔問題的初始狀態(tài)

在移動紙盤時應(yīng)遵守以下移動規(guī)則：

規(guī)則(1)：每次只能移動一個紙盤；

規(guī)則(2)：任何時刻都不允許將較大的紙盤壓在較小的紙盤

之上；

規(guī)則(3)：在滿足移動規(guī)則(1)和(2)的前提下，可將紙

盤移至月，B,。中任一根金針上。

分析與解答：

(1)漢諾塔問題的遞歸算法如下：

publicstaticvoidHanoi(intn,intA,intB,intC)

(

if(n>0){

Hanoi(n-1,A,C,B)'

Move(n,A,B);

Hanoi(n-l,C,B,A);

}

|

(2)漢諾塔問題的非遞歸算法。

教材中所述非遞歸算法的目的塔座不確定。當(dāng)n為奇數(shù)時，

目的塔座是B,按順時針方向移動；而當(dāng)n為偶數(shù)時，目的塔座為

C,按反時針方向移動。為確定起見，規(guī)定目的塔座為B。漢諾塔

問題的非遞歸算法可描述如下：

publicstaticvoidHanoi(intn)

(

int[]top={0,0,0}

int[][]tower=newint[n+1][3];

intx,y,min=0;

Booleanb,bb;

for(inti=0;i<=n;i++)

{tower[i][0]=n-i+l;tower[i][l]=n+l;

tower[i][2]=n+l;}

top[0]=n;b=odd(n);bb=true;;

while(top[1]<n){

if(bb){

x=min;

if(b)y=(x+l)%3

elsey=(x+2)%3;

min=y;bb=false;

)

else{

if(tower[top[x]][x]>tower[top[y]]|y])

{inttmp=x;x=y;y_tmp;}

}

move(tower[top[x]][x],x+1,y+1);

tower[top[y]+1][y]=tower[top[x]][x];

top[x]一;top[y]++;

}

]

下面用數(shù)學(xué)歸納法證明遞歸算法和非遞歸算法產(chǎn)生相同的移

動序列。

當(dāng)27=1和77=2時容易直接驗證。設(shè)當(dāng)k&n~\時，遞歸算

法和非遞歸算法產(chǎn)生完全相同的移動序列?？疾斓那樾巍?/p>

將移動分為順時針移動(C)、逆時針移動(CC)和非最小圓

盤塔座間的移動(0)o

當(dāng)〃為奇數(shù)時，順時針非遞歸算法產(chǎn)生的移動序列為：C,0,

C,0,C；逆時針非遞歸算法產(chǎn)生的移動序列為：CC,0,CC,

0,…，CCo

當(dāng)n為偶數(shù)時，順時針非遞歸算法產(chǎn)生的移動序列為：CC,0,

CC,0,CC；逆時針非遞歸算法產(chǎn)生的移動序列為：C,0,C,

0,…，Co

①當(dāng)n為奇數(shù)時，順時針遞歸算法Hanoi(n,A,B,C)產(chǎn)

生的移動序列為：

Hanoi(n-1,A,C,B)產(chǎn)生的移動序列，0,Hanoi(n-1,

C,B,A)產(chǎn)生的移動序列。

Hanoi(n-1,A,C,B)和Hanoi(n-1,C,B,A)均為偶

數(shù)圓盤逆時針移動問題。由數(shù)學(xué)歸納法知，產(chǎn)生的移動序列均為：

C,0,C,0,…，Co因此，Hanoi(n,A,B,C)產(chǎn)生的移動序

列為：C,0,C,0,Co

②當(dāng)n為偶數(shù)時，順時針遞歸算法Hanoi(n,A,B,C)產(chǎn)

生的移動序列為：

Hanoi(n-1,A,C,B)產(chǎn)生的移動序列，0,Hanoi(n-1,

C,B,A)產(chǎn)生的移動序列。

Hanoi(〃一1,A,C,B)和Hanoi(〃一1,C,B,/)均為奇

數(shù)圓盤逆時針移動問題。由數(shù)學(xué)歸納法知，產(chǎn)生的移動序列均為：

CC,0,CC,0,…，CCo因此，Hanoi(〃，A,B,C)產(chǎn)生的移動

一序列為：CC,0,CC,0,CCo

當(dāng)n為奇數(shù)和偶數(shù)時的逆時針遞歸算法也類似。

由數(shù)學(xué)歸納法即知，遞歸算法和非遞歸算法產(chǎn)生相同的移動

序列。

(3)雙色漢諾塔問題：設(shè)爾B、。是三根金針。開始時，在

金針力上有〃只紙盤，這些紙盤自下而上，由大到小地疊放一起，

各紙盤從小到大編號為1,2,…，n,奇數(shù)編號圓盤為白色，偶數(shù)

編號圓盤為黑色。如圖A-2所示。現(xiàn)要求將金針月上的這一疊紙

盤移到金針夕上，并仍按同樣順序疊置。

圖A-2雙色漢諾塔問題的初始狀態(tài)

在移動紙盤時應(yīng)遵守以下移動規(guī)則：

規(guī)則(1)：每次只能移動一個紙盤；

規(guī)則(2)：任何時刻都不允許將較大的紙盤壓在較小的紙盤

之上；

規(guī)則(3)：任何時刻都不允許將同色圓盤疊在一起；

規(guī)則(4)：在滿足移動規(guī)則(1)和(3)的前提下，可將紙

盤移至小B,。中任一根金針上。

試設(shè)計一個算法，用最少的移動次數(shù)將塔座4上的〃個圓盤

移到塔座方上，并仍按同樣順序疊置。

分析與解答：

可用教材中的標(biāo)準(zhǔn)Hanoi塔算法。問題是要證明標(biāo)準(zhǔn)Hanoi

塔算法不違反規(guī)則(3)。

用數(shù)學(xué)歸納法。

設(shè)Hanoi(A,A,B,C)將塔座A上的n個圓盤，以塔座C

為輔助塔座，移到目的塔座〃上的標(biāo)準(zhǔn)Hanoi塔算法。

歸納假設(shè)：當(dāng)圓盤個數(shù)小于〃時一，Hanoi(〃，A,B,C)不違

反規(guī)則(3),且在移動過程中，目的塔座B上最底圓盤的編號與n

具有相同奇偶性，輔助塔座C上最底圓盤的編號與n具有不同奇

偶性。

當(dāng)圓盤個數(shù)為n時，標(biāo)準(zhǔn)Hanoi塔算法Hanoi(〃，A,B,C)

由以下3個步驟完成。

①Hanoi(n~1,A,C,夕)；

②Move(A,B)；

③Hanoi(z?—1,C,B,力)。

按歸納假設(shè)，步驟①不違反規(guī)則(3),且在移動過程中，塔

座C上最底圓盤的編號與n-\具有相同奇偶性，塔座方上最底圓

盤的編號與n-1具有不同奇偶性，從而塔座〃上最底圓盤的編號

與n具有相同奇偶性，塔座。上最底圓盤的編號與n具有不同奇

偶性。

步驟②也不違反規(guī)則(3),且塔座B上最底圓盤的編號與n

相同。

按歸納假設(shè)，步驟③不違反規(guī)則(3),且在移動過程中，塔

座〃上倒數(shù)第2個圓盤的編號與n—1具有相同奇偶性，塔座月上

最底圓盤的編號與n~\具有不同奇偶性，從而塔座夕上倒數(shù)第2

個圓盤的編號與〃具有不同奇偶性，塔座A上最底圓盤的編號與〃

具有相同奇偶性。

因此在移動過程中，塔座方上圓盤不違反規(guī)則(3),而且塔

座〃上最底圓盤的編號與n具有相同奇偶性，塔座。上最底圓盤

的編號與n具有不同奇偶性。

由數(shù)學(xué)歸納法即知，Hanoi",A,B,C)不違反規(guī)則(3)。

第3章

一、選擇題

1.B2.B

二、填空題

1.LlognJ+1

2.2n-l

三、簡答題

1.將一個難以直接解決的大問題，分割成一些規(guī)模較小的

類型相同問題，這些子問題相互獨立，以便各個擊破，分而治之。

如果原問題可分割成"個子問題，1并且這些子問題都可

解，然后求解這些問題，那么就可利用這些子問題的解求出原問

題的解；如果子問題還比較復(fù)雜而不能直接求解，還可以繼續(xù)細(xì)

分，直到子問題足夠小，能夠直接求解為止。此外，為了得到原

始問題的解，必須找到一種途徑能夠?qū)⒏鱾€子問題的解組合成原

始問題的一個完整答案。

2.將待查的數(shù)據(jù)與非降序數(shù)組中的中間元素進(jìn)行比較，若

二者相等則表示查到；若該數(shù)據(jù)小于中間元素的值，則下次在數(shù)

組的前半部分中繼續(xù)找；否則，在數(shù)組的后半部分中查找。即每

次檢索將與待查數(shù)據(jù)的比較次數(shù)減半。如此繼續(xù)進(jìn)行下去，直到

查到該值的元素或不存在所查找的數(shù)據(jù)。此種分治方法，稱為二

分檢索。

四、計算題

1.作一個“二分”檢索算法，它將原集合分成1/3和2/3

大小的兩個子集。分析此算法并與算法3.1比較。

輸入：已按非減序分類的〃個元素的數(shù)組4和X乃是被檢索

的項。4[0]未用。

輸出：若￥在力中，輸出下標(biāo)j滿足才，否則輸出0。

IntBinarySearch(A,n,X)

{intk=l;m=n;

while(k<=m)

{j=(k+m)/3;/*j=(k+m)/3*/

if(X==A[j])

returnj;

if(X<A[jD

m=j-1

else

k=j+1;

return0；

)

時間分析：比較次數(shù)

2.作一個“三分”檢索算法，它首先檢查1/3處的元素是

否與X相等，然后檢查2/3處的元素，等等。這樣，或者找到X,

或者將集合縮小到原來的1/3O試寫出此算法并分析其復(fù)雜性。

輸入：已安排減序分類的〃個元素的數(shù)組/和人才是被檢索

的項。的0]未用。

輸出：若X在A中，輸出下標(biāo)j滿足A[j]=X,否則輸出0。

IntThirdSearch(A,n,X)

{intk=1;m=n;

While(k<=m)

{i=(k+m)/3;/*i=(k+m)/3*/

if(X==A[i])

returni;

if(X<A[iJ)

m=i-1

else

{j=2(k+m)/3)/;/*j=2(k+m)/3)

if(X==A[j])

returnj;

if(X<A[j])

{k=i+1;

m=j-1}

else

k=j+1;

)

)

return0；

}

時間分析：比較次數(shù)

解得方程:T(n)=l+log3n

3.設(shè)計一個在有n個元素的集合中通過比較找出最大和次

最大元素的算法，使其復(fù)雜度為n+logn-2。

算法：找最大和次大元素

輸入：有n個元素的數(shù)組A

輸出：最大和次最大元素Max和SubMax。

voidFind(A)〃遞歸算法

{if(|A|==2)

{設(shè)人=匕4}

(Max,SubMax)(Max(a,b),SubMax(a,b));

}

else

{把A分成兩個子集Al和A2,各有一半元素；

(MaxifSubMaxi)Find(Al);

(Max2,SubMax2)Find(A2);

SubMax3=Min(Maxi,Max2);

SubMax4=Max(SubMaxi,SubMax2)

(Max^SubMax)(Max(Max1,

Max2),SubMax(SubMax3,SubMax4))

)

]

時間分析：T(n)為算法的最壞時間。當(dāng)n=2時-，T(n)=l；當(dāng)

n>2時，則需要進(jìn)行兩次遞歸調(diào)用及之后的比較。故有：

T(n)=5n/2

4.求解最接近中位數(shù)的k個數(shù)：給定由n個互不相同的數(shù)

組成的集合A以及正整數(shù)kWn,設(shè)計一個0(n)時間復(fù)雜度的查

找A中最接近A的中位數(shù)的k個數(shù)的算法。在采用分治法進(jìn)行查

找時，為了滿足分治法的平衡原則，需要將數(shù)組分成兩個大小基

本相同的子數(shù)組，其中的那個劃分點就是中位數(shù)。所以，中位數(shù)

是指數(shù)組中能將數(shù)組劃分成兩個大小基本相同的兩個子數(shù)組的那

個元素，即中位數(shù)是第「n/21小的數(shù)。

解析：

(1)找出A中的中位數(shù)mid；

(2)計算T={|a-mid,aeA}；

(3)找出T的第k小元素b；

(4)根據(jù)b找出所要的解{|a-mid|Wb,aeA}。

由于在最壞情況想選擇的時間復(fù)雜度為0(n)o所以，(1)和

(3)需要0(n)次計算，(2)和(4)也只需要0(n)次計算。

因此，本算法在最壞情況下，時間復(fù)雜度為0(n)。

例如，A={50,13,80,30,6,27,35},k=3,求最接

近中位數(shù)的k個數(shù)。

(1)找出A中的中位數(shù)mid：將A排序={6,13,27,30,

35,50,80},mid=30o

(2)計算T={|a-mid|,aeA}：T={20,13,50,0,24,

3,5}o

(3)找出T的第k小元素b：T的第k小元素b=5o

(4)根據(jù)b找出所要的解{a,1a-mid|Wb,aeA}：{30,

27,35}o

5.求有序數(shù)組A和B的中位數(shù)

設(shè)A[0：n-1]和B[0：n-1]為兩個數(shù)組，每個數(shù)組中含有

n個已排好序的數(shù)。設(shè)計一個O(logn)時間復(fù)雜度的算法，找出A

和B的2n個數(shù)的中位數(shù)median。

解析：

(1)算法設(shè)計思想。

考慮問題的一般性：設(shè)A[il：jl]和BLi2：j2]是A和B

的排序好的子數(shù)組，且長度同，即jl-il=i2-j2。找出這兩個子

數(shù)組中2(jl-il+1)個數(shù)的中位數(shù)。

首先注意到，若A[il]WB[j2],則中位數(shù)median滿足A

[il]WmedianWB[j2]°同理，若A[il]2B[j2],則B[j2]

WmedianWA[il]。

設(shè)ml=(il+jl)/2,m2=(i2+j2)/2,則

ml十m2=((il+jl)/2+(i2+j2)/2

=il+(jl—il)/2+i2+(j2—i2)/2

=il+i2+(jl-i1)/2+(j2—i2)/2o

由于jl—il=j2—i2,故

(jl-il)/2+(j2-i2)/2=jl-*il=j2-i2o

因此，ml+m2=il+i2+jl一i1=i2+jl=i1+i2+j2一

i2=il+j2o

當(dāng)A[ml]=B[m2]時，median=A[ml]=B[m2]。

當(dāng)A[ml]<B[m2]時，設(shè)medianl是A[ml：jl]和B[j2：

m2]的中位數(shù)，則median=Medianl。

當(dāng)A[ml]>B[m2]時，設(shè)median2是A[il：ml]和B[i2：

J2]的中位數(shù)，類似地有median=median2o

通過以上的討論，可以設(shè)計出查找兩個子數(shù)組A和

B[i2:j2]的中位數(shù)median的算法。

(2)算法復(fù)雜性。

設(shè)在最壞情況下，算法所需的計算時間為T(2n)0由算法中

ml和m2的選取策略可知，在遞歸調(diào)用時、數(shù)組A和B的大小都減

少了一半。因此，T(2n)滿足遞歸式：

解此速歸方程可得：T(2n)=0(logn)0

比如A={12,34,56,62,78,81,95},B={23,38,45,

67,89,103,120)0求數(shù)組A和B中位數(shù)。

解析：ml=(il+jl)/2=3,m2=(i2+j2)/2=3。

A[ml]=62,B[m2]=67,則根據(jù)

當(dāng)A[ml]<B[m2]時，設(shè)medianl是A[ml：jl]

和B[i2：m2]的中位數(shù)，則median=Medianl。

有：

median=A[ml：jl]和B[i2：m2]的中位數(shù)

=A[3：6]和B[0：3]的中位數(shù)

=(62,78,81,95}和{23,38,45,67}的中位數(shù)

=62

再比如A={12,34,56,62,78,81,95},B={23,38,45,

60,89,103,120}o求數(shù)組A和B中位數(shù)。

解析：ml=(il+jl)/2=3,m2=(i2+j2)12=3。

A[ml]=62,B[m2]=60,則根據(jù)

當(dāng)A[ml]>B[m2]時，設(shè)median2是A[i1：ml]

和B[m2：j2]的中位數(shù)，類似地有median=median2。

有：

median=A[0：3]和B[3：6]的中位數(shù)

=A[3：6]和B[0：3]的中位數(shù)

=｛12,34,56,62｝和｛60,89,103,120｝的中位數(shù)

=60

6.利用整數(shù)相乘算法3-7計算兩個二進(jìn)制數(shù)1011和1101及

兩個十進(jìn)制數(shù)3141和5327的乘積。

解答：

(1)x=1011,y=1101

MuKlOll,1101,4)〃整數(shù)相乘算法3.1

A=10,B=ll,C=ll,D=01

ml=Mul(A,C,n/2)=Mul(10,11,2)〃遞歸調(diào)用

A=l,B=0,C=l,D=1

ml=Mul(A,C,n/2)=Mul(l,1,2/2)=1〃遞歸調(diào)用并返回

Mul(l,1,2/2)

m2=Mul(A-B,D-C,n/2)=Mul(l,0,2/2)=0

m3=Mul(B,D,n/2)=Mui(0,1,2/2)=0

1*(1*22+(1+0+0)*2'+0)=110//返回Mui(10,11,2)=110

m2=Mul(A-B,D-C,n/2)=Mul(10-11,01-11,2)=

Mul(-1,-10,2)

s=(-1)*(-1)=1

A=0,B=l,C=l,D=0

Jml=Mui(A,C,n/2)=Mul(O,1,2/2)=0

m2=Mul(A-B,D-C,n/2)=Mui(-1,-1,2/2)=l

m3=Mui(B,D,n/2)=Mui(1,0,2/2)=0

1*(0*2?+(0+1+0)*2'+0)=10

m3=Mui(B,D,n/2)=Mui(11,01,2/2)

A=l,B=l,C=0,D=1

ml=Mui(A,C,n/2)=Mui(1,0,2/2)=0

m2=Mul(A-B,D-C,n/2)=Mui(0,1,2/2)=0

m3=Mui(B,D,n/2)=Mul(l,1,2/2)=l

1*(0*2?+(0+0+1)*241)=11

l*(110*24+(110+10+ll)*22+ll)=10001111//返回Mui(1011,

1101,4)=10001111

(2)x=3141,y=5327

Mui(3141,5327,4)〃整數(shù)相乘算法4.1

A=31,B=41,C=53,D=27

ml=Mul(A,C,n/2)=Mul(31,53,2)

A=3,B=l,C=5,D=3

Jml=Mui(A,C,n/2)=Mui(3,5,2/2)=15

m2=Mul(A-B,D-C,n/2)=Mui(2,-2,2/2)=-4

m3=Mui(B,D,n/2)=Mui(1,3,2/2)=3

1*(15*10,(15-4+3)*10+3)=1643

m2=Mul(A-B,D-C,n/2)=Mul(31-41,27-53,2)=

Mui(-1,-10,2)

s=(-l)*(-1)=1

A=l,B=0,C=2,D=6

ml=Mui(A,C,n/2)=Mui(1,2,2/2)=2

m2=Mul(A-B,D-C,n/2)=Mui(1,4,2/2)=4

m3=Mui(B,D,n/2)=Mui(0,6,2/2)=0

1*(2*102+(2+4+0)*10'+0)=260

m3=Mul(B,D,n/2)=Mui(41,27,2/2)

A=4,B=l,C=2,D=7

Jml=Mui(A,C,n/2)=Mui(4,2,2/2)=8

m2=Mul(A-B,D-C,n/2)=Mui(3,5,2/2)=15

m3=Mul(B,D,n/2)=Mul(l,7,2/2)=7

l*(8*102+(8+15+7)*10l+7)=1107

1*(1643*10,(1643+260+1107)*102+1107)=16732107〃返

回Mui(3141,5327,4)=16732107

7.修改整數(shù)乘積算法3-7,把每個整數(shù)分成：(1)三段，(2)

四段，然后給出相應(yīng)算法的復(fù)雜度。

解答：

(1)三段。

假定n是3的哥。我們把n位的二進(jìn)制整數(shù)看成由三個n/3

位整數(shù)構(gòu)成的。則有：

那么，X和Y的乘積可表示為：

2n/3n/3

X*Y=(A2+B2+C)*(D22n/3+E2n/3+F)

=AD2'n/3+(AE+BD)2n+(AF+BE+CD)22n/3+(BF+CE)2n/3+CF

改進(jìn)如下：

X*Y=AD2"+(VW+AD+BE)2n+(MN+AD+BE+CF)22n/3+(PS+BE+CF)

2n/3+CF

其中，V=A-B,W=E-D,M=A-C,N=F-D,P=B-C,S=F-E

時間分析：記T(n)為算法的最壞時間，則比較總次數(shù)為

方程的解是

算法：分三段整數(shù)乘積

輸入：兩個n位的二進(jìn)制整數(shù)X和Y。

輸出：整數(shù)的乘積。

IntMult(X,Y,n)

{s=sign(X)*sign(Y);

X=abs(X);Y=abs(Y);

If(n==l)

ReturnX*Y;

Else