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

[klem4]

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

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

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

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



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

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

[Unconnected]

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

[klem4]

Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны?

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

Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят.

Именно так.

И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?)

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

[Unconnected]

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

Жди меня (Показать/Скрыть)

Итак, первый робот дождался, пока приземлится второй, и начинается.. Роботы должны начинать ходить от места приземления вперёд-назад, с каждым разом проходя на один шаг больше. Например, так: шаг вперёд - два назад - три вперёд - четыре назад - пять вперёд - и так далее. Самое интересное - роботы должны считать, сколько раз они наступят на парашют (опять же, неважно, какой). И если робот двигается например вперёд и наступает на парашют второй раз - он должен остановиться и ждать с моря погоды. Второй должен с ним встретиться, на обратном пути)

Сообщение отредактировано: Unconnected - 2.02.2010 2:48

[Lapp]

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

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

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

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

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

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

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

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

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

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

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

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

[Unconnected]

Пойдёт-пойдёт (Показать/Скрыть)

Я, наверное, недостаточно подробно описал решение:) Когда робот поворачивается, то счётчик "нахождений парашюта" у него обнуляется)

[Lapp]

Ответ на Пойдёт-пойдёт (Показать/Скрыть)

Я, наверное, недостаточно подробно описал решение:) Когда робот поворачивается, то счётчик "нахождений парашюта" у него обнуляется)

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

[-Unconnected-]

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

[SKVOZNJAK]

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

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

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

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

[SKVOZNJAK]

ыыыы

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

[TarasBer]

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

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

[Lapp]

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

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

begin
end.

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

[klem4]

Решение 1.

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

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

Решение 2.

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

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

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

[Lapp]

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

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

Робот ... считает сколько парашютов

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

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

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

klem4 +1

[Unconnected]

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

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

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

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

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

Сообщение отредактировано: Unconnected - 4.02.2010 3:53

[Lapp]

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

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

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

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

[klem4]

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

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

а зацикливания на первом парашюте не будет ?

[Unconnected]

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

Будет, читай на три поста выше:)

[SKVOZNJAK]

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

[Unconnected]

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

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