2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 8  След.
 
 Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 00:12 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Вы находитесь в поезде, вагоны которого закольцованы: последний вагон прицеплен к первому (кабина машиниста отсутствует). Все вагоны идентичны. Каждый вагон может быть либо освещен, либо не освещен.
Изначально свет в вагонах горит случайным образом. Вы можете свободно перемещаться между вагонами и включать-выключать свет в вагоне, в котором находитесь.
Вопросы:
1) Придумать алгоритм, который позволит определить количество вагонов в поезде.
2) Существует ли алгоритм со сложностью $O(N)$, где $N$ - число вагонов? Сложность алгоритма - это общее количество перемещений между вагонами.
3) Предлагаю побороться также за константу в $O(f(N))$, т.е. получить самое быстрое время не в виде $O(f(N))$, а в виде $f(N)+o(f(N))$, что куда сложнее.

Первые два вопроса авторские (их я решил), последний вопрос добавил лично я (пока открыт).
Задача взята с конкурса, который проводил один из российских банков.

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 00:32 


05/09/12
2587
Вперед на 1 включаем, назад на 1 гасим, вперед на 2 включаем, назад на 2 гасим и т.п. пока не встретим вдруг расхождение с тем, что мы уже включили/погасили по нашим данным.

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 02:33 


05/09/12
2587
В принципе, необязательно, чтобы приращения вперед-назад были равны единице, они даже не обязаны быть равны и постоянны - главное, чтобы мы знали закон их изменения, и чтобы на каждом шаге они были не больше реального количества вагонов (скорее всего, надо продумать этот момент поточнее, а может и половины вагонов...). Но т.к. количество вагонов нам заранее неизвестно, то начать лучше с единицы, а потом... надо подумать, или геометрическая прогрессия с коэффициентом 2 (и может минус 1), или какие-нибудь другие Фибоначчи :-)

ЗЫ и, в частном случае, если не ошибаюсь, один длинный закольцованный в себя вагон определить нельзя :-)

-- 05.05.2013, 02:53 --

Жаль спать хочется (4 часа ночи), очень хочу сам дорешать, но чувствую, до конца сейчас не добью, а завтра наверняка уже кто-нибудь другой умнее все доведет до конца и мне ничего не останется... А я пока баранов вагоны считать пойду... :-)

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 04:16 
Заслуженный участник
Аватара пользователя


08/11/11
5940
Специально для _Ivana помещу в спойлер :)

Собственно, я так понял, что это примерно то же самое.

(Оффтоп)

2) Гасим первые 2 вагона. Потом возвращаемся назад и на обратном пути включаем. Если попался уже включенный, то мы нашли цикл. Потом повторяем то же со 4 вагонами, потом с 8 и т. д.

Количество операций будет не больше $2\cdot \sum\limits_{2^{k-1}\le n} \le 4n.$

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 10:57 


31/12/10
1555
Предлагаю сначала последовательно включить свет во всех вагонах, а затем
последовательно выключать.

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 11:15 


26/08/11
2057
vorvalm в сообщении #719806 писал(а):
Предлагаю сначала последовательно включить свет во всех вагонах, а затем
последовательно выключать.
Во всех это во сколько?

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 13:14 


31/12/10
1555
Их же не бесконечно.

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 13:24 
Заслуженный участник
Аватара пользователя


28/07/09
1178
_Ivana в сообщении #719720 писал(а):
Но т.к. количество вагонов нам заранее неизвестно, то начать лучше с единицы, а потом... надо подумать, или геометрическая прогрессия с коэффициентом 2 (и может минус 1), или какие-нибудь другие Фибоначчи

Я тоже к этому пришёл. И далеко не факт, что геометрическая прогрессия $2^k$, до которой легко догадаться - самая "быстрая" из всех последовательностей вообще. С ней у меня получилось $\sim 7N$.
_Ivana в сообщении #719720 писал(а):
ЗЫ и, в частном случае, если не ошибаюсь, один длинный закольцованный в себя вагон определить нельзя

Конечно можно. Запоминаем свет в первом вагоне, идём во второй, там меняем, возвращаемся в первый. Если в первом тоже изменилось, то первый вагон=второй вагон.
g______d в сообщении #719727 писал(а):
Гасим первые 2 вагона. Потом возвращаемся назад и на обратном пути включаем. Если попался уже включенный, то мы нашли цикл. Потом повторяем то же со 4 вагонами, потом с 8 и т. д.

Количество операций будет не больше $2\cdot \sum\limits_{2^{k-1}\le n} \le 4n.$

Да, алгоритм верный. У меня примерно такой же алгоритм, только я шёл в $2^k$-ый вагон, менял там свет, возвращался в начальный и смотрел, поменялся ли где-нибудь ещё. Если поменялся, значит мы прошли поезд по кругу. Время получается $ \sim 8N$, если всегда возвращаться в первый и $\sim 7N$, если в последней итерации уже не возвращаться в первый.

А вот с количеством операций $4n$ вы ошиблись. В наихудшем случае $n=2^{k-1}+1$ получается как раз $7n$, как и у меня, посмотрите.

Итак, остаётся открытым третий вопрос: можно ли сделать быстрее, чем за $7N$ (или за $4N$, если я не прав и оценка g______d всё-таки верная).

Если шагаем по геометрической прогрессии со знаменателем $a$, то $T \sim N (2a+1+\frac{2}{a-1})$, минимум этой функции достигается как раз в точке $a=2$ (что довольно любопытно).

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 15:21 
Заслуженный участник
Аватара пользователя


08/11/11
5940
Да, про $8N$ Вы правы.

По-моему, можно сократить до $6N$. А именно, после $k$-го шага у нас есть $2^k$ вагонов, про которые мы точно знаем. Почему бы на следующем шаге это не использовать? Т. е. пойти в другую сторону и делать такие же вагоны, а потом пойти обратно и делать противоположные. Таким образом, на каждой итерации вместо $2\cdot 2^k$ будет $2^k+2^{k-1}$, т. е. мы сокращаем общее время на четверть.

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 15:44 


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

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

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 15:57 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
$2^0$ по, $2^1$ против, $2^2$ по, $2^3$ против. Найдем за $5N$

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 21:08 


05/09/12
2587
Построил по своему алгоритму график нормированного к числу вагонов числа шагов алгоритма - получилось не так плохо (если я не ошибся при расчетах)
Изображение

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 22:47 


05/09/12
2587
Сравнил с количеством шагов по первому методу g______d (в одну сторону) - там получается диапазон от $4N$ до $7N$, максимумы и минимумы конечно в других точках, чем в моем алгоритме. Подтвердите уже или опровергните мои расчеты, кому интересна тема :-) Могу дать количество шагов для любых (компьютерно рассчитываемых) значений $N$.

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 23:14 
Заслуженный участник
Аватара пользователя


08/11/11
5940
_Ivana в сообщении #720139 писал(а):
Построил по своему алгоритму график нормированного к числу вагонов числа шагов алгоритма - получилось не так плохо (если я не ошибся при расчетах)


А максимум -- это $3+\sqrt{5}$?

 Профиль  
                  
 
 Re: Кольцевой поезд - найти число вагонов.
Сообщение05.05.2013, 23:19 


05/09/12
2587
Не могу сказать, я моделировал на компьютере численно, в радикалах в общем виде сумму ряда не вычислял. Хотя наверное можно записать ряд в аналитическом виде и посчитать.
Кстати, в первых постах я и имел в виду этот мой алгоритм, но написал его непонятно, что он вполне оказался похож и на ваш, и на ТС :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 108 ]  На страницу 1, 2, 3, 4, 5 ... 8  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group