Кольцевой поезд - найти число вагонов.

[nikvic]

TOTAL в сообщении #723132 писал(а):

nikvic в сообщении #723128 писал(а):

У поезда 10 вагонов, АВ содержит только 9, АС - 16. сколько шагов до перехлёста?
Вагоны занумерованы цифрами 0..9, точка А соответствует вагону №0, движение АС - в сторону вагона №1 (повезло нам).

Меняем цвет вагона $C$, т.е. вагона N15. Т.к. N15 совпадает с N5, то из N15 надо будет дойти до N5, чтобы обнаружить изменение. Это как раз 10 вагонов.

В отличие от Вас, я меняю цвета вагонов с N0 до N5, и до вагон N0 мне всего 5 шагов.

[TOTAL]

nikvic в сообщении #723136 писал(а):

В отличие от Вас, я меняю цвета вагонов с N0 до N5, и до вагон N0 мне всего 5 шагов.

В вагоне N0 (он же N10) цвет остался такой же, какой он был тогда, когда его покидали.

[nikvic]

TOTAL в сообщении #723137 писал(а):

nikvic в сообщении #723136 писал(а):

В отличие от Вас, я меняю цвета вагонов с N0 до N5, и до вагон N0 мне всего 5 шагов.

В вагоне N0 (он же N10) цвет остался такой же, какой он был тогда, когда его покидали.

Этот вагон перекрашивается (второй раз) в соответствии с пустотой в ячейке №10 моей ленты.

[TOTAL]

nikvic в сообщении #723145 писал(а):

Этот вагон перекрашивается (второй раз) в соответствии с пустотой в ячейке №10 моей ленты.

Да хоть сто раз перекрашивайте, не имеет значения. Каким Вы его покинули, таким и нашли на обратном пути.

[nikvic]

TOTAL в сообщении #723146 писал(а):

nikvic в сообщении #723145 писал(а):

Этот вагон перекрашивается (второй раз) в соответствии с пустотой в ячейке №10 моей ленты.

Да хоть сто раз перекрашивайте, не имеет значения. Каким Вы его покинули, таким и нашли на обратном пути.

Ок, свой заскок "по модулю N" увидел - правы Вы.
Пошёл за пеплом

[sup]

Вроде бы константу можно улучшить до $2 + 2\sqrt {2}$.
В изложенных алгоритмах никак не учитывался свет в вагоне при "прямом" проходе. Типичный ход - идем вперед $n$ шагов и выключаем свет. Идем обратно $2n$ шагов. Если свет выключен, то включаем, в противном случае найден цикл.
Однако, если во всех вагонах где я побывал свет горит, а я попал в вагон без света, то цикл гарантированно длиннее. Идея и заключается в том, чтобы оставлять за собой определенную комбинацию освещения так, чтобы в некоторых случаях можно было бы сразу отбросить вариант зацикливания. Заменим выражение свет горит или не горит на 1 и 0.
Пусть мне уже известна цепочка из $n > 2$ вагонов такая, что
1. Длина поезда гарантированно не меньше $n$
2. Свет горит во всех вагонах кроме второго.
Графически это можно изобразить как последовательность из 0 и 1.
Например
1 0 1 1 1
Что происходит дальше? Мы будем проверять дальше вагоны, при этом независимо ни от чего свет в вагоне будем включать(устанавливать в 1). Это гарантирует, что если цикл не найден, то выполнено условие 2.
Итак, в данный момент я знаю, что длина цикла может быть только $L \geqslant n$.
А. Проверяем следующий вагон.
Б. Там 0. Значит цикл длины $n$ невозможен. Выставляю 1 (как уже упоминалось), заменяю $n=n+1$ и иду в шаг А.
В. Там 1. Никакой новой информации. Идем в следующий шаг.
Г. Проверяем следующий вагон. Возникает два подварианта.
Г1. Там 1. Ага, цикл длины $L = n$ невозможен, а возможны только $L \geqslant n+1$. Заменяю $n=n+1$ и иду в шаг Г (как после шага В).
Г2. Там 0. Это значит, что возможен цикл длины $L = n$ или $L \geqslant n+2$. Но невозможен цикл длины $L = n+1$. Включаю свет и иду в следующий шаг.
Д. Для некоторого $\lambda$ один за другим проверяю $\lambda n-2$ вагонов.
Если напарываюсь на 0, то "короткие" циклы невозможны и я попадаю в ситуацию варианта Б. К этому моменту имеется $m$ просмотренных вагонов и длина цикла не меньше $m-2$. Поэтому полагаем $n=m-2$ и идем в шаг Д.
Е. Итак просмотрено $m = n + \lambda n$ вагонов. При этом либо цикл имеет длину $n$ и тогда во всех вагонах горит свет, поскольку единственный вагон (номер 2) без света мы "ликвидировали" на шаге Г2. Либо цикл имеет длину не меньше чем $m-1$. Проверяем гипотезу $L=n$. Для этого выставим в вагоне 0, сбегаем на $n$ вагонов назад. Если там 0 - то цикл найден, если нет то возвращаемся туда где были (еще $n$ шагов). При этом $L \geqslant m-1$. В этот момент мы тратим либо $n$ шагов и задача решена, либо $2n$ шагов и задача продолжается с $n = m-1$. И вот тут надо грамотно выбрать $\lambda$. Отмечу, что $\lambda = 1$ соответствует предыдущим схемам и дает константу 5. Однако, для $\lambda = \sqrt 2$ константа равна $2 + 2\sqrt {2}$.
Пусть $S_n$ общее кол-во просмотров вагонов к моменту шага А.
Для получения нужной оценки достаточно по индукции доказать, что $S_n \leqslant n (\lambda +2)/\lambda$. Если будет найден цикл длины $n$, то на это будет затрачено $S_n + \lambda n +n$ просмотров. В противном случае будет затрачено $S_n + \lambda n +2n$ просмотров, а $n$ увеличится до $(1+\lambda)n$.
Это кажется странным, что "лишние" проверки (почти в полтора раза) могут ускорить алгоритм. Однако они позволяют "резко" увеличить оценку снизу для длины цикла (если гипотеза провалилась), что и приводит к выигрышу.

[vorvalm]

Предлагаю другой алгоритм при тех же обозначениях:

$1, 0, 1, 0, 11, 0, 111, 0, 1111, 0.......$ до встречи комбинации $1, 0, 1, 0 ....$

Одновременно идет учет числа вагонов.

[TOTAL]

vorvalm в сообщении #723587 писал(а):

до встречи комбинации $1, 0, 1, 0 ....$

Что делать после встречи такой комбинации?

[Corwin]

TOTAL в сообщении #720267 писал(а):

Если $2^{k-1} < N \le 2^k,$ то число вагонов находится за $2^{k+1}+N-1$ шагов, т.е. менее $5N$ шагов. Идем вправо на 1 вагон, меняем цвет вагона. Идем влево на 2 вагона, меняем цвет вагона. Идем вправо на 4 вагона, меняем цвет вагона. И т.д. Поиск завершен, когда на обратном пути обнаруживается изменение в цвете вагона.

Можно подробнее? На примере 6 вагонов. Начальные цвета пусть будут, например, 101010. Цвета каких вагонов и в какой момент меняем?

[nikvic]

Оптимальность - штука тонкая
В нашем случае пока обсуждается определения оптимальности в смысле верхнего предела отношения числа шагов к длине поезда. TOTAL "сделал" пятёрку и доказал, что лучше нельзя в классе алгоритмов с показательным ростом шага.
Вполне возможно, что лучше вообще нельзя - в смысле указанного предела. Хотя "придёца помучица", исходя только из необходимого условия окончания работы -
существует отрезок АВ длины N+1, пройденный туда-сюда.

Это условие в качестве нижней оценки даёт двойку, и она, похоже, достижима в смысле "средней" оптимальности. Вот идея (натолкнул sup ) такого "алгоритма" -
Будем двигаться по поезду, определяя новый цвет подбрасыванием монеты. Ведём "протокол" изменений (слово P из 0,1) и "хвост" - слово Q, где запоминаем старые цвета. Когда пройдём около 1000 шагов, может оказаться, что начало P длиной 100 совпадает с концом хвоста - что весьма маловероятно как случайное совпадение и служит сигналом для разворота для проверки (в точке разворота цвет меняем).
До конца проверки монета не понадобится, в случае неудачи продолжим попятное движение, пополняя протокол и хвост.
Понятно, что "сто на тысячу" - чисто для иллюстрации идеи, достаточно, чтобы квадрат "сигнальной" длины хвоста рос заметно быстрее длины протокола.

[vorvalm]

TOTAL в сообщении #723610 писал(а):

vorvalm в сообщении #723587 писал(а):

до встречи комбинации $1, 0, 1, 0 ....$

Что делать после встречи такой комбинации?

Проверять дальше алгоритм. Если не совпадает, то вернуться к комбинации $1,0,1,0$
и продолжать алгоритм до следующей комбинации. Мы ничего не теряем, т.к. все время движемся вперед.

[Corwin]

Цитата:

Мы ничего не теряем, т.к. все время движемся вперед.

Получается бесконечное движение вперёд?

[vorvalm]

В условии задачи число вагонов конечно.

[TOTAL]

vorvalm в сообщении #723651 писал(а):

TOTAL в сообщении #723610 писал(а):

vorvalm в сообщении #723587 писал(а):

до встречи комбинации $1, 0, 1, 0 ....$

Что делать после встречи такой комбинации?

Проверять дальше алгоритм. Если не совпадает, то вернуться к комбинации $1,0,1,0$

Когда останавливаться?

[Corwin]

vorvalm в сообщении #723670 писал(а):

В условии задачи число вагонов конечно.

Если твой алгоритм предполагает только движение вперёд, то для любого предложенного тобой критерия остановки можно подобрать начальное состояние цветов, которое вызовет ошибочную остановку.
Если твой алгоритм предполагает возвращение назад при некоторых условиях, то можно подобрать такое начальное состояние цветов, что ты будешь возвращаться назад "слишком часто" (после минимально допустимого твоим алгоритмом числа сравнений).