中科院計算機算法分析與設(shè)計習題答案課件

第一章復雜性分析初步習題

語句s/e頻率總步數(shù)template<classT>voidMult(T**a,T**b,intm,intn,intp)000{for(inti=0;i<m;i++)1m+1m+1for(intj=0;j<p;j++){1m*(p+1)m*p+mTsum=0;1m*pm*pfor(intk=0;k<n;k++)1m*p*(n+1)m*p*n+m*p

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

1m*pm*p}}

總計2*m*p*n+4*m*p+2*m+11.試確定下述程序的執(zhí)行步數(shù)，該函數(shù)實現(xiàn)一個m×n矩陣與一個n×p矩陣之間的乘法:s/e表示每次執(zhí)行該語句所要執(zhí)行的程序步數(shù),頻率是指該語句總的執(zhí)行次數(shù)。12．函數(shù)MinMax用來查找數(shù)組a[0:n-1]中的最大元素和最小元素，以下給出兩個程序。令n為實例特征。試問：在各個程序中，a中元素之間的比較次數(shù)在最壞情況下各是多少？

6.按照漸進階從低到高的順序排列以下表達式:template<classT>boolMinMax(Ta[],intn,int&Min,int&Max){if(n<1)returnfalse;Min=Max=0;//初始化

for(inti=1;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){if(n<1)returnfalse;Min=Max=0;//初始化

for(inti=1;i<n;i++){if(a[Min]>a[i])Min=i;elseif(a[Max]<a[i])Max=i;}returntrue;}最壞2*（n-1）最好n-1,平均27.1）假設(shè)某算法在輸入規(guī)模是時為.在某臺計算機上實現(xiàn)并完成該算法的時間是秒.現(xiàn)有另一臺計算機,其運行速度為第一臺的64倍,那么,在這臺計算機上用同一算法在秒內(nèi)能解決規(guī)模為多大的問題?規(guī)模時間復雜度（步數(shù)）原運行速度（時間/每步）總時間關(guān)系式:時間復雜度（計算步數(shù)）*運行速度(時間/每步)=運行所需時間解:設(shè)在新機器上秒內(nèi)能解決規(guī)模為的問題，時間復雜度為由于新機器運行速度提高64倍，則運行速度變?yōu)橛申P(guān)系式，得解，得3由于新復雜度，新機器的運行速度為2)若上述算法改進后，新算法的計算復雜度為,則在新機器上用秒時間能解決輸入規(guī)模為多大的問題？代入關(guān)系式，得設(shè)在新機器上用秒時間能解決輸入規(guī)模為的問題，則解，得43）若進一步改進算法，最新的算法的時間復雜度為，其余條件不變，在新機器上運行，在秒內(nèi)能夠解決輸入規(guī)模為多大的問題？設(shè)可解決的最大時間復雜度為，則可解決的最大時間復雜度為，（n為原始的輸入規(guī)模）。所以任意規(guī)模的問題都可在t秒內(nèi)解決。因為，且為常數(shù)不隨輸入規(guī)模n變化，58.Fibonacci數(shù)有遞推關(guān)系：試求出的表達式。6的出度連接點，使得第二章圖與遍歷算法習題1.證明下列結(jié)論:1）在一個無向圖中，如果每個頂點的度大于等于2，則該圖一定含有圈；2）在一個有向圖D中，如果每個頂點的出度都大于等于1，則該圖一定含有一個有向圈。1）證明:設(shè)無向圖最長的無重復頂點的跡因為每個頂點的度大于等于2，故存在與相異的點與相鄰。若則得到比更長的跡，與P的取法矛盾。因此，,

故是閉跡。因無重復頂點，故存在圈2）證明:同（1），設(shè)有向圖最長的無重復頂點的有向跡因為每個頂點出度大于等于1，故存在為成為一條有向邊，若則得到比更長的有向跡，與P最長矛盾。，從而該圖一定含有有向圈。因此必有(若頂點重復已含有圈)782.設(shè)D是至少有三個頂點的連通有向圖。如果D中包含有向的Euler環(huán)游（即是通過D中每條有向邊恰好一次的閉跡），則D中每一頂點的出度和入度相等。反之，如果D中每一頂點的出度與入度都相等，則D一定包含有向的Euler環(huán)游。這兩個結(jié)論是正確的嗎？請說明理由。如果G是至少有三個頂點的無向圖，則G包含Euler環(huán)游的條件是什么？3．設(shè)G是具有n個頂點和m條邊的無向圖，如果G是連通的，而且滿足m=n-1,證明G是樹。4．假設(shè)用一個n×n的數(shù)組來描述一個有向圖的n×n鄰接矩陣，完成下面工作：1）編寫一個函數(shù)以確定頂點的出度，函數(shù)的復雜性應(yīng)為；2）編寫一個函數(shù)以確定圖中邊的數(shù)目，函數(shù)的復雜性應(yīng)為；3）編寫一個函數(shù)刪除邊（i，j），并確定代碼的復雜性。5.實現(xiàn)圖的D-搜索算法。要求用ALGEN語言寫出算法的偽代碼，或者用一種計算機高級語言寫出程序。96.下面的無向圖以鄰接鏈表存儲，而且在關(guān)于每個頂點的鏈表中與該頂點相鄰的頂點是按照字母順序排列的。試以此圖為例描述講義中算法DFNL的執(zhí)行過程。一個無向圖GABEDGCF11234756111554鄰接鏈表A->B->E|0B->A->C|0C->B->D->E|0D->C|0E->A->C->F->G|0F->E->G|0G->E->F|010ABEDGCF11234756111554A->B->E|0B->A->C|0C->B->D->E|0D->C|0E->A->C->F->G|0F->E->G|0G->E->F|0初始化DFN:=0，num:=1；DFNL(A,null)，

DFN(A):=num=1;L(A):=num=1;num+:=2?！逥FN(B)=0,∴DFNL(B,A)

DFN(B):=num=2,L(B):=num=2,num+:=3;DFN(A)=1

0,A=A,無操作。

∵DFN(C)=0∴DFNL(C,B)

DFN(C):=num=3,L(C):=num=3,num+:=4;DFN(B)=10,B=B,無操作.

∵DFN(D)=0,∴DFNL(D,C)，

DFN(D):=num=4;L(D):=num=4;num+:=5;DFN(C)=3≠0,C=C，無操作.

DFNL(D,C)結(jié)束。

∵DFN(E)=0,

DFNL(E,C),

DFN(E):=5;L(E):=5;num+:=6;

DFN(A)=1≠0,A≠C,L(E)=min(L(E),DFN(A))=1。DFN(C)=3≠0，C=C，無操作。

∵

DFN(F)=0，DFNL(F,E)，

DFN(F):=num=6;L(F):=num=6;num+:=7;

DFN(E)=5≠0，E=E，無操作。

∵

DFN(G)=0，DFNL(G,F)，

DFN(G):=num=7;L(G):=num=7;num+:=8；DFN(E)=5≠0,E≠F，L(G)=min(L(G),DFN(E))=5;

DFN(F)=6≠0,F=F,無操作。DFNL(G,F)結(jié)束L(F):=min(L(F)，L(G))=min(6,5)=5DFNL(F,E)的結(jié)束。

L(E):=min(L(E),L(F))=min(1,5)=1

DFNL(E,C)結(jié)束。L(C):=min(L(C),L(E))=min(3,1)=1

DFNL(C,B)結(jié)束。L(B):=min(L(B),L(C))=min(2,1)=1DFNL(B,A)結(jié)束。L(A):=min(L(A),L(B))=1

因DFN(E)=0，E≠null,則L(A)=min(L(A),DFN(E))=1DFNL(A,null)結(jié)束。11序號頂點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)};C5E5(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,F)}E8(1,1,1,4,1,5,5){(E,A),(B,C),(A,B)}127.對圖的另一種檢索方法是D-Search。該方法與BFS的不同之處在于將隊列換成棧，即下一個要檢測的結(jié)點是最新加到未檢測結(jié)點表的那個結(jié)點。1）寫一個D-Search算法；2）證明由結(jié)點v開始的D-Search能夠訪問v可到達的所有結(jié)點；3）你的算法的時、空復雜度是什么？（類比BFS算法）（類比定理2.2.1證明）13procDBFS(v)//PushS(v,S);//將S初始化為只含有一個元素v的棧whileS非空dou:=PullHead(S);count:=count+1;visited[u]:=count;for鄰接于u的所有頂點wdoifs[w]=0thenPushS(w,S);//將w壓入棧中s[w]:=1;end{if}end{for}end{while}end{DBFS}圖的D—搜索算法偽代碼：procDBFT(G,ν)//count、s同DBFS中的說明，branch是統(tǒng)計圖G的連通分支數(shù)count:=0;branch:=0;foritondos[i]:=0;//將所有的頂點標記為未被訪問end{for}foritoνdoifs[i]=0thenDBFS(i);branch:=branch+1;end{if}end{for}end{DBFT}142）證明：除結(jié)點v外，只有當結(jié)點w滿足s[w]=0時才被壓入棧中，因此每個結(jié)點至多有一次被壓入棧中，搜索不會出現(xiàn)重疊和死循環(huán)現(xiàn)象，對于每一個v可到達的節(jié)點，要么直接被訪問，要么被壓入棧中，只有棧內(nèi)節(jié)點全部彈出被訪問后，搜索才會結(jié)束，所以由結(jié)點v開始的D-Search能夠訪問v可到達的所有結(jié)點。3）除結(jié)點v外，只有當結(jié)點w滿足s[w]=0時才被壓入棧中，因此每個結(jié)點至多有一次被壓入棧中。需要的?？臻g至多是ν-1；visited數(shù)組變量所需要的空間為ν；其余變量所用的空間為O(1)，所以s(ν,ε)=Θ(ν)。如果使用鄰接鏈表，for循環(huán)要做d(u)次，而while循環(huán)需要做ν次，又visited、s和count的賦值都需要ν次操作，因而t(ν,ε)=Θ(ν+ε)。如果采用鄰接矩陣，則while循環(huán)總共需要做ν2次操作，visited、s和count的賦值都需要ν次操作，因而t(ν,ε)=Θ(ν2)。158.考慮下面這棵假想的對策樹：1）使用最大最小方法(2-4-2)式獲取各結(jié)點的值；2）弈者A為獲勝應(yīng)該什么棋著？3）列出算法VEB計算這棵對策樹結(jié)點的值時各結(jié)點被計算的順序4）對樹中每個結(jié)點X，用(2-4-3)式計算V(X)；5）在取X＝根，l=10,LB=-∞,D=∞的情況下，用算法AB計算此樹的根的值期間，這棵樹的那些結(jié)點沒有計算？841551030592050186151052016206420548156203055084152051030592050186151055201）使用最大最小方法(2-4-2)式獲取各結(jié)點的值maxmaxmaxminmin172）弈者A為獲勝應(yīng)該什么棋著？20642054815620305508415205103059205018615105520XX1X2X3X4X1.1X1.2X2.1X2.2X3.1X3.2X4.1X4.2X1.1.1X1.1.2X1.1.3X1.2.1X2.1.1X2.2.1X3.1.1X3.1.2X1.1.1.1X3.1.2.1X3.2.1X3.2.2X3.2.3X4.1.1X4.2.1X4.4.2X4.2.3X4.2.4183）列出算法VEB計算這棵對策樹結(jié)點的值時各結(jié)點被計算的順序46151051-523469-10-1515-665