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

[Sun]

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

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


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

[HiLuxSurfer]

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

[Andruxa_N]

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

[HiLuxSurfer]

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


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

[Бульдозер]

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

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

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

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

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

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

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

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

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

[HiLuxSurfer]

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

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

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

[GaXX]

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

[GaXX]

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

[Andruxa_N]

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

[кум]

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

[GaXX]

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

[Demige]

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

[Jabo]

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

[Sun]

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

[HiLuxSurfer]

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

[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) вычисляем кол-во вагонов

[Бульдозер]

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

[Sun]

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