Ах, эти загадочные задания из ЕГЭ по информатике! Если бы их объясняли так же весело, как я сейчас попробую, может быть, и в школе не пришлось бы прятаться под партой с калькулятором.
Представьте себе: у нас есть исполнитель — такой цифровой волшебник, который умеет превращать одно число в другое с помощью магических команд. Но не просто так, а с условиями, словно мы играем в какую-то компьютерную игру уровня «Избегай злодеев и найди сокровище».
В двух предыдущих эпопеях мы уже научились считать количество способов превратить число А в число В, при этом либо обходя стороной определённое число (например, чтобы не наступить на мину), либо обязательно проходя через заданное число (чтобы забрать заветный ключ).
Теперь же нам предстоит объединить эти два правила — то есть одновременно избегать одного числа и обязательно посетить другое. Это как если бы вы решили пойти на вечеринку только через черный ход, но при этом обязательно заглянуть к соседу за солью. Вот такие вот ребусы.
Давайте разберёмся на конкретном примере — для тех, кто любит математику с перчинкой.
Задание 2322 звучит почти как сюжет для квеста: у нашего исполнителя есть три команды — прибавить 1, прибавить 2 и умножить на 2. Начинаем с числа 3 и хотим получить 20. Но внимание!
Траектория должна содержать число 7 (чтобы встретиться с драконом) и не содержать число 10 (иначе вас съест тролль). Сначала кажется, что это похоже на попытку пройти лабиринт с закрытыми глазами. Но нет! Мы пишем код — наш верный меч и щит — который проверяет каждый шаг.
Сначала говорим программе: если вдруг наступили на запретное число N (в нашем случае 10), то возвращаем ноль — то есть путь мёртвый конец.
Если дошли до цели — возвращаем единицу, что означает успешный маршрут. Потом применяем все три возможных действия к текущему числу x: прибавляем 1, прибавляем 2 или умножаем на 2 и суммируем количество способов дойти до цели из каждого нового состояния. Для удобства разбиваем путешествие на две части: от стартового числа до обязательной точки встречи (число M =7), а потом от неё до финала (20).
Перемножаем результаты — ведь без встречи с драконом дальше идти нельзя!
Запускаем программу и получаем ответ: целых семьсот девяносто две программы! Представляете? Почти восемь сотен вариантов обойти все ловушки и добраться до цели!
Как говорится, «если хочешь сделать хорошо — сделай много вариантов».
Если вам кажется сложным идти вперёд по числам — ничего страшного! В задании 2319 наш герой идёт в обратную сторону: от шестьдесят к единице. Тут команды другие: вычесть один или взять целую часть от деления на два (короче говоря, «делись пополам»).
И снова надо пройти через точку 20 и избежать опасного числа 4. Тут уже меняются условия сравнения в коде — теперь проверяем условие «x больше y», потому что идём вниз по числовой лестнице.
Результат? Целых тысяча семьсот шестьдесят способов спуститься без приключений!
Кто сказал, что движение назад проще? Иногда оно даже интереснее.
А теперь представьте ещё один пример с движением вверх — задача номер 2317: от трёх до восемнадцати нужно добраться так, чтобы встретиться с четырнадцатью и не попасться восьмёрке-ловушке. Казалось бы – мелочь какая-то восьмёрка!
Но для программиста это как минное поле. И тут мы уже не расписываем подробности – просто повторяем ту же схему волшебных преобразований и получаем… триста шестьдесят способов пройти успешно!