Поймать кролика

[coceg]

1) Кролик раз в секунду перепрыгивает 16 кочек и остается на 17, либо он каждую 1/17 секунды прыгает на соседнюю?

2) Как могу прыгать я — с какой частотой и через сколько кочек?

[zvulon]

1) секунда номер ноль, кролик в т. 0, через секунду в т. 17
2) в этом и состоит задача

[coceg]

1) Где находится кролик в момент времени t=0.5 с? На нулевой кочке, на промежуточной кочке, или «нигде» (в воздухе)?
2) Т.е. никаких ограничений на мое движение нет?

[zvulon]

1) нигде.
2) вы — физ. объект присутствуете в каждый момент времени лишь в одном месте. можете прыгать, так далеко, как вам хочется.

[MiXei4]

А можно как нибудь подробнее про пункт 3? Как мне может это помочь?

[zvulon]

Вы можете предотвратить ситуацию, что кролик в воздухе, а вы на кочке (или наоборот).

[steck]

А какая скорость у меня?

[zvulon]

это и есть задача. (найти функцию вашего перемещения )

[steck]

Я спрашивал про ограничения скорости.
То есть не больше, чем на столько то клеток.

Без этого ограничения моё решение чуть ниже:
habrahabr.ru/blogs/zadachki/87276/#comment_2612215

[zvulon]

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

[steck]

хм, мы движемся быстрее кролика, на одну клетку. То есть если направление совпадает, то рано или поздно мы его догоним.
Дальше, из-за того что мы довольно резко увеличиаем количество шагов в одну сторону, то они компенсируют и предыдущие шаги (N*S ) и шаги кролика (17*N)
Я правда выбрал довольно маленькое увелечие N ( N = N*N )
Но если взять, скажем, N = N*N*N, то N*N*N>N*S + 17*N и следовательно в тот момент, когда выполнится
N*N*N>N*S + 17*N + D, где D — расстояние от исходной точки до кролика, на этом этапе кролик будет догнан.

[zvulon]

я понимаю вашу логику, но почему-то у меня есть сомнения, тк кролик может проскакивавать между вашими прыжками по 18. ктому же N растет в квадрате (кубе). я даже скрипт написал с вашим алго. но с 1000 влево он не поймал (это конечно же ни чего не доказывает).
Вобщем я опубликовал тн «правильное» решение — взгляните.

[dohlik]

Ну, если мы находимся впереди кролика, то достаточно просто прыгать вперед на (17-1) кочек — так мы постепенно будем с ним сближаться…

[dohlik]

Если позади (т.е. кролик прыгает от нас), то вперед на 17+1

[steck]

вот и алгоритм.

N = 17.
S = 17+1=18
D = 1
while(не пойман){
for( i =0; i < N; i++){
Прыжок на S*D кочек
Осмотр нет ли кролика
}
D = -D
N = N*N
}

[zvulon]

кролик в т. 1000 и движется влево (x_rabbit -= 17) вы вт. 0 удачного поиска.

[zvulon]

вы не знаете с какой стороны от вас кролик.

[zvulon]

Вобщем близко, но это явно не полный ответ.

[MiXei4]

Допустим мы знаем начальную точку кролика K0. Тогда в каждый момент времени t кролик находится либо в K0+17t либо в K0-17t
Теперь перебираем все K0 пока не найдем кролика.
Пусть мы находимся в точке 0. Тогда прыжки будут такие
-1+17 -1-34
1+51 1-68
-2+85 -2-102
2+119 2-136
…
-i+(i*4-3)*17 -i-(i*4-2)*17
i+(i*4-1)*17 i-(i*4)*17
…

i и -i это как раз те K0, которые мы перебираем, а остальное это смещение кролика относительно начальной точки за время наших предыдущих прыжков :)

[zvulon]

Вполне цельное решение.

Ну и объяснение:
изначально кролик находиться от нас на расстоянии x.
и движеться либо вправо d=+1 либо влево d=-1
функция передвижения кролика f_rab(t) = x + t*17*d;

мы просто поддерживаем исходное рассояние от нас для двух случаев
s=
# в право 17*t
# в лево -17*t
и для каждого случая сокращаем исходное расстояние:
# кролик был слева: s — t
# кролик был справа: s + t
таким образом наша функция выглядит следующим образом:
f(t) = switch( t % 4) {
case 0: return 17*t — t
case 1: return 17*t + t
case 2: return -17*t — t
case 3: return -17*t + t
}