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

參考答案

第1章

一、選擇題

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

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

二、填空題

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

2.程序；有窮性

3.算法復(fù)雜度

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

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

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

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

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

9.基本運(yùn)算

10.原地工作

三、簡答題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

序可靠性高。

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

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

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

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

耗費(fèi)的折衷，靈活地滿足用戶要求。

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

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

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

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

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

封裝，便于移植和重用。

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

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

性的分析。

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

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

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

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

四、計(jì)算題

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

0(1)<0(log77)<0(Z?)<0(Z?log77)<0(z?2)

及0(2。)<0(〃!)<0(4)。

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

證明2：反證法。

證明3：定義證明

令f,(77)=0(1),五(〃)=0(logz?),￡(〃)=0(n),工(〃)=

0(7?10g7?),￡(〃)=05)。

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

和馬，使得對所有的gA)，有A77)<cg(〃)o

那么，就有￡(〃)WC,工(〃)WGlog/7,f￡n)WCsn,

f.\(n)WGniogn,f5(z?)C5n0

所以，O(g(M)之間的比較可以通過HA)之間的比較得以實(shí)

現(xiàn)。

而當(dāng)〃o時(shí)，G<Glogz?<Qn<CAz?logz?<C5成立。

再根據(jù)。(g(M)表示所有/'(M增長的階不超過g(M的

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

則△(〃)的上界<￡(〃)的上界〈右5)的上界<工(血的上界〈

￡(〃)的上界

那么就驗(yàn)證了

0(1)<0(log77)<0(2?)<0(nlogT?)<0(772)O

同理，有：0(2")<0(「!)<0(4)。

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

"1而->8。6/。(1。8〃)=0,所以，。⑴vO(k)g〃).

limO(log刀)/0(刀)=limC,logn/C/i=C.ZClim(Ioge/n)/l=0,所以，O(logn)<0(〃)。

n->a>n->oo2L2〃->oo

limO(〃)/O(〃log〃)=lim〃/(〃log〃)=0,所以，。(〃)vO(〃log〃)。

“一>oo?—>t?

limO(nlogn)/0(n2)=lim(nlogn)/(w2)=lim(logn)/n=0,所以，O(nlogn)<0(1)。

所以，有：0(1)<O(logn)<0(n)<O(/ilogn)<0(n2)o

nn

同理,可證：O(2)<O(n!)<O(n)o

2.找出下述證明中的錯(cuò)誤：因?yàn)椤?0(〃)，2n=0(/?),…,

故：

〃Il

Z5=Z°(〃)=0(〃)〃=0(/)

氏=|^=1

解答：概念不清。

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

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

力如是數(shù)值求和，即首項(xiàng)為〃的〃項(xiàng)等差為〃的數(shù)列求和

*=1

所以，$>*之。5)。應(yīng)該是

*=lA=l

“

牛-

17?+277+3Z?+?+nn=Z?(TT+1)n/2,而

”

小O(w)+O(7i)++0(〃)

〃個(gè)

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

=0(max(f,g))

=0(/7)〃集合操作，上界的并取最大者

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

2n

5/?+8n,3n~/11+3",56+3/n,logn,6log4o

解答：

2

54+8n=0(/7);1

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

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

logz?"=0(log/?);

6log4"=0(7?)o

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

n,log/?,3”,45n,6,3n2,〃!。

解答：

2

log??,45n,3n,5rT,3",n\0

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

(7?)=0(g(n))或廣(〃)=Q(g(〃))或/'(〃)=0(g(〃))，

并簡述理由。

(1)f(〃)=logIT,g(7?)=log〃+7;

(2)f(72)=logn,g(7?)=??；

(3)f(77)=n,g(7?)=log2n；

(4)f(z?)=nlogn+n,g(z?)=logz?；

(5)f(z?)=11,g(z?)=og11；

(6)f(72)=log'n,g(/?)=log72;

(7)f(z?)=2",g(72)=100if-,

(8)f(A)=2",g(77)=3flo

解答：

(1)f(n)=log//=。(log〃+7)=0(g(〃))；

(2)f(n)=logn=0(小)=0(g(n))；

(3)f(zz)=n=Q(log2z?)=Q(g(n))；

(4)f(n)=nlogn+n=Q(logn)=Q(g(/?))；

(5)f(.ri')=11=0(log11)=0(g(/?))；

(6)f(.ri')=log?n=Q(log7?)=Q(g(〃))；

(7)f(/7)=2"=。(100n)=Q(g(〃))；

(8)f(n)=2"=0(3")=0(g(加)。

6.證明：〃！=0(")o

證明：

n\?(2^/z)1~(k/e)"(1+0(1/〃))

=lim(2乃〃)'~(1+0(1/〃))/〃"=0

/.n\=。(〃")

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

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

證明：

4(N)=ZP(I)T(NJ)<ZP(/)甲axTXM/'QTXM/')gP(/)

IWDNIWDN1EDFT/￡%

=T(N，m)

r、”x⑻=。億￡"))=Q(。(/(")))=。(/("))

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

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

別為〃，n2,r和加的各算法，若用ABC公司的計(jì)算機(jī)在1小時(shí)

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

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

解答：

n=100/2；

n2=100z?2,n=10z?;

n3=100z?3,n=10V3Z?=4.64Z?;

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

9.

(1)假設(shè)某算法在輸入規(guī)模為免時(shí)的計(jì)算時(shí)間為7(加=3

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

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

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

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

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

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

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

的問題？

解答：

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

題，則有

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

(2)n2=64T72,得=872；

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

問題。

五、上機(jī)題

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

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

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

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

否則，輸出不存在信息。

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

較，如果相等則結(jié)束。否則，若x〈a[AV2],由于a是有序的，

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

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

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

一個(gè)相等的元素為止。

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

鍵盤輸人。

#include<stdio.h>.

ttdefneN50

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

個(gè)數(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;〃相等時(shí)綺束，返回元求下標(biāo)

else

if(x<a[mid])

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

整

else

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

整

)

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

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

}

voidmain()

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

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

個(gè)數(shù)

scanf("%d",&n);

printf(u'Inputal1elermnts:'');

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

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

用空格分隔

printf("inputdatasearchedv;

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.遞歸消除有利于提高算法的時(shí)空性能；研究遞歸消除有

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

三、簡答題

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

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

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

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

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

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

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

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

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

四、計(jì)算題

1.求和：

⑴t<a

i=l

(2)y,,.'

乙Cn

i-i

解答：

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

S=a+2a2+3/+???+〃/①

等式兩邊同乘a,得

aS=a2+2a+,''+na"，｝②

①-②得：

(1-a)S=a+a2+a+'^+a1-na'y

整理得：

S-a(l-a")/(1-a)--na^/(1-a)

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

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

S=C：+2c：+3C；++n/2c"2+(”/2+l)C；/2+,++(n-2)Cf2+(H-1)C；-1+nC；,

；；；/2；

=nC'n+nC+++“Cl"+n/2C+nC

=〃/2(C：+d+C；++C；/2+C；/2t,++C：-2+C：；-'+C；；)+n/2C：；

=n/2(2"-l)+n/2

=iilnX

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

S=C：+2C；+3C；++(?-l)/2cz"2+5+1)/Ze：""?++(n_2)C；2+(n_1)C；I+nC：

=，C+〃C；+〃c；++y+〃c：

="(C：+C：+C；++C：-W)+"C：2.

=n12(C：+C：+C；++a”"2+C；*i"2++(n-2)C；-2+("-1)C；'+C；)+"/2C；

=n/2(2"-l)+n/2

=〃2”T

設(shè)勿，〃都是整數(shù)，計(jì)算

(1)|_(〃+而/2」+[_(zr研1)/2」

(2)「(〃+勿)/2]+「(zr■研1)/2~|

解答：

(1)因?yàn)槲?，〃都是整?shù)，所以〃+勿與止勿同時(shí)為奇數(shù)或偶數(shù)。

當(dāng)〃+勿與77-勿同時(shí)為奇數(shù)時(shí)，原式=(〃+zzrl)/2+(zr研1)/2=

n

當(dāng)〃+勿與/?-勿同時(shí)為偶數(shù)時(shí)，原式=(〃+%)/2+(27-%)/2=n

(2)同理，",〃都是整數(shù)，所以〃+勿與〃-勿同時(shí)為奇數(shù)或偶

數(shù)。

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

〃+1

當(dāng)〃+勿與n-m同時(shí)為偶數(shù)時(shí)，原式=(77+勿)/2+(n~瑤]2+1=〃+1

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

(I)(Lx」)s=Lx1/2J

(2)「(「一)”21=「/2]

(3)r(Lx」)"21=「一1

解答：(i)當(dāng)戶此k為整數(shù)時(shí)，原等式成立。

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

而右端為整數(shù)。

(2)等式成立。

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

當(dāng)xW*,A為整數(shù)時(shí)，原等式不成立。此時(shí)，(Lx」)"2<「x

1匕所以左端小于右端。

4.求證：

(1)l_x」+l_y」Wx+y

(2)「x]+「yl2「x+y〕

(3)「log(z?+l)~|=Llogz?J+1

(4)L(x+ni)/n\=L(LxJ+力)/〃」

⑸力?/2」=L〃74

k=\

證明：

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

當(dāng)x,y不為整數(shù)時(shí)，令x=|_x」+Ax,y=LyJ+Ay,其

中0<Ax,AyWlo則有

x+y=|_x」+Ax+|_y」+Ay=L.x」+L,y」+Ax+A

y

因?yàn)?<Ax,Ay<1,所以0<Nx+ky<2

貝l」l_x」+Ly」+Ax+Ay〉Lx」+Ly」，即有：x+y

>L^J+LyJ

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

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

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

中0<Ax,Ay<1。則有：

「x+yl=「「x]-Ax+「y]-Ay[=「「x[+「y]—(A

x+Ay)1

因?yàn)?WAx,Ay<1,所以有0WNx+Ny<2。因此，

「x+y1W「「xl+「y]]=「xl+「4

所以，原不等式「4+「yl2「x+y]成立。

(3)當(dāng)〃為2"時(shí)，「log(〃+l)]=A+1,而LlogzzJ+1=A+1,

所以，原等式成立。

當(dāng)〃不為2"時(shí)，則次此處A=|_log〃」，那么2"+1"

+1W2,則有：

riog(?2+l)l=A+1,Llogz?J+1=k+\,所以，原等式成立。

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

而“(8+間/〃-(|_》」+，”)/“=0,這里x=l_x」+Ax,0WAx<1

左端=litn|(|_A*J+|^B^|t^pJ+/nyn|=limx/n=0=右端

所以，原等式成立。

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

左端=0+1+1+2+2+3+3+…+研獷2*(1+))m/2-m{\+in)

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

所以，原等式成立。

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

左端=0+1+1+2+2+3+3+…+(/zrl)+(/zrl)+/?

2*(l+zzrl)(zzrl)/2+/=m

右端=l_(2勿)2/4」-m-/=左端

所以，原等式成立。

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

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

xmod0=x

依據(jù)上述定義：

(1)若尸T,計(jì)算xmod28o

(2)若xmod3=2,xmod5=3,求xmod15。

解答：

(1)當(dāng)尸T時(shí)，mod28=(-l)mod28=(-1)-28L(T)/28」

=-1-28*(-1)「1/28~|=27

(2)

①當(dāng)xmod3=2,xmod5=3,那么有命題xmod(2zrl)=z?

成立，此時(shí)x>0。

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

當(dāng)72=3時(shí)，有xmod5=3,成立。

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

成立，

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

即有：xmod(2(A+1)-1)=A+1。

根據(jù)命題Amod(2T?-1)=n,有在Amod(2zrl)=Amodl5中，

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

所以，Amodl5=8o

②

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

，存在整數(shù)左，kz,使得：x=3左+2,同時(shí)，x=5^+3,

即有：3左+2=54+3,得左=(5左+1)/3=5(左T)

/3+2

???左，人為整數(shù)存在整數(shù)衣，使得：k=(左T)/3,即

有：左=3A+1

...x=5L+3=5(34+l)+3=15A+8

jrmodl5=8o

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

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

{〃（0）=2,72=0

H（n）=2n+3n,n=l,2,3,…

設(shè)生成函數(shù)為G（X）=￡“（〃）X”，將〃（〃）=2〃+3"代入，得

n=O

G（x）=￡（2"+3"卜"，

n-O

將上式展開并整理，得

G(x)=[2-5才+(2n+2+3n)Z*+(3*2a+2*3"|)xF/[(1-2^)(1-3^)]

7.給定a0=l,l31=1,a*2=a〃+i+6a0,試求出a〃的非遞歸形式的表

達(dá)式。

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

a2-a-6=0

為齊次方程，則齊次解：S=3,3=-2,重?cái)?shù)均為1。

記通解的形式為：3=4s"+氏72"=43"+B（-2）n

將ao=l,ai=l代入上式，得

A+B=l

34-2爐1

解得：4=3/5,分2/5

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

8.設(shè)有ao=O,ai=l,a2=-l和a?=-an-i+16a?-2-20a^,當(dāng)n

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

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

/+/-16^20=0

解得特征方程的根：6=-5,0=2,重?cái)?shù)分別為1和2。

nn

記通解的形式為：a尸(A+Bn)qx+Cq/=(A+Bn)*2+6*(-5)"

將ao=0,a}=1,&=T代入上式，得

"A+C=0

Y

2(4+而-5C=1

4(4+26)+(-5y--1

解得：4=5/49,爐1/7,^-5/49

從而，得名的非遞歸形式的表達(dá)式為：a尸(5/49W7)*2"

+(-5嚴(yán)/49。

9.設(shè)為=1,4=5,a尸ag+6a",當(dāng)〃22。求出的解析表達(dá)

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

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

齊次特征的解為：6=3,桃=-2,重?cái)?shù)均為1。

記通解的形式為：4=力6"+方Q2”=43"+6(-2)n

將a()=l,ai=5代入上式，得

{4+B=l

3A-2B=5

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

n0+1

記通解的形式為：an=Aq：+Bq2=(7*3"+(-2))/5

10.求解方程：

{T(2)=1,n=l

7(〃)="〃丁(4/2)+〃，〃>2,且有片使得機(jī)2?”

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

75)=/7,/2T(771/2)+n

=J2[(J2)"27(5")/2)+J2]+A

=n/2nI/4T(Z?I/1)+n+n

=/2，/2/71/4[(/7l/4)1/2A(/7，/4)1/2)W/，]+2/7

=nV4口i/?T(/)+3〃

令％2九則有

,QBG&J付）彷）r（丹3"

=22*'>2-^；(22-)+4?

=22"+*+22逐“++2：(2)+及

=22'+^

7(/7)=/2(l/2+log(log/7))

11.求證方程

x(l)=1,n=1

r-1

的解是x(n+l)=CZ/(n+l)

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

x⑵=x(l)x(1)=1=8/2

x(3)=x(l)x(2)+x(2)x(1)=1+1=2=C\/3

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

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

x⑷x⑴=14=C%/5

X(〃)=C''2(片l)/〃

X(》1)=仁2〃/(加1)

12.求證遞歸方程

{7(1)=0

7(/7)=T(Ln/2\)+T(「〃/21)+〃-1,A>1

的解是=A「log/21-2riogn1+lo

證明：

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

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

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

(2)假設(shè)當(dāng)時(shí)成立，既有7(m=在「logA]-2M+1

是原遞歸方程的解。

那么當(dāng)〃=A+1時(shí)，下面證明7U+1)=(A+l)「log(4+l)]-2r

1。晨是原遞歸方程的解。

當(dāng)〃WA時(shí)，7(14/2」)+T(「k/2\)+hl=k「log￡|-2「儂八

+1

當(dāng)〃=4+1且女為奇數(shù)時(shí)，有

7([_(女+1)/2」)+7(「(々+1)/21)+A+1-1

=7(|_4/2」+1)+7(「女/2])+k

=27(「4/21)+4

=2[\k/2\?Flog「4/211-2「皿「"211+i]+攵

=(4+1)?「log「4/211-2「儂「SU"+2+左

riog(k+1)/2+10g21

=(A+1)(Flog(A+l)/2+11)-2+1

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

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

=T(A+1)

當(dāng)77=々+1且4為偶數(shù)時(shí)，有

7(1_01)/2」)+7(「(4+1)/2])+A+1-1

=7(4/2)+7U/2+1)+k

=(V2)riog(V2)l-2riog(k/2)1+1+[(A/2+1)「logJ/2+1)1

-2riog(k/2+l)1+1]+k

=(4/2+A/2+l)Flog(V2)l-(2「0(k/2)1+2「io，(k/2+Dl)+2+k

=(々+1)Flog(V2)l-2r，og(k/2)1+1+2+k

=T(A+1)

即當(dāng)n-k+\時(shí)，命題成立。

所以，原命題成立。

五、上機(jī)題

1.計(jì)算Hermite多項(xiàng)式

Voidmain()

(

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

)

DobuleH(intn,floatx)

Switch(n)

Case0:return1;

Case1:2*x;

)

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

)

2.求解漢諾塔問題

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

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

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

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

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

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

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

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

之上；

規(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-1,C,B,A);

}

}

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

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

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

C,按反時(shí)針方向移動。為確定起見，規(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][1]=n+l;

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

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

while(top[l]<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)〃=1和〃=2時(shí)容易直接驗(yàn)證。設(shè)當(dāng)kWn~\時(shí)，遞歸算

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

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

盤塔座間的移動(0)。

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

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

0,…，CCo

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

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

0,…，Co

①當(dāng)n為奇數(shù)時(shí)，順時(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í)針移動問題。由數(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ù)時(shí)，順時(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(n-l,C,B,A)均為奇

數(shù)圓盤逆時(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í)的逆時(shí)針遞歸算法也類似。

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

序列。

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

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

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

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

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

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

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

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

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

之上；

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

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

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

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

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

分析與解答：

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

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

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

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

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

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

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

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

偶性。

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

由以下3個(gè)步驟完成。

①Hanoi(n—1,A,C,B)；

②Move(4B)；

③HanoiC,B,A)O

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

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

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

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

偶性。

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

相同。

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

座夕上倒數(shù)第2個(gè)圓盤的編號與n-1具有相同奇偶性，塔座A上

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

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

具有相同奇偶性。

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

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

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

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

第3章

一、選擇題

1.B2.B

二、填空題

1.LlognJ+1

2.2n-l

三、簡答題

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

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

如果原問題可分割成勿個(gè)子問題，\＜辰小并且這些子問題都可

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

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

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

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

始問題的一個(gè)完整答案。

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

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

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

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

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

分檢索。

四、計(jì)算題

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

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

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

的項(xiàng)。40]未用。

輸出：若乃在[中，輸出下標(biāo)j滿足加刃=片，否則輸出0。

IntBinarySearch(A,n,X)

{intk=l;m=n;

while(k<=m)

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

if(X==A[j])

returnj;

if(X<A[jJ)

m=j-1

else

k=j+1;

return0；

}

時(shí)間分析:比較次數(shù)7(〃)上…/2T(2/3)/2

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

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

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

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

的項(xiàng)。爪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=L(k+m)/3」*/

if(X==A[i])

returni;

if(X<A[iD

m=i-1

else

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

*/

if(X==A[j])

returnj;

if(X<A[j])

{k=i+1;

m=j-1}

else

k=j+1;

return0；

}

時(shí)間分析：比較次數(shù)7(止,一…:二，,

']l/3*(l+T(〃/3))+2/3(2+7'(〃/3))=5/3+7'(〃/3)n>\

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

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

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

算法：找最大和次大元素

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

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

voidFind(A)〃遞歸算法

{if(|A|==2)

{設(shè)A={a,b}

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

}

else

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

(Maxl^SubMaxl)Find(Al);

(Max2^SubMax2)Find(A2);

SubMax3=Min(Maxi,Max2);

SubMax4=Max(SubMaxi,SubMax2)

(Ma^~SubMax)(Max(Max1,

Max2),SubMax(SubMax3,SubMax4))

)

}

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

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

[1〃=2

r(，1)=[2T(n/2)+4n<2

T(n)=5n/2

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

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

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

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

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

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

個(gè)元素，即中位數(shù)是第Fn/21小的數(shù)。

解析：

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

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

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

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

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

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

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

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

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

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

35,50,80},mid=30o

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

3,5}o

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

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

27,35}o

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

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

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

和B的2n個(gè)數(shù)的中位數(shù)mediano

解析：

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

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

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

數(shù)組中2(jbil+l)個(gè)數(shù)的中位數(shù)。

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

[il]WmedianWB[j2]o同理，若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—⑵/2。

由于jl—il=j2—i2,故

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

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

i2=il+j20

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

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

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

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

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

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

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

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

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

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

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

7(2〃)=[°⑴，1<C

\T(n)+0(1)”2c

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

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

67,89,103,120)o求數(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í)，設(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)/2=3。

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

當(dāng)A[ml]>B[m2]時(shí),設(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ì)算兩個(gè)二進(jìn)制數(shù)1011和1101及

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

解答：

(1)x=1011,y=1101

Mui(1011,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(1,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,l,2/2)=0

1*