В деревне есть $%3$% дома с координатами $%(0, 0), (1, 0), (0.5 , \frac{\sqrt{3}}{2})$%, в которых живут соответственно $%N, P$% и $%Q$% человек. Где стоит построить колодец, чтобы суммарная длина пути всех людей до колодца была минимальна? Если таких точек много, то выберите ту, у которой максимальная длина пути минимальна. Я бы сам решил, если бы не было дано еще условие о жильцах - это сильно усложняет задачу.

задан 28 Янв '14 17:43

изменен 28 Янв '14 20:52

Deleted's gravatar image


126

1

@falcao, на составление программы, но я не могу определить, насколько переменные P,N,Q будут влиять на точку

(29 Янв '14 1:12) kirill1771

Здесь аналитически вряд ли есть какая-то "красивая" формула. Даже для обычной точки Торричелли, которая легко строится геометрически, выражения для координат не самые простые.

Если это задача по программированию, то должна быть, наверное, задана точность десятичного приближения? Может, тогда её надо решать на "сетке", или при помощи численных методов?

(29 Янв '14 2:39) falcao

@kirill1771: это один из возможных методов. Всё зависит от того, какая точность десятичного приближения здесь нужна. Допустим, она составляет порядка $%10^{-3}$%. Тогда "сетка" будет иметь порядка $%10^6$% "узлов". Перебрать такое число вариантов для программы -- дело нехитрое. Вид функции, которая при этом минимизируется, довольно простой. Если нужна более высокая точность, то можно сначала получить квадрат со стороной порядка $%10^{-3}$% первым способом, а потом уже его разбивать на более мелкие квадраты.

(29 Янв '14 18:11) falcao

@falcao,спасибо, я почти разобрался (скоро выложу код программы). У меня только один вопрос остался: как понять "Если таких точек много, то выберите ту, у которой максимальная длина пути минимальна"?

(30 Янв '14 13:19) kirill1771

@kirill1771: я не знаю примеров, чтобы в этой задаче точка не была единственной. Правда, я не пытался доказывать соответствующее утверждение. "На вскидку", оно представляется верным. Мне кажется, поскольку априори не известно, единственно ли решение, то авторы сделали эту оговорку просто "для порядка". А мог иметься в виду случай типа N=0, когда точек много.

Ещё одно соображение: если в одной из точек находится слишком много человек (столько, сколько их имеется вместе в двух других точках, или больше), то из неравенства треугольника следует, что колодец именно в этой точке и расположен.

(30 Янв '14 13:32) falcao

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

(30 Янв '14 13:41) kirill1771

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

(30 Янв '14 13:53) falcao

@falcao,мне предложили метод решения этой задачи через центры масс материальных точек (сейчас опишу в ответе)

(31 Янв '14 16:43) kirill1771
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
2

Мне предложили метод решения этой задачи через центры масс материальных точек: $$x=\frac{x_1m_1+x_2m_2+x_3m_3}{m_1+m_2+m_3}$$

$$y=\frac{y_1m_1+y_2m_2+y_3m_3}{m_1+m_2+m_3},$$ где $%m_i$% - количество жильцов

ссылка

отвечен 31 Янв '14 16:47

изменен 31 Янв '14 16:58

falcao's gravatar image


228k2845

@kirill1771: я отредактировал Ваш текст, убрав оттуда все лишние символы, чтобы он правильно читался редактором. Что касается формул для системы точек с массами, то я думаю, что этот подход не работает. То, что он неприменим в общем случае, не вызывает никаких сомнений, потому что при $%m_1=m_2=m_3=1$% должна получиться точка Торричелли, а не точка пересечения медиан. И даже для случая равностороннего треугольника легко построить контрпример. Скажем, при $%m_2=m_3=1$% и $%m_1 > 2$% колодец должен быть расположен в (0;0), а формулы указывают на нечто другое.

(31 Янв '14 17:49) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×4,049
×3,250
×2,640
×149

задан
28 Янв '14 17:43

показан
856 раз

обновлен
31 Янв '14 17:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru