Задача о двух роботах. Опции

[klem4]

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

Имеем одномерную планету. Над ней летит самолет, десантирует сначала первого робота, затем второго. Роботы ничего не знают ни друг о друге ни о самолете (в какую сторону летел, кого сбросил первым, на каком расстоянии, в общем ничего). Робот может двигаться вправо или влево (назад и вперед то есть), при этом он может оценить что находится в той точке, на которую он встал, а это может быть
1) просто земля
2) парашют (свой от чужого не отличает)
3) другой робот

Задача: написать алгоритм перемещения (который будет применен к обоим роботам одновременно после высадки последнего) робота, таким образом, чтобы они встретились со 100% вероятностью.

Я задачу решил, если понадобится выложу ответ. Задача легкая, но по мне очень забавная. Удачи.



Решения просьба оформлять в спойлер.

Сообщение отредактировано: klem4 - 2.02.2010 1:37

[klem4]

Решение 1.

Спойлер (Показать/Скрыть)

Каждому из них на пути следования встретится мужик с гаечным ключом и они встретятся на местном радио рынке.

Решение 2.

Спойлер (Показать/Скрыть)

Практически все предложили верные или почти верные решения. Робот ходит назад вперед, наращивая амплитуду и считает сколько парашютов встретил на пути следования в торону X(назад или вперед), если он встретил 2 парашюта, то далее продолжает движение только в ту сторону, в которую шел(второй же так как шел в туже сторону что и первый, скоро развернется и пойдет ему на встречу).

Задача #2 на подходе.