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

[Corwin]

Corwin в сообщении #724694 писал(а):

Реализовал алгоритм предложенный sup
....
Результаты странные... Возможно, я где-то ошибся с реализацией худшего случая...

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

Правильные результаты (максимальные значения R при длине поезда не более 1000000):

lambda = 1,000000, ratio = 4,9999942780
lambda = 1,100000, ratio = 4,9181560307
lambda = 1,200000, ratio = 4,8666504282
lambda = 1,300000, ratio = 4,8384396324
lambda = 1,400000, ratio = 4,8285533862
lambda = 1,414214, ratio = 4,8283994977
lambda = 1,500000, ratio = 4,8333245115
lambda = 1,600000, ratio = 4,8499871191
lambda = 1,700000, ratio = 4,8764603015
lambda = 1,800000, ratio = 4,9110973985
lambda = 1,900000, ratio = 4,9526224871
lambda = 2,000000, ratio = 4,9999971775

Похоже, что предел $R = 5$ при $\lambda = 1$ или $\lambda = 2$ и предел $R = (2 + 2 \sqrt{2})$ при $\lambda = \sqrt{2}$.

[nikvic]

Corwin в сообщении #725091 писал(а):

Похоже, что предел $R = 5$ при $\lambda = 1$ или $\lambda = 2$ и предел $R = (2 + 2 \sqrt{2})$ при $\lambda = \sqrt{2}$.

Особой нужды в точных "прогонках" нет. 20 строк в таблице Экселя - и предел в кармане

[sup]

Могу предложить "сырое" доказательство того, что константа $2 +2\sqrt 2$ не улучшаема.
Предположим, что у нас имеется алгоритм, с некоторой константой $\gamma$. Пусть в какой-то момент обратная проверка окончилась неудачей и мы продолжаем поиск цикла. К этому моменту мы имеем $n$ вагонов с известным состоянием и затраты $S$.
Предположим, что сразу же после этого наблюдается повтор с началом, как если бы цикл был длины $n+1$. Что делает наш алгоритм? Он продолжает просмотр до некоторого вагона $m$, после чего запускает обратную проверку гипотезы $L = n+1$. Если гипотеза подтвердится, то будет найден цикл длины $L = n+1$, а затраты составят $S + (m-n) +(n+1) = S + m+1 \leqslant \gamma (n+1)$. Если же гипотеза не подтвердится, то затраты возрастут до $S + (m-n) +2(n+1) = S + m+n + 2$, но и известных вагонов станет $m$ штук. Таким образом возникает последовательность точек разворота $n_k$ с затратами $S_k$. Отбрасывая всякие единички и двойки как "малые", получим

$S_{k+1} = S_k + n_k + n_{k+1}$

$\frac {S_k + n_{k+1}}{n_k} \leqslant \gamma$

Положим $M_k = \frac {S_k}{n_k}$
Тогда
$M_{k+1} = 1+ \frac {S_k + n_k}{n_{k+1}} \geqslant 1+ \frac {S_k + n_k}{\gamma n_k -S_k} = \frac {\gamma + 1}{\gamma - M_k}$
Легко проверить, что при $\gamma < 2 +2\sqrt 2$ последовательность $M_k$ должна монотонно возрастать и не может быть ограничена сверху константой $\gamma$.