算法設計與分析課后答案+田翠華著_第1頁
算法設計與分析課后答案+田翠華著_第2頁
算法設計與分析課后答案+田翠華著_第3頁
算法設計與分析課后答案+田翠華著_第4頁
算法設計與分析課后答案+田翠華著_第5頁
已閱讀5頁,還剩109頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

參考答案

第1章

一、選擇題

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

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

二、填空題

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

2.程序;有窮性

3.算法復雜度

4.時間復雜度;空間復雜度

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

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

7.復雜性盡可能低的算法;其中復雜性最低者

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

9.基本運算

10.原地工作

三、簡答題

1.高級程序設計語言的主要好處是:

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

術人員只需要兒周時間的培訓就可以勝任程序員的工作;

(2)高級語言為程序員提供了結構化程序設計的環(huán)境和工

具,使得設計出來的程序可讀性好,可維護性強,可靠性高;

(3)高級語言不依賴于機器語言,與具體的計算機硬件關系

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

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

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

性勞動,提高程序質量。

2.使用抽象數據類型帶給算法設計的好處主要有:

(1)算法頂層設計與底層實現分離,使得在進行頂層設計時

不考慮它所用到的數據,運算表示和實現;反過來,在表示數據

和實現底層運算時,只要定義清楚抽象數據類型而不必考慮在什

么場合引用它。這樣做使算法設計的復雜性降低了,條理性增強

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

序可靠性高。

(2)算法設計與數據結構設計隔開,允許數據結構自由選擇,

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

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

映它們之間內在的互相依賴和互相制約的關系,便于空間和時間

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

(4)由于頂層設計和底層實現局部化,在設計中出現的差錯

也是局部的,因而容易查找也容易糾正,在設計中常常要做的增、

刪、改也都是局部的,因而也都容易進行。因此,用抽象數據類

型表述的算法具有很好的可維護性。

(5)算法自然呈現模塊化,抽象數據類型的表示和實現可以

封裝,便于移植和重用。

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

(7)算法結構清晰,層次分明,便于算法正確的證明和復雜

性的分析。

3.算法的復雜度是算法運行所需要的計算機資源的量。

4.當問題的規(guī)模遞增時,將復雜度的極限稱為漸進復雜度。

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

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

四、計算題

1.驗證下面的關系:

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

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

證明1:數學歸納法。

證明2:反證法。

證明3:定義證明

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

0(7?log77),£?=0(,)。

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

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

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

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

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

現。

而當〃N〃()時,Ci<Glog水Qn<&Hog水C5萬成立。

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

函數的集合,它用以表達一個算法運行時間的上界。

則£(〃)的上界〈分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,-??,的階是

力不是數值上相等。

是數值求和,即首項為〃的〃項等差為〃的數列求和

所以,。應該是:

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

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

=0(max(f,g))

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

3.求以下各式的漸進表達式:

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)表示常數;

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

6log4n-0(7?)O

4.按照漸進階從低到高的順序排列下列表達式:

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

解答:

1

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

5.確定關系:對于下列各組函數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(n)),則該算法在最壞情況下所需的計算時間是。(f(n))o

證明:

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

度為其競爭對手ABC公司同類產品的100倍。對于計算復雜性分

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

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

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

解答:

n=100/7;

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

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

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

9.

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

X2"。在某臺計算機上實現并完成該算法的時間為1秒?,F有另一

臺計算機,其運行速度為第一臺的64倍,那么在這臺新機器上用

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

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

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

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

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

的問題?

解答:

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

題,則有

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

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

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

問題。

五、上機題

二分檢索是指在一個已經排序的數組中查找一個指定的數據

是否存在的問題。進一步說,假定一個具有4個元素的整型數組a

和一個整數x,數組a的元素已經按由小到大的順序排序,希望查

找X在數組a中是否出現。若出現,輸出對應的數組元素下標,

否則,輸出不存在信息。

編程時具體的實現方法是:將?x與a的中間元素a\_N/2]比

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

可以肯定x只可能出現在前半個數組中;若x>a[N/2],則x

只可能出現在后半個數組中。然后,將得到的半個數組看成原來

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

一個相等的元素為止。

在進行程序設計時,力是數組大小的上限,實際的元素個數由

鍵盤輸人。

#include<stdio.h>.

ttdefneN50

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

個數和被查找的值

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

最大和中間元素下標

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

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

{mid=(k+m)/2;〃取中間下標,注意整數相除取整

if(x==a[mid];

returnmid;〃相等時綺束,返回元求下標

else

if(x<a[mid])

m=mid-1;〃x應在前半個數組中,最大下標凋

else

k=mid+1;〃x應在后半個數組中,最小下標調

)

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

返回-1作標志

)

voidrnain()

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

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

個數

scanf("%d",&n);

printf(“'Inputal1elermnts:'');

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

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

用空格分隔

printf(inputdatasearched");

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

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

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

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

第2章

一、選擇題

1.C2.C

二、填空題

1.遞推法;生成函數法;特征方程法;數學歸納法;不規(guī)

則法

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

利于透徹理解遞歸機制

三、簡答題

1.人們在解決一些復雜問題時,為了降低問題的復雜程度

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

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

題進行求解,而只是在解決了最后那些最簡單的問題后,再沿著

原來分解的逆過程逐步進行綜合,這就是遞歸的基本思想。

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

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

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

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

四、計算題

1.求和:

(1)

(2)

解答:

(1)設和為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)設和為S,則有

當n為偶數時,

當n為奇數時,

2.設回〃都是整數,計算

(1)(加勿)/2」+(77-研1)/2」

(2)「(77+%)/21+「(77-研1)/21

解答:

(1)因為勿,〃都是整數,所以加加與止"同時為奇數或偶數。

當加必與77-%同時為奇數時,原式=(/?+獷1)/2+(ZT研1)/2=

n

當〃+/與77-必同時為偶數時,原式=(72+血/2+(77-%)/2=n

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

數。

當??+勿與ZT?必同時為奇數時,原式=(77+研1)/2+(77-研1)/2=

n+\

當n+m與n-m同時為偶數時,原式=(〃+%)/2+^n-ni)/2+1=n+\

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

(1)(LX」差=2」

⑵「(「x[)"2]=「

(3)r(LJ)1/21=「一1

解答:(1)當后代k為整數時,原等式成立。

當為整數時,原等式不成立。此時左端不一定為整數,

而右端為整數。

(2)等式成立。

(3)當尸〃,k為整數時,原等式成立。

當xa4為整數時,原等式不成立。此時,(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)當x,y為整數時,原等式成立。

當x,y不為整數時,令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)當x,y為整數時,原不等式成立。

當x,y不為整數時,令*=「才]—^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)當A為2"時,「log(/zH)1=A+1,而Llogz?J+1=A+l,

所以,原等式成立。

當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)當爐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+勿)=左端

所以,原等式成立。

當爐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.設x,y為任意實數,定義:

{xmody-x-y\_x/yJ,當yW0

xmod0=x

依據上述定義:

(1)若尸-1,計算xmod28o

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

解答:

(1)當下T時一,xmod28=(-l)mod28=(-1)-28L(T)/28」

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

(2)

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

成立,此時x>0。

用數學歸納法證明命題:當上2時,有xmod3=2,成立。

當/7=3時,有xmod5=3,成立。

假設當〃=A時,有Amod(2A-1)=k

成立,

然后證明當爐〃+1成立。所以,命題成立。

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

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

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

所以,Amodl5=8o

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

.??存在整數%,使得:x=3左+2,同時,x=5L+3,

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

/3+2

k、,人為整數.??存在整數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〃的生成函數。

解答:根據題義,得

〃(0)=2,77=0

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

設生成函數為,將,(〃)=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?,試求出劣的非遞歸形式的表

達式。

解答:原方程所對應的特征方程為:

(a2-a-6=0

為齊次方程,則齊次解:S=3,0=-2,重數均為1。

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

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

{A+B=l

34-2廬1

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

從而,得當的非遞歸形式的表達式為:4=(3"-/5。

8.設有國,=0,品=1,a=T和a=-a^i+16五2-20a^,當〃

N3。求出a”的表達式。

解答:原遞歸方程所對應的特征方程為:

/+/-16^-20=0

解得特征方程的根:<7.=-5,/=2,重數分別為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

從而,得當的非遞歸形式的表達式為:/=(5/49W7)*2"

+(-5)ntl/49o

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

式。

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

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

齊次特征的解為:s=3,0=-2,重數均為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)

證明:根據遞歸方程,遞推得

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)當〃=2時,由遞歸方程和初值,推得

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

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

(2)假設當4時.成立,既有7(〃)=A「log〃]-2hogAl+1

是原遞歸方程的解。

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

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

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

+1

當爐A+1且A為奇數時,有

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)

當上〃+1且A為偶數時,有

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)

即當n=k+l時;命題成立。

所以,原命題成立。

五、上機題

1.計算Hermite多項式

Voidmain()

(

Printf(“\n%f“,H(2,2.0));//輸出結果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.求解漢諾塔問題

漢諾塔問題:設4B、。是三根金針。開始時,在金針4上

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

從小到大編號為1,2,…,n,如圖A-1所示。現要求將金針A

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

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

在移動紙盤時應遵守以下移動規(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)漢諾塔問題的非遞歸算法。

教材中所述非遞歸算法的目的塔座不確定。當n為奇數時,

目的塔座是B,按順時針方向移動;而當n為偶數時,目的塔座為

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]++;

}

]

下面用數學歸納法證明遞歸算法和非遞歸算法產生相同的移

動序列。

當27=1和77=2時容易直接驗證。設當k&n~\時,遞歸算

法和非遞歸算法產生完全相同的移動序列。考察的情形。

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

盤塔座間的移動(0)o

當〃為奇數時,順時針非遞歸算法產生的移動序列為:C,0,

C,0,C;逆時針非遞歸算法產生的移動序列為:CC,0,CC,

0,…,CCo

當n為偶數時,順時針非遞歸算法產生的移動序列為:CC,0,

CC,0,CC;逆時針非遞歸算法產生的移動序列為:C,0,C,

0,…,Co

①當n為奇數時,順時針遞歸算法Hanoi(n,A,B,C)產

生的移動序列為:

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

C,B,A)產生的移動序列。

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

數圓盤逆時針移動問題。由數學歸納法知,產生的移動序列均為:

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

列為:C,0,C,0,Co

②當n為偶數時,順時針遞歸算法Hanoi(n,A,B,C)產

生的移動序列為:

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

C,B,A)產生的移動序列。

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

數圓盤逆時針移動問題。由數學歸納法知,產生的移動序列均為:

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

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

當n為奇數和偶數時的逆時針遞歸算法也類似。

由數學歸納法即知,遞歸算法和非遞歸算法產生相同的移動

序列。

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

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

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

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

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

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

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

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

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

之上;

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

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

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

試設計一個算法,用最少的移動次數將塔座4上的〃個圓盤

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

分析與解答:

可用教材中的標準Hanoi塔算法。問題是要證明標準Hanoi

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

用數學歸納法。

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

為輔助塔座,移到目的塔座〃上的標準Hanoi塔算法。

歸納假設:當圓盤個數小于〃時一,Hanoi(〃,A,B,C)不違

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

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

偶性。

當圓盤個數為n時,標準Hanoi塔算法Hanoi(〃,A,B,C)

由以下3個步驟完成。

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

②Move(A,B);

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

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

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

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

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

偶性。

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

相同。

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

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

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

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

具有相同奇偶性。

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

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

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

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

第3章

一、選擇題

1.B2.B

二、填空題

1.LlognJ+1

2.2n-l

三、簡答題

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

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

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

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

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

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

始問題的解,必須找到一種途徑能夠將各個子問題的解組合成原

始問題的一個完整答案。

2.將待查的數據與非降序數組中的中間元素進行比較,若

二者相等則表示查到;若該數據小于中間元素的值,則下次在數

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

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

查到該值的元素或不存在所查找的數據。此種分治方法,稱為二

分檢索。

四、計算題

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

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

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

的項。4[0]未用。

輸出:若¥在力中,輸出下標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;

)

時間分析:比較次數

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

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

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

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

的項。的0]未用。

輸出:若X在A中,輸出下標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;

}

時間分析:比較次數

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

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

最大元素的算法,使其復雜度為n+logn-2。

算法:找最大和次大元素

輸入:有n個元素的數組A

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

voidFind(A)〃遞歸算法

{if(|A|==2)

{設人=匕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)為算法的最壞時間。當n=2時-,T(n)=l;當

n>2時,則需要進行兩次遞歸調用及之后的比較。故有:

T(n)=5n/2

4.求解最接近中位數的k個數:給定由n個互不相同的數

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

找A中最接近A的中位數的k個數的算法。在采用分治法進行查

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

本相同的子數組,其中的那個劃分點就是中位數。所以,中位數

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

個元素,即中位數是第「n/21小的數。

解析:

(1)找出A中的中位數mid;

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

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

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

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

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

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

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

近中位數的k個數。

(1)找出A中的中位數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)根據b找出所要的解{a,1a-mid|Wb,aeA}:{30,

27,35}o

5.求有序數組A和B的中位數

設A[0:n-1]和B[0:n-1]為兩個數組,每個數組中含有

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

和B的2n個數的中位數median。

解析:

(1)算法設計思想。

考慮問題的一般性:設A[il:jl]和BLi2:j2]是A和B

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

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

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

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

WmedianWA[il]。

設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

當A[ml]=B[m2]時,median=A[ml]=B[m2]。

當A[ml]<B[m2]時,設medianl是A[ml:jl]和B[j2:

m2]的中位數,則median=Medianl。

當A[ml]>B[m2]時,設median2是A[il:ml]和B[i2:

J2]的中位數,類似地有median=median2o

通過以上的討論,可以設計出查找兩個子數組A和

B[i2:j2]的中位數median的算法。

(2)算法復雜性。

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

ml和m2的選取策略可知,在遞歸調用時、數組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求數組A和B中位數。

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

A[ml]=62,B[m2]=67,則根據

當A[ml]<B[m2]時,設medianl是A[ml:jl]

和B[i2:m2]的中位數,則median=Medianl。

有:

median=A[ml:jl]和B[i2:m2]的中位數

=A[3:6]和B[0:3]的中位數

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

=62

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

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

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

A[ml]=62,B[m2]=60,則根據

當A[ml]>B[m2]時,設median2是A[i1:ml]

和B[m2:j2]的中位數,類似地有median=median2。

有:

median=A[0:3]和B[3:6]的中位數

=A[3:6]和B[0:3]的中位數

={12,34,56,62}和{60,89,103,120}的中位數

=60

6.利用整數相乘算法3-7計算兩個二進制數1011和1101及

兩個十進制數3141和5327的乘積。

解答:

(1)x=1011,y=1101

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

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

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

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

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

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)〃整數相乘算法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.修改整數乘積算法3-7,把每個整數分成:(1)三段,(2)

四段,然后給出相應算法的復雜度。

解答:

(1)三段。

假定n是3的哥。我們把n位的二進制整數看成由三個n/3

位整數構成的。則有:

那么,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

改進如下:

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)為算法的最壞時間,則比較總次數為

方程的解是

算法:分三段整數乘積

輸入:兩個n位的二進制整數X和Y。

輸出:整數的乘積。

IntMult(X,Y,n)

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

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

If(n==l)

ReturnX*Y;

Else

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論