Растолкуйте мне задачку про циклический поезд...

[Sun]

... что-то меня на ней переклинило)

Есть поезд, состоящий из некоторого количества вагонов. Вы находитесь в одном из них. Это очень странный поезд, потому что его вагоны сцеплены в кольцо. В каждом вагоне есть лампочка, которую вы можете включать и выключать. Ваша задача заключается в том, чтобы определить количество вагонов в поезде. Опишите алгоритм решения этой задачи. Других людей и прочих живых или неживых существ в поезде нет. Лампочки нельзя выкручивать, они не перегорают и не нагреваются, рисовать на стенах мелом нельзя, окон у вагонов нет. В общем, состояние поезда — это только лампочки. Кстати, начальное состояние поезда неизвестно, то есть изначально какие-то лампочки могут гореть, а какие-то не гореть. Единственный способ узнать, горит ли лампочка в определенном вагоне — это войти в него и посмотреть. Источник: https://eax.me/interview-questions/


Что-то мне кажется, что тут в формулировке забыли про максимум, т.е. количество вагонов надо ограничить сверху. Иначе под любой алгоритм, ищущий повторяющиеся периоды и включающий/выключающий лампочки для выяснения кратности можно построить очень длинный поезд, на котором этот алгоритм выдаст неверный ответ. Или я ошибаюсь?

[HiLuxSurfer]

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

[кум]

Не ту задачу выбрал. Твоя со скобочками же.

[Andruxa_N]

Одну разбить. Оставить свой ботинок.

[Андрей Терентьев]

1. Идём и включаем все лампочки, пока нам не перестанут попадаться выключенные. Попутно считаем. Численное значение - ну х.з., ну пусть, например, сколько прошли и включили штук, столько же надо чтобы потом подряд было включенных.
2. После этого начинаем идти и выключать лампочки, пока не дойдём до выключенной. Считаем. Если получилось примерно столько же, сколько и в п.1 (на момент, пока мы не решили, что что выключенные нам больше не попадаются) - значит, считаем, что мы получили ответ.
3. Поскольку у нас нет достоверного ограничения количества вагонов "сверху", т.е., грубо говоря, мы насчитали таким методом 25 вагонов, а на самом деле их миллиард, т.е. нам тупо повезло, то и результатом задачи является не нахождение точного значения, а всего лишь оценка. А значит, теперь надо сделать проверку. Любую. Например, прогнать алгоритм по кругу, исходя из найденного ответа, заданное число раз (чтобы общее число пройденных в ходе теста вагонов было на порядки больше полученного в п. 2 ответа), и чтобы при этом не было ни одной ошибки (т.е. каждое включение всех и последующее выключение всех подтверждало полученный ответ).
Таким образом, можно получить достаточно качественную оценку.

[Andruxa_N]

Т.е. до первой включенной? Ок.=N 2N+1-все вкл. 2N +2-выкл. вагонов - XN

[HiLuxSurfer]

Ответ: 1. Включаем свет в первом вагоне, если он еще не включен.
2. Идем по вагонам вперед, считая N = количество пройденных вагонов (первый не в счет), до тех пор, пока не войдем в очередной вагон с включенным светом. Поскольку поезд циклический, рано или поздно это случится.
3. Выключаем свет и идем на N вагонов назад.
4. Если по возвращению в начальный вагон свет оказывается выключенным, значит мы нашли ответ — в поезде N вагонов.
5. Перейти к шагу 2.


Чот не совсем понял.....

[HiLuxSurfer]

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

[GaXX]

а если в N+1 назад лампочка горит?

[GaXX]

Тупанул, понял

[GaXX]

оптимизация 1: переходим от N^2 к (log N / m + N) - каждый следующий шаг длиннее предыдущего в m раз
оптимизация 2: как 1, но если лампа в вагоне не горит, то повторяем шаг. но здесь я чёт пока не соображу какая сложность получается

[Sun]

А можно поподробнее для тупых? "Следующий шаг" - это какие именно действия?

[GaXX]

Имеем N > 8 вагонов, стоим в 0-м, m == 2:
1. Шаг 1: смотрим вагон 0+ (m^0 == 1) = 1
2. Шаг 2: смотрим вагон 0+(m^1 == 2) = 2
3. Шаг 3: смотрим вагон 0+(m^2 == 4) = 4
4. Шаг 4: смотрим вагон 0+(m^3 == 8) = 8
таким образом идём до потухшей лампочки в 0-м вагоне и за max(m^k -1) вычисляем кол-во вагонов

[Sun]

При N=12, нумерация вагонов начинается с 0.
2^4=(3+1)*2^2=12+2^2 - попадаем в 4й вагон
2^5=(3+1)*2^3=12*2+2^3 - 8й вагон
2^6=(3+1)*2^4=12*2^2+2^4=12*2^2+12+2^2=12(2^2+1)+2 ^2 - 4й вагон
2^7=(3+1)*2^5=12*2^3+2^5=12*2^3+12*2+2^3=12(2^3+2) +2^3 - 8й вагон
и т.д., согласно принципу индукции, шагая по степеням двойки, мы всегда будем попадать либо в 4й либо в 8й вагон. И чего нам это даст? Или я не так вас поняла?

[GaXX]

по пути выключаем лампы в каждом вагоне, соответственно на шаге N все лампы будут выключены (и в 0 вагоне тоже) -> значит мы пошли по кругу -> возвращаемся назад в 0 вагон, включаем лампу -> идём на 2^(N-1) вагонов вперёд и дальше последовательно до горящей лампочки -> бинго!

[Sun]

По-вашему на каком шаге надо возвращаться в 0 вагон?

[GaXX]

на каждом

[Sun]

Ок. N=12. На четвертом шаге выключили все лампочки до 8 вагона, кроме нулевой. На пятом мы проходим нулевой вагон, но мы этого не знаем, т.к. не знаем, что N=12. Гасим лампочку в нулевом вагоне и, по вашему алгоритму, далее до 4го вагона (по нашему линейному счету 16-го) - и возвращаемся на 16 вагонов назад. Света нет - вывод - количество вагонов 16? Или 15? Или сколько от 8 до 16?

[GaXX]

На 5 шаге мы гасим лампу в 0 вагоне (не зная что он 0) -> возвращаемся назад на 16 шагов в 0 вагон -> видим что лампа погашена -> включаем её -> идем на 2^4=8 шагов и еще 4 шага до включённой лампы -> 0 вагон найден -> кол-во вагонов равно 8 + 4 == 12

[Sun]

поняла, спасибо

[Sun]

оптимизация 1: переходим от N^2 к (log N / m + N) - каждый следующий шаг длиннее предыдущего в m раз
оптимизация 2: как 1, но если лампа в вагоне не горит, то повторяем шаг. но здесь я чёт пока не соображу какая сложность получается

если точнее, то наверное так: если по пути не встретилось ни одной горящей лампы - повторяем шаг - да?
А сложность, если в исходном состоянии все лампы горят, будет такая же.
А если все выключены - 2*N - туда и обратно

[Sun]

Класс! 7 минут всего, вы гений)))

[HiLuxSurfer]

да, я прекрасно владею гуглом ))

[Sun]

ну вот, чо ж вы не дали маньякам поманьячить))

[Бульдозер]

Вагоны без локомотива поездом не считаются!!!

Хотя традиционно слово «поезд» и связывают с железнодорожным транспортом, появилось оно значительно раньше первых паровозов (1804 год). Так, согласно словарю Даля слово «поезд» происходит от слова «поездка» и изначально обозначало ряд повозок, следующих друг за другом — в этом значении слово сохранилось, в частности, в словосочетании «свадебный поезд»^[3].В дальнейшем с развитием железнодорожного транспорта слово «поезд» стало применяться и к нему. В том же словаре Даля можно встретить и такое определение: «Поезд железной дороги — сколько везет паровоз, или что сцеплено вместе, в одно целое.»^[3] Под это определение попадает и группа сцепленных между собой вагонов — железнодорожный состав.
Определение, данное в словаре Брокгауза и Ефрона, уже оговаривает наличие в составе тяговых единиц:

Поезд — сцепленные вместе экипажи для следования по железной дороге. Обыкновенно П. составляется из ряда вагонов, ведомых помещённым в голове локомотивом.

По мере сокращения использования гужевого транспорта слово «поезд» постепенно утратило своё первоначальное значение («ряд повозок») и стало ассоциироваться исключительно с железной дорогой.

Поезд железнодорожный, сформированный и сцепленный состав из вагонов с одним или несколькими действующими локомотивами или моторными вагонами, имеющий световые и др. опознавательные сигналы^[4]

Наконец, Правила технической эксплуатации железных дорог дают аналогичное официальное определение слова «поезд», но со следующей оговоркой:

Локомотивы без вагонов, моторные вагоны, автомотрисы и дрезины несъёмного типа, отправляемые на перегон, рассматриваются как поезд.

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

https://ru.wikipedia.org/wiki/%D0%9F...B5%D0%B7%D0%B4

[Demige]

А на*** ходить по поезду и включать-выключать лампочки? Не лучше ли найти вагон ресторан и приятно провести вечер под бутылочку крепкого?

[Jabo]

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

[Бульдозер]

Если вагонов +100500, а ты прошел всего вагонов эдак 25, а в остальных 25и лампочки например выключены?

[Jabo]

П2. Проходишь ещё раз и контролируешь естественно при бесконечном количестве вагонов задача не имеет решения.
ЗЫ: Можно конечно насрать в одном из вагонов, а потом найти - самый быстрый стопроцентный результат.

[HiLuxSurfer]

кстати! срать не запрещено по условиям задачи....

[Lex]

при бесконечном количестве вагонов
насрать в одном из вагонов

не получится, приспичит еще не раз ))

[Jabo]

можно насрать и спрятать

[forvard]

Вася, проснись

[Jabo]

этож не баня а вагоны

[axel]

все проще: в самом первом вагоне где респаунились пишем на стене "***" и идем до вагона ресторана.. лампочки можно не включать и не выключать, на это есть проводник.. если ресторана-вагона не находим, а метка х попадается снова, то вспоминаем сколько прошли вагонов.. и грустим.. пива то не попить.

[Jaguar-nn]

Тоже думал про точку отсчета типа включать везде свет и т.д. Но ведь действительно если не знаешь сколько вагонов ты по ним топаешь и вроде как ахулиард подряд включенных лампочек, ты типа останавливаешься и говоришь в поезде ахулиард вагонов, а оказалось в ахулиард+1 вагоне до которого недошел свет выключен.
Так вот задача намного проще чем кажется: надо дойти до локомотива и отсчитывать от него!