資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：查詢最佳服務中心位置
假設我們有一組位置座標點，這些點代表一些房屋的位置。如果想在 (xc, yc) 處建立一個服務中心，使得從任意給定點到 (xc, yc) 的歐幾里得距離之和最小，那麼我們需要找到這個最小距離之和。
例如，如果輸入是 positions = [(10,11),(11,10),(11,12),(12,11)]，則輸出為 4.0
為了解決這個問題，我們將遵循以下步驟：
numIter := 50
定義一個函式 total()。該函式接收 cx, cy, positions 作為引數。
total := 0.0
對於 positions 中的每個點 p，執行以下操作：
x, y := p
total := total + (cx, cy) 和 (x, y) 之間的歐幾里得距離
返回 total
定義一個函式 fy()。該函式接收 x, positions 作為引數。
l := 0, r := 101
res := 0
對於 i in range(0, numIter)，執行以下操作：
y1 := l + (r - l) / 3
y2 := r - (r - l) / 3
t1 := total(x, y1, positions)
t2 := total(x, y2, positions)
res := min(t1, t2)
如果 t1 < t2，則
r := y2
否則，
l := y1
返回 res
定義一個函式 fx()。該函式接收 positions 作為引數。
l := 0, r := 101
res := 0
對於 i in range(0, numIter)，執行以下操作：
x1 := l + (r - l) / 3
x2 := r - (r - l) / 3
t1 := fy(x1, positions)
t2 := fy(x2, positions)
res := min(t1, t2)
如果 t1 < t2，則
r := x2
否則，
l := x1
返回 res
在主方法中，返回 fx(positions)
示例
讓我們來看下面的實現來更好地理解。
from math import sqrt
def solve(points):
numIter = 50
def total(cx, cy, positions):
total = 0.0
for p in positions:
x, y = p
total += sqrt((cx - x) * (cx - x) + (cy - y) * (cy - y))
return total
def fy(x, positions):
l, r = 0, 101
res = 0
for i in range(numIter):
y1 = l + (r - l) / 3
y2 = r - (r - l) / 3
t1 = total(x, y1, positions)
t2 = total(x, y2, positions)
res = min(t1, t2)
if t1 < t2:
r = y2
else:
l = y1
return res
def fx(positions):
l, r = 0, 101
res = 0
for i in range(numIter):
x1 = l + (r - l) / 3
x2 = r - (r - l) / 3
t1 = fy(x1, positions)
t2 = fy(x2, positions)
res = min(t1, t2)
if t1 < t2:
r = x2
else:
l = x1
return res
return fx(positions)
positions = [(10,11),(11,10),(11,12),(12,11)]
print(solve(positions))輸入
[(10,11),(11,10),(11,12),(12,11)]
輸出
4.0
瀏覽量：118
