задача

[juan_gandhi]

На прямую высаживаются два робота с идентичной программой. Свои координаты они не знают. Как их запрограммировать так, чтобы они обязятельно встретились?

Кто-нибудь знает эту задачу? Или её решение? Мое решение было такое - случайные блуждания. Но мой коллега, malaya_zemlya, заметил, что совершенно неочевидно, что роботы имеют доступ к датчику случайных чисел, а внутренний генератор... ну вы поняли, он их синхронизирует.

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

Comments

[ded-maxim.livejournal.com]

А сообщения они друг другу посылать могут?

[cmm.livejournal.com]

пущай ходят туда-сюда с увеличивающейся раз от раза амплитудой, и пущай у первого робота амплитуда растёт быстрее чем у второго.

или я чего недопонял?

[luzhin.livejournal.com]

Или метки, скажем, на прямой оставлять.
Как мальчик-с-пальчик.

[spamsink.livejournal.com]

Случайные блуждания не гарантируют обязательности. Эту задачу я видел на форуме головоломок http://wu.webhop.org/ но уже не помню, как она называлась.

[nine_k]

+1

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

[cmm.livejournal.com]

> или я чего недопонял?

про идентичную программу, ага...

[spamsink.livejournal.com]

Они знают, кто из них первый, кто второй?

[spamsink.livejournal.com]

У задачи есть существенное дополнение. На месте высадки роботы оставляют парашют. Тогда никаких случайных чисел не надо, а решение довольно прямолинейно, пардон за каламбур.

[goshen.livejournal.com]

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

[ex-ex-zhuzh.livejournal.com]

именно-именно. если нет никаких меток, они так и будут всегда на одном и том же расстоянии друг от друга.

[ex-ex-zhuzh.livejournal.com]

по условию они идентичны.

[goshen.livejournal.com]

а, идентичной... у них имеется хоть какое-нибудь устройство ввода?

[ded-maxim.livejournal.com]

У них одинаковые программы. Но это решение работает, если роботы могут посылать друг другу сообщения и договориться, кто будет стоять на месте, а кто бродить влево-вправо.

[ded-maxim.livejournal.com]

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

[goshen.livejournal.com]

ну выше уже сказали про парашюты - фактически это сообщение.

[nine_k]

Засчёт чего именно не предполагает?

Можно привязаться ко времени высадки, если она не одновременна.

[selfmade.livejournal.com]

Так что, парашут-то остаётся, или они в потьмах бродят?

[ded-maxim.livejournal.com]

Даже если высадка не одновременна. Надо полагать, у роботов есть всякие устройства ввода/вывода, и выполняемая в данный момент строка может зависеть от сигналов на этих устройствах. В комментариях уже упомянули парашюты, например, которые роботы могут увидеть.

[nine_k]

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

Есть есть ввод-вывод, то всё тривиально, и решений масса (даже с ограниченным расстоянием зрения).

[ygam.livejournal.com]

Я знаю эту задачу.

[arkanoid.livejournal.com]

Очевидно что задача решается если по условию они высаживаются не строго одновременно.

[goshen.livejournal.com]

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

[goshen.livejournal.com]

особенно если у них нет ограничений на скорость.

[itman.livejournal.com]

Эта задача имеет несколько вариаций. Все зависит от того, какие ограничения на программу, и скорость передвижения.

[ivan-gandhi.livejournal.com]

Ну, с парашютом это полная фигня а не задача.