Медианы

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
evgeny_d
Сообщения: 62
Зарегистрирован: 23 мар 2004, 08:31

Сообщение evgeny_d » 14 сен 2004, 07:01

Тут если доказать, что количество медиан зависит только от n (кол-ва точек) и не зависит от расположения точек, то можно рассматривать равносторонний многоугольник с n вершинами, у которого n/2 "медиан".

А вот как строго доказать первый факт надо подумать...

evgeny_d
Сообщения: 62
Зарегистрирован: 23 мар 2004, 08:31

Сообщение evgeny_d » 14 сен 2004, 07:09

А можно так.
Пусть всего n точек.
Тогда каждой точке x, очевидно, соответствует строго одна точка y из оставшихся n-1 точки, так чтобы пара (x,y) образовывала медиану (такая медиана существует для любой x, т.к. n-1 нечетно и никакие 3 точки не лежат на прямой).

Вспоминаем правило рукопожатия (если пара(x,y) образует медиану, то пара (y,x) образует ту же медиану, которую мы уже посчитали) и получаем результат - n/2

evgeny_d
Сообщения: 62
Зарегистрирован: 23 мар 2004, 08:31

Сообщение evgeny_d » 14 сен 2004, 10:12

Да уж...
Значит предположение "если доказать, что количество медиан зависит только от n" не верно.
Тут еще один примерчик в голову пришел - (0,0)(0,4)(4,0)(1,1)(1,2)(2,1) - 6 точек, 6 медиан.

По любому условия прийдется ставить на взаимное расположение точек...
Правда для одного случая задача решена %))

В остальном - трудно сказать.

evgeny_d
Сообщения: 62
Зарегистрирован: 23 мар 2004, 08:31

Сообщение evgeny_d » 14 сен 2004, 13:25

А какого объема множество, с которым прийдется работать?
Если небольшое - то почему бы просто не перебрать все пары и для каждой посмотреть, является ли она медианой (подставлять в уравнение прямой, полученной по двум точкам значение третьей точки, чтобы определить, с какой стороны эта третья точка, т.е. сравнивать полученно значение с 0).

Т.е. порядка n(n-1)/2 операций на перебор ребер и порядка (n-2) операции на перебор точек.
Итого такой алгоритм будет за O(n^3) находить не только количество медиан, но и все медианы.

Или надо более быстрый алгоритм?

Аватара пользователя
Naeel Maqsudov
Сообщения: 2551
Зарегистрирован: 20 фев 2004, 19:17
Откуда: Moscow, Russia
Контактная информация:

Сообщение Naeel Maqsudov » 15 сен 2004, 07:00

Все естественно порушится, если хотя бы у двух точек координата Y будет одинакова.

Ответить