算法設(shè)計(jì)與分析答案參考

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

2、畫出循環(huán)賽日程表。1234567821436587解：（1）至少要進(jìn)行 n 天3412785643218765（2）如右圖：567812346587214378563412876543213、對(duì)于下圖使用Dijkstra算法求由頂點(diǎn)a 到頂點(diǎn) h 的最短路徑。be2g122ad233218cf2h解：用 V1 表示已經(jīng)找到最短路徑的頂點(diǎn)， V2 表示與 V1 中某個(gè)頂點(diǎn)相鄰接且不在 V1 中的頂點(diǎn)； E1 表示加入到最短路徑中的邊， E2 為與 V1 中的頂點(diǎn)相鄰接且距離最短的路徑。步驟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結(jié)果：從 a 到 h 的最短路徑為 abdfe gh ，權(quán)值為 18。求所有頂點(diǎn)對(duì)之間的最短路徑可以使用Dijkstra算法，使其起始節(jié)點(diǎn)從a 循環(huán)到 h，每次求起始節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑，最終可以求得所有頂點(diǎn)對(duì)之間的最短路徑。補(bǔ)充例題：求 A 到各個(gè)頂點(diǎn)的最短路徑：解：4、用動(dòng)態(tài)規(guī)劃策略求解最長(zhǎng)公共子序列問題：（1）給出計(jì)

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

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

6、03765250808555757046652505585807570465570758085655027、對(duì)于下圖，寫出圖著色算法得出一種著色方案的過程。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找到一個(gè)解（ 1， 2， 3， 3）8、有n 個(gè)物品，已知n=7, 利潤(rùn)為P=(10,5,15,7,6,18,3)，重量W=(2,3,5,

7、7,1,4,1)，背包容積M=15, 物品只能選擇全部裝入背包或不裝入背包，設(shè)計(jì)貪心算法，并討論是否可獲最優(yōu)解。解：定義結(jié)構(gòu)體數(shù)組G 將物品編號(hào)、利潤(rùn)、重量作為一個(gè)結(jié)構(gòu)體例如 Gk=1,10,2求最優(yōu)解按利潤(rùn)/ 重量的遞減序有：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