Раз пошла такая пьянка...)

[Disprein]

Вот еще задачка.

На одномерную бесконечную ленту десантируют роботов. Лента поделена на ячейки. Требуется запрограммировать роботов так, чтобы они однажды собрались все вместе (в одной ячейке).

Каждый робот после посадки оставляет в месте приземления парашют.
Далее роботы начинают действовать в соответствии с заложенной в них программой. За один шаг программы робот может проверить, есть ли в его ячейке какой-нибудь парашют (но не может проверить, есть ли в ячейке другой робот!), и может при желании сдвинуться влево или вправо на одну ячейку. Программы всех роботов выполняются с одинаковой скоростью.
Количество роботов неизвестно. Но это количество — конечное число.

После того, как роботы соберутся вместе, не обязательно, чтобы они оставались в этом положении или остановились. Достаточно лишь, чтобы за конечное число шагов гарантированно наступила ситуация, когда все роботы находятся в одной и той же ячейке ленты.

@темы: Головоломки и занимательные задачи

Comments

[=penelopa=]

ого)) пошла рисовать алгоритм))

[KingArthur]

А алгоритм у всех роботов одинаков? Или можно половину по друргому запрограмировать?

[Фабий]

У роботов возможность = только двигаться в одном из двух направлений или стоять на месте? И что будет, если они упрутся один в другого? Остановятся или «протолкнут»?

[Disprein]

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

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

[Amicus Plato]

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

[Amicus Plato]

А если так: пустить их всех в одном направлении: всё равно влево или вправо.
Пусть вправо.
И чем больше парашютов он там встретил, тем быстрее он начинает двигаться, чтобы догнать всех, кто правее него.
Идея такая. До первого парашюта он идет медленнее всего. Нашел первый парашют — пошел чуть быстрее, чтоб догнать того, кто приземлился правее. Нашел еще один — это значит, что он отстает уже от двоих — пошел еще быстрее.
А если ничего не нашел, то он должен ждать всех остальных и идти медленно.
Но, блин, они так могут проскочить друг мимо друга...
И непонятно только какой темп задать с самого начала.....

[Disprein]

Да и приземляться они могут на разных расстояниях друг от друга, так что с ускорением трудно угадать.

[Amicus Plato]

Disprein
А память у них есть?
Можно например завести счетчик с количеством увиденных парашютов?

[Trotil]

А я пока не могу понять, что могут дать в такой ситуации парашюты...

[Amicus Plato]

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

После того, как роботы соберутся вместе, не обязательно, чтобы они оставались в этом положении или остановились. Достаточно лишь, чтобы за конечное число шагов гарантированно наступила ситуация, когда все роботы находятся в одной и той же ячейке ленты.

[Disprein]

Amicus Plato, да, память есть. И счетчик можно. Можно вообще считать мозг робота наисовременнейшим компьютером. Или даже еще более мощной машиной Тьюринга.
Но из органов чувств у робота есть только средство определения того, присутствует ли в текущей ячейке парашют.

Trotil, каждый парашют — это точка, в которой начал функционировать какой-то робот...
По сути, парашюты — это единственный способ для роботов хоть что-то понять в окружающем их жестоком мире, то есть жестокой ленте)

[Trotil]

> Вот бы заставить их найти центральный парашют и там поджидать всех остальных.

Они не смогут его найти.
Потому что при очередном поиске они не знают, будут впереди парашюты или нет...

[Фабий]

Но это решение неправильное.

Если есть память, то вполне подходит, по-моему.

[Amicus Plato]

Disprein
счетчик хорошо... буду думать )))

Trotil
>

Они не смогут его найти.

да я понимаю...
но всё равно надо как-то от парашютов отталкиваться.

Фабий
у нас слева и справа по бесконечности. Если бы были ограничители, тогда легко.

[Trotil]

Предлагаю такой алгоритм.

Робот начинает колебаться вокруг своего парашюта (тут надо подумать, либо R-0-R, либо R-0, O - парашют), каждый раз отходя от него на шаг дальше, чем в прошлый раз. Как только слева он наталкивается на чей-то парашют, счетчик сбрасывает, и он начинает снова так ходить.
Этот алгоритм приведет к тому, что все роботы за конечное число шагов будут колебаться вокруг одного и того же парашюта. А вот встретятся ли они при этом - нужно еще подумать.

[Amicus Plato]

Trotil

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

Ты уверен?

[Amicus Plato]

Если два парашюта близко друг к другу, эти два робота зациклятся.

[Trotil]

эти два робота зациклятся.

Дык роботам интересуют новые парашюты только с одной стороны (допустим, с левой.). На правые парашюты они не будут обращать внимания.

[Amicus Plato]

А, только в одну сторону....
Ну, да.
Теперь бы еще действительно их собрать в одной точке!

[Trotil]

Гипотеза )

Алгоритм верный, если для любого массива чисел a1, a2, ..., an существует такое число k, что все ai+k будут являться квадратами целого числа )))

P.S. В решении я допускал, что он может задерживаться в ячейке на любое число ходов.

[Фабий]

у нас слева и справа по бесконечности. Если бы были ограничители, тогда легко.

Бесконечности ленты. А роботов ограниченное число. Следовательно, и паршутов тоже.

[Disprein]

Фабий, мы не знаем, сколько всего роботов. И робот не знает, сколько всего парашютов на ленте.

[Amicus Plato]

Trotil

Алгоритм верный, если для любого массива чисел a1, a2, ..., an существует такое число k, что все ai+k будут являться квадратами целого числа )))

да уж )))

А если вот так:
Все они в итоге совершают колебания возле самого левого парашюта.
У нас есть счетчик количества совершенных колебаний ai.
При этом каждый раз прежде чем отправиться в новый поход влево, они задерживаются на ai тактов (или не на ai, а лучше 2ai, чтобы робот стоял и ходил одинаковое количество времени).
Первый робот (который приземлился левее всех) к тому времени как начнут собираться все остальные, будет там делать самые большие задержки. Второй дошедший — несколько меньше, и т.д.

О! А еще лучше не 2ai, а с другим коэффициентом, больше 2. Чтобы стояли они дольше чем ходили. Тогда, устремив счетчик к бесконечности, получим, что они стоят практически вечность... Хотя иногда и ходят )))

И стоят все в одной точке.

Но не знаю, можно ли строго доказать...

[Trotil]

Но не знаю, можно ли строго доказать...

Так вот я и попытался построить некоторую модель.

Рассуждал примерно следующим образом: введем понятие "номер хода" - an. По этому номеру хода можно узнать, в какой клетке стоит робот и в каком направлении он движется.

Пусть алгоритм такой:
0, 1, 0, 0, 1, 2, 1, 0, 0, 1, 2, 3, 2, 1, 0, 0, 1, 2, 3, 4, 3 ...

(отходит на один шаг вправо, а когда возвращается на место парашюта, стоит один ход)
Последовательность - номер клетки в момент хода i.

Тогда в точке 0 робот побывает на 0, 3, 8, 15, 24 ходу и т.д.
В x^-2 -1 ходу робот гарантированно будет в точке 0.

Когда робот находит новый парашют, отсчет начинается с нуля и с новой точки отсчета.

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

Более того, нам неизвестно, в какой момент времени это произойдет. Мы только знаем, что первый робот будет совершать a1 ход, второй - a2 ход, ...
И т.д.
Можно считать, что начальные значения a1, a2, ... - абсолютно случайны.
И вот пришли к такой системе, а встречей в точке 0 через k ходов будет условие ai+k = bi^2 - квадрат некоторого числа.

-------------------------

Но! Как я понял через некоторое время, это лишь приблизительный набросок, более того,он не выполним.
(из-за того, что система критериев неполна - одного этого условия недостаточно)
Необходимо доработать идею - изменить немного алгоритм.

[J.Random]

imho:
счетчики:
С1: 0, 1, 1 при высадке
С2: int, 0 при высадке
C3: int, 0 при высадке

Если С3=0, то
если С1=0, то С1=1
иначе С1=0, двигаться вправо на одну ячейку, С2=С2+1
иначе двигаться вправо на одну ячейку, С3=С3-1, С2 = С2+1
осмотреть ячейку, если есть парашют, то С3=С3+С2*2, С2=0
повторить.

На коленке за 5 минут, но результатом по идее должно стать то, что все роботы будут через какое-то время синхронно раз в два такта передвигаться вправо, находясь постоянно в одной ячейке.

[Disprein]

Black_Diver, да, похоже на правду.)

Disprein
На одномерную бесконечную ленту десантируют роботов ..
• • •

Один вопросец покоя не даёт!
А как железяки узнают, где Право, а где Лево?
Лента шерстью в одну сторону причёсана,
а они её на ощупь бачут?

[Disprein]

Crowood, например. Или по солнцу. Над бесконечными лентами всякое случается.

Crowood
А как железяки узнают, где Право, а где Лево?
Disprein
.. по солнцу. Над бесконечными лентами всякое случается.

Уточняю вопрос:
Подразумевается ли в условии неявно, что
лента ориентирована и роботы способны таковую определить?

Или по-другому:
Подразумевается ли в условии неявно, что
роботов десантируют всех мордой на одну сторону ленты?

Или каким-либо ещё равносильным образом ..?

[Disprein]

Crowood, да, подразумевается, что все роботы ориентированы одинаково. Мордой на одну сторону ленты или как-либо еще — не суть важно.