 |
|
Математика:
Вычислительная геометрия:
Разное.
На прямой задано N точек с координатами X1,X2,...,Xn. Написать программу, которая находит на прямой такую точку z, сумма расстояний от которой до данных N точек минимальна.
Пусть координаты точек x1, ..., xN не убывают (если это не так, то просто отсортируем предварительно последовательность).
Метод решения #1.
Предположим, что мы нашли точку z, и она лежит на интервале (x[i],x[i+1]). Справа от нее i точек, слева - N-i. Сумма расстояний Smin будет такой:
Smin=(z-x[1])+ ... +(z-x[i])+(x[i+1]-z)+ ... +(x[N]-z).
Предположим, что i>N-i и мы в пределах интервала сдвигаем точку z влево на какую-то маленькую величину d (d<z-x[i]). Получаем новую сумму S
S=(z-d-x[1])+ ... +(z-d-x[i])+(x[i+1]-(z-d))+ ... +(x[N]-(z-d))=Smin-d*i+d*(N-i).
А так как, по предположению, i>N-i, то S<Smin !?
Ситуация, когда N-i>i, исследуется аналогично - мы делаем сдвиг на величину d<x[N+1] - z вправо, не выходя при этом за границы интервала, и опять же получаем, что новая сумма S<Smin. Случай, когда z совпадает с одной из точек x[i] исследуется так же, как и выше, используя маленькие сдвиги.
Следовательно, для того, чтобы точка z была искомой, необходимо и достаточно, чтобы справа и слева от нее лежало одно и то же число точек. Если N=2k, то точка z может быть любой из точек отрезка [x[k],x[k+1]], если же N=2k+1, то точка z=x[k+1].
Метод решения #2.
Пусть мы решаем задачу для N точек на прямой.
Точка z должна, очевидно, лежать на отрезке [x[1],x[N]].
Если N=1, то данная точка и является искомой.
Если N=2, то z может лежать где угодно на отрезке [x1,xN] - суммарное расстояние будет одинаковым и равным длине отрезка.
Если N>2, то суммарное расстояние от точки z до точек с минимальной и максимальной координатами (т.е. до точек x1 и xN) не зависит от местоположения точки z и равно длине отрезка [x1, xN]. Так как суммарное расстояние до этих двух точек постоянно, то поэтому мы можем их отбросить, и решать задачу уже для N-2 точек x2,...,xN-1. Проведя необходимое число раз сокращение количества точек, мы придем к уже рассмотренным случаям одной или двух точек.
Окончательно получаем: если N=2k, то точка z может быть любой из точек отрезка [xk,xk+1], если же N=2k+1, то точка z=x[k+1].
Вверх по странице, к оглавлению и навигации.