我國科學(xué)院大學(xué)歷年計算機算法作業(yè)和歷年習(xí)題集

中國科學(xué)院大學(xué)歷年習(xí)題

習(xí)題一復(fù)雜性分析初步

1.試確定下述程序的執(zhí)行步數(shù)，該函數(shù)實現(xiàn)一個mXn矩陣與一個nXp矩

陣之間的乘法：

矩陣乘法運算

template<classT>

voidMult（T**a,T**b,intm,intn,intp）

{//mXn矩陣a與nXp矩陣b相成得到mXp矩陣c

for（inti=0；i<m；i++）

for（intj=0；j<p；j++）{

Tsum=0；

for（intk=0；k<n；k++）

Sum+=a[i][k]*b[k][j]；

C[i][j]=sum；

)

語句s/e頻率總步數(shù)

template<classT>

voidMult(T**a,T**b,intm,intn,intp)000

(

for(inti=0;i<m;i++)1m+1m+l

for(intj=O;j<p;j++){1m*(p+l)m*p+m

Tsum=0;1m*pm*p

for(intk=0;k<n;k++)1m*p*(n+l)m*p*n+m*p

Sum+=a[i][k]*b[k][j];1m*p*nm*p*n

C[i][j]=sum;1m*pm*p

)

)

總計2*m*p*n+4*m*p+2*m+l

其中s/e表示每次執(zhí)行該語句所要執(zhí)行的程序步數(shù)。

頻率是指該語句總的執(zhí)行次數(shù)。

2.函數(shù)MinMax用來查找數(shù)組a[O：nT]中的最大元素和最小元素，以下

給出兩個程序。令n為實例特征。試問：在各個程序中，a中元素之間的比擬次

數(shù)在最壞情況下各是多少？

找最大最小元素方法一

template<classT>

boolMinMax(Ta[],intn,int&Min,int&Max)

{//尋找a[0：n-l]中的最小元素與最大元素

〃如果數(shù)組中的元素數(shù)目小于1,那么還回false

if(n<l)returnfalse；

Min=Max=0；〃初始化

for(inti=l；i<n；i++){

if(a[Min]>a[i])Min=i；

if(a[Max]<a[i])Max=i；

returntrue；

最好，最壞，平均比擬次數(shù)都是2*[n-1]

______________找最大最小元素方法二

template<classT>

boolMinMax(Ta[],intn,int&Min,int&Max)

{//尋找a[0：n-l]中的最小元素與最大元素

〃如果數(shù)組中的元素數(shù)目小于1,那么還回false

if(n<l)returnfalse；

Min=Max=0；〃初始化

for(inti=l；i<n；i++){

if(a[Min]>a[i])Min=i；

elseif(a[Max]<a[i])Max=i；

)

returntrue；

i

J

最壞2*〔n-口,最好nT,平均笥蟲

3.證明以下不等式不成立：

1).10n2+9=0(〃)；

2).n2log/?=0(n2);

4.證明:當(dāng)且僅當(dāng)lim/(鹿)/g(〃)=0時,/5)=o(g(〃))o

〃一>00

5.下面那些規(guī)那么是正確的？為什么？

1).{/(〃)=O(%〃)),g(〃)=O(G(〃))}n/5)/g(〃)=O(W〃)/G(〃))；錯

2).{/(")=0(/("))，8(")=。(6(〃))}=>/(〃)/8(〃)=。(/(〃)/6(〃))；錯

3).{/(n)=O(F(n)),g{ri)=O(G(n))}^>/(?)/g(n)=0(F(n)/G(n));錯

4).{/(”)=Q(F(〃)),g(〃)=C(G(〃))}n/(〃)/g(〃)=Q(b(〃)/G(〃))；錯

5).{/(")=C(F(〃)),g(〃)=Q(G(〃))}n/(〃)/g(〃)=O(F(”)/G(〃))。錯

6).{/(?)=0(F(n)),g(〃)=?(G(〃))}n/(〃)/g(〃)=?("〃)/G(〃))對

6.按照漸進階從低到高的順序排列以下表達式：

順序：logn<”<20/1<4幾2<3"<n\

7.1)假設(shè)某算法在輸入規(guī)模是〃時為T(〃)=3*2".在某臺計算機上實現(xiàn)

并完成該算法的時間是f秒.現(xiàn)有另一臺計算機，其運行速度為第一臺的64倍,

那么，在這臺計算機上用同一算法在f秒內(nèi)能解決規(guī)模為多大的問題？

規(guī)模時間復(fù)雜度〔步數(shù)〕原運行速度〔時間/每步〕總時間

nT(”)=3*2"t

關(guān)系式為時間復(fù)雜度〔計算步數(shù)〕*運行速度(時間/每步)=運行所需時間，即

解：設(shè)在新機器上f秒內(nèi)能解決規(guī)模為機的問題，時間復(fù)雜度變?yōu)?(⑼=3*2"，

由于新機器運行速度提高64倍，那么運行速度變?yōu)轳?*,

由關(guān)系式T(〃)*fo=f,0)*3=/,得

n

3*2*t0=t,

解得

2)假設(shè)上述算法改良后，新算法的計算復(fù)雜度為T(〃)="2,那么在新機器

上用f秒時間能解決輸入規(guī)模為多大的問題？

設(shè)在新機器上用f秒時間能解決輸入規(guī)模為N的問題，那么

由于新復(fù)雜度T￡N)=N\新機器的運行速度為,新=2，

64

代入關(guān)系式0(N)*、=f,得

N2*_L=f=3*2〃*玲

64

解得

3〕假設(shè)進一步改良算法，最新的算法的時間復(fù)雜度為T(〃)=8,其余條件

不變，在新機器上運行，在f秒內(nèi)能夠解決輸入規(guī)模為多大的問題？

設(shè)可解決的最大時間復(fù)雜度為Ma、，那么

可解決的最大時間復(fù)雜度為(nax=192*2\(n為原始的輸入規(guī)?！场?/p>

因為丁(〃)=8</穌，且T(〃)為常數(shù)不隨輸入規(guī)模n變化，

所以任意規(guī)模的n都可在t秒內(nèi)解決。

8.Fibonacci數(shù)有遞推關(guān)系：

試求出F{ri)的表達式。

解：方法一：

當(dāng)〃>1時，由遞推公式F(n)=F(n-1)+F(H-2)得

特征方程為

解得

1+V51-V5

x\二—2—，=—2—

那么可設(shè)

由F(2)=2,F(3)=3,解得G=1±萼，c2=--

245

故F(n)=2[(當(dāng)1)向—(上汽產(chǎn)刀,

當(dāng)"=0,1時，帶入驗證亦成立。

故F(n)=-^[(-^2)-'-(1^.)-']

方法二：

也可直接推導(dǎo)

可得

可得

a1+V5

a，B=?2，

設(shè)

b”=aH-aan_x,

那么么為等比數(shù)列，先求出加然后代入即可求得明。

第二章局部習(xí)題參考答案

L證明以下結(jié)論：

1］在一個無向圖中，如果每個頂點的度大于等于2,那么該該圖一定含有圈；

2］在一個有向圖D中，如果每個頂點的出度都大于等于1,那么該圖一定含有

一個有向圈。

1〕證明：設(shè)無向圖最長的跡尸=匕匕…九,每個頂點度大于等于2,故存在

與匕相異的點V'與匕相鄰，假設(shè)V'￡P(guān),那么得到比P更長的跡，與P的取法矛

盾。因此，V'eP,是閉跡，從而存在圈XM…V%.

證明*:設(shè)在無向圖G中，有n個頂點，m條邊。由題意知，m>=(2n)/2=n,

而一個含有n個頂點的樹有n-1條邊。因m>=n>n-l,故該圖一定含有圈。

〔定義：跡是指邊不重復(fù)的途徑，而頂點不重復(fù)的途徑稱為路。起點和終點重合

的途徑稱為閉途徑，起點和終點重合的跡稱為閉跡，頂點不重復(fù)的閉跡稱為圈?！?/p>

2〕證明：設(shè)有向圖最長的有向跡P=…匕，每個頂點出度大于等于1,故

存在修為片的出度連接點，使得匕丫，成為一條有向邊,假設(shè)VWP,那么得到比P

更長的有向跡，與P矛盾，因此必有V'eP,從而該圖一定含有有向圈。

2.設(shè)D是至少有三個頂點的連通有向圖。如果D中包含有向的Euler環(huán)游〔即是

通過D中每條有向邊恰好一次的閉跡〕，那么D中每一頂點的出度和入度相等。

反之，如果D中每一頂點的出度與入度都相等，那么D一定包含有向的Euler

環(huán)游。這兩個結(jié)論是正確的嗎？請說明理由。如果G是至少有三個頂點的無向圖，

那么G包含Euler環(huán)游的條件是什么？

證明：1〕假設(shè)圖D中包含有向Euler環(huán)游，下證明每個頂點的入度和出度相等。

如果該有向圖含有Euler環(huán)游，那么該環(huán)游必經(jīng)過每個頂點至少一次，每

經(jīng)過一次，必為“進〃一次接著“出〃一次，從而入度等于出度。從而，對于任

意頂點，不管該環(huán)游經(jīng)過該頂點多少次，必有入度等于出度。

2〕假設(shè)圖D中每個頂點的入度和出度相等，那么該圖D包含Euler環(huán)游。證

明如下。

對頂點個數(shù)進展歸納

當(dāng)頂點數(shù)N(D)1=2時,因為每個點的入度和出度相等，易得構(gòu)成有向Euler

環(huán)游。

假設(shè)頂點數(shù)|v(D)|=k時結(jié)論成立，那么

當(dāng)頂點數(shù)|v(D)|=k+1時，任取丫￡丫(口).設(shè)5=｛以v為終點的邊｝,K=｛以

v為始點的邊｝,因為v的入度和出度相等，故S和K中邊數(shù)相等。記6=口-丫.對

G做如下操作：

任取S和K中各一條邊勺、%,設(shè)在D中勺=叩，e2=vv2,那么對G和S

做如下操作G=G+V,V2)S=S-｛g｝,重復(fù)此步驟直到S為空。這個過程最終

得到的G有k個頂點，且每個頂點的度與在G中完全一樣。由歸納假設(shè)，G中存

在有向Euler環(huán)游，設(shè)為C。在G中從任一點出發(fā)沿C的對應(yīng)邊前行，每當(dāng)遇到

上述添加邊vlv2時，都用對應(yīng)的兩條邊el,e2代替，這樣可以獲得有向Euler

環(huán)游。

3〕G是至少有三個頂點的無向圖，那么G包含Euler環(huán)游等價于G中無奇度

頂點。〔即任意頂點的度為偶數(shù)〕。

3.設(shè)G是具有n個頂點和m條邊的無向圖,如果G是連通的，而且滿足m=n-l,

證明G是樹。

證明：思路一：

只需證明G中無圈。

假設(shè)G中有圈，那么刪去圈上任一條邊G仍連通。而每個連通圖邊數(shù)e>=n(頂點數(shù))-1,

但刪去一條邊后G中只有n-2條邊，此時不連通，從而矛盾，故G中無圈，所以G為樹。

思路二：

當(dāng)“=2時，m=2—1=1,兩個頂點一條邊且連通無環(huán)路，顯然是樹。

設(shè)當(dāng)〃=后一1伏6",左22)時，命題成立，那么

當(dāng)“=女時，因為G連通且無環(huán)路，所以至少存在一個頂點匕，他的度數(shù)為1,設(shè)

該頂點所關(guān)聯(lián)的邊為，=(匕,匕).那么去掉頂點匕和“，便得到了一個有k-1個

頂點的連通無向無環(huán)路的子圖G',且G'的邊數(shù)機=1,頂點數(shù)〃=〃-1。由

于m二nT,所以加==(〃-1)-1=〃-1,由歸納假設(shè)知，G是樹。

由于G相當(dāng)于在G'中為V2添加了一個子節(jié)點，所以G也是樹。

由〔1〕，〔2〕原命題得證。

4.假設(shè)用一個〃x〃的數(shù)組來描述一個有向圖的〃X”鄰接矩陣,完成下面

工作：

1〕編寫一個函數(shù)以確定頂點的出度，函數(shù)的復(fù)雜性應(yīng)為。(〃)；：

2〕編寫一個函數(shù)以確定圖中邊的數(shù)目，函數(shù)的復(fù)雜性應(yīng)為。(〃2)；

3〕編寫一個函數(shù)刪除邊(i"),并確定代碼的復(fù)雜性。

解答：〔1〕鄰接矩陣表示為%X,,待確定的頂點為第m個頂點小

intCountVout(int*a,intn,intm){

intout=0；

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

if(a[m-l][i]==l)out++；

returnout；

)

〔2〕確定圖中邊的數(shù)目的函數(shù)如下：

intEdgeNumber(int*a,intn){

intnum=0；

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

for(intj=0；j<n；j++)

if(a[i][j]==l)num++；

returnnum；

}

〔3〕刪除邊〔i,j〕的函數(shù)如下:

voiddeleteEdge(int*a,inti,intj){

if(a[i-l]Lj-l]==O)return；

=0；

return；

代碼的時間復(fù)雜性為?(1)

5.實現(xiàn)圖的D-搜索算法，要求用SPARKS語言寫出算法的偽代碼，或者用一種

計算機高級語言寫出程序。

解:D搜索算法的根本思想是，用棧代替BFS中的隊列，先將起始頂點存入棧中，搜索時,

取出棧頂?shù)脑?，遍歷搜索其相鄰接點，假設(shè)其鄰接點還未搜索，那么存入棧中并標(biāo)記,

遍歷所有鄰接點后，取出此時棧頂?shù)脑剞D(zhuǎn)入下一輪遍歷搜索，直至棧變?yōu)榭諚！?/p>

ProcDBFS(v)〃從頂點v開場，數(shù)組visited標(biāo)示頂點被訪問的順序；

PushS(v,S)；//首先訪問V,將S初始化為只含有一個元素v的棧

count：=count+1；visited[v]：=count；

WhileS非空do

u：=PullHead(S)；count：=count+l；visited[w]：=count；區(qū)另U隊站;三進七

此先進后出

for鄰接于u的所有頂點wdo

ifs[w]=0then

PushS(w,S)；//將w存入棧S

s[w]：=1；

end{if}

end(for}

end{while)

end{DBFS}

注：PushS(w,S)將w存入棧S；PullHead(S)為取出棧最上面的元素，并從棧中刪除

ProcDBFT(G,m)為不連通分支數(shù)

count：=0；計數(shù)器，標(biāo)示已經(jīng)被訪問的頂點個數(shù)

foritondo

s[i]：=0；//數(shù)組s用來標(biāo)示各頂點是否曾被搜索，是那么標(biāo)記為1,否那么標(biāo)記為

0；

end{for)

foritomdo〃遍歷不連通分支的情況

ifs[i]=0then

DBFS(i)；

end{if}

end{for}

end{DBET)

6.下面的無向圖以鄰接鏈表存儲，而且在關(guān)于每個頂點的鏈表中與該頂點

相鄰的頂點是按照字母順序排列的。試以此圖為例描述講義中算法DFNL的執(zhí)行

過程。

鄰接鏈表

A->B->E|0

B->A->C|0

C->B->D->E|0

D->C|0

E->A->C->F->G|0

F->E->G|0

G->E->F|0

解：初始化數(shù)組DFN：=0,num=l;

A為樹的根節(jié)點,對A計算DFNL(A,null),

DFN(A):=num=l；L(A):=num=l；num：=l+l=20

從鄰接鏈表查到A的鄰接點B,

因為DFN(B)=0,對B計算DFNL(B,A)

DFN(B):=num=2；L(B):=num=2；num:=2+1=3。

查鄰接鏈表得到B的鄰接點A,因為DFN(A)=1M,但A=A,即是B的父節(jié)點，無操作。

接著查找鄰接鏈表得到B的鄰接點C,

因為DFN(0=0,對C計算DFNL(C,B)

DFN(C):=num=3；L(C):=num=3；num：=3+1=4。

查找C的鄰接點B,因為DFN(B)=1M,但8=13,即是C的父節(jié)點，無操作。

接著查找鄰接鏈表得到C的鄰接點D,

因為DFN(D)=0,對D計算DFNL(D,C),

DFN(D):=num=4；L(D):=num=4；num：=4+1=5。

查找得D鄰接點C,而DFN(C)=3力0,但C=C,為D的父節(jié)點，L(D)保持不變。

D的鄰接鏈表完畢，DFNL(D,C)的計算完畢。

返回到D的父節(jié)點C,查找鄰接鏈表得到C的鄰接點E,

因為DFN(E)=0,對E計算DFNL(E,C),

DFN(E):=num=5；L(E):=num=5；num：5+1=6；

查找得E鄰接點A,因DFN(A)=1片0,又A聲C,變換L(E)=min(L(E),DFN(A))=1。

查找得E鄰接點C,因DFN(C)=3￥0,但C=C,無操作。

查找得E鄰接點F,因DFN(F)=0,

對F計算DFNL(F,E),

DFN(F):=num=6；L(F):=num=6；num：=6+1=7；

查找得F鄰接點E,因DFN(E)=540,但￡=￡,無操作。

查找得F鄰接點G,因DFN(G)=0,

對G計算DFNL(G.F),

DFN(G):=num=7；L(G):=num=7；num=7+l=8;

查找G鄰接點E,因DFN(E)=5R0,又E-F,L(G)=min(L(G),DFN(E))=5

查找得G鄰接點F,因DFN(F)=6中0,但F=F,無操作。

G的鄰接鏈表完畢，DFNL(G,F)的計算完畢。

L(F):=min(L(F),L(G))=min(6,5)=5

F的鄰接鏈表完畢,DFNL(F,E)的計算完畢。

L(E)：=min(L(E),L(F))=min(l,5)=1

E鄰接鏈表完畢，DENL(E,C)計算完畢。

L(C)：=min(L(C),L(E))=min(3,1)=1

C的鄰接鏈表完畢，DFNL(C,B)計算完畢。

L(B)：=min(L(B),L(C))=min(2,1)=1

查找B的鄰接鏈表完畢，DFNL(B,A)計算完畢。

L(A)：=min(L(A),L(B))=1

查找得A的鄰接點E,因DFN(E)=0,又E于null,那么L(A)=min(L(A),DFN(E))=l

查找A的鄰接鏈表完畢，DFNL(A,nul1)計算完畢。

最終結(jié)果為：深索數(shù)DFN,與最低深索數(shù)L如下

DFN(A)=1,DFN(B)=2,DFN(C)=3,DFN(D)=4,DFN(E)=5,DFN(F)=6,DFN(G)=7

L(A)=1；L(B)=1；L(C)=1；L(D)=4；L(E)=1；L(F)=5；L(G)=5.

序-M-DFNL棧頂一棧底2-連通割

點點

1A1(1,0,0,0,0,0,0)(A,B)

2B2(1,2,0,0,0,0,0)(B,C),(A,B)

3C3(1,2,3,0,0,0,0)(C,D),(B,C),(A,B)

4D4(1,2,3,4,0,0,0)(B,C),(A,B){(C,D)}；c

5E5(1,1,1,4,1,0,0)(E,F),(E,A),(B,C),(A,B)

6F6(1,1,1,4,1,6,0)(F,G),

(E,F),(E,A),(B,C),(A,B)

7G7(1,1,1,4,1,5,5)(E,A),(B,C),(A.B){(G,E),(F,G),E

(E,F)}

8(1,1,1,4,1,5,5){(E,A),(B,C),(A,B)}

附課本講義程序2-3-1對圖2-3-5的執(zhí)行過程

開場DFNL(A,*)

DFN(A)：=1；L(A)：=1；num：=2；

DFN(B)=0,.-.DFNL(B,A)

DFN(B)：=2；L(B)：=2；num：=3；

??,DFN(A)=l*0,但人=人，不做任何事情

DFN(C)=0,.-.DFNL(C,B)

DFN(C)：=3；L(C)：=3；num：=4；

??1DFN(B)=2M,但8=8,，不做任何事情

???DFN(D)=0,.-.DFNL(D,C)

DFN(D)：=4；L(D)：=4>DFN(C)；num：=5；

DFN(C)=3M,但C=C,...不做任何事情

DFN(E)=O,.?.DFNL(E.C)

DFN(E)：=5；L(E)：=5>DFN(C)；num：=6；

DFN(C)=3^0,但C=C,

???DFN(F)=0,.,.DFNL(F,C)

DFN(F)：=6；L(F)：=6；num：=7；

DFN(A)=1M,AM,L(F)：=min{6,1}=1；

???DFN(C)=3M,但C=C,

DFN(G)=O,.,.DFNL(G,F)

DFN(G)：=7；L(G)：=7；num：=8；

DFN(F)=6wO,但尸=尸，

?/DFN(H)=O,.,.DFNL(H,G)

DFN(H)：=8；L(H)：=8>DFN(G)；num：=9；彈出〔G,H〕邊

DFN(G)=7M,但6=6,

DFN(I)=O,.-.DFNLd.G)

DFN(I)：=9；L(I)：=9；num：=10；

DFN(F)=6卻,FHG,L(I)：=min{9,6}=6；

DFN(G)=7wO,但16,

DFN(J)=O,.-.DFNLU,I)

DFN(J)：=10；L(J)：=10；num：=ll；

DFN(F)=6M,FHI,L(J)：=min{10,6}=6；

???DFN(G)=7M,GwI,/.L(J)：=min{6,7}=6；

DFN⑴=9*0,但1=1,

L(I)：=min{6,6}=6；

L(G)：=min{7,6}=6>DFN(F)彈出(J,G),(J,F),(I,J),(I,F),

(G.I),(F,G)邊

L(F)：=min{l,6}=1；

L(C)：=min{3,1}=1；

L(B)：=min{2,1}=1>DFN(A)彈出(F,A),(C,F),

(B,C),(A,B)邊

7對圖的另一種檢索方法是D-Search。該方法與BFS的不同之處在于將隊列換成棧，即下

一個要檢測的結(jié)點是最新加到未檢測結(jié)點表的那個結(jié)點。

1］寫一個D-Search算法;

2］證明由結(jié)點v開場的D-Search能夠訪問v可到達的所有結(jié)點；

3］你的算法的時、空復(fù)雜度是什么？

解：1］同第5題，

procDBFS(v)〃寬度優(yōu)先搜索G,從頂點v開場執(zhí)行，數(shù)組visited標(biāo)示各

〃頂點被訪問的序數(shù)；數(shù)組s將用來標(biāo)示各頂點是否曾被放進待檢查隊

〃列，是那么過標(biāo)記為1,否那么標(biāo)記為0；計數(shù)器count計數(shù)到目前為止已

〃經(jīng)被訪問的頂點個數(shù)，其初始化為在V之前已經(jīng)被訪問的頂點個數(shù)

PushS(v,S)；//將S初始化為只含有一個元素v的棧

whileS非空do

u：=PullHead(S)；count*=count+l；visited[u]*=count；

for鄰接于u的所有頂點wdo

ifs[w]=0then

PushS(w,S)；〃將w壓入棧中

s[w]：=1；

end{if}

end{for)

end(while)

end{DBFS}

圖的D-搜索算法偽代碼：

procDBFT(G,v)//countys同DBFS中的說明，branch是統(tǒng)計圖G的連通分支數(shù)

count:=0；branch*=0；

foritondo

s[i]：=0；〃將所有的頂點標(biāo)記為未被訪問

end{for)

foritovdo

ifs[i]=0then

DBFS(i)；branch=branch+l；

end{if)

end{for)

end{DBFT)

2]證明：除結(jié)點v外，只有當(dāng)結(jié)點w滿足s[w]=0時才被壓人棧中，因此每個結(jié)點至多有一

次被壓人棧中，搜索不會出現(xiàn)重疊和死循環(huán)現(xiàn)象，對于每一個V可到達的節(jié)點，要么直接被

訪問，要么被壓入棧中，只有棧內(nèi)節(jié)點全部彈出被訪問后，搜索才會完畢，所以由結(jié)點V

開場的D-Search能夠訪問v可到達的所有結(jié)點。

3〕：除結(jié)點v外，只有當(dāng)結(jié)點w滿足s[w]=0時才被壓入棧中，因此每個結(jié)點至多有一次被

壓人棧中。需要的?？臻g至多是；visited數(shù)組變量所需要的空間為v;其余變量所

用的空間為0(1),所以S(T,￡)=@(V)°

如果使用鄰接鏈表，for循環(huán)要做d(u)次，而while循環(huán)需要做v次，又visited、s和

count的賦值都需要T次操作，因而t(v,E)=&(v+￡)0

如果采用鄰接矩陣，那么while循環(huán)總共需要做/次操作，visited、s和count的賦值都

需要v次操作，因而t(v,￡)=@(小)。

8.考慮下面這棵假想的對策樹：

解：

1)使用最大最小方法(2-4-2)式獲取各結(jié)點的值

Smax

min

max

min

0Smax

2]

2)弈者A為獲勝應(yīng)該什么棋著?

第三章分治算法習(xí)題

1、編寫程序?qū)崿F(xiàn)歸并算法和快速排序算法

參見后附程序

2、用長為100、200、300、400、500、600、700、800、900、1000的10個數(shù)組的排列來統(tǒng)

計這兩種算法的時間復(fù)雜性。

有些同學(xué)用的微秒us

用s可能需要把上面的長度改為10000,……，100000,都可以

大局部的結(jié)果是快速排序算法要比歸并算法快一些。

3、討論歸并排序算法的空間復(fù)雜性。

解析：歸并排序由分解與合并兩局部組成，如果用5(n)表示歸并排序所用的空間。

那么由

MergeSort(low,mid)〃將第一子數(shù)組排序S(〃/2)

MergeSort(mid+1,high)〃將第二子數(shù)組排序S(n/2)

Merge(low,mid,high)//歸并兩個已經(jīng)排序的子數(shù)組O(〃)a2”

那么

遞歸推導(dǎo)得

又由存儲數(shù)組長度為〃，那么有S(?)>O(n)

因此，空間復(fù)雜度為0(〃)。

4、說明算法PartSelect的時間復(fù)雜性為0(”)

證明：提示：假定數(shù)組中的元素各不一樣，且第一次劃分時劃分元素u是第i小元素的概率

為1/〃。因為Partition中的case語句所要求的時間都是。(“)，所以，存在常數(shù)c,使得

算法PartSelect的平均時間復(fù)雜度《(〃)可以表示為

令R(〃)=max(C*(n)),JfeC>R⑴,試證明R(n)<4cn。

證明：令C：(〃)表示n個元素的數(shù)組A中尋找第k小元素的平均時間復(fù)雜度，因

Partition(0,n-1)的時間復(fù)雜度是0(“)，故存在常數(shù)c,使得算法PartSelect的平均時間

復(fù)雜度C(〃)可以表示為0(〃)W+LZ(n_0+0(/-1))

〃\<i<kk<i<n

令R(〃)=max(C：(〃)),且不妨設(shè)等式在k=kn時成立，那么??(")滿足

k

以下用第二數(shù)學(xué)歸納法證明R(〃)<4cn0取C之R⑴，

當(dāng)九=1時，取c>C/4,那么7?(1)<4c

當(dāng)〃=2時，7?(2)<2c+-/?(l)<2c+-4c=4c成立。

22

對于一般的n,設(shè)對所有小于n的自然數(shù)R(〃)44c〃成立，那么

得證。

證明：〔1〕當(dāng)，=7時，假設(shè)數(shù)組A中元素互不一樣。由于每個具有7個元素的數(shù)組的中間

值u是該數(shù)組中的第4小元素，因此數(shù)組中至少有4個元素不大于u,個中間值中

至少有「］〃/7」/2］個不大于這些中間值的中間值丫。因此，在數(shù)組A中至少有

個元素不大于V。換句話說，A中至多有

512

個元素大于V。同理，至多有一〃+一個元素小于V。這樣，以v為劃分元素，產(chǎn)生的新數(shù)

77

51251211

組至多有一〃+一個元素。當(dāng)〃224時，一〃+一<—nQ

777714

另一方面，在整個執(zhí)行過程中，遞歸調(diào)用Select函數(shù)一次，涉及規(guī)模為力/7,而下一次循

環(huán)Loop涉及的數(shù)組規(guī)模為U”。程序中其他執(zhí)行步的時間復(fù)雜度至多是n的倍數(shù)C77,用

14

T(n)表示算法在數(shù)組長度為n的時間復(fù)雜度，那么當(dāng)〃224時，有遞歸關(guān)系

用數(shù)學(xué)歸納法可以證明，T(H)<14CHO所以時間復(fù)雜度是0(〃)。

225

⑵當(dāng)r=3時，使用上述方法進展分析，可知在進展劃分后數(shù)組A中有至多*〃+*<士〃

336

個元素。而遞歸關(guān)系為T(n)KTd〃)+T(3〃)+c〃。假設(shè)通過歸納法證明出有

36

的形式，用數(shù)學(xué)歸納法可以證明，T(n)<28CHO所以時間復(fù)雜度是0(〃)。

歸并排序的C++語言描述

#include<iostream.h>

template<classT>voidMergeSort(Ta[],intleft,intright)；

template<classT>voidMerge(Tc[],Td[],int1,intm,intr)；

template<classT>voidCopy(Ta[],Tb[],int1,intr)；

voidmain()

(

intconstn(5)；

inta[n]；

cout<<z，lnput，，<<n<<，，numbersplease："；

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

cin?a[i]；

//for(intj=0；j<n；j++)

//b[j]=a[j]；

MergeSort(a,0,n-1)；

cout<<zzThesortedarrayis，z<<endl；

for(i=0；i<n；i++)

cout<<a[i]；

cout<<endl；

)

template<classT>

voidMergeSort(Ta[],intleft,intright)//

(

if(left<right)

{

inti=(left+right)/2；

T*b=newT[]；

MergeSort(a,left,i)；

MergeSort(a,i+1,right)；

Merge(a,b,left,i,right)；

Copy(a,b,left,right)；

)

template<classT>

voidMerge(Tc[],Td[],int1,intm,intr)

inti=l；

intj=m+l；

intk=l；

while((i<=m)&&(j<=r))

(

if(c[i]<=c[j])d[k++]=c[i++]；

elsed[k++]=c[j++]；

)

if(i>m)

(

for(intq=j；q<=r；q++)

d[k++]=c[q]；

)

else

for(intq=i；q<=m；q++)

d[k++]=c[q]；

)

template<classT>

voidCopy(Ta[],Tb口，int1,intr)

(

for(inti=l；i<=r；i++)

a[i]=b[i]；

)

快速排序的C++語言描述

#include<iostream.h>

template<classT>voidQuicksort(Ta[],intp,intr)；

template<classT>intPartition(Ta[],intp,intr)；

voidmain()

(

intconstn(5)；

inta[n]；

cout?/zInputz，?n?，，numbersplease："；

for(inti=0；i〈n；i++)

cin?a[i]；

Quicksort(a,0,n-l)；

cout?，，Thesortedarrayis〃<Xendl；

for(i=0；i<n；i++)

cout?a[i]?，z，z；

cout<<endl；

)

template<classT>

voidQuicksort(Ta[],intp,intr)

(

if(p<r)

{

intq=Partition(a,p,r)；

Quicksort(a,p,q-1)；

Quicksort(a,q+1,r)；

)

)

template<classT>

intPartition(Ta[],intp,intr)

(

inti=p,j=r+l；

Tx=a[p]；

while(true)

(

while(a[++i]<x)；

while(a[-j]>x)；

if(i>=j)break；

Swap(a[i],a[jl)；

)

a[p]=a[j]；

a[j]=x；

returnj；

)

template<classT>

inlinevoidSwap(T&s,T&t)

(

Ttempos；

s~t；

t=temp；

)

第四章作業(yè)局部參考答案

i.設(shè)有幾個顧客同時等待一項效勞。顧客i需要的效勞時間為qv〃。

應(yīng)該如何安排〃個顧客的效勞次序才能使總的等待時間到達最??？總的等待時

間是各顧客等待效勞的時間的總和。試給出你的做法的理由〔證明〕。

策略：

對4.1Ki。進展排序，t.4%<…斗”，然后按照遞增順序依次效勞強，…，

即可。

解析：設(shè)得到效勞的顧客的順序為，，/2,，那么總等待時間為

T=(〃-l)r+(n-2)r,+…+21+%,那么在總等待時間T中加的權(quán)重最大，

J\J2Jn-2Jn-iJ,

tjn的權(quán)重最小。故讓所需時間少的顧客先得到效勞可以減少總等待時間。

證明：設(shè)下證明當(dāng)按照不減順序依次效勞時，為最優(yōu)策略。

記按照i也…次序效勞時，等待時間為7,下證明任意互換兩者的次序，T

都不減。即假設(shè)互換V（i</）兩位顧客的次序，互換后等待總時間為了，那么

有亍NT.

由于

那么有

同理可證其它次序，都可以由，&???，；經(jīng)過有限次兩兩調(diào)換順序后得到，而

每次交換，總時間不減，從而i也…。為最優(yōu)策略。

2.字符。~〃出現(xiàn)的頻率分布恰好是前8個Fibonacci數(shù)，它們的Huffman

編碼是什么？將結(jié)果推廣到n個字符的頻率分布恰好是前〃個Fibonacci數(shù)的情

形。Fibonacci數(shù)的定義為：/=】，片=］，工="-2+Ei礦〃>1

解：前8個數(shù)為a,b,c,d,e,f,g,h

1,1,2,3,5,8,13,21

Huffman哈夫曼編碼樹為：

所以a的編碼為：1111111

b的編碼為：1111110

C的編碼為:111110

d的編碼為:11110

e的編碼為：1110

f的編碼為：110

g的編碼為：10

h的編碼為：0

推廣到n個字符：

第1個字符:n-l個1,11--1

n-l

第2個字符:n-2個1,1個0,11---10

n-2

第3個字符:n-3個1,1個0,11---10

v~V~'

n-3

第n-1個字符：1個1,1個0,10

第n個字符：1個0,0

3.設(shè)p”P2,…,p”是準(zhǔn)備存放到長為L的磁帶上的n個程序，程序p,需要的

帶長為《。設(shè)之…,要求選取一個能放在帶上的程序的最大子集合〔即其中

含有最多個數(shù)的程序〕Q。構(gòu)造。的一種貪心策略是按《的非降次序?qū)⒊绦蛴嬋?/p>

集合。

I）證明這一策略總能找到最大子集。，使得

PfQ

2）設(shè)。是使用上述貪心算法得到的子集合，磁帶的利用率可以小到何種程度？

3）試說明1）中提到的設(shè)計謀略不一定得到使取最大值的子集合。

p?Q

1）證明：不妨設(shè)44a2?…，假設(shè)該貪心策略構(gòu)造的子集合。為

[ax,a2,---,as},那么s滿足ZqWL、>4+〈十〉L。

（=1（=1

要證明能找到最大子集，只需說明s為可包含的最多程序段數(shù)即可。

即證不存在多于S個的程序集合0={%,令…僅>s）,使得

Pi^Q

k

反證法，假設(shè)存在多于S個的程序集Q="，4,…,%},（左>$）,滿足

*>1

因為4<4<…-an非降序排列，那么。]+。2+…4T----卜4-%+%T----,氣WLo

因為k>s且為整數(shù)，那么其前s+1項滿足q+生+…4+4+]<LQ

這與貪心策略構(gòu)造的子集和Q中S滿足的+as+i>L矛盾。故假設(shè)不成立，得證。

/=1

2〕磁帶的利用率為faJL；〔甚至最小可為0,此時任意《>L或者￡〕

PgQ0G。

3)按照1〕的策略可以使磁帶上的程序數(shù)量最多，但程序的總長度不一定是最大

的，假設(shè){q,的，…，。,}為Q的最大子集，但是假設(shè)用6%代替小，仍滿足

^ak+aM<L,那么{卬,。2,…,?！?嗎+1}為總長度更優(yōu)子集。

A=1

4.同學(xué)們的幾種不同答案

構(gòu)造哈夫曼樹思想，將所有的節(jié)點放到一個隊列中，用一個節(jié)點替換兩個頻率最低的節(jié)

點，新節(jié)點的頻率就是這兩個節(jié)點的頻率之和。這樣，新節(jié)點就是兩個被替換節(jié)點的父

節(jié)點了。如此循環(huán)，直到隊列中只剩一個節(jié)點〔樹根〕。

答案1〕

偽代碼：

typedefstruct

(

unsignedintweight；

unsignedintparent,Ichild,rchild；

(HTNode,*HuffmanTree；

typedefchar**HuffmanCode；

procHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)

ifn<=lthenreturn

HuffmanTreep；

integersi,s2,i,m,start,c,f；

char*cd；

m：=2*n-1；

HT[0].weight：=1000000；

p：=HT+1；

foritondo

(*p).weight：=*w；

(*p).parent：=(*p).IchiId：=(*p).rchild：=0；

++p；++w；

end{for}

foritomdo

(*p).weight=(*p).parent=(*p).IchiId=(*p).rchild=

0；

++p；

end{for}

forifromn+1tomdo

Select(HT,i-1,si,s2)；

HT[sl].parent：=i；

HT[s2].parent：=i；

HT[i].Ichild:二si；

HT[i].rchild：=s2；

HT[i].weight：=weight+HT[s2].weight；

end{for}

cd[n-l]='￥0'；〃編碼完畢符

foritondo