Загадка №2 — Замкнутый бесконечный поезд

Продолжая рубрику загадок, хочу предложить вам небольшую логическую задачку, которую мне когда-то задавали на собеседовании. Это весьма распространённая и известная головоломка, при этом очень лёгкая — даже если вы испытываете стресс во время собеседования, теоретически, должны справиться 🙂

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

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

ВНИМАНИЕ. Ниже будет дан ответ. Желательно, разгадать загадку самостоятельно.

Поскольку единственное, что мы можем привязать к вагону — это бит света (1 — включён, 0 — выключен) — перво-наперво включим свет (1) в нашем стартовом вагоне (S) от которого начинаем отсчёт. Нет разницы куда идти (само направление), главное считать наши шаги. Подходя к первому вагону (N1) мы столкнёмся с одной из двух ситуаций: когда свет горит (1) и когда не горит (0). В первом случае — нам необходимо потушить свет и сделать N уже пройденных шагов в обратном направлении, чтобы посмотреть не является ли N1 нашим стартовый вагоном S. Если проделав путь назад мы увидели, что свет в вагоне горит, значит N1 != S и мы можем повторить. В случае же, когда свет вагона N1 потушен — мы просто прибавляем к количеству вагонов единицу и идём к следующему. Повторять необходимо до тех пор, пока при обратном ходе мы не увидим выключенным стартовый вагон S и тем самым получим точное количество вагонов в составе поезда.

Сам алгоритм в псевдокоде выглядит примерно так:

N=1;
ПРОГРАММА {
	ПРОЙТИ ВПЕРЁД К ВАГОНУ N;
	ВКЛЮЧИТЬ СВЕТ В ВАГОНЕ N;
	ПРОЙТИ N ВАГОНОВ НАЗАД;
	ЕСЛИ СВЕТ В ТЕКУЩЕМ ВАГОНЕ ВКЛЮЧЕН:
		ВЕРНУТЬ ОТВЕТ N;
		ВЫЙТИ ИЗ ПРОГРАММЫ;
	ЕСЛИ СВЕТ В ТЕКУЩЕМ ВАГОНЕ ОТКЛЮЧЕН:
		N++;
		ПРОДОЛЖИТЬ;
}

Лучшим сценарием является состав, в котором отключены все вагоны. Худшим, соответственно, когда все включены.