《算法设计与分析-作业-第3章.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-作业-第3章.ppt（13页珍藏版）》请在三一办公上搜索。
1、编程实现下述4个算法，并利用给定的数据，验证算法正确性,最长公共子序列最大子段和凸多边形最优三角剖分0-1背包问题,最长公共子序列,利用“附件1.最长公共子序列输入数据”中给出的字符串A,B,C,D,分别找出下列两两字符串间的最长公共子串，并输出结果：A-B,C-D,A-D,C-B,最长公共子序列,字符串A,B,C,D 生成方法：产生由9个数字0,1,2,3,4,5,6,7,8,9组成的长度在400-500之间（也可以更长）的序列A1,C1 产生由9个符号),!,+,$,%,&,*,(组成的长度在400-500之间（也可以更长）的序列B1,D1+改成:-,=,最长公共子序列,将由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,最长公共子序列,注意：由26个英文字母和+组成的字符串中的各个符号插入到A1,B1,C1,D1中后，任意2个符号间应当有数字隔开。例如，1a27n4+498a3l9g76o,不
3、要出现“1an4+498al9g76o”,最大子段和,针对“附件2.最大子段和输入数据-序列1”、“附件2.最大子段和输入数据-序列2”中给出的序列1、序列2,分别计算其最大子段和 序列1：长度在300-400之间，由(-100,100)内的数字组成 序列2：长度在100-200之间，由(-50,50)内的数字组成,最大子段和,要求：1.指出最大子段和在原序列中的位置 2.给出最大子段和具体值,凸多边形最优三角剖分,利用：1.“附件3-1.21个基站凸多边形数据”2.“附件3-2.29个基站凸多边形数据”给出21凸多边形顶点数据、29凸多边形顶点数据，以顶点间的地理距离作为连接2个顶点的边、弦
4、到的权值，对这2个凸多边形进行最优三角剖分,凸多边形最优三角剖分,21凸多边形构造方法 根据xx市TD-LTE网络配置数据，选取全部基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有21个顶点的凸21边形,凸多边形最优三角剖分,29凸多边形构造方法 根据xx市TD-LTE网络配置数据，选取部分基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有29个顶点的凸29边形,凸多边形最优三角剖分,要求：1.做图表示最优三角剖分结果 可以手绘 2.计算最优三角剖分对应的最优目标值最小边长弦长总和 3.2种方法:启发式,DP,0-1背包问题,利用“附件4.背包问题输入数据”给出的2组背包数据（背包容量、物品重量、物品价值），计算最优物品装载方案第1组数据：50个物品 第2组数据：100个物品,0-1背包问题,要求：指出最优方案中，1.各个物品是否被放入 2.物品放入后的背包总重量、总价值,
