задача

[juan_gandhi]

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

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

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

Comments

[malaya-zemlya.livejournal.com]

Нет, конечно. Но если существует максимальная скорость движения, то существует (ИМХО) и ограничение на расстояние (2*v_max*dT), а скорость света роботам вряд ли преодолеть...

[spamsink.livejournal.com]

Гм-м-м... А чему у нас равна скорость света на вещественной прямой? :)

[malaya-zemlya.livejournal.com]

1 :)

[malaya-zemlya.livejournal.com]

Поскольку задача программерская, автор поста - программист, и участвуют в ней роботы, я предположил что прямая не вещественная, а целочисленная. Что-то типа ленты машины Тьюринга, а сами роботы - что-то вроде двух головок машины Тьюринга. Может, я и не прав : )