学习]算法设计与分析-作业-第3章.ppt

《学习]算法设计与分析-作业-第3章.ppt》由会员分享，可在线阅读，更多相关《学习]算法设计与分析-作业-第3章.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编程实现下述4个算法，并利用给定的数据，验证算法正确性n最长公共子序列n最大子段和n凸多边形最优三角剖分n0-1背包n问题最长公共子序列n利用“附件1.最长公共子序列输入数据”中给出的字符串A,B,C,D,分别找出下列两两字符串间的最长公共子串，并输出结果：A-B,C-D,A-D,C-B最长公共子序列字符串A,B,C,D生成方法：n产生由9个数字0,1,2,3,4,5,6,7,8,9组成的长度在400-500之间（也可以更长）的序列A1,C1n产生由9个符号),!,+,$,%,&,*,(组成的长度在400-500之间（也可以更长）的序列B1,D1n+改成:-,=最长公共子序列n将由26个英文字

2、母和符号“+”组成的字符串an+algorithm+is+any+welldefined+computational+procedure+that+takes+some+values+as+input+and+produces+some+values+as+output注：在C、D中，An+algorithm中的各个字母和符号“+”在保持原有前后顺序的前提下插入到字符串A1,B1,C1,D1中，得到字符串A,B,C,D最长公共子序列n注意：由26个英文字母和+组成的字符串中的各个符号插入到A1,B1,C1,D1中后，任意2个符号间应当有数字隔开。例如，1a27n4+498a3l9g76o,不要

3、出现“1an4+498al9g76o”最大子段和n针对“附件2.最大子段和输入数据-序列1”、“附件2.最大子段和输入数据-序列2”中给出的序列1、序列2,分别计算其最大子段和n序列1：长度在300-400之间，由(-100,100)内的数字组成序列2：长度在100-200之间，由(-50,50)内的数字组成最大子段和n要求：1.指出最大子段和在原序列中的位置2.给出最大子段和具体值凸多边形最优三角剖分n利用：1.“附件3-1.21个基站凸多边形数据”2.“附件3-2.29个基站凸多边形数据”给出21凸多边形顶点数据、29凸多边形顶点数据，以顶点间的地理距离作为连接2个顶点的边、弦到的权值，对

4、这2个凸多边形进行最优三角剖分凸多边形最优三角剖分n21凸多边形构造方法根据xx市TD-LTE网络配置数据，选取全部基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有21个顶点的凸21边形凸多边形最优三角剖分n29凸多边形构造方法根据xx市TD-LTE网络配置数据，选取部分基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有29个顶点的凸29边形凸多边形最优三角剖分n要求：1.做图做图表示最优三角剖分结果可以手绘2.计算最优三角剖分对应的最优目标值最小边长弦长总和3.2种方法:启发式,DP0-1背包问题n利用“附件4.背包问题输入数据”给出的2组背包数据（背包容量、物品重量、物品价值），计算最优物品装载方案n第1组数据：50个物品第2组数据：100个物品0-1背包问题n要求：指出最优方案中，1.各个物品是否被放入2.物品放入后的背包总重量、总价值