Несколько вагонов сцеплены кольцом: последний вагон прицеплен к первому. В каких-то вагонах горит свет, в каких-то темно. Вы находитесь в одном из вагонов и можете переходить из вагона в вагон и включать/выключать свет.
Как определить, сколько вагонов в кольце, если все вагоны неотличимы друг от друга, а начальное распределение тёмных и светлых вагонов заранее неизвестно?
Решение
Для определённости будем считать, что изначально мы находимся в светлом вагоне. Если это не так, включим в нём свет специально.
Теперь идём по составу вперёд, считая вагоны. Если в очередном вагоне темно, то сразу идём в следующий. Если же в вагоне горит свет, то выключаем его и идём обратно в первый вагон (мы можем это сделать, т.к. считали все пройденные вагоны).
Если теперь в первом вагоне темно, то мы определили длину кольца: она равна числу пройденных вагонов, включая первый.
Если же в первом вагоне по-прежнему светло, снова идём по составу вперёд, пока не встретим очередной светлый вагон, и повторяем процедуру. Рано или поздно во всём составе не останется светлых вагонов, кроме первого, и мы определим длину кольца.
Как определить, сколько вагонов в кольце, если все вагоны неотличимы друг от друга, а начальное распределение тёмных и светлых вагонов заранее неизвестно?
Решение
Для определённости будем считать, что изначально мы находимся в светлом вагоне. Если это не так, включим в нём свет специально.
Теперь идём по составу вперёд, считая вагоны. Если в очередном вагоне темно, то сразу идём в следующий. Если же в вагоне горит свет, то выключаем его и идём обратно в первый вагон (мы можем это сделать, т.к. считали все пройденные вагоны).
Если теперь в первом вагоне темно, то мы определили длину кольца: она равна числу пройденных вагонов, включая первый.
Если же в первом вагоне по-прежнему светло, снова идём по составу вперёд, пока не встретим очередной светлый вагон, и повторяем процедуру. Рано или поздно во всём составе не останется светлых вагонов, кроме первого, и мы определим длину кольца.
В решении, кажется, очепятка:
ОтветитьУдалитьчетвертый абзац лучше бы начать со слов "Если же в первом вагоне по-прежнему светло".
Спасибо, поправил.
ОтветитьУдалитьИнтересно, но не понимаю логики возврата в первый вагон.
ОтветитьУдалитьПочему бы не пройти по кругу и выключить вначале везде свет, а затем включить в одном и пройтись по всем еще раз только со счетом? :)
Если я сразу начинаю идти по кругу, выключая везде свет, то как я могу быть уверенным, что я действительно прошёл весь поезд по кругу?
ОтветитьУдалитьЕсли мне на пути попалось сто вагонов с выключенным светом, возможны два варианта:
1. В поезде меньше ста вагонов, и я уже выключил свет везде.
2. В поезде много больше ста вагонов, просто мне попался такой "удачный" участок из 100 тёмных вагонов подряд. Возможно, в сто первом вагоне меня будет ждать включенный свет?
Можно попытаться улучшить алгоритм:
ОтветитьУдалить1. Включили в 1ом вагоне свет;
2. Прошли N вагонов, находимся в N+1 и свет горит.
3. Выключаем свет и проходим еще N+1 вагон.
3.1. Если, пока идем следующие N+1 вагонов, встречаем вагон со светом - обновляем значение N и идем снова N+1;
3.2. Если, пока пройдя N+1 вагон, увидим что везде свет выключен - идем назад 2 * (N+1) вагон и убеждаемся, что свет в 1ом выключен. Если не выключен - снова идем вперед, считая вагоны.
4. Если темных вагонов намного больше - возвращаясь в 1ый вагон - выключаем свет, а в остальных включаем. Т.о. экономим число проходов. Даже в самом худшем случае, мы остаемся при своем или в выигрыше.
Профит: в том случае, если вагоны с включенный светом попадаются часто, то когда мы прошли 100 вагонов и нам выгоднее пройти вперед еще 100, чтобы попытаться увидеть очередной вагон со светом, чем сразу пройти 100 вагонов назад-вперед, потом увидев 101 вагон со светом, пройти еще раз 101 взад-вперед.
Ленивое исполнение.