задача

[juan_gandhi]

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

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

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

Comments

[itman.livejournal.com]

Как раз с парашютом только и можно решить эту задачу, но при определенных условиях. Представьте себе, что у Вас ограниченный язык, в котором
каждая команда выглядит как:
ШАГ ВЛЕВО (повторить если нет парашюта)
ШАГ ВПРАВО (повторить если нет парашюта)
СМЕНИТЬ НАПРАВЛЕНИЕ (если проскочили парашют)
Насколько я вижу, в данной постановке решения нет. Потому что если первая команда: ШАГ ВЛЕВО, то робот, высадившийся левее, будет всегда идти со скоростью один шаг в так, а второй его никогда не догонит.