数据结构
网络
关系数据库管理系统 (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
