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

《算法设计与分析-作业-第2章.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析-作业-第2章.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 编程实现下述4个算法，并利用xx省会城市TD-LTE网络的小区/基站数据验证算法正确性n合并排序 n快速排序n线性时间选择n平面最近点对TD-LTE网络小区/基站配置数据nTD-LTE网络覆盖区域由一系列小区组成，小区覆盖范围；n基站为小区内的用户提供无线通信服务n1个基站覆盖范围划分为多个小区、扇区cell/sector1cell3/sector3cell2/sector2BTSxxx省会城市TD-LTE网络结构xxx省会城市TD-LTE网络结构n基站1030个,小区2920个n区域:横向 22,356m 纵向 16,389mn经度范围(102.673290,102.895277)纬度范围

2、 (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(经度)long

3、itude: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个基站数据”n基站标识ENODEBIDn基站经度LONGITUDEn基站纬度LATITUDEn基站k-dist距离K_DIST 离该基站

4、最近的k个基站的平均距离，或者：离该基站第k近的基站距离 e.g.k=3,4小区数据 参见文件“tbcellkm1030-v2”n小区标识SECTOR_IDn小区名称SECTOR_NAMEn基站标识ENODEBIDn基站名称ENODENAMEn小区/基站经度LONGITUDEn小区/基站纬度LATITUDEn小区/基站k-dist距离K_DISTn小区天线方位角AZIMUTHn小区天线高度HEIGHT已知两点经纬度求两点间距离已知两点的经纬度求距离步骤：1.将2点经纬度转化为相应的弧度：2.距离公式：参数说明：R代表赤道半径 Latitude:纬度 Longitude:经度nRadLat：纬度

5、对应的弧度 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,

6、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;作业要求：排序n采用合并排序算法，根据基站k-dist距离，对基站从小到大进行排序n采用快速排序算法，根据基站k-dist距离，对基站从小到大进行排序作业要求：线性时间选择 采用线性时间选择算法，根据基站k-dist距离，挑选出nk-dist值最小的基站nk-dist第5小的基站nk-dist值第50小的基站nk-dist值最大的基站作业要求：平面最近点对 采用平面最近点对算法，根据基站经纬度，挑选出n距离最近的2个基站n距离次最近的2个基站