Чива Ротсен писал(а):Свежак
Есть поезд, закольцованный по кругу. То есть первый вагон так же соединяется с последним, как и со вторым. Окон нет. Из вагона в вагон переходить можно. В каждом вагоне можно включать или выключать лампочку. Никаких пометок на стенах или где-либо еще в вагоне делать нельзя. Определить количество вагонов.
Чива, - вообще это, конечно, НЕ СВЕЖАК. Свежаком является только формулировка про поезд. Скажем, в формулировке про циклический конвейер мы ту же самую задачу давали еще в 1994 году. А на самом деле она намного более старая - восходит к классическим книжкам по информатике (Кнут, Дэвид Грис, Дейустра и т.д.), просто очень лениво искать, в какой именно книжке она была впервые.
Вот еще версия очень похожей задачи. Юзер открывает веб-браузер на своей любимой страничке и начинает играть в такую игру: попав на очередную страничку, он переходит с нее по первой встретившейся там ссылке (предположим, что на каждой страничке есть хотя бы одна ссылка). Ясно, что рано или поздно такая игра приведет его на ту страничку, на которой он уже побывал, а после этого начнется цикл. Как (с минимальными издержками - что это такое, более-менее понятно, а конкретику я специально не навожу) найти длину этого цикла?