算法設計與分析答案參考

1、1、用 Floyd 算法求下圖每一對頂點之間的最短路徑長度，計算矩陣D0，D1，D2 和 D3，其中 Dk i, j 表示從頂點 i 到頂點 j 的不經過編號大于 k 的頂點的最短路徑長度。解020202072D 0306D 1305D 2305D 330510501050850850在每條邊的矩陣行中依次加入頂點1,2,3，判斷有無最短路徑2、設有 n=2k 個運動員要進行循環(huán)賽， 現設計一個滿足以下要求的比賽日程表：每個選手必須與其他 n-1 名選手比賽各一次；每個選手一天至多只能賽一次；循環(huán)賽要在最短時間內完成。（1）如果 n=2k，循環(huán)賽最少需要進行幾天；（2）當 n=23=8 時，請

2、畫出循環(huán)賽日程表。1234567821436587解：（1）至少要進行 n 天3412785643218765（2）如右圖：567812346587214378563412876543213、對于下圖使用Dijkstra算法求由頂點a 到頂點 h 的最短路徑。be2g122ad233218cf2h解：用 V1 表示已經找到最短路徑的頂點， V2 表示與 V1 中某個頂點相鄰接且不在 V1 中的頂點； E1 表示加入到最短路徑中的邊， E2 為與 V1 中的頂點相鄰接且距離最短的路徑。步驟V 1V2E1E 21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,

3、cfab,bddf5.a,b,c,d,feab,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,hab,bd,de,df,fe,eg,gh結果：從 a 到 h 的最短路徑為 abdfe gh ，權值為 18。求所有頂點對之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點從a 循環(huán)到 h，每次求起始節(jié)點到其他節(jié)點的最短路徑，最終可以求得所有頂點對之間的最短路徑。補充例題：求 A 到各個頂點的最短路徑：解：4、用動態(tài)規(guī)劃策略求解最長公共子序列問題：（1）給出計

4、算最優(yōu)值的遞歸方程。（2）給定兩個序列X=B,C,D,A ，Y=A,B,C,B ，請采用動態(tài)規(guī)劃策略求出其最長公共子序列，要求給出過程。解： (1)ci,j0ci1, j11當i0或j0時當i, j0且xiy i 時max(ci,j1, ci1, j )當i, j0且xiyi 時（ 2）000000111001220012201122最長公共子序列：5、對下圖所示的連通網絡G，用克魯斯卡爾 (Kruskal)算法求 G 的最小生成樹 T, 請寫出在算法執(zhí)行過程中，依次加入T 的邊集 TE 中11822171911693261554617的邊。說明該算法的貪心策略和算法的基本思想，并簡要分析算法

5、的時間復雜度。答：TE=(3,4), (2,3),(1,5),（4,6 ）（ 4,5 ）貪心策略是每次都在連接兩個不同連通分量的邊中選權值最小的邊?；舅枷耄菏紫葘D中所有頂點都放到生成樹中，然后每次都在連接兩個不同連通分量的邊中選權值最小的邊，將其放入生成樹中， 直到生成樹中有n-1條邊。時間復雜度為： O(eloge)6、快速排序算法對下列實例排序，算法執(zhí)行過程中，寫出數組A 第一次被分割的過程。A=(65,70,75,80,85,55,50,2)解：第一個分割元素為65(1)(2)(3)(4) (5) (6) (7)(8)ip6570758085555022865275808555507

6、03765250808555757046652505585807570465570758085655027、對于下圖，寫出圖著色算法得出一種著色方案的過程。2314解： K1X11 , 返回 trueX21, 返回 false; X2X2+1=2,返回 trueX31 , 返回 false; X3X3+1=2,返回 false;X3X3+1=3, 返回 trueX4 1,返回 false;X4 X4+1=2,返回 false;X4X4+1=3,返回 true找到一個解（ 1， 2， 3， 3）8、有n 個物品，已知n=7, 利潤為P=(10,5,15,7,6,18,3)，重量W=(2,3,5,

7、7,1,4,1)，背包容積M=15, 物品只能選擇全部裝入背包或不裝入背包，設計貪心算法，并討論是否可獲最優(yōu)解。解：定義結構體數組G 將物品編號、利潤、重量作為一個結構體例如 Gk=1,10,2求最優(yōu)解按利潤/ 重量的遞減序有：5,6,1,6 、 1,10,2,56,18,4,9/2、3,15,5,3 、7,3,1,3 、 2,5,3,5/3、4,7,7,1算法：procedureKNAPSACK(PWMXn)x 11ax10ajx21x0a2ix 31x 41ax30x 40adx 41ex0x054bx 51ehx 60x 50egcx0x067fQ 1404030503515011519

8、0.625(1,1,1,1,7,0,0)4040305030150115177.540860(1,1,1,1,0, 7 ,0)12c 4040305010170(1,1,1,1,0,0,1)d.4040303530150105167.5(1,1,1,0,1, 3 ,0)604e.40405035301501301751,0)60(1,1,0,1,1,3f.4040503510150130(1,1,0,1,1,0, 4)35170.717g.40405030160(1,1,0,1,0,1,0)h.4040353010150140146.85(1,1,0,0,1,1, 2 )357i. 4030503530150125167.5 (1,0,1,1,1,5,0)6012