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

[klem4]

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

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

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

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



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

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

[SKVOZNJAK]

Запутанное условие, только сейчас дошло что планета не абсолютно круглый шар. Опять же возможности роботов не известны, предположу что это всё таки роботы а не тачка с камнями на вечном двигателе.

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

Значит планета кольцо. В задаче ничего не сказано о незнании робота о самом себе. Каждый робот пишет на своём парашюте свой номер и начальное направление движения. Находя чужой парашют пишет под чужим номером свой. Тот у которого номер меньше увидев на парашюте больший номер, останавливается. Обладатель большего номера, напротив, идёт навстречу другому роботу.

Сообщение отредактировано: SKVOZNJAK - 2.02.2010 17:52