《算法设计与分析-作业-第3章.ppt》由会员分享,可在线阅读,更多相关《算法设计与分析-作业-第3章.ppt(13页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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.物品放入后的背包总重量、总价值