Просмотр полной версии : Добрые инопланетяне
Добрые инопланетяне, прибывшие к нам на орбиту с дружественным визитом, для установления контакта любезно умыкнули Вас тепленьким к себе на корабль, буквально из постели от жены, убедились, что с галактическими языками у Вас не очень, согласно инструкции миссии просканировали Ваш мозг нейроспайдером, ну и из чистой любознательности загадали загадку. Отгадаешь, мол, - отпустим: "Наш корабль - он в виде тора, отсеки - сектора тора. Дверь вперед, дверь назад - все соединены. В отсеках включен свет, не во всех, а в случайном порядке. Можешь ходить по отсекам взад-вперед в любом направлении, можешь включать и выключать свет в любом отсеке сколько угодно раз. Требуется определить, сколько всего отсеков на корабле! Метить двери, отсеки мелом, пинком, разбитием лампочки или еще как нельзя."
И вот, стоите вы голый и ошарашенный босиком на холодном металлическом полу и озираетесь. Ни иллюминаторов, ни заметной кривизны стен или потолка, никаких косвенных признаков величины или направления кривизны тора не наблюдаете. Начинаете лихорадочно соображать, а можно ли, действительно, разгадать загадку, только включая и выключая свет в отсеках?
Домой-то хочется.
Nadir Zaitov
09.11.2012, 10:51
Домой-то хочется.
1. Нужно оговорить, что свет включенный сам не выключается и наоборот.
2. Нужно оговорить, что число комнат конечно, а то в 4-хмерном пространстве мы будем «заходить в разную воду». Межпланетный корабль может существовать в 4-х мерном пространстве (иначе тяжело двигаться между звездами с досветовой скоростью), стало быть тор может оказаться бутылкой Клёйна :).
3. Комнаты линейно соединены по секторам тора Это ж инопланетяне. У них всякое бывает.
4. Считать нам не запретишь.
Теперь об идеальном варианте. Решение есть,
1. Выключим за спиной свет и назовем эту комнату нулевой.
2. В первой комнате включим свет. Проверим, что за спиной свет не погас (комната не одна)
3. Установим N=1;
4. Включаем свет в 2^N комнатах. (включен в них или выключен свет был - не важно если включен, то считаем, что включили мы и только что)
5. Возвращаемся обратно до нулевой комнаты (отсчитывая 2^N комнат назад).
7. Если свет в нулевой комнате выключен, то увеличиваем N на единицу, и идем к пункту 3 выше.
6. Если свет в нулевой комнате включен, то выключаем его и начинаем считать комнаты начиная с первой по первую комнату с выключенным светом. Конец (ответ число комнат).
Так как число комнат конечно и зациклено линейным циклом, 2^N сремится к бесконечности с ростом N, то рано или поздно ответ мы найдем.
Timofeus
09.11.2012, 11:02
Если не ош., количество отсеков можно определить лишь с той или иной степенью вероятности.
Fedorov Stanislav
09.11.2012, 11:29
А что мешает сначала включить все а потом наматывая круги выключать отсеки друг за другом, засекая количество кругов.
Akmal Bafoev
09.11.2012, 11:32
А что мешает сначала включить все а потом наматывая круги выключать отсеки друг за другом, засекая количество кругов.
неизвестно общее количество, то есть их может быть сколь угодно большое конечное число.
Nadir Zaitov
09.11.2012, 13:17
А что мешает сначала включить всеТак вопрос же в том, что для того, чтобы "включить все" вы должны знать, что вы их все прошли. Комнаты условно абсолютно неотличимы. Так? Сначала нужно объять необъятное. Как только выяснится, что прошли все и веде включили свет, то дело конечно же простое: пометить начало и пересчитать. Это мы и сделали в самом конце.
Fedorov Stanislav
09.11.2012, 14:01
А естественные нужды организма в процессе подсчета не будут являться маркерами отсека?
Nadir Zaitov
09.11.2012, 14:29
А естественные нужды организма в процессе подсчета не будут являться маркерами отсека?
А вообще, это оффтоп в теме. Задачка поставлено достаточно ясно.
А где гарантия, что маркеры не зеркализируюутся в других комнатах или не будут убраны автоматикой инопланетян? Нет. Т.е. и надежды на них нет.
Случайный порядок предполагает, что возможны циклические повторения сочетаний тёмных и светлых отсеков, от 2 до бесконечности. При таком раскладе невозможно будет ответить наверняка сколько отсеков.
Vitaliy Fioktistov
09.11.2012, 20:26
По-моему, единственная проблема, как определить, что ты в данном отсеке уже был.
Например, включаем свет в той комнате, в которой находимся, далее идем вперед и в каждой из следующих комнат свет гасим. До тех пор, пока не дойдем до протяженного темного участка (например, 1000 комнат), который прерывается одной освещенной, после которой снова идет 1000 неосвещенных комнат и за ними снова одна освещенная.
При этом огромная вероятность, что мы уже ходим по кругу, но есть определенная вероятность, что мы нарвались на естественный участок и еще не дошли до нашей первой комнаты.
Vitaliy Fioktistov
09.11.2012, 20:45
Млять, как все просто. Решение от Dmitriy Skorobogatov (http://uforum.uz/member.php?u=6970).
1. Нумеруем комнату, в которой находимся, как нулевую.
2. Выключаем в ней свет
3. Устанавливаем свой внутренний счетчик в 0
4. Инкрементируем счетчик на 1
5. Идем в любом направлении на значение счетчика, включаем в этой комнате свет
5. Возвращаемся в нулевую (для этого просто отмотать назад количество комнат равное текущему значению счетчика)
6. Смотрим, включен ли свет в нулевой комнате. Если да - готово. Количество комнат = значению счетчика. Если нет, переходим к шагу 4.
Ну как то так вот))
shumbola
09.11.2012, 21:05
Vitaliy Fioktistov,
А теперь на PHP (ну или на любом другом языке) код, который реализовывает этот алгоритм выложите. ;-)
Evgeniy Sklyarevskiy
09.11.2012, 21:36
Смотрим, включен ли свет в нулевой комнате. Если да - готово. Количество комнат = значению счетчика. Если нет, переходим к шагу 4 То есть, при замыкании тора мы вернемся не в нулевую темную, а в следующую за ней первую со светом? В этом фишка? или я не так понял? Идея — супер!
А я хотел предложить 1 погасить потом 2 включить потом 3 погасить и пр... продолжать, пока не наткнемся на начало, потом потушить во 2й комнате и вернуться обратно для проверки.
Dmitriy Skorobogatov
10.11.2012, 09:12
То есть, при замыкании тора мы вернемся не в нулевую темную, а в следующую за ней первую со светом? В этом фишка?
Нет. Идея в том, что если в торе N комнат, то N-ая комната совпадет с 0-ой. Значит, включая свет в N-ой комнате, мы включаем свет в 0-ой. Убедившись, что в 0-ой комнате горит свет, мы заключаем, что в торе N комнат.
Nadir Zaitov
10.11.2012, 13:14
Млять, как все просто. Решение от Dmitriy Skorobogatov.А чем оно отличается от моего?
vBulletin® v3.8.5, Copyright ©2000-2025, Jelsoft Enterprises Ltd. Перевод: zCarot