[學(xué)習(xí)]算法設(shè)計(jì)與分析-作業(yè)-第3章

1、編程實(shí)現(xiàn)下述4個(gè)算法，并利用給定的數(shù)據(jù)，驗(yàn)證算法正確性,最長(zhǎng)公共子序列最大子段和凸多邊形最優(yōu)三角剖分0-1背包問(wèn)題,最長(zhǎng)公共子序列,利用“附件1.最長(zhǎng)公共子序列輸入數(shù)據(jù)” 中給出的字符串A, B, C, D, 分別找出下列兩兩字符串間的最長(zhǎng)公共子串，并輸出結(jié)果： A-B, C-D, A-D, C-B,最長(zhǎng)公共子序列,字符串A, B, C, D 生成方法：產(chǎn)生由9個(gè)數(shù)字

2、{0,1,2,3,4,5,6,7,8,9}組成的長(zhǎng)度在400-500之間（也可以更長(zhǎng)）的序列A1, C1 產(chǎn)生由9個(gè)符號(hào){),!,@,+,$,%,^,&,*,(}組成的長(zhǎng)度在400-500之間（也可以更長(zhǎng)）的序列B1, D1 +改成: -,=,最長(zhǎng)公共子序列,將由26個(gè)英文字母和符號(hào)“+”組成的字符串a(chǎn)n+algorithm+is+any+welldefined+computational+procedure+that+

3、takes+some+values+as+input+and+produces+some+values+as+output注：在C、D中，An+algorithm… 中的各個(gè)字母和符號(hào)“+”在保持原有前后順序的前提下插入到字符串A1, B1, C1, D1中，得到字符串A, B, C, D,最長(zhǎng)公共子序列,注意： 由26個(gè)英文字母和+組成的字符串中的各個(gè)符號(hào)插入到A1, B1, C1, D1中后，任意2個(gè)符號(hào)間

4、應(yīng)當(dāng)有數(shù)字隔開(kāi)。 例如，1a27n4+498a3l9g76o,不要出現(xiàn)“1an4+498al9g76o”,最大子段和,針對(duì) “附件2.最大子段和輸入數(shù)據(jù)-序列1”、 “附件2.最大子段和輸入數(shù)據(jù)-序列2” 中給出的序列1、序列2, 分別計(jì)算其最大子段和 序列1：長(zhǎng)度在300-400之間，由(-100,100)內(nèi)的數(shù)字組成 序列2：長(zhǎng)度在100-200之間，由(-50,50

5、)內(nèi)的數(shù)字組成,最大子段和,要求： 1. 指出最大子段和在原序列中的位置 2. 給出最大子段和具體值,凸多邊形最優(yōu)三角剖分,利用： 1. “附件3-1.21個(gè)基站凸多邊形數(shù)據(jù)” 2. “附件3-2.29個(gè)基站凸多邊形數(shù)據(jù)” 給出21凸多邊形頂點(diǎn)數(shù)據(jù)、 29凸多邊形頂點(diǎn)數(shù)據(jù)，以頂點(diǎn)間的地理距離作為連接2個(gè)頂點(diǎn)的邊、弦到的權(quán)值，對(duì)這2個(gè)凸多邊形進(jìn)行最優(yōu)三角剖分,凸多邊形最優(yōu)三角剖分,21凸多邊

6、形構(gòu)造方法 根據(jù)xx市TD-LTE網(wǎng)絡(luò)配置數(shù)據(jù)，選取全部基站eNODEB； 以這些基站作為平面點(diǎn)，構(gòu)造平面點(diǎn)集的凸包，得到具有21個(gè)頂點(diǎn)的凸21邊形,凸多邊形最優(yōu)三角剖分,29凸多邊形構(gòu)造方法 根據(jù)xx市TD-LTE網(wǎng)絡(luò)配置數(shù)據(jù)，選取部分基站eNODEB； 以這些基站作為平面點(diǎn)，構(gòu)造平面點(diǎn)集的凸包，得到具有29個(gè)頂點(diǎn)的凸29邊形,凸多邊形最優(yōu)三角剖分,要求： 1. 做圖表示最優(yōu)三角剖分結(jié)果

7、可以手繪 2. 計(jì)算最優(yōu)三角剖分對(duì)應(yīng)的最優(yōu)目標(biāo)值——最小邊長(zhǎng)弦長(zhǎng)總和 3. 2種方法: 啟發(fā)式, DP,0-1背包問(wèn)題,利用 “附件4.背包問(wèn)題輸入數(shù)據(jù)” 給出的2組背包數(shù)據(jù)（背包容量、物品重量、物品價(jià)值） ，計(jì)算最優(yōu)物品裝載方案第1組數(shù)據(jù)：50個(gè)物品 第2組數(shù)據(jù)：100個(gè)物品,0-1背包問(wèn)題,要求： 指出最優(yōu)方案中， 1. 各個(gè)物品是否被放入 2. 物品放入后的背包總重量、總