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

[TOTAL]

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

Если шагаем по геометрической прогрессии со знаменателем $a$, то $T \sim N (2a-1+\frac{a}{a-1})$.

Так получилось у меня. Последнее слагаемое - накопленный за "к" шагов путь, первые два - следующий шаг и частичный возврат.
Для Вашего варианта (из двойки) получаем пятёрку 5.

Для $N=a^{k-1}+1$ надо $1+a^1+a^2+ \cdots + a^k +N.$ шагов. Найдите отношение.

[nikvic]

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

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

Если шагаем по геометрической прогрессии со знаменателем $a$, то $T \sim N (2a-1+\frac{a}{a-1})$.

Так получилось у меня. Последнее слагаемое - накопленный за "к" шагов путь, первые два - следующий шаг и частичный возврат.
Для Вашего варианта (из двойки) получаем пятёрку 5.

Для $N=a^{k-1}+1$ надо $1+a^1+a^2+ \cdots + a^k +N.$ шагов. Найдите отношение.

Последний знак "+" у Вас неверен: при некотором увеличении длины поезда последний шаг укорачивается, а не увеличивается.

[TOTAL]

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

Последний знак "+" у Вас неверен: при некотором увеличении длины поезда последний шаг укорачивается, а не увеличивается.

Дайте свой верный вариант. За сколько шагов в описанном случае (и как) найдете длину поезда?

[nikvic]

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

Для $N=a^{k-1}+1$ надо $1+a^1+a^2+ \cdots + a^k +N.$ шагов. Найдите отношение.

Понял, где мы разнимся. Эта Ваша формула исходит из того, что множитель шага не меньше двух, и встреча с изменением освещения происходит "рано", на траектории предыдущего шага.
Для множителя менее 2-х - позже, на траектории пред-предыдущего.

[TOTAL]

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

Понял, где мы разнимся. Эта Ваша формула исходит из того, что множитель шага не меньше двух, и встреча с изменением освещения происходит "рано", на траектории предыдущего шага.
Для множителя менее 2-х - позже, на траектории пред-предыдущего.

На это ответите?

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

Дайте свой верный вариант. За сколько шагов в описанном случае (и как) найдете длину поезда?

[nikvic]

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

На это ответите?

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

Дайте свой верный вариант. За сколько шагов в описанном случае (и как) найдете длину поезда?

У меня проблемы с разрешённым написанием формул
Замените в Вашей формуле последнее "эн" на "а" в к-й минус эн.

С освещением есть два естественных варианта, просто инверсия при проходе (с запоминанием результатов) или пушкинского кота: идёт направо - песнь заводит, налево - сказку говорит. О

[_Ivana]

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

С освещением есть два естественных варианта, просто инверсия при проходе (с запоминанием результатов) или пушкинского кота: идёт направо - песнь заводит, налево - сказку говорит. О

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

Legioner93 в сообщении #722380 писал(а):

На этом тему двух классов алгоритмов, предложенных здесь, считаю завершенной.

, поскольку даже для прогрессии с множителем $4$ я не увидел здесь четко описанного алгоритма изменения света в вагонах, который однозначно даст нам количество вагонов при встрече с первым расхождением с нашими представлениями. Не говоря уже про бОльшие множители... Сильно подозреваю, что такого алгоритма может не существовать в принципе. Более того, я не разбирал еще предложенный алгоритм прогрессии с множителем $2$ вперед-назад - как там надо менять свет, чтобы при любом количестве вагонов однозначно определить их количество при перехлесте. Если кто может - напишите подробно по шагам для какого-то конкретного $N$

[TOTAL]

_Ivana в сообщении #722669 писал(а):

Если кто может - напишите подробно по шагам для какого-то конкретного $N$

Здесь уже давно сказали, что меняем цвет вагона в пункте разворота.

[nikvic]

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

Здесь уже давно сказали, что меняем цвет вагона в пункте разворота.

У меня иначе.
-- Вс май 12, 2013 12:21:54 --

_Ivana в сообщении #722669 писал(а):

как там надо менять свет, чтобы при любом количестве вагонов однозначно определить их количество при перехлесте

Однократная инверсия и запоминание результата для данного вагона.

Своё положение относительно исходного вагона мы знаем и не меняем цвет, если уже были там. "Перехлёст" - когда приходим в вагон, в котором уже были, и видим там иной цвет по сравнению с запомненным для этого вагона.

[nikvic]

Попробую описать всё "в одном флаконе".

"Алгоритм", кроме умения переходить из вагонов в соседние, имеет ленту из (нумерованных целыми числами) клеточек, первоначально пустых. На ленте - передвижное окошко-указатель, первоначально на клетке номер 0.
Каждый раз, перейдя из вагона в соседний, алгоритм двигает и окошко - так сказать, в ту же сторону.
Если клетка в окошке пуста, "цвет" вагона инвертируется, и в клетку пишется этот новый цвет (ноль либо один).
Если клетка содержит ноль либо один (мы уже были в этом вагоне!!), то её цвет сверяется с цветом вагона. При совпадении продолжить поиск, при несовпадении заканчиваем работу - есть перехлёст, длину можно объявлять.

Как и у TOTAL, двигаемся туда-сюда, увеличивая такие шаги (почти) по геометрической прогрессии. Множитель у TOTAL равен двум, однако оптимум равен единице плюс корень из половинки. Экономия достигается за счёт перекраски однократным инверитированием: для перехлёста нет необходимости на последнем шаги делать N переходов.

[TOTAL]

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

для перехлёста нет необходимости на последнем шаги делать N переходов.

Здесь ошибка, для перехлеста необходимы $N$ шагов.

Перекрашивать какие-либо вагоны, отличные от тех, где разворачиваемся, нет никакого смысла.

[nikvic]

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

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

для перехлёста нет необходимости на последнем шаги делать N переходов.

Здесь ошибка, для перехлеста необходимы $N$ шагов.

Перекрашивать какие-либо вагоны, отличные от тех, где разворачиваемся, нет никакого смысла.

Давайте разбираться. "В деле" участвуют 3 позиции разворота, А, В, С.
Из В мы пришли в А, затем шли в С и направились в сторону А.
Будем считать, без ограничения общности, что эти позиции расположены на целочисленной оси в порядке АВС, расстояние АВ "не хватило", расстояние АС больше длины - т.е. N реализуется как расстояние АB' для точки между В и С.
Двигаясь от В к С (в процессе движения от А к С), мы изменим состояние в А и B', т.к. это нумерует один и тот же вагон. И это обнаружится раньше, чем у Вас, после поворота в точке С.
У вас от поворота в С нужно пройти N, у меня АС минус N.

[TOTAL]

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

У вас от поворота в С нужно пройти N, у меня АС минус N.

Чтобы обнаружить изменение, после поворота надо пройти $N$ вагонов, разбирайтесь.

Обнаружить изменение можно только после поворота в точке $C$. Самым первым изменением, которое обнаружится на обратном пути из $C$ в сторону $A$, будет изменение, сделанное в $C$.

[nikvic]

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

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

У вас от поворота в С нужно пройти N, у меня АС минус N.

Чтобы обнаружить изменение, после поворота надо пройти $N$ вагонов, разбирайтесь.

Обнаружить изменение можно только после поворота в точке $C$. Самым первым изменением, которое обнаружится на обратном пути из $C$ в сторону $A$, будет изменение, сделанное в $C$.

Придёца на числах

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

[TOTAL]

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

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

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