Непростая задачка... кому интересно...

← →
MeamoryLeak (2002-08-06 14:08) [0]

Дана окружность разбитая N точками(находящиеся на дуге окружности) на равные части..
K точек c разными номерами убрали.
Двигать каждую и зоставшихся точек по направлению часовой стрелки со скоростью из интервала от Vmin до Vmax, пока окружность снова не будет разбита на равные части.
Определить скорость каждой точки, при которой время движения будует минимальной... Вывести скорости для кадой точки, с которыми они должны двигаться и время, за которе произойдёт перемещение.
на входе файл : первая строка: N K <длина окр> Vmin Vmax [N - колво точек K -количество удалённых] вторая строка: K чисел - номера точек, удаленных

Все данные отсортированы по возрастанию.

← →
MBo (2002-08-06 14:19) [1]

Задачка как раз простая, и очень смахивает на домашнее задание.

← →
Ev_genus (2002-08-06 14:20) [2]

Возмём любые оставшиеся две точки 1 и 2. Понятно из оставшихся точек будет неподвижной(либо двигатся со скоростью Vmin, если Vmin >0). точка 2 - предыдущая(против часовой стрелки), по отношению к 1. Общее время движеня будет минимальным если будет максимальной общая скорость движения. Введём понятия общего пути, как сумму путей которые нужно пройти точкам. Тогда общая скорость = сумме скоростей. Ответ каждая точка движется со скоростью Vmax пока не дойдёт до нужного места. Потом остановится (либо будет двигатся со скоростью Vmin, если Vmin >0). Стоячая точка выбирается по принципу: если расстояние между 2 и 1 > длинны окр / k, а между 1 и k < то 1 - стоячая точка. Понятно почему такая найдётся.

Может я и неправильно понял. Объясните подробнее.

← →
MeamoryLeak (2002-08-06 14:35) [3]

>Ev_genus все точки двигаются по часой стрелке... точек N, к примеру 120, окружность поделена на 120 равных частей, удалили точки со разными порядковыми номерами 40 штук. Оставшиеся 80 нужно распеделить за минимальный отрезок времени, увеличивая/уменьшая скорость каждой точки в интервале от Vmin до Vmax.

>MBo а решение не такое уж и простое в итоге!

← →
MBo (2002-08-06 14:42) [4]

> а решение не такое уж и простое
согласен, поспешил

← →
MeamoryLeak (2002-08-06 14:51) [5]

>Ev_genus скорость в процессе движения должна быть постоянная..никаких...остановиться...подождать..

← →
iZEN (2002-08-06 15:22) [6]

Навскидку:

Скорость каждой из оставшихся точек:
Vi=(i-1)*(L/(N-K)-L/N)/t,
где
i - номер оставшейся точки, которую надо двигать;
L = 2*pi*r - длина окружности;
N - число точек первоначально;
N-K - число оставшихся точек;
t - время движения каждой точки такое, что Vmin < Vm < Vmax,
или:
t=(L/(N-K)-L/N)/Vmin;

также должно соблюдаться условие:
t>=(i-1)*(L/(N-K)-L/N)/Vmax
иначе задача не имеет решения.

← →
MeamoryLeak (2002-08-06 16:02) [7]

>iZEN формулу не проверял, но для первой точки скорость будет 0.
И как эта формула будет работать, если она зависима только от порядкогого номера точки, чем выше номер, тем выше скорость.?.
быть может (i-1) ты имел ввиду номер оставшейся точки(предыдущей/следующей), а не предыдущий порядковый. Ведь в таком случае, для одинаковой длины окружности скорость точек, с одними и теме же порядковыми номерами, меняться не будет. Допустим если в одном случае точка с номером 3 не была удалена, то имеет скорость V3. В следующем случае были удалены другие точки в том же количестве, помимо третьей, но тогда она снова будет иметь туже самую скорость...

← →
ACR (2002-08-06 16:09) [8]

интересно узнать практический смысл приводящий к данной задаче?

← →
MeamoryLeak (2002-08-07 00:53) [9]

Выравнивание центрифуги..

← →
Igorek (2002-08-07 10:00) [10]

2 MeamoryLeak
Так кто-нибудь ее решил? Если да, то даже лень браться.

← →
MeamoryLeak (2002-08-07 10:14) [11]

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

← →
Alx2 (2002-08-07 10:44) [12]

IMHO скорость движения каждой точки должна быть пропорциональной расстоянию от нее до положения ее равновесия.

← →
False_Delirium (2002-08-07 13:47) [13]

Кинул тебе на мыло решение.

← →
Igorek (2002-08-08 10:24) [14]

← →
McSimm (2002-08-08 10:43) [15]

А не могли бы вы помочь мне понять условие задачи?

> Определить скорость каждой точки, при которой время движения
> будует минимальной

ИМХО Vmax. Чем больше скорость, тем меньше время.

> и время, за которе произойдёт перемещение

T(i) = S(i) / Vmax

Я понимаю, что просто недопонял условие. Что я не так понял?

← →
Igorek (2002-08-08 10:53) [16]

Два вопроса на уточнение задачи:
1) для решения необходимо знать радиус искомой окружности, если скорости не радиальные (типа градусов/сек)
2) скорости должны быть постоянны или могут изменяться?

← →
Igorek (2002-08-08 10:55) [17]

Ой не увидел, что длина окружности известна.

← →
Igorek (2002-08-08 14:12) [18]

Разобрался - элементарная минимаксная задача.

Непростая задачка... кому интересно... Найти похожие ветки