задача

[juan_gandhi]

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

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

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

Comments

[malaya-zemlya.livejournal.com]

Я, наверное, туплю - но неодновременная высадка как помогает? Если программы у роботов одинаковы, то они будут ходить с отставанием на dT шагов. Если расстояние между ними больше 2*dT, то как же им встретиться?

(Я предполагаю, что роботы не знают, кто из них высадился первым, а кто вторым. Иначе совсем неинтересно.)

[spamsink.livejournal.com]

Роботы будут менять направление движения не одновременно.

[malaya-zemlya.livejournal.com]

Они будут менять направление движения с задержкой dT. Как это помогает?

Мне кажется, что расстояние между ними может измениться максимум на 2*dT относительно исходного. Что я не понимаю?

[spamsink.livejournal.com]

Где-то сказано, что у них скорость постоянна?

[malaya-zemlya.livejournal.com]

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

[spamsink.livejournal.com]

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

[malaya-zemlya.livejournal.com]

1 :)

[malaya-zemlya.livejournal.com]

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