(1)假設有7個城市,且各城市等距分布,人口分布如下:
(2) 只要城市數量大於等於4,就要繼續劃分,從中間的城市找出一個行政中心,此行政中心的找法是以「人力移動距離」(人口數×城市與行政中心距離),最小者為行政中心,若有相同「人力移動距離」,則取座標小者為行政中心。本題演算法同快速排序法,也就是分而治之。
第一輪:aa(a,1,7),因為7減1大於等於2
7-1 >= 2
所以,分別以城市2~6為城市中心,計算各城市的人力移動距離。
城市2=2×1+3×0+1×1+3×2+7×3+6×4+9×5=99
城市3=2×2+3×1+1×0+3×1+7×2+6×3+9×4=78
城市4=2×3+3×2+1×1+3×0+7×1+6×2+9×3=59
城市5=2×4+3×3+1×2+3×1+7×0+6×1+9×2=46
城市6=2×5+3×4+1×3+3×2+7×1+6×0+9×1=47
以下是使用Excel幫忙驗證的結果:
經過以上運算,第一輪選到城市5為行政中心(因為其人力移動距離是46,為最小值)。這樣就將這些城市分成兩區塊(1 , 4)與(6 , 7),且此兩區塊的城市劃分,也和原方法相同,可以繼續呼叫原函式。所以程式如下,此即為「分而治之」的道理。
aa(a,1,4)
aa(a,6,7)
5 2
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||