9个点退化为一维的情况,即x轴的9个实数:1,4,7,12,15,17,22,25,28。最近点对即为9个实数中相差最小的两个实数。编写递归函数,以分治的思想求解这9个点在一维的情况下的最近点对以及对应的距离。 要求:输
时间: 2024-05-10 16:16:01 浏览: 1
入9个实数,输出最近点对及其距离。
以下是Python代码实现:
```python
import math
def closest_pair(points):
n = len(points)
if n <= 1:
return None, float('inf')
elif n == 2:
return points, abs(points[0] - points[1])
else:
mid = n // 2
left_points = points[:mid]
right_points = points[mid:]
left_pair, left_dist = closest_pair(left_points)
right_pair, right_dist = closest_pair(right_points)
if left_dist < right_dist:
min_pair = left_pair
min_dist = left_dist
else:
min_pair = right_pair
min_dist = right_dist
mid_point = points[mid]
strip = []
for i in range(mid-1, -1, -1):
if abs(points[i] - mid_point) < min_dist:
strip.append(points[i])
else:
break
for i in range(mid, n):
if abs(points[i] - mid_point) < min_dist:
strip.append(points[i])
else:
break
strip.sort()
strip_len = len(strip)
for i in range(strip_len - 1):
for j in range(i+1, min(i+8, strip_len)):
dist = abs(strip[i] - strip[j])
if dist < min_dist:
min_dist = dist
min_pair = [strip[i], strip[j]]
return min_pair, min_dist
points = [1, 4, 7, 12, 15, 17, 22, 25, 28]
min_pair, min_dist = closest_pair(points)
print("最近点对:", min_pair)
print("最近距离:", min_dist)
```
输出结果为:
```
最近点对: [15, 17]
最近距离: 2
```