Форум «Всё о Паскале» _ Свободное общение _ Задача о двух роботах.
Автор: klem4 2.02.2010 1:35
Всем привет. Коллега рассказал одну задачу, которую ему задали на одном из собеседований, мне она очень понравилась. Возможно многие ее знают, тем не менее выкладываю условие:
Имеем одномерную планету. Над ней летит самолет, десантирует сначала первого робота, затем второго. Роботы ничего не знают ни друг о друге ни о самолете (в какую сторону летел, кого сбросил первым, на каком расстоянии, в общем ничего). Робот может двигаться вправо или влево (назад и вперед то есть), при этом он может оценить что находится в той точке, на которую он встал, а это может быть 1) просто земля 2) парашют (свой от чужого не отличает) 3) другой робот
Задача: написать алгоритм перемещения (который будет применен к обоим роботам одновременно после высадки последнего) робота, таким образом, чтобы они встретились со 100% вероятностью.
Я задачу решил, если понадобится выложу ответ. Задача легкая, но по мне очень забавная. Удачи.
Решения просьба оформлять в спойлер.
Автор: Unconnected 2.02.2010 2:09
Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны? Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят. И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?)
Автор: klem4 2.02.2010 2:20
Цитата
Интересно. А "одномерная планета" - границы, начала координат имеются или она бесконечная во все стороны?
Бесконечная прямая.
Цитата
Самолёт, я так понял, сбросил их на одной "линии", раз они только вперёд-назад ходят.
Именно так.
Цитата
И ещё вопрос, вот когда робот только приземлился, это считается за событие, что он наступил на парашют?)
Пожалуй нет. Не знаю. Это не существенно . Алгоритм (одинаковый у обоих) включается как только приземлится второй из них.
Автор: Unconnected 2.02.2010 2:38
Я придумал) Может, немного извращенно, но всё же:
Жди меня(Показать/Скрыть)
Итак, первый робот дождался, пока приземлится второй, и начинается.. Роботы должны начинать ходить от места приземления вперёд-назад, с каждым разом проходя на один шаг больше. Например, так: шаг вперёд - два назад - три вперёд - четыре назад - пять вперёд - и так далее. Самое интересное - роботы должны считать, сколько раз они наступят на парашют (опять же, неважно, какой). И если робот двигается например вперёд и наступает на парашют второй раз - он должен остановиться и ждать с моря погоды. Второй должен с ним встретиться, на обратном пути)
Автор: Lapp 2.02.2010 3:09
Приятная задачка. как раз для программерских мозгов . У меня есть несколько вопросов.. Думаю, их нет смысла прятать. Не совсем ясно, что умеет робот. Ясно, например что он должен уметь двигаться на определенное расстояние, иначе задача не очень осмыслена. Наверняка он может менять направление на противоположное. А вот может ли он, скажем, измерить пройденное расстояние, а затем произвести с ним математические действия (умножить/поделить на 2, например). Может он запомнить, что уже нашел один парашют и отличить другой найденный от первого? Может он запомнить, где был парашют и вернуться к нему? И еще один очень важный вопрос: могут два парашюта лежать в одной точке? Если да, то может ли робот распознать такую ситуацию? Может он хотя бы запомнить, что уже нашел один парашют? В зависимости от ответов на эти вопросы алгоритм может меняться..
Два возможных алгоритма(Показать/Скрыть)
Оба решения ниже преполагают, что парашюты лежат в разных точках.
Самое простое, но требующее максимум функциональности от роботов, мне кажется, такое: посредством колебаний с увеличивающейся амплитудой найти оба парашюта, затем вычислить среднюю точку между ними, пойти в нее, остановиться там и ждать.
Теперь решение, не требующее запоминания положений парашютов иои вычисления расстояний. Начало то же: делаем колебания с увеличивающиейся амплитудой вокруг начальной точки (может быть любой. На каждом развороте сьрасываем память о найденных парашютах. Дожидаемся ситуации, когда на одном проходе найдены ОБА парашюта. У второго разворачиваемся и далее осциллируем между парашютами. Все.
Добавлено через 5 мин.
Решение, требующее минимум предположений (как мне кажется))(Показать/Скрыть)
Еще одно решение, не требующее памяти о том, что один парашют найден. Начинаем колебания с убеличивающейся амплитудой. Всякий раз, когда находим парашют, начинаем этот процесс сначала, с некоторой начальной амплитуды. Все.
Добавлено через 6 мин. Unconnected, так не пойдет )).
Опровергающий пример(Показать/Скрыть)
Все на числовой оси. Парашют 1 в -2 парашют 2 в 2 робот 1 в -1 робот 2 в 2 робот 1 идет влево, проходит свой парашют, разворачивается, снова доходит до своего парашюта и останавливается на нем. робот 2 идет вправо, проходит свой парашют, разворачивается, снова доходит до своего парашюта и останавливается на нем. И они никогда не встретят друг друга..
Добавлено через 8 мин. Я очень извиняюсь, спутал ники . Видел ник Rathar'а в теме, ну и автоматически распространил его на сообщение.. Исправлено. Извините, буду внимательнее )).
Автор: Unconnected 2.02.2010 3:30
Пойдёт-пойдёт(Показать/Скрыть)
Я, наверное, недостаточно подробно описал решение:) Когда робот поворачивается, то счётчик "нахождений парашюта" у него обнуляется)
Автор: Lapp 2.02.2010 3:37
Ответ на Пойдёт-пойдёт(Показать/Скрыть)
Цитата
Я, наверное, недостаточно подробно описал решение:) Когда робот поворачивается, то счётчик "нахождений парашюта" у него обнуляется)
Оставил инициализацию за циклом? Все, программа нерабочая )). Исправленная - да, наверное "пойдет-пойдет" )) Впрочем, подождем Клему, я тут не судья..
Автор: -Unconnected- 2.02.2010 14:00
Не исправленная, а дополненная
Автор: SKVOZNJAK 2.02.2010 21:00
Запутанное условие, только сейчас дошло что планета не абсолютно круглый шар. Опять же возможности роботов не известны, предположу что это всё таки роботы а не тачка с камнями на вечном двигателе.
Спойлер(Показать/Скрыть)
Значит планета кольцо. В задаче ничего не сказано о незнании робота о самом себе. Каждый робот пишет на своём парашюте свой номер и начальное направление движения. Находя чужой парашют пишет под чужим номером свой. Тот у которого номер меньше увидев на парашюте больший номер, останавливается. Обладатель большего номера, напротив, идёт навстречу другому роботу.
Автор: SKVOZNJAK 2.02.2010 21:26
ыыыы
Автор: TarasBer 2.02.2010 22:52
Спойлер(Показать/Скрыть)
Робот ходит вокруг точки приземления туда-сюда, наращивая амплитуду. Встретив другого робота или встретив два парашюта, не разделённых сменой направления, остановиться.
Автор: Lapp 3.02.2010 8:22
Цитата(-Unconnected- @ 2.02.2010 10:00)
Не исправленная, а дополненная
Ага. Напиши универсальную программу:
begin end.
- и дополняй ее.. А можно еще и всех в плагиате обвинить: взяли твой код и дополнили! И ведь даже изменить не попытались, наглые такие ))
Автор: klem4 4.02.2010 0:55
Решение 1.
Спойлер(Показать/Скрыть)
Каждому из них на пути следования встретится мужик с гаечным ключом и они встретятся на местном радио рынке.
Решение 2.
Спойлер(Показать/Скрыть)
Практически все предложили верные или почти верные решения. Робот ходит назад вперед, наращивая амплитуду и считает сколько парашютов встретил на пути следования в торону X(назад или вперед), если он встретил 2 парашюта, то далее продолжает движение только в ту сторону, в которую шел(второй же так как шел в туже сторону что и первый, скоро развернется и пойдет ему на встречу).
Задача #2 на подходе.
Автор: Lapp 4.02.2010 3:01
Цитата(klem4 @ 3.02.2010 20:55)
мужик с гаечным ключом и они встретятся на местном радио рынке.
Одномерный ключ на 12? Мужик будет о двадцати семи пальцах с одиннадцатью суставами каждый, растущими из шеи.. Но тоже одномерный!
Цитата
Робот ... считает сколько парашютов
Есть решение, не требующее подсчета парашютов! см. пост #5.
Цитата
Задача #2 на подходе.
Ждем с нетерпением!
klem4 +1
Автор: Unconnected 4.02.2010 3:45
Цитата
Решение, требующее минимум предположений (как мне кажется))(Показать/Скрыть)
Решение, требующее минимум предположений (как мне кажется)) (Показать/Скрыть) Еще одно решение, не требующее памяти о том, что один парашют найден. Начинаем колебания с убеличивающейся амплитудой. Всякий раз, когда находим парашют, начинаем этот процесс сначала, с некоторой начальной амплитуды. Все.
Lapp, так не пойдёт ))
Робот делает шаг вперёд, потом шаг назад, находит парашют и опять сначала, делает шаг вперёд... Если, конечно, под "начальной амплитудой" подразумевалась постоянная величина.
Да-да, klem4, спасибо, может, теперь на работу возьмут..))
Автор: Lapp 4.02.2010 4:05
Цитата(Unconnected @ 3.02.2010 23:45)
Lapp, так не пойдёт ))
Робот делает шаг вперёд, потом шаг назад, находит парашют и опять сначала, делает шаг вперёд... Если, конечно, под "начальной амплитудой" подразумевалась постоянная величина.
робот помнит последний найденный парашют (то есть место, где он найден) и игнорирует его. Я согласен, это некая фича, которая может быть не реализована в его прошивке.. Я не знаю, что лучше: считать парашюты или помнить, где нашел)).
Добавлено через 17 мин. Собственно, это практически эквивалентно подсчету. Признаю )).
Автор: klem4 5.02.2010 0:03
Спойлер(Показать/Скрыть)
Цитата
Всякий раз, когда находим парашют, начинаем этот процесс сначала, с некоторой начальной амплитуды. Все.
а зацикливания на первом парашюте не будет ?
Автор: Unconnected 5.02.2010 2:01
Спойлер(Показать/Скрыть)
Будет, читай на три поста выше:)
Автор: SKVOZNJAK 6.02.2010 8:42
klem4, со вторым твоим решеним не всё ясно. В задании говорится о 100% вероятности встречи, но если они высадятся на кольце симметрично в нужное время, то и действовать станут симметрично - могут и не встретиться.
Автор: Unconnected 6.02.2010 16:33
Кольца нет, есть
Цитата
Бесконечная прямая.
Автор: SKVOZNJAK 6.02.2010 22:50
А в кольце прямая разве имеет конец? К тому же бесконечно огромная в длину планета называется галактикой, вселенной, туннелем, свёрнутым измерением но никак не планетой. Опять тест на "угадай мою логику".