задача

[juan_gandhi]

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

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

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

Comments

[ex-ex-zhuzh.livejournal.com]

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

[ded-maxim.livejournal.com]

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

[nine_k]

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

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

[ded-maxim.livejournal.com]

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

[nine_k]

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

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

[goshen.livejournal.com]

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

[goshen.livejournal.com]

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