算法设计与分析作业第2章.ppt

编程实现下述4个算法，并利用xx省会城市TD-LTE网络的小区/基站数据验证算法正确性•合并排序 •快速排序•线性时间选择•平面最近点对TD-LTE网络小区/基站配置数据•TD-LTE网络覆盖区域由一系列小区组成，小区覆盖范围；•基站为小区内的用户提供无线通信服务•1个基站覆盖范围划分为多个小区、扇区cell/sector1cell3/sector3cell2/sector2BTSxxx省会城市TD-LTE网络结构xxx省会城市TD-LTE网络结构•基站1030个, 小区2920个•区域: 横向 22,356m 纵向 16,389m•经度范围 (102.673290, 102.895277) 纬度范围 (24.955100, 25.102470) 示例1：基站ENODEBID 566999 (经度)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个小区SECTOR_ID：565696_3longitude: 102.747000 Latitude: 25.041300SECTOR_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小区数据 参见文件“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 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 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个基站。