задача

[juan_gandhi]

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

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

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

Comments

Re: Робот №88

[furia-krucha.livejournal.com]

Задача 2: Линейный список, возможно замкнутый на себя. Как узнать, замкнут он на себя, или имеет конец?
Надо пустить по списку два бегунка, один из которых движется в два раза быстрее второго. Если список замкнут (даже не обязательно в кольцо, можно "с хвостиком") --- бегунки рано или поздно встретятся. Нечто вроде

(defun cyclic-p (list)
    (let ((slow list)
	  (fast (cdr list))
	  (odd nil))
      (while (not (eq fast slow))
        (set 'fast (cdr fast))
        (if odd (set 'slow (cdr slow)))
        (set 'odd (not odd)))
      slow))