На одномерную бесконечную ленту десантируют роботов. Лента поделена на ячейки. Требуется запрограммировать роботов так, чтобы они однажды собрались все вместе (в одной ячейке).
Каждый робот после посадки оставляет в месте приземления парашют.
Далее роботы начинают действовать в соответствии с заложенной в них программой. За один шаг программы робот может проверить, есть ли в его ячейке какой-нибудь парашют (но не может проверить, есть ли в ячейке другой робот!), и может при желании сдвинуться влево или вправо на одну ячейку. Программы всех роботов выполняются с одинаковой скоростью.
Количество роботов неизвестно. Но это количество — конечное число.
После того, как роботы соберутся вместе, не обязательно, чтобы они оставались в этом положении или остановились. Достаточно лишь, чтобы за конечное число шагов гарантированно наступила ситуация, когда все роботы находятся в одной и той же ячейке ленты.
Каждый робот после посадки оставляет в месте приземления парашют.
Далее роботы начинают действовать в соответствии с заложенной в них программой. За один шаг программы робот может проверить, есть ли в его ячейке какой-нибудь парашют (но не может проверить, есть ли в ячейке другой робот!), и может при желании сдвинуться влево или вправо на одну ячейку. Программы всех роботов выполняются с одинаковой скоростью.
Количество роботов неизвестно. Но это количество — конечное число.
После того, как роботы соберутся вместе, не обязательно, чтобы они оставались в этом положении или остановились. Достаточно лишь, чтобы за конечное число шагов гарантированно наступила ситуация, когда все роботы находятся в одной и той же ячейке ленты.
8 комментариев:
Не совсем понял задачу. Сколько роботов может поместить в ячейке? Что значит не может проверить есть ли робот в другой ячейке, но может проверить есть ли парашют? Каковы условия передвижения роботов: если ячейка занята парашютом или другим роботом, может ли робот туда переместиться? Что в итоге требуется получить?
@Nodir:
роботы не мешают друг другу, т.е. их может быть в одной ячейке сколько угодно. Парашют так же не создаёт преград - парашют является меткой. Требуется получить программу для роботов, которая заставит их собраться всем когда-нибудь в одном месте.
- То есть я правильно понимаю, что роботы способны отличить парашют от парашюта? Ну то есть по парашюту можно определить, был ли уже робот в этой ячейке или нет.
- Если робот не может проверить существует ли другой робот в соседней ячейке, то может ли он проверить, есть ли он в той же, что и он?
- Лента является подвижной? То есть если робот подпрыгнет на месте, по приземлению он окажется в другой ячейке?
- Может ли робот двигаться по диагонали?
1. Знают ли роботы о своём количестве "в рантайме"?
2. Можно ли разных роботов запрограммировать по-разному?
3. Можно ли, программируя роботов, научить их отличать одно направление ленты от другого (т. е., для определённости, чтобы они одно направление одинаково считали направлением "вперёд", а другое -- "назад")?
4. Может ли в одной ячейче находиться более одного парашюта? Т. е. возможна ли Бозе-конденсация парашютов в одном квантовом состоянии?
5. Может ли робот при своём перемещении из ячейки с парашютами захватить все парашюты с собой (т. е. снять булевский флаг "в ячейке есть парашюты"?
Некоторый уточнения данные по GTalk:
me: привет! :)
Vladimir: салют
me: я там еще комментарий написал, как то условия все равно не очевидны хотел попробовать решить задачку в рамках изучения OCaml, Сорри, что пристаю с уточнениями
Vladimir: ага, доступ к гмылу меня только из дома
- у робота есть память (сколько хочешь под какие хочешь структуры)
лента не движется т.е робот сам принимает решение куда двигаться
что значит "по-диагонали" если одномерная лента?
соо-но он может определить если ли парашют в ячейке или нет
me: ааа, то есть робот может двинуться либо вправо либо влево
я то думал, что система двухмерная
Vladimir: На одномерную бесконечную ленту десантируют роботов.
me: лента широкая и поделена на ячеки как шахматная доска
Vladimir: широкая, но 1-мерная
me: точно, надо читать внимательнее
Vladimir: может при желании сдвинуться влево или вправо на одну ячейку. Программы всех роботов выполняются с одинаковой скоростью.
me: а парашют от парашюта отличить может?
Vladimir: т.е ?
me: ну то есть: свой, чужой, уже видел
Vladimir: ну если есть память
me: ну чтобы использовать парашюты как метки, что уже был в ячейке
Vladimir: он может считать свою позицию относительно своего места посадки
me: все, точно, все таки видимо я уже окончательно испорчен embedded developing-ом, когда каждый байт считать надо :)
Vladimir: :)))))))))))))))))))))
я же сказу сказал - память есть сколько угодно и под какие угодно структуры
После того, как роботы соберутся вместе, не обязательно, чтобы они оставались в этом положении или остановились. Достаточно лишь, чтобы за конечное число шагов гарантированно наступила ситуация, когда все роботы находятся в одной и той же ячейке ленты.
me: угу, но жучок то в голове уже сидит (Оптимизация использования памяти!!!)
Vladimir: :)) я понимаю
Никто не решил эту задачу?
Должен остаться только один. Все роботы как роботы, а один терминатор. Он двигается по расширяющейся амплитуде и убивает всех встречных роботов и пожирает их. Предварительно хачит все их коды доступов, пароли и явки, чтобы если чё, можно было сойти за сожранного(вспоминаем тематичные игры/фильмы). Попутно запоминает сколько сожрал, сколько парашютов видел. Вот как то так. Когда сожрёт всех - взламывает систему и вызывает спасательный шатл в котором отправляется на землю за добавкой.
Отправить комментарий