《算法设计与分析-作业-第2章.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-作业-第2章.ppt（15页珍藏版）》请在三一办公上搜索。
1、编程实现下述4个算法，并利用xx省会城市TD-LTE网络的小区/基站数据验证算法正确性,合并排序 快速排序线性时间选择平面最近点对,TD-LTE网络小区/基站配置数据,TD-LTE网络覆盖区域由一系列小区组成，小区覆盖范围；基站为小区内的用户提供无线通信服务1个基站覆盖范围划分为多个小区、扇区,xxx省会城市TD-LTE网络结构,xxx省会城市TD-LTE网络结构,基站1030个,小区2920个区域:横向 22,356m 纵向 16,389m经度范围(102.673290,102.895277)纬度范围(24.955100,25.102470),示例1：基站ENODEBID 566999,(经
2、度)longitude:102.756000(纬度)Latitude:25.040070 包含3个小区,SECTOR_ID：566999_3longitude:102.756000 Latitude:25.040070,SECTOR_ID：566999_1longitude:102.756000 Latitude:25.04007,SECTOR_ID：566999_2longitude:102.756000 Latitude:25.040070,示例2：基站ENODEBID 565696,(经度)longitude:102.747000(纬度)Latitude:25.041300包含3个小区,
3、SECTOR_ID：565696_3longitude:102.747000 Latitude:25.041300,SECTOR_ID：565696_1longitude:102.747000 Latitude:25.041300,SECTOR_ID：565696_2longitude:102.747000 Latitude:25.041300,基站数据,参见文件“1033个基站数据”基站标识ENODEBID基站经度LONGITUDE基站纬度LATITUDE基站k-dist距离K_DIST 离该基站最近的k个基站的平均距离，或者：离该基站第k近的基站距离 e.g.k=3,4,小区数据,参见文件
4、“tbcellkm1030-v2”小区标识SECTOR_ID小区名称SECTOR_NAME基站标识ENODEBID基站名称ENODENAME小区/基站经度LONGITUDE小区/基站纬度LATITUDE小区/基站k-dist距离K_DIST小区天线方位角AZIMUTH小区天线高度HEIGHT,已知两点经纬度求两点间距离,已知两点的经纬度求距离步骤：1.将2点经纬度转化为相应的弧度：2.距离公式：参数说明：R代表赤道半径 Latitude:纬度 Longitude:经度RadLat：纬度对应的弧度 RadLon:经度对应的弧度,已知两点的经纬度求距离代码,已知两点的经纬度求距离代码：public
5、 const double EARTH_RADIUS=6378.137;/赤道半径km/将对应的经纬度转化为弧度 public static double rad(double LatOrLon）return LatOrLon*Math.PI/180.0;/利用两点的经纬度求两点的距离/第一个点的经度/第一个点的纬度/第二个点的经度/第二个点的纬度/两点距离(m)public static double GetDistance2(double lng1,double lat1,double lng2,double lat2),已知两点的经纬度求距离代码,/将对应的经纬度转化为弧度 double
6、 radLat1=rad(lat1);double radLat2=rad(lat2);double radlng1=rad(lng1);double radlng2=rad(lng2);/利用正弦余弦公式求距离 double s=Math.Acos(Math.Cos(radLat1)*Math.Cos(radLat2)*Math.Cos(radlng1-radlng2)+Math.Sin(radLat1)*Math.Sin(radLat2);s=s*EARTH_RADIUS;s=Math.Round(s*1000,6);return s;,作业要求：排序,采用合并排序算法，根据基站k-dist距离，对基站从小到大进行排序采用快速排序算法，根据基站k-dist距离，对基站从小到大进行排序,作业要求：线性时间选择,采用线性时间选择算法，根据基站k-dist距离，挑选出k-dist值最小的基站k-dist第5小的基站k-dist值第50小的基站k-dist值最大的基站,作业要求：平面最近点对,采用平面最近点对算法，根据基站经纬度，挑选出距离最近的2个基站距离次最近的2个基站,
