c054: P163 城市行政劃分(107年03月APCS試題)
Tags : Python
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-12-09 11:01

Content

(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)

Input
Output
Sample Input #1


											
										
Sample Output #1
5
2
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
Tags:
Python
出處:
[管理者: zero(育達管理員) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」