算法設計與分析-作業(yè)-第2章

1、 編程實現下述4個算法，并利用xx省會城市td-lte網絡的小區(qū)/基站數據驗證算法正確性 合并排序 快速排序 線性時間選擇 平面最近點對td-lte網絡小區(qū)/基站配置數據 td-lte網絡覆蓋區(qū)域由一系列小區(qū)組成，小區(qū)覆蓋范圍； 基站為小區(qū)內的用戶提供無線通信服務 1個基站覆蓋范圍劃分為多個小區(qū)、扇區(qū)cell/sector1cell3/sector3cell2/sector2bts基站bts移動交換機msc基站控制器bsc數據庫vlr/hlr網絡管理公共電話網pstn基站控制器bsc基站bts基站bts基站bts手持機hsms移動臺ms移動臺xxx省會城市td-lte網絡結構xxx省會城市td

2、-lte網絡結構 基站1030個, 小區(qū)2920個 區(qū)域: 橫向 22,356m 縱向 16,389m 經度范圍 (102.673290, 102.895277) 緯度范圍 (24.955100, 25.102470) 示例1：基站enodebid 566999 (經度)longitude: 102.756000 (緯度)latitude: 25.040070 包含3個小區(qū)sector_id： 566999_3longitude: 102.756000 latitude: 25.040070 sector_id： 566999_1longitude: 102.756000 latitude:

3、25.04007 sector_id： 566999_2longitude: 102.756000 latitude: 25.040070 示例2：基站enodebid 565696 (經度)longitude: 102.747000 (緯度)latitude: 25.041300包含3個小區(qū)sector_id：565696_3longitude: 102.747000 latitude: 25.041300sector_id： 565696_1longitude: 102.747000 latitude: 25.041300 sector_id： 565696_2longitude: 102

4、.747000 latitude: 25.041300 基站數據 參見文件“1033個基站數據” 基站標識enodebid 基站經度longitude 基站緯度latitude 基站k-dist距離k_dist 離該基站最近的k個基站的平均距離，或者：離該基站第k近的基站距離 e.g. k=3,4小區(qū)數據 參見文件“tbcellkm1030-v2” 小區(qū)標識sector_id 小區(qū)名稱sector_name 基站標識enodebid 基站名稱enodename 小區(qū)/基站經度longitude 小區(qū)/基站緯度latitude 小區(qū)/基站k-dist距離k_dist 小區(qū)天線方位角azimuth

5、 小區(qū)天線高度height已知兩點經緯度求兩點間距離已知兩點的經緯度求距離步驟：1.將2點經緯度轉化為相應的弧度：2.距離公式： 參數說明：r代表赤道半徑 latitude:緯度 longitude:經度 radlat：緯度對應的弧度 radlon:經度對應的弧度*arccos(cos(radlat1)*cos(radlat2)*cos(radlon1 radlon2)sin(radlat1)*sin(radlat2)r* /180radlatlatitude* /180radlonlongitude已知兩點的經緯度求距離代碼已知兩點的經緯度求距離代碼： public const double

6、 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)已知兩點的經緯度求距離代碼 /將對應的經

7、緯度轉化為弧度 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; 作業(yè)要求：排序 采用合并排序算法，根據基站k-dist距離，對基站從小到大進行排序 采用快速排序算法，根據基站k-dist距離，對基站從小到大進行排序作業(yè)要求：線性時間選擇 采用線性時間選擇算法，根據基站k-di