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

[Legioner93]

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

Да, найденные варианты асимптотически гораздо суровее, чем придуманный мной алгоритм - ходить вперед/назад, вперед все включать, назад все выключать, до первого расхождения с нашими представлениями о том, что мы уже включили/выключили, от выбранного раздела вагонов на величины из последовательности $1, 1, 2, 3, 5, 8, 13, ...$, где каждое следующее значение является суммой двух предыдущих.

UPD а может и не гораздо, надо будет посчитать и сравнить длины пробега...

Если я правильно понял ваш алгоритм, то вы "шагаете" числами Фибоначчи вместо наших степеней двойки. В таком случае наихудшее время (когда $N=F_{n-1}+1$) будет $2\cdot(1+\dots+F_n)-(F_n - F_{n-1})=2\cdot F_{n+2}-(F_n - F_{n-1})=N\cdot(2 \varphi ^3 - \varphi +1)$.
Это $\dfrac{3}{2}(3+\sqrt{5})N$, примерно $7,85N$. Равенства асимптотические, а $\varphi$ - золотое сечение.

-- Пн май 06, 2013 01:02:37 --

Этот максимум, кстати, не совпадает с вашим максимум на графике. Кто-то из нас ошибся, возможно я.

[_Ivana]

Legioner93, давайте сделаем так - вы напишете маленькое $N$ в котором по вашим расчетам мой алгоритм требует столько шагов, сколько вы написали - а я попробую написать вам по шагам, как я определяю это число и за сколько шагов.

[Legioner93]

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

Legioner93, давайте сделаем так - вы напишете маленькое $N$ в котором по вашим расчетам мой алгоритм требует столько шагов, сколько вы написали - а я попробую написать вам по шагам, как я определяю это число и за сколько шагов.

По моим рассчётам ваш алгоритм делает столько шагов на больших $N$, а не на маленьких
Ну давайте $N=145=144+1$ (144 - число фибоначчи). Всё равно все шаги, кроме последнего, свернутся в "и т.д."

[_Ivana]

Терминология для определенности: + вперед, - назад, количество вагонов считается от некоей условной границы между вагонами, которую мы выбрали как старт. Соответственно, если мы сделали $n$ шагов в +, то чтобы вернуться в вагон №1 (от условной границы раздела) нам надо сделать $n-1$ шагов назад. Итак:
+1
-1
+2
-3
+5
-8
+13
-21
+34
-55
+89
-144
проделав все эти шаги и вернувшись в наш условный ноль, мы еще не узнали $N$, а сделали $740$ шагов (каждая строка умножается на 2, из результата вычитается 1 и это все суммируется построчно). Для узнавания $N$ нам теперь осталось сделать 2 шага в +, там мы увидим расхождение по свету в вагоне. Итого, $742$ шага, делим на $N$ - получаем $5.12$.

ЗЫ могли бы не жадничать и выбрать $N$ поменьше Кстати, для $N=144$ мне потребовалось бы тоже максимальное относительно число шагов, потому что одно число Фибоначчи $144$ не опоясывает весь поезд с перехлестом.

[TOTAL]

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

[nikvic]

У меня получился оптимальный множитель - не двойка и не множитель Фибоначчи. Результирующая константа меньше семи.

[nikvic]

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

[TOTAL]

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

У меня получился оптимальный множитель - не двойка и не множитель Фибоначчи. Результирующая константа меньше семи.

Какой же он оптимальный, если при двойке множитель меньше пяти?

[_Ivana]

nikvic, константы меньше $7$ уже получены выше: g______d и TOTAL получили $5$ (у них, насколько я понял, один и тот же алгоритм, первым его предложил g______d, а TOTAL потом просто перепостил его дважды), я с Фибоначчи получил $3+\sqrt{5}$. Никто не ограничивает рассмотрение любых алгоритмов - приведите свой вариант.
ЗЫ другое дело, в какую сторону "оптимизировать" алгоритм. Вот если, например, я придумаю алгоритм, который на бесконечности будет давать оценку $3N$, но при этом для $N<1000000$ будет во много раз хуже, чем $10N$ - это будет оптимальный алгоритм? Если придумать как ходить по прогрессии с коэффициентом к примеру $100$, и при этом включать/выключать вагоны, то это будет подобным алгоритмом.

[Legioner93]

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

Вот если, например, я придумаю алгоритм, который на бесконечности будет давать оценку $3N$, но при этом для $N<1000000$ будет во много раз хуже, чем $10N$ - это будет оптимальный алгоритм?

Да, будет. Точнее, он будет оптимальнее, чем все предыдущие.

Может ли кто-нибудь доказать, что если ходить взад-вперед числами $a_k$, то минимальное время будет при $a_k \sim 2^k$ при $k \to \infty$?

[_Ivana]

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

Да, будет. Точнее, он будет оптимальнее, чем все предыдущие.

По оценке на бесконечности - да. Но на практике будут выбирать другие простые одножо (С Саус Парк) схемы.

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

Может ли кто-нибудь доказать, что если ходить взад-вперед числами $a_k$, то минимальное время будет при $a_k \sim 2^k$ при $k \to \infty$?

Да можно тогда ходить не степенями двойки а любой стремительно возрастающей последовательностью. Например, первым этапом сделали $10^{10}$ ходов вперед, потом $10^{100000}$ ходов назад, потом 2 хода вперед - и нашли что мы в поезде из 2 вагонов

[Legioner93]

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

Может ли кто-нибудь доказать, что если ходить взад-вперед числами $a_k$, то минимальное время будет при $a_k \sim 2^k$ при $k \to \infty$?

Как-то так. Доказываю для хождения всегда вправо из нуля, т.е. для своей схемы (где получается $7N$ для степеней двойки). Для более эффективной схемы, предложенной позднее (ходить сначала вправо, потом влево) по-моему всё то же самое.

1) $\frac{a_{k+1}}{a_k} \ne \omega(1)$, потому что в противном случае $\sum\limits_{i=1}^{k+1}a_i \sim a_{k+1}$; при $N=a_{k}+C$ получаем, что $T \sim 2 a_{k+1} = \omega (N) \ne O(N)$

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

2) А из $\frac{a_{k+1}}{a_k} \sim 1$ следует, что асимптотически $\sum\limits_{i=1}^{k+1}a_i > C \cdot a_{k+1}$ для $\forall C$. То есть опять же получаем $T=\omega (N)$, причём теперь уже для вообще любого $N \in (a_k , a_{k+1}]$

Поэтому $1+\varepsilon<\frac{a_{k+1}}{a_k} < \infty$ (оба неравенства строгие). Для множества же всех геометрических прогрессий оптимальность $2^k$ доказывается тупым подсчетом суммы, который я уже приводил на первой странице.

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

-- Сб май 11, 2013 16:45:52 --

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

Да можно тогда ходить не степенями двойки а любой стремительно возрастающей последовательностью.

Нет

[nikvic]

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

nikvic, константы меньше уже получены выше: g______d и TOTAL получили (у них, насколько я понял, один и тот же алгоритм, первым его предложил g______d, а TOTAL потом просто перепостил его дважды),

Да, я был неправ - нужно каждый ход увеличивать, я же смотрел двойные ходы туда-сюда.
Однако не в 2 раза, а в один + корень из половины, 1.707 - ищется нижняя точка ветви гиперболы.
С константой 4.828

[TOTAL]

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

Да, я был неправ - нужно каждый ход увеличивать, я же смотрел двойные ходы туда-сюда.
Однако не в 2 раза, а в один + корень из половины, 1.707 - ищется нижняя точка ветви гиперболы.
С константой 4.828

Больше пяти, пересчитайте.

[nikvic]

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

Больше пяти, пересчитайте.

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

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