Здравствуйте, Уважаемые программисты! Я открыла для себя удивительный язык С++ совсем недавно. Да некоторых пор проблем не возникало (язык легко дается). Но вот задали задачку, к которой я не знаю, с какой стороны подобраться... Звучит она так: Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна! Единственное, что я точно знаю, без многомерных массивов здесь не обойтись. Очень надеюсь на вашу помощь в решении этого вопроса! Заранее благодарна!

Можно и без многомерных, обычного вектора (который std::vector) хватит.

В принципе, действительно нет необходимости в многомерном массиве... Достаточно 2 одномерных:
1. массив координат точек (на N элементов)
2. массив сумм расстояний для каждой точки (на N элементов)
Что делать - идешь по первому массиву и считаешь сумму расстояний для i-ой точки и записываешь в i-ый элемент второго массива. Затем находишь во втором массиве минимальный элемент - его индекс позволит узнать точку, которой он соответствует.

А, мы такое делали.. Ток не вышло ничего)

Это сообщение отредактировал(а) Garcian - 10.12.2008, 20:11

Впринципе понятно... Только с геометрией не все хорошо,   

случай клинический...
есть множество точек {(x,y)}
искомая точка это (Xсредн,Yсредн)

какие многомерные массивы... какие std::vector.... 
математику учить в школе надо было

Добавлено через 1 минуту и 20 секунд

бред какой %)

Может и бред... раздел для новичков)   

 

Снежанна, какой пример? как среднее арифметическое считать? я как-то забыл как это делается, потому не могу написать, и учебника за 5й класс под рукой нету =\

Мне понять как это в программе осущетвить. А среднее арифмитическое могу напомнить   

а может он не просто так   


что-то мне это видится более чем не очевидно  

Добавлено через 8 минут и 28 секунд
или вы имели ввиду средневзвешенное?

расстояние между двумя точками считается, как квадратный корень из суммы квадратов разностей координат: 

Добавлено через 2 минуты и 31 секунду

M bsa

Сообщения, не относящиеся к теме, удалил

когда-то писал, может пригодится: 
тут класс точки и класс прямой, прямая может возвращать расстояние между точками, которыми задана, tg угла наклона и смещение, те короче
y=kx+b, она может вернуть k, b, а также расстояние между точками, которыми задана...
<myline.h>


а это <mypoint.h>

Признаю я был не прав. Среднее арифметическое там не подходит хотя бы потому что оно выдает точку не обязательно принадлежащую к множеству заданных точек.
Однако я заметил что C++ убило мозг участников форума, т.к. никто так и не попытался решить задачу математически.
При беглом анализе, очевидно что для вырожденного случая с 2я точками обе точки являются решениями, также точки могут совпадать друг с другом. Для вырожденного случая когда все точки находятся на одной прямой, если число точек нечетно, решением является "средняя" точка, если четно - две "средние" точки. Я не проверял, но с большой долей вероятности "средней" точкой является точка ближайшая к центру масс, т.е. к среднему арифметическому координат точек.

Наоборот. Мозг ищет более рациональное решение. Мне, допустим, легче сначала решить эту задачу программно в лоб, а потом, если время позволит произвести анализ решения.

среднеарифметическое и центр масс необязательно совпадают, потому, что это разные вещи

J0ker, при одинаковых массах совпадают. Я привел такую формулировку для удобного перехода от более очевидного физического подхода к формулировке задачи к менее очевидному математическому.

upd: убрал очипятку) поспешишь....

Это сообщение отредактировал(а) GoldFinch - 11.12.2008, 21:00

  Спасибо, bsa,  Dmi3ev (хотя я не совсем представляю, как воспользоваться <mypoint.h>). Также, мне необхадимо указать все некорректные ситуации. Что это значит?

при одинаковых массах точек
тогда да

Добавлено через 1 минуту и 55 секунд
но это интуитивное решение... надо-бы как-то подкрепить док-вом... впрочем я думаю оно легко выводится и так оно и будет

Это значит, что ты должна указать все ситуации, когда твоя программа будет работать некорректно. Например, если есть более одной искомой точки (частные варианты: все точки в одном месте, всего 2 точки, все точки в вершинах правильных N-угольков), или всего одна точка в массиве.

Столько споров, давайте посмотрим, я набросал решение (оно не идеально, но...):

Центр масс имеет место быть ))) По-моему мнению. А вото mypoint.h


Добавлено через 7 минут и 27 секунд
хотя алгоритм нахождения центра масс фигуры, а потом сравнивание этого центра с каждой точкой (какая ближе)...
хз, по-моему, так проще, хотя, может, прав не я...   

Вообщем, как говорится, ЧТД
Решил двумя способами, 1-сумма расстояний, 2-расстояние до центра масс, ответы совпадают )))

это не может считаться док-вом, т.к. верно на ограниченом множестве проверенным с помощью вашей программы например

J0ker, Вы не юрист? или математик? просто эти люди любят к словам докапываться. Хорошо, не чтд. Скажу так, данная программа выдает из 10(0) раз одинаковые решения обоими способами, я задавал множество и побольше размером, точно все также... Вобщем, на доказательство не претендую, но ... Мне кажется все стало ясно... Себе я доказал, что хотел... Решил поделиться с другими своими изысканиями... Но другие слишком умные... Можно еще не только целые координаты задавать(у меня они только целые в программе)... Я согласен с тем, что это доказательство не может считаться неопровержимым. Да я и не в том смысле говорил чтд. Я имел в виду, что догадки GoldFinch да и ваши тоже оказались подкреплены и программой...  

я бы на месте препода точно-бы докопался  

Добавлено через 1 минуту и 12 секунд

ну звиняйте
для меня чтд означает "что и требовалось доказать"    

я ж говорю, шибко умный ВЫ   у меня с математикой неплохо, я все это прекрасно знаю, что такое ЧТД и даже еще кое-что   но медальками не звеню, в отличии от ВАС   Ладно, боюсь сказать лишнего, а то ВЫ определениями задавите  

чето незаметно

Добавлю, что лучше в таком случае считывать x- и y-координаты в бинарные деревья, чтобы потом быстро найти точку, ближе всего лежащую к среднему арифметическому.

GoldFinch! Докажи обратное))) Если бы ты сидел со мной рядом и я бы тебе сказал, что точки принадлежащие одной прямой не лежат в одной плоскости, или, что шар квадратный, ты вряд ли бы стал спорить))) А кричать о том, что ты умный, не значит быть умным))) Скорее это значит обратное))) Что конкретно в программной реализации тебя не устраивает??? По делу говори, а не посты зарабатывай...))) заметно, незаметно... Удачи...

Dmi3ev, это инженерное доказательство, но не математическое. Если математическое, то примерно так:



В производной здесь опечатка, понятно, что если дифференцируем по x, то игрековой части не будет. Лень перерисовывать.

Это сообщение отредактировал(а) Ln78 - 12.12.2008, 20:28

Ln78, да я не претендовал на доказательство математическое. Просто пока разводились базары, решил быстренько написать программку, которая собственно и являлась целью вопроса автора. Но когда я её написал, опять начались базары, только уже по поводу того, что я не совсем правильно выразился, сказал чтд, ***ны в рот. Но я так сказал, всего лишь потому, что решил двумя способами, они давали, как предполагалось одинаковое решение. И тут вдруг опять споры... Ненавижу эти споры... Всё, доказывайте, спорьте, делайте, что хотите, для меня все ясно с самого начала... Всем удачи...

это ты про себя так сказал?

вот именно таким образом рождаются самые заковыристые заблуждения   
просто надо понять, что не всегда то, что очевидно - верно

а что за функция рандом? Компилятор не распознает.

Вообщем выдает 2 ошибки...



В чем проблема?

for (int i=1; i<n; i++)

и в самом конце текста добавьте пустую строку.

mes, спасибо, а то она в личку пишет, почему не работает??? а я не знаю, у меня на компе рабочая версия этой проги, я же не знаю, что она видоизменяет после моего написания   у меня в этом месте ошибки нет, а человек стер int и нашел себе проблемы...  

Снежанна, то, что после // можно и убрать, я просто тебе отослал с ними, потому, что быстро исправлял...  а ты могла бы и навести красоту, ты же девушка...

Снежанна, вот это:Надо писать так:

уж извините, что в универе на компах 90х приходится с Борландом работать   Там пишет мультипат дикларэйшон или что то типа того) Спасибо, bsa

Это сообщение отредактировал(а) Снежанна - 24.12.2008, 20:40

Да и еще, до этого я составляла только входные и выходные файлы. А как сделать файл протокола, который содержал бы в себе оба этих файла, так и еще  показывал все промежуточные рассчеты и неккоректные ситуации (с которыми, собственно говоря, тоже не успеваю разобраться), покажите, пожалуйста