Задача про циклический поезд

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

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

Ответ: 1. Включаем свет в первом вагоне, если он еще не включен.
2. Идем по вагонам вперед, считая N = количество пройденных вагонов (первый не в счет), до тех пор, пока не войдем в очередной вагон с включенным светом. Поскольку поезд циклический, рано или поздно это случится.
3. Выключаем свет и идем на N вагонов назад.
4. Если по возвращению в начальный вагон свет оказывается выключенным, значит мы нашли ответ — в поезде N вагонов.
5. Перейти к шагу 2.

Ваша оценка: Нет Средняя: 3.5 (59 оценки)


Комментарии

Ещё можно построить аналогичный алгортм решения, если первый вагон оставить с включённым светом.

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

*с ВЫКЛЮЧЕННЫМ светом

Верно, эта задача как раз из тех, что задают на собеседовании в некоторых конторах