Алгоритм. Движение по окружности
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Алгоритм. Движение по окружности - 2009-03-17 15:56:26.626666
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
Уважаемые форумчане, прошу помощи с определением оптимального алгоритма.
Дана окружность. На ней на равном друг от друга расстоянии расположено N точек. Расстояние между точками по прямой = D. Они начинают одновременно двигаться, причем так, что мгновенная скорость каждой точки направлена к соседней , если смотреть по часовой стрелке, точке. В итоге траектория движения получается в виде некоторой спирали закрученной по часовой стрелке, и, в конце концов, точки одновременно встречаются где-то внутри окружности (предположительно в ее центре). И нужно найти расстояние, которая каждая точка пройдет до момента встречи.
входные данные
n=2 d=10
ответ = 5, так как обе точки по диаметру будут двигаться навстречу друг другу.
при n=3 d=10, ответ = 6.67. Хз как он получается. Предположительно формула otvet = d-d/n . Но если была бы такая формула, то задача была бы слишком легкой и не программерской даже. В общем, рассмотрю все предположения.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 16:16:32.230000
|
|
|
jeka5555
Сообщений: 18
Оценки: 0
Присоединился: 2009-03-10 08:43:28.223333
|
Сложная для восприятия задача, было бы не плохо в графическом виде посмотреть её постановку, график так сказать.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 16:22:59.030000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
Нарисовал.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 16:28:16.776666
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Имхо не хватает данных. Либо что брать за "точку", либо скорости.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 16:38:36.690000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Да. Хотя, имхо, точки могут просто не сойтись :). Чёт я туплю…
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 16:41:46.316666
|
|
|
jeka5555
Сообщений: 18
Оценки: 0
Присоединился: 2009-03-10 08:43:28.223333
|
quote:
ORIGINAL: gotoxardas
Хватает. Задача с серьезной олимпиады. Скорость может быть любая, расстояние пройденное точками не измениться от этого.
Скорость любая, главное что бы для всех точек одинаковая была, как я понял.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 16:50:56.286666
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
quote:
ORIGINAL: jeka5555
quote:
ORIGINAL: gotoxardas
Хватает. Задача с серьезной олимпиады. Скорость может быть любая, расстояние пройденное точками не измениться от этого.
Скорость любая, главное что бы для всех точек одинаковая была, как я понял.
Абсолютно верно
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 18:15:37.320000
|
|
|
L2nkeR
Сообщений: 115
Оценки: 0
Присоединился: 2009-02-02 04:03:17.786666
|
Тут нужно работать с полярной системой, а именно: с неким случаем спирали Архимеда. Главная задача: найти динамику возростания расстояния от точки к центру. Длину дуги можно проинтегрировать и найти пройденный путь точкой.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 18:25:35.296666
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
quote:
ORIGINAL: L2nkeR
Тут нужно работать с полярной системой, а именно: с неким случаем спирали Архимеда. Главная задача: найти динамику возростания расстояния от точки к центру. Длину дуги можно проинтегрировать и найти пройденный путь точкой.
Честно, у меня на это знаний не хватит. Какую длину дуги интегрировать? И как ее интегрировать? В школьном курсе такое особо не проходиться. Если можно, то поподробнее пожалуйста.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 18:47:35.210000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
Вот нашел еще одну очень похожую на мою задачу. Может она для восприятия легче будет
В вершинах равностороннего треугольника со стороной 200 метров сидит по собаке. По команде "старт!" каждая из них начинает гнаться за своей соседкой слева со скоростью 200 метров в минуту. Каждая собака бежит точно в направлении текущего положения своей (тоже, разумеется, бегущей) цели. Поэтому их траектории представляют некие сходящиеся спирали. Через какое время все собаки сойдутся, (вернее, сбегутся) в центре? (вариант популярной задачи)
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 19:45:44.463333
|
|
|
OCTAGRAM
Сообщений: 20
Оценки: 0
Присоединился: 2006-05-04 15:40:00
|
Тут есть круговая симметрия (или циркулярная), и движение эту симметрию не нарушает. Таким образом, в любой момент система будет выглядеть как равноудалённые точки на окружности. Из этого факта следует, что точки всегда движутся под одинаковым углом к радиус–вектору. А это значит, что точки движутся по логарифмической спирали.
Логарифмическая спираль точно в центр не сходится, однако, её длина конечна.
Теперь формулы:
Угол между вектором скорости и радиус–вектором: φ = 90° - 180°/N
Длина траектории точки R / cos φ, где R — изначальное расстояние до центра.
R = D / 2cos φ.
Если я нигде не накосячил, получается
l = D / 2cos² (90° - 180°/N) = D / 2sin² (180°/N)
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-17 20:22:19.126666
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
quote:
ORIGINAL: OCTAGRAM
Тут есть круговая симметрия (или циркулярная), и движение эту симметрию не нарушает. Таким образом, в любой момент система будет выглядеть как равноудалённые точки на окружности. Из этого факта следует, что точки всегда движутся под одинаковым углом к радиус–вектору. А это значит, что точки движутся по логарифмической спирали.
Логарифмическая спираль точно в центр не сходится, однако, её длина конечна.
Теперь формулы:
Угол между вектором скорости и радиус–вектором: φ = 90° - 180°/N
Длина траектории точки R / cos φ, где R — изначальное расстояние до центра.
R = D / 2cos φ.
Если я нигде не накосячил, получается
l = D / 2cos² (90° - 180°/N) = D / 2sin² (180°/N)
Ну ты крут). Это +2 однозначно, если сам это вывел и сам пришел к тому, что это логарифмическая кривая!
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-18 13:07:14.996666
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Эта задача, если мне не изменяет памяти решается без формул вообще. Лишь здравый смысл. Надо представить себя блохой сидящей на одной из собак, и посмотреть на собаку догоняющую. Та будет двигаться перпендикулярно нашему движению, то есть скорость приближения той собаки будет равна ровно 200м/мин (скорость нашей собаки не влияет не это). Значит, если исходное расстояние было равно 200м, то нужна минута, чтобы собаки сошлись в центре.
Задача же открывающая топик не совсем ясна. Если известна скорость собаки, то пройденное расстояние считается как произведение скорости на время.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-18 14:23:51.420000
|
|
|
jeka5555
Сообщений: 18
Оценки: 0
Присоединился: 2009-03-10 08:43:28.223333
|
В задаче открывающей топик скорость, как таковая, вообще не имеет значения, так как при равных скоростях всех точек, расстояние пройденное до места где они встретятся, будет всегда одинаковое, не зависимо от значения скорости.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-18 14:51:02.010000
|
|
|
gotoxardas
Сообщений: 842
Оценки: 0
Присоединился: 2007-05-25 08:15:21.840000
|
quote:
ORIGINAL: rgo
Эта задача, если мне не изменяет памяти решается без формул вообще. Лишь здравый смысл. Надо представить себя блохой сидящей на одной из собак, и посмотреть на собаку догоняющую. Та будет двигаться перпендикулярно нашему движению, то есть скорость приближения той собаки будет равна ровно 200м/мин (скорость нашей собаки не влияет не это). Значит, если исходное расстояние было равно 200м, то нужна минута, чтобы собаки сошлись в центре.
Задача же открывающая топик не совсем ясна. Если известна скорость собаки, то пройденное расстояние считается как произведение скорости на время.
Это было бы так, если бы первая собака "на который сидит блоха" не двигалась. Реальная скорость второй собаки относительно блохи = 200+200*cos60=300 ( так как треугольник равносторонний). И того они встретятся через 200/300 минуты, то есть через 40 секунд.
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-18 18:21:20.470000
|
|
|
Таксист
Сообщений: 68
Оценки: 0
Присоединился: 2009-03-13 09:11:37.530000
|
quote:
Это было бы так, если бы первая собака "на который сидит блоха" не двигалась. Реальная скорость второй собаки относительно блохи = 200+200*cos60=300 ( так как треугольник равносторонний). И того они встретятся через 200/300 минуты, то есть через 40 секунд.
Задача действительно старая…
Есть и собаки, коты и жуки!
Если собаки четыре
В любой момент времени собаки находятся в вершинах квадрата который сжимается и поворачивается по мере сближения. Из этого следует что путь собаки всегда перпендикулярен пути преследуемой. Это говорит нам о том что собака нагонит другую за тот же промежуток времени - как если бы она стояла на месте.
Следует - длинна спирали равна стороне квадрата и т.д.
:D4 собакам нужна 1 минута , трем 2/3 минуты двум 1/2 а одной?
p.s. В варианте с тремя собаками путь собаки равен 2/3 стороны треугольника, cos 60 гр. 1/2
|
|
|
|
|
RE: Алгоритм. Движение по окружности - 2009-03-19 08:45:41.380000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
ORIGINAL: gotoxardas
Это было бы так, если бы первая собака "на который сидит блоха" не двигалась. Реальная скорость второй собаки относительно блохи = 200+200*cos60=300 ( так как треугольник равносторонний). И того они встретятся через 200/300 минуты, то есть через 40 секунд.
А, ну да. Про то что собаки три я пропустил. Видел раньше эту задачу для четырёх собак. Ну собственно не сильно-то и сложнее ;)
|
|
|
|
|
|
