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

[klem4]

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

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

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

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



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

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

[Lapp]

Приятная задачка. как раз для программерских мозгов .
У меня есть несколько вопросов.. Думаю, их нет смысла прятать.
Не совсем ясно, что умеет робот. Ясно, например что он должен уметь двигаться на определенное расстояние, иначе задача не очень осмыслена. Наверняка он может менять направление на противоположное. А вот может ли он, скажем, измерить пройденное расстояние, а затем произвести с ним математические действия (умножить/поделить на 2, например). Может он запомнить, что уже нашел один парашют и отличить другой найденный от первого? Может он запомнить, где был парашют и вернуться к нему? И еще один очень важный вопрос: могут два парашюта лежать в одной точке? Если да, то может ли робот распознать такую ситуацию? Может он хотя бы запомнить, что уже нашел один парашют? В зависимости от ответов на эти вопросы алгоритм может меняться..

Два возможных алгоритма (Показать/Скрыть)

Оба решения ниже преполагают, что парашюты лежат в разных точках.

Самое простое, но требующее максимум функциональности от роботов, мне кажется, такое: посредством колебаний с увеличивающейся амплитудой найти оба парашюта, затем вычислить среднюю точку между ними, пойти в нее, остановиться там и ждать.

Теперь решение, не требующее запоминания положений парашютов иои вычисления расстояний.
Начало то же: делаем колебания с увеличивающиейся амплитудой вокруг начальной точки (может быть любой. На каждом развороте сьрасываем память о найденных парашютах. Дожидаемся ситуации, когда на одном проходе найдены ОБА парашюта. У второго разворачиваемся и далее осциллируем между парашютами. Все.

Добавлено через 5 мин.

Решение, требующее минимум предположений (как мне кажется)) (Показать/Скрыть)

Еще одно решение, не требующее памяти о том, что один парашют найден.
Начинаем колебания с убеличивающейся амплитудой. Всякий раз, когда находим парашют, начинаем этот процесс сначала, с некоторой начальной амплитуды. Все.

Добавлено через 6 мин.
Unconnected, так не пойдет )).

Опровергающий пример (Показать/Скрыть)

Все на числовой оси.
Парашют 1 в -2
парашют 2 в 2
робот 1 в -1
робот 2 в 2
робот 1 идет влево, проходит свой парашют, разворачивается, снова доходит до своего парашюта и останавливается на нем.
робот 2 идет вправо, проходит свой парашют, разворачивается, снова доходит до своего парашюта и останавливается на нем.
И они никогда не встретят друг друга..

Добавлено через 8 мин.
Я очень извиняюсь, спутал ники . Видел ник Rathar'а в теме, ну и автоматически распространил его на сообщение..
Исправлено. Извините, буду внимательнее )).