[學習]算法設計與分析-作業(yè)-第3章

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

2、{0,1,2,3,4,5,6,7,8,9}組成的長度在400-500之間（也可以更長）的序列A1, C1 產(chǎn)生由9個符號{),!,@,+,$,%,^,&,*,(}組成的長度在400-500之間（也可以更長）的序列B1, D1 +改成: -,=,最長公共子序列,將由26個英文字母和符號“+”組成的字符串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… 中的各個字母和符號“+”在保持原有前后順序的前提下插入到字符串A1, B1, C1, D1中，得到字符串A, B, C, D,最長公共子序列,注意： 由26個英文字母和+組成的字符串中的各個符號插入到A1, B1, C1, D1中后，任意2個符號間

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

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

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

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