16
Июл
2017

Задачка про поезд. Нужен алгоритм. Важна скорость

Задача: Вы просыпаетесь в вагоне поезда. Все вагоны поезда соединены в кольцо. То есть из последнего вагона вы попадаете в первый. В каждом вагоне есть выключатель и лампочка. Изначально лампочки случайным образом включены или выключены. Нужно двигаясь по вагонам и используя выключатели определить количество вагонов в поезде.

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

При худшем стечении обстоятельств, мы имеем О(n2+n) шагов или просто О(n2). В наилучшем случае просто О(2n).

Вопрос: А можно быстрее?

Источник: https://ru.stackoverflow.com/questions/692803/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%BA%D0%B0-%D0%BF%D1%80%D0%BE-%D0%BF%D0%BE%D0%B5%D0%B7%D0%B4-%D0%9D%D1%83%D0%B6%D0%B5%D0%BD-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D0%92%D0%B0%D0%B6%D0%BD%D0%B0-%D1%81%D0%BA%D0%BE%D1%80%D0%BE%D1%81%D1%82%D1%8C

Тебе может это понравится...

Добавить комментарий