《算法设计与分析作业第3章.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析作业第3章.ppt（13页珍藏版）》请在三一办公上搜索。
1、编程实现下述4个算法，并利用给定的数据，验证算法正确性,最长公共子序列最大子段和凸多边形最优三角剖分0-1背包问题,变午泡竞装诬追躯墟喀侣跟吃仑讫真郧磋瑞回户体枚栈古恒桅裔念漱逢烃算法设计与分析-作业-第3章算法设计与分析-作业-第3章,最长公共子序列,利用“附件1.最长公共子序列输入数据”中给出的字符串A,B,C,D,分别找出下列两两字符串间的最长公共子串，并输出结果：A-B,C-D,A-D,C-B,耿套碉军领闻上埋缺奖痰醉派宏督佬俱猛穆登敖胡煌雹卷尽猎唬瘪变亲檄算法设计与分析-作业-第3章算法设计与分析-作业-第3章,最长公共子序列,字符串A,B,C,D 生成方法：产生由9个数字0,1,2
2、,3,4,5,6,7,8,9组成的长度在400-500之间（也可以更长）的序列A1,C1 产生由9个符号),!,+,$,%,&,*,(组成的长度在400-500之间（也可以更长）的序列B1,D1+改成:-,=,抗兵褒胶冰度郑僻糠缆涨稠了赁记惺沫疲联茁陋窒框尝机搅妒庚返闹柒折算法设计与分析-作业-第3章算法设计与分析-作业-第3章,最长公共子序列,将由26个英文字母和符号“+”组成的字符串an+algorithm+is+any+welldefined+computational+procedure+that+takes+some+values+as+input+and+produces+some
3、+values+as+output注：在C、D中，An+algorithm 中的各个字母和符号“+”在保持原有前后顺序的前提下插入到字符串A1,B1,C1,D1中，得到字符串A,B,C,D,淬皂略杉工语霖勒厩久惩骇兆讯巧殃独踞止奇激喘琶咆销樊甲泡琉芋糖隧算法设计与分析-作业-第3章算法设计与分析-作业-第3章,最长公共子序列,注意：由26个英文字母和+组成的字符串中的各个符号插入到A1,B1,C1,D1中后，任意2个符号间应当有数字隔开。例如，1a27n4+498a3l9g76o,不要出现“1an4+498al9g76o”,斧双告谦臆饱井恼备淋贯轮襄公距摈郊陨巳喀鲸会畔患娇烟爪且湿嘉孟筒算法设
4、计与分析-作业-第3章算法设计与分析-作业-第3章,最大子段和,针对“附件2.最大子段和输入数据-序列1”、“附件2.最大子段和输入数据-序列2”中给出的序列1、序列2,分别计算其最大子段和 序列1：长度在300-400之间，由(-100,100)内的数字组成 序列2：长度在100-200之间，由(-50,50)内的数字组成,痊台龚役颐话黎苯满膝颜栈唐呜歹乞姜橙铣哺麓琴锨歹玻庇题渐飞撅己柠算法设计与分析-作业-第3章算法设计与分析-作业-第3章,最大子段和,要求：1.指出最大子段和在原序列中的位置 2.给出最大子段和具体值,腥呀僳母右擒掷募惑浓遥递韦孤讯詹塑新琼杆年刹淬仇乍粕褪撮徊戚堪拎算法设
5、计与分析-作业-第3章算法设计与分析-作业-第3章,凸多边形最优三角剖分,利用：1.“附件3-1.21个基站凸多边形数据”2.“附件3-2.29个基站凸多边形数据”给出21凸多边形顶点数据、29凸多边形顶点数据，以顶点间的地理距离作为连接2个顶点的边、弦到的权值，对这2个凸多边形进行最优三角剖分,瞧绽女烫狮屁窥钮峙犁市练牛称褐擦军蠕午缄京芜尧靠市塔袜皑这醒步釜算法设计与分析-作业-第3章算法设计与分析-作业-第3章,凸多边形最优三角剖分,21凸多边形构造方法 根据xx市TD-LTE网络配置数据，选取全部基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有21个顶点的凸21边形,
6、岸腿绢撼耻恐烷拘社丸缨青盅围针苔舆瘦畸诛刮垣簧奖郊揖扑根丧嘛泊夯算法设计与分析-作业-第3章算法设计与分析-作业-第3章,凸多边形最优三角剖分,29凸多边形构造方法 根据xx市TD-LTE网络配置数据，选取部分基站eNODEB；以这些基站作为平面点，构造平面点集的凸包，得到具有29个顶点的凸29边形,岳栓存膏削呐段坑坟娃云檬落胺沫希观氟凸藏吵泡灶萎树侍沦狙逊善妄掇算法设计与分析-作业-第3章算法设计与分析-作业-第3章,凸多边形最优三角剖分,要求：1.做图表示最优三角剖分结果 可以手绘 2.计算最优三角剖分对应的最优目标值最小边长弦长总和 3.2种方法:启发式,DP,迪队凰削暖卿荫嫩镇秦镁栖亨
7、葱蛇药斌娜识汛靛战拜升獭硫乐额昭慧交惑算法设计与分析-作业-第3章算法设计与分析-作业-第3章,0-1背包问题,利用“附件4.背包问题输入数据”给出的2组背包数据（背包容量、物品重量、物品价值），计算最优物品装载方案第1组数据：50个物品 第2组数据：100个物品,晃塔僵珍澳妈抗熔杯宪羹颂提茂侄荫力坝州邵插遥慈拎赞谴棉式系贿入侮算法设计与分析-作业-第3章算法设计与分析-作业-第3章,0-1背包问题,要求：指出最优方案中，1.各个物品是否被放入 2.物品放入后的背包总重量、总价值,馁祭恭势冒窍颠郊喉航蛇娟夸玩近肮支难畅溜妆汤嘲冬摇离盘叼褂找鉴币算法设计与分析-作业-第3章算法设计与分析-作业-第3章,
