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

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

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

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



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

Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны? Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят. И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?)

Бесконечная прямая.



Именно так.



Пожалуй нет. Не знаю. Это не существенно . Алгоритм (одинаковый у обоих) включается как только приземлится второй из них.

Я придумал) Может, немного извращенно, но всё же:

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



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


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



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

Не исправленная, а дополненная

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

ыыыы

Ага. Напиши универсальную программу:

begin
end.

- и дополняй ее.. А можно еще и всех в плагиате обвинить: взяли твой код и дополнили! И ведь даже изменить не попытались, наглые такие ))

Решение 1.



Решение 2.


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

Одномерный ключ на 12? Мужик будет о двадцати семи пальцах с одиннадцатью суставами каждый, растущими из шеи.. Но тоже одномерный!

Есть решение, не требующее подсчета парашютов! см. пост #5.

Ждем с нетерпением!

klem4 +1

Lapp, так не пойдёт ))

Робот делает шаг вперёд, потом шаг назад, находит парашют и опять сначала, делает шаг вперёд... Если, конечно, под "начальной амплитудой" подразумевалась постоянная величина.

Да-да, klem4, спасибо, может, теперь на работу возьмут..))

робот помнит последний найденный парашют (то есть место, где он найден) и игнорирует его. Я согласен, это некая фича, которая может быть не реализована в его прошивке..
Я не знаю, что лучше: считать парашюты или помнить, где нашел)).

Добавлено через 17 мин.
Собственно, это практически эквивалентно подсчету. Признаю )).

klem4, со вторым твоим решеним не всё ясно. В задании говорится о 100% вероятности встречи, но если они высадятся на кольце симметрично в нужное время, то и действовать станут симметрично - могут и не встретиться.

Кольца нет, есть

А в кольце прямая разве имеет конец? К тому же бесконечно огромная в длину планета называется галактикой, вселенной, туннелем, свёрнутым измерением но никак не планетой. Опять тест на "угадай мою логику".

SKVOZNJAK, не придирайся))