Популярное здесь решение с выключением лампочки с одной стороны и последующим возвращением в исходный вагон - не самое эффективное. Трудоёмкость будет квадратичная, если все лампочки окажутся включенными.
Т.е. если вагонов тыщща, то вагонов придётся обойти порядка мильёна!
У Семёна эффективнее решение, но нужно дофига памяти. Трудоёмкость - сходу неясна, надо подумать.
Можно решить линейно-логарифмически. С константной памятью.
Т.е. на тысячу вагонов обойти придётся порядка десяти тысяч. Примерно в 100 раз эффективнее. Ну, или ещё сильно круче для более длинных поездов.
Ага
>если общество так легко согласилось с тем, что "другие предложенные тут варианты не дают стопроцентной гарантии".
> Был бs весьма признателен товарищам за описание ситуации, в которой не работает метод, предложенный в посте #25/
Легко. Прогони его для случая, когда изначально свет везде выключен :)
Более того, достаточно, чтобы в двух ближайших вагонах свет не горел, и этот метод накрывается медным тазом: засекаем в первом вагоне: темно, засекаем во втором: темно. Получили дублирование: две единичной длины цепочки одинаковых значений. Значит, разворачиваемся и идем назад. По дороге выключаем в первом вагоне и без того выключенный свет. Никак не изменив начального состояния, заходим на второй, ... стопицотмиллионный круг.
> Можно решить линейно-логарифмически. С константной памятью.
> Т.е. на тысячу вагонов обойти придётся порядка десяти тысяч. Примерно в 100 раз эффективнее. Ну, или ещё сильно круче для более длинных поездов.
Вру.
Зачем линейно-логарифмически, если можно линейно.
> Значит, разворачиваемся и идем назад. По дороге выключаем в первом вагоне и без того выключенный свет.
Нет, как я понимаю, в первом вагоне мы (по методу Семена) меняем свет и перерисовываем паттерн: т.е. если до этого мы прошли: Т-т, то теперь запоминаем С-т?. Идем во "второй" вагон - и если он светлый (т.е. поменялся - вместо С-т? видим С-с!) - стоп - знаем результат: 1 вагон.
Если второй вагон темный (т.е. паттерн правильный), значит, длина вагонов 2+.
Идем дальше до первого уже светлого вагона, дорисовывая паттерн предыдущими темными вагонами (т.е. С-Т-...-), а этот берем под сомнение - не первый ли он.
Допустим, ближайший светлый - третий (ну или {k-тый}) - соответственно, нам надо пройти теперь от него вперед максимум на длину паттерна - минимум на 1 вагон - проверить паттерн. Т.е. если в 4м {k+1} вагоне светло - т.е. не подходит под паттерн (напоминаю, для 3х сейчас С-Т-с?), то предыдущий вагон рисуем в паттерн, а этот берем под сомнение, паттерн становится: С-Т-С-с?.
Если в 4м вагоне темно (т.е. похоже на запомненный паттерн), то нам нужно вернуться назад к первому вагону и поменять там свет, перезапомнив паттерн (был С-Т-с?, стало Т-Т-с?) и опять из первого вагона пойти во второй, а дальше - в третий. Если третий окажется темным - бинго. Свет поменялся, значит, решение найдено, длина вагонов = 2 {k-1}.
Если третий все еще светлый, значит длина вагонов 4+ {2(k-1)+}, дорисовываем третий вагон в паттерн вместе с четвертым и дальше - до ближайшего темного, приписывая к паттерну все светлые вагоны (Т-Т-С-Т-...-) соответственно ближайший темный берем под сомнение и т.д.
---------------
Метод на самом деле тоже 100%, т.к. мы точно определяем точку окончания, возвращаясь и меняя свет, но не факт, что этот метод оптимальнее, чем простой "туда-сюда-поменял" Белого Клыка, т.к. для проверки паттерна придется проходить в случае повтора длину 2к, а не к. Так что для разных комбинаций вагонов более оптимальным может быть другой метод.
тут поступило предложение менять лампочку не в первом вагоне, а в подозрительном, тогда момент проверки (стоп-не стоп) наступает при доходе до первого, а беготня несколько сокращается.
Вариант с сигнатурой - хорош. Не 100% гарантию дает, но если в качестве ее длины взять хотя бы 30-40 вагонов, вероятность ошибки будет стремится к нулю (1/2^30 это очень мало)
> Нет, как я понимаю, в первом вагоне мы (по методу Семена) меняем свет и перерисовываем паттерн
Вот дословно #25:
1) Идем по вагонам, записывая ситуацию (0 - темно, 1 - светло) до тех пор, пока не получим первый цикл (2к вагонов, первый отрезок длины к совпадает во вторым).
2) Возвращаемся в первый вагон и выключаем свет в первых к вагонах.
3) Идем дальше и если оказывается, что первый светлый вагон во втором отрезке погашен, значит вагонов всего к.
4) Если оказывается, что во втором отрезке вагоны освещены также, как и до выключения первого отрезка, возвращаемся в первый вагон и переходим к п 1).
1. Измеряем длину вагона.
2. В тамбуре смотрим угол сочленения соседних вагонов.
3. Вычисляем, сколько вагонов потребуется чтобы вписать их в окружность заданной длины.
1. В текущем вагоне (0) зажгли лампу.
2. Идём налево, гасим лампу в двух вагонах (-2, -1).
3. Возвращаемся к нулевому вагону (0).
4. Идём направо, зажигаем свет в вагонах (0, 1, 2, 3), попутно проверяя, не потух ли в первой четверти (0) из прошедших вагонов.
5. Возвращаемся к нулевому вагону (0).
6. Идём налево, зажигая свет в вагонах (-1, -2, -3, -4, -5, -6, -7, -8), попутно проверяя, не зажёгся ли свет где-то в первой четверти (-2, -1).
7. Возвращаемся к нулевому вагону (0).
8. Идём направо, зажигаем свет в вагонах (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15), попутно проверяя, не потух ли в первой четверти (0, 1, 2, 3) из прошедших вагонов.
9. Возвращаемся к нулевому вагону (0).
10. Идём налево, зажигая свет в вагонах (-1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26, -27, -28, -29, -30, -31, -32), попутно проверяя, не зажёгся ли свет где-то в первой четверти (-8, -7, -6, -5, -4, -3, -2, -1).
Повторяем процедуру до тех пор, пока вдруг где-то в первой четверти не встретим погашенную лампу (справа), либо зажжённую (слева).
Вариант с сигнатурой: используя более простой метод, устанавливаем, что число вагонов в поезде превышает, скажем, 30. Затем расставляем произвольную, от балды, последовательность вкл/выкл в этих вагонах, желательно используя хороший генератор случайных значений - например, кубик или монетку. Запоминаем эти 30 значений и идем всегда вперед, ищя запомненную последовательность. На очень длинных поездах такой метод даст трудоемкость ~n, а вероятность ошибки - ничтожно мала и на практике никогда не проявит себя. Для совсем дотошных - можно взять сигнатуру побольше, например, из 128 значений, как у количества GUID.
Сейчас, сейчас