it Задачи Помогите найти кота!
Помогите найти кота!

Помогите найти кота!

717
08 февраля 2021 в 16:45

В комнате стоят 5 коробок, и в какой-то из них сидит кот. Зачем нам нужен этот кот и к чему тратить время на его поиски? Конечно же, чтобы развивать алгоритмическое мышление!

В новой квартире после переезда остались стоять 5 пустых коробок, которые и полюбились коту: он начал в них спать. Коробки пронумерованы цифрами 1, 2, 3, 4, 5 и стоят в один ряд именно в таком порядке.


Проснувшись, кот выпрыгивает из коробки, а на следующую ночь отправляется спать в стоящую по соседству (слева либо справа) к той коробке, в которой он находился перед этим. Вам разрешается утром открыть лишь одну коробку и проверить, не в ней ли спит кот.


Нам неизвестно, в какой именно коробке кот ночевал в первый раз. Есть ли стратегия, позволяющая однажды гарантированно отыскать кота? Логику и жизненность в этой задаче искать не нужно, давайте просто начнем рассуждать.



Решение

Раз кот постоянно переходит спать в стоящую по соседству коробку, значит, он ночует по очереди то в четном «номере», то в нечетном. Воспользуемся этим для решения.


Вариант 1: Первую ночь кот провел в коробке с четным числом

То есть кот начал со второй или четвертой коробки. Предположим, первой мы откроем коробку №2: кот в ней – мы победили, если нет – то он спит в коробке №4. А раз так, значит, завтра он отправится ночевать в коробку №3 или №5. 


На следующий день смотрим в коробку №3: кот в ней – мы победили, если нет – то он находится в коробке №5. Это говорит о том, что ближайшей ночью он будет спать в четвертой коробке, так как у пятой другой соседней нет.


Третьим утром мы открываем коробку №4 и обнаруживаем в ней кота. Задача выполнена!


Вариант 2: Первую ночь кот провел в коробке с нечетным числом

Если предыдущий алгоритм не сработал, и кота в коробке №4 не оказалось, значит, он начал ночевать в нечетной коробке. Первое утро - нечетная коробка, второе утро – четная, третье – опять нечетная. 


Выходит, что на четвертую ночь кот будет спать снова в коробке с четным номером: или 2, или 4. Именно с этого мы начали поиски в предыдущем варианте, значит, нам нужно просто повторить описанную выше стратегию: по очереди открыть коробки №2, №3 и №4.

 

Старайтесь чаще думать над решением подобных задач, потому что разработчику очень важно регулярно качать свою «алгоритмическую мышцу»!


Больше интересных новостей

Комментарии для сайта Cackle