Задача про поезд
Логическая задача, для её решения не нужно обладать навыками программирования или математики, но тем не менее она была задана на собеседовании в одну очень крупную и известную IT компанию.
Вы находитесь в пустом поезде. Это даже не поезд, а просто вагоны, они сцеплены друг с другом. Все вагоны внутри одинаковы, двери на выход из вагона закрыты, через окна ничего не видно. Вы можете включать и выключать свет в вагоне в котором находитесь, можете сходить в соседний вагон, там тоже можно включать или выключать свет. Вам известно, что вагоны стоят на кольце и сами сцеплены в кольцо, первый вагон сцеплен с последним, ходить по кругу можно сколько угодно. В момент начала решения задачи в каких-то вагонах свет уже горит, в каких-то — не горит.
Ваша задача при помощи управления светом в вагонах и перемещения по ним узнать сколько в этом кольце вагонов.
UPD: Лампочки трогать нельзя, они находятся за стеклом, и потому по теплоте лампочек определить включали мы их или нет нельзя.
UPD2: Решение есть в комментариях. Закрыто спойлером.
UPD3: Весь интерес задачи в решении её логически, с применением только лампочек. Вариант оставить что-нибудь в вагоне и обойти кругом не интересен.
на вскидку – брести, чередуя включенный и выключенный свет в вагоне, однажды пройдёшь круг или даж больше, потом либо везде включать, либо наоборот выключать свет и просто считать пройденные вагоны пока везде не будет темно/светло. М?
Количество вагонов может быть любым, и стартовые условия тоже. Например начиная с сотого вагона направо идёт чередование света, и вы с начала начинаете чередовать, вот идете, чередуете, а том хоп и чередование началось, как вы сможете убедиться что это вы их включали, или не вы. Если начнете их при этом выключать, то потом может оказаться опять длительная последовательность выключенных лампочек. Как определить что это круг?
я бы насрал в первом вагоне. Ну а далее понятно=)
Это весьма жизненный способ решения. А если абстрагироваться от физиологических особенностей и попробовать решить задачу при помощи лампочек?
думаю решение в хождении туда-сюда
лево – центр – право
лево – лево – центр – право – право
И? Дальше то что? Как понять что мы пересечемся хождением направо и налево, ведь стартовые последовательности лам могут быть какие угодно.
без математики на ум приходит самое легкое – ходить туда-сюда и включать свет.
В первом выключить сразу. Рано или поздно останется только 1 без света.
Ход мыслей конечно правильный. Но это не полное решение.
Допустим вы идёте и включаете все лампочки подряд. Рано или поздно пойдут вагоны только с включённым светом. Можно предположить что вы замкнули кольцо, но есть вероятность что так и было с начала. По этому при данных условиях логически задача нерешаема.
Не будьте так категоричны. В этом и прелесть данной задачи, сначала она кажется нерешаемой. При вашем способе решения задача действительно не решаема. Есть другие тактики. Я точно знаю одну, которая не зависит ни от стартового распределения лампочек, ни от вероятности. Просто выполняешь и в определенный момент точно, без всяких вероятностей, знаешь ответ. Подуйте еще, если хотите, могу вам выслать решение на e-mail.
все просто: Решение верное, спрятал в спойлер. Михаил.
Show »
из вагона N в котором очнулись идем в одну сторону и выключаем свет в трех вагонах (N-1, N-2 и N-3) возвращаемся в вагон N включаем в нем свет. проходим в вагон N+1, N+2, N+3 если свет в них не горит, включаем свет в вагоне N+2 и бежим в вагон N-2 если свет там включился, считаем количество вагонов, если свет горит в одном из них, включаем свет в N+2, и смотрим вагоны N+3,4,5. если свет не горит во всех трех, включаем в N+4 и бежим в N-2 ну и т.д.
Сложновато но верно. Есть вариант проще:
Show »
В своём вагоне включаем свет, идем в одну сторону и выключаем, при этом считая вагоны. При каждом выключении ходим в начальный вагон и смотрим не выключился ли там свет. Как только выключился — это мы с другой стороны, подсчет можно окончить.
с точки зрения беготни, мой вариант экономнее. т.к. решение о том, что нужно бежать обратно принимается не каждый раз при выключении света в очередном вагоне, а при выявлении более редкого сочетания – свет не должен гореть сразу в трех «новых» вагонах
а если вагон один =) ?
да и спасибо за красивую задачку для собеседований, взял на вооружение
Советую оценить ещё эту задачу
Спасибо, но задачка для собеседований по моему профилю не подходит, т.к. компания управляющая.
можно в разы ускорить процесс:
каждый раз возвращаясь к контрольным вагонам – увеличивать их количество, скажем на те же 3 вагона…
Нам понадобится два целых числа – left, right. Light здесь для упрощения – массив состояния освещения в вагонах. Его размер мы узнать не можем.
Show »
Мы стоим в вагоне 0. min = max = Light[0]. Идем налево, left = Light[left+1] xor 1 (т.е. меняем освещение на противоположное) и запоминаем. Теперь топаем направо, right = Light[right-1] xor 1 (делаем то же самое, что и слева).
Ну а теперь двигаемся то влево, то вправо и делаем ту же процедуру, но сначала проверяем, уж не поменялось ли освещение, например:
if(left != Light[li]) ура, мы прошли все вагоны! (li – номер вагона, куда мы добрались слева)
Значит, всего вагонов – li*2.
Надеюсь, я понятно описал решение.
Да, а если мы справа обнаружили изменение освещения, то ri*2+1. Это в случае, если вагонов нечетное количество.
Да, у Goodways намного более экономное решение.
а если поезд бесконечный и невлезает в оперативную память =) ?
Мне алгоритмы решения выше показались запутанными.
Вот легче, хотя принцип тот же.
Show »
1. Значит во-первых найдем вагон с выключенным светом. Назовем ее начальной.
2. Включим.
3. Идем, например, вправо, пока не встретим включенную лампочку. Выключаем ее и идем обратно в начальный.
4. Если свет в начальном вагоне выключен. Значит мы сделали круг. Иначе снова 3.
Решение верное, тоже спрятал в спойлер
Tип Wagon имеет следующий интерфейс:
interface Wagon
{
bool IsOff(); /* выключен ли свет */
bool IsOn() /* включен ли свет */
void TurnOn() /* включить свет в вагоне */
void TurnOff() /* выключить свет в вагоне */
};
Тип WagonIterator – обёртка вокруг типа Wagon предназначенная для беготни по вагонам, то бишь в его интерфейсе есть операторы инкремента и декремента, а также оператор «стрелка» (->) для получения доступа к методам интерфейса Wagon.
Грубо говоря типичный STL like bidirectional iterator.
Тогда:
int GetSize(WagonIterator iterIndex)
{
int ret = 1;
iterIndex->TurnOn();
++iterIndex;
while ( iterIndex->IsOff() )
{
++iterIndex;
++ret;
}
iterIndex->TurnOff();
/* сместить итератор на ret позиций назад */
std::advance(iterIndex, -ret);
if ( iterIndex->IsOff() )
return ret;
/* здесь начинается рекурсия: */
return GetSize(iterIndex);
}
а если поезд бесконечный и не влезает в оперативную память =) ?
А что если, в одном вагоне включить лампу, во всех остальных выключать, таким образом, чтобы осталась одна лампа?
очухиваемся в вагоне, выключаем в нём свет, и двигаем в какую-либо сторону, попутно выключая свет во всех светящихся вагонах до тех пор, пока весь поезд не погаснет. это будет где-то 1.5 круга. потом включаем свет в вагоне, в котором стоим и шагаем, считая вагоны, пока не дойдём к светящемуся.