中科院計算機算法分析與設(shè)計習(xí)題1-2答案.ppt

第一章 復(fù)雜性分析初步 習(xí)題,1. 試確定下述程序的執(zhí)行步數(shù)，該函數(shù)實現(xiàn)一個mn矩陣與一個np矩陣之間的乘法:,s/e 表示每次執(zhí)行該語句所要執(zhí)行的程序步數(shù),頻率是指該語句總的執(zhí)行次數(shù)。,2 函數(shù)MinMax用來查找數(shù)組a0:n-1中的最大元素和最小元素，以下給出兩個程序。令n為實例特征。試問：在各個程序中，a中元素之間的比較次數(shù)在最壞情況下各是多少？,6. 按照漸進階從低到高的順序排列以下表達式:,template bool MinMax(T a, int n, int ,最好，最壞，平均比較次數(shù)都是 2*（n-1）,template bool MinMax(T a, int n, int ,最壞2*（n-1） 最好 n-1, 平均,7. 1）假設(shè)某算法在輸入規(guī)模是 時為 .在某臺計算機上實現(xiàn)并完成該算法的時間是 秒. 現(xiàn)有另一臺計算機,其運行速度為第一臺的64倍, 那么,在這臺計算機上用同一算法在 秒內(nèi)能解決規(guī)模為多大的問題?,關(guān)系式: 時間復(fù)雜度（計算步數(shù)）*運行速度(時間/每步)=運行所需時間,解:設(shè)在新機器上 秒內(nèi)能解決規(guī)模為 的問題，時間復(fù)雜度為,由于新機器運行速度提高64倍，則運行速度變?yōu)?由關(guān)系式,，得,解，得,由于新復(fù)雜度 ，新機器的運行速度為,2) 若上述算法改進后，新算法的計算復(fù)雜度為 , 則在新機器上用,秒時間能解決輸入規(guī)模為多大的問題？,代入關(guān)系式,，得,設(shè)在新機器上用 秒時間能解決輸入規(guī)模為 的問題，則,解，得,3）若進一步改進算法，最新的算法的時間復(fù)雜度為 ，其余條件不變，在新機器上運行，在 秒內(nèi)能夠解決輸入規(guī)模為多大的問題？,設(shè)可解決的最大時間復(fù)雜度為 ，則,可解決的最大時間復(fù)雜度為,，（n為原始的輸入規(guī)模）。,所以任意規(guī)模的問題都可在t秒內(nèi)解決。,因為 ，且為常數(shù)不隨輸入規(guī)模n變化，,8. Fibonacci數(shù)有遞推關(guān)系：,試求出,的表達式。,的出度連接點，使得,第二章 圖與遍歷算法 習(xí)題,1.證明下列結(jié)論: 1）在一個無向圖中，如果每個頂點的度大于等于2，則該圖一定含有圈； 2）在一個有向圖D中，如果每個頂點的出度都大于等于1，則該圖一定含有一個有向圈。,1）證明:設(shè)無向圖最長的無重復(fù)頂點的跡,因為每個頂點的度大于等于2，,故存在與 相異的點 與 相鄰。,若 則得到比 更長的跡，與P的取法矛盾。,因此， , 故 是閉跡。因無重復(fù)頂點，故存在圈,2）證明:同（1），設(shè)有向圖最長的無重復(fù)頂點的有向跡,因為每個頂點出度大于等于1，故存在 為,成為一條有向邊，若,則得到比,更長的有向跡，與P最長矛盾。,，從而該圖一定含有有向圈。,因此必有,(若頂點重復(fù)已含有圈),2.設(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è)用一個nn的數(shù)組來描述一個有向圖的nn鄰接矩陣，完成下面工作： 1）編寫一個函數(shù)以確定頂點的出度，函數(shù)的復(fù)雜性應(yīng)為 ； 2）編寫一個函數(shù)以確定圖中邊的數(shù)目，函數(shù)的復(fù)雜性應(yīng)為 ； 3）編寫一個函數(shù)刪除邊（i，j），并確定代碼的復(fù)雜性。,5.實現(xiàn)圖的D-搜索算法。要求用ALGEN語言寫出算法的偽代碼，或者用一種計算機高級語言寫出程序。,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,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,初始化 DFN:=0，num:=1； DFNL(A,null)， DFN(A):=num=1; L(A):=num=1; num+:=2。 DFN(B)=0, DFNL(B,A) DFN(B):=num= 2, L(B):=num=2, num+:=3; DFN(A)=10, 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)=30,C=C，無操作. DFNL(D,C) 結(jié)束。 DFN(E)=0, DFNL(E,C), DFN(E):=5; L(E):=5; num+:=6; DFN(A)=10,AC, L(E)=min (L(E), DFN(A)=1。 DFN(C)=30，C=C，無操作。 DFN(F)=0，DFNL(F,E)， DFN(F):=num=6; L(F):=num=6; num+:=7; DFN(E)=50，E=E，無操作。 DFN(G)=0，DFNL(G,F)， DFN(G):=num=7; L(G):=num=7; num+:=8； DFN(E)=50,EF，L(G)=min (L(G),DFN(E)=5; DFN(F)=60,F=F,無操作。 DFNL(G,F) 結(jié)束 L(F):=min (L(F)，L(G)=min(6,5)=5 DFNL(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)=1 DFNL(B,A) 結(jié)束。 L(A):=min (L(A),L(B)=1 因DFN(E)=0，E null,則L(A)=min (L(A),DFN(E)=1 DFNL(A,null) 結(jié)束。,7. 對圖的另一種檢索方法是 D-Search。該方法與 BFS 的不同之處在于將隊列換成棧，即下一個要檢測的結(jié)點是最新加到未檢測結(jié)點表的那個結(jié)點。 1）寫一個D-Search算法； 2）證明由結(jié)點v開始的D-Search能夠訪問v可到達的所有結(jié)點； 3）你的算法的時、空復(fù)雜度是什么？,（類比BFS算法）,（類比定理2.2.1證明）,proc DBFS(v) / PushS(v , S);/ 將S初始化為只含有一個元素v的棧 while S非空 do u:= PullHead(S); count:=count+1; visitedu:=count; for 鄰接于u的所有頂點w do if sw=0 then PushS(w , S); /將w壓入棧中 sw:=1; endif endfor endwhile endDBFS 圖的D搜索算法偽代碼： proc DBFT(G, ) /count、s同DBFS中的說明，branch是統(tǒng)計圖G的連通分支數(shù) count:=0; branch:=0; for i to n do si:=0; /將所有的頂點標(biāo)記為未被訪問 endfor for i to do if si=0 then DBFS(i); branch:=branch+1; endif endfor endDBFT,2）證明：除結(jié)點v外，只有當(dāng)結(jié)點w滿足sw=0時才被壓入棧中，因此每個結(jié)點至多有一次被壓入棧中，搜索不會出現(xiàn)重疊和死循環(huán)現(xiàn)象，對于每一個v可到達的節(jié)點，要么直接被訪問，要么被壓入棧中，只有棧內(nèi)節(jié)點全部彈出被訪問后，搜索才會結(jié)束，所以由結(jié)點v開始的D-Search能夠訪問v可到達的所有結(jié)點。 3）除結(jié)點v外，只有當(dāng)結(jié)點w滿足sw=0時才被壓入棧中，因此每個結(jié)點至多有一次被壓入棧中。需要的棧 空間至多是-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)。,8.考慮下面這棵假想的對策樹： 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é)點沒有計算？,1）使用最大最小方法(2-4-2)式獲取各結(jié)點的值,max,max,max,min,min,2）弈者A為獲勝應(yīng)該什么棋著？,20,6,4,20,5,4,8,15,6,20,30,5,50,8,4,15,20,5,10,30,5,9,20,50,18,6,15,10,5,5,20,X,X1,X2,X3,X4,X1.1,X1.2,X2.1,X2.2,X3.1,X3.2,X4.1,X4.2,X1.1.1,X1.1.2,X1.1.3,X1.2.1,X2.1.1,X2.2.1,X3.1.1,X3.1.2,X1.1.1.1,X3.1.2.1,X3.2.1,X3.2.2,X3.2.3,X4.1.1,X4.2.1,X4.4.2,X4.2.3,X4.2.4,3）列出算法VEB計算這棵對策樹結(jié)點的值時各結(jié)點被計算的順序,4,6,15,10,5,1,-5,2,3,4,6,9,-10,-15,15,-6,6,5,7,8,-6,-4,4,10,11,-4,3）列出算法VEB計算這棵對策樹結(jié)點的值時各結(jié)點被計算的順序,4）對樹中每個結(jié)點X，用(2-4-3)式計算V(X)；,5）在取X根，l=10, LB =-, D=的情況下，用算法AB計算此樹的根的值期間，這棵樹的那些結(jié)點沒有計算？,20,-6,-6,-20,-20,6,15,6,20,30,20,-4,-15,-20,-5,-10,-30,-5,-6,-15,-10,-5,5,20,5）在取X根，l=10, LB =-, D=的情況下，用算法AB計算此樹的根