Тип 2
В прошлой статье мы познакомились с типизацией 23 задания ЕГЭ по информатике и разобрали алгоритм решения первого типа.
Мы научились писать программу так, чтобы она «обходила» стороной запрещённые числа в траектории вычисления. Но теперь перед нами стоит обратная задача: траектория вычисления обязательно должна содержать какое-то число, заданное в условии.
Давайте рассмотрим, как это отразится на алгоритме решения.
Алгоритм решения
Снова вернёмся к нашему примеру с преобразованием числа 1 в число 8 двумя командами:
- Прибавить 3
- Умножить на 2
Ранее мы уже поняли, что для того, чтобы исключить число из траектории, нужно добавить его в базовый случай, при котором функция возвращает 0. Теперь рассмотрим обратную ситуацию: что, если траектория обязательно должна проходить через определённое число?
Допустим, мы хотим найти количество способов получить из 1 число 8 так, чтобы по пути обязательно встретилось число 4. Вспомним изображение всех возможных путей из 1 в 8 из самой первой статьи:
Действительно, четвёрка есть сразу в двух траекториях:
- 1 → 2 → 4 → 8
- 1→ 4 → 8
Давайте внимательно посмотрим на обе траектории и найдём нечто общее. Их можно разделить на две части:
- Путь от 1 до 4 (1 → 2 → 4 и 1→ 4)
- Путь от 4 до 8 (4 → 8 в обоих случаях)
То есть любая подходящая траектория выглядит так: сначала мы как-то добираемся от 1 до 4, а затем как-то добираемся от 4 до 8. Число 4 становится промежуточной точкой, через которую проходят все допустимые пути.
Давайте разберём это на конкретном примере. Сначала найдём все способы добраться от 1 до 4. Их два:
- 1 → 2 → 4 (умножили на 2, потом ещё раз умножили на 2)
- 1 → 4 (прибавили 3)
Делаем вывод: обе команды могут привести из 1 к 4.
Теперь найдём все способы добраться от 4 до 8. Их тоже два:
- 4 → 8 (умножили на 2)
- 4 → 7 → 8 (прибавили 3, потом… стоп, 7 нельзя превратить в 8 нашими командами)
Здесь же иная ситуация: из 4 в 8 может привести только одна команда (умножить на 2).
А теперь самое интересное. Каждый путь первого этапа можно «склеить» с каждым путём второго этапа.
Представьте, что вы едете из Москвы в Казань через Нижний Новгород. От Москвы до Нижнего ведут, скажем, две дороги. От Нижнего до Казани — ещё одна. Сколько всего маршрутов?
Берём первую дорогу до Нижнего, потом единственную дорогу до Казани — вот один маршрут.
Берём вторую дорогу до Нижнего, потом ту же дорогу до Казани — вот второй маршрут.
Итого: 2 × 1 = 2 маршрута.
В нашей задаче то же самое. Путь «1 → 2 → 4» можно продолжить путём «4 → 8», получим полный маршрут «1 → 2 → 4 → 8». Путь «1 → 4» тоже можно продолжить путём «4 → 8», получим «1 → 4 → 8». Два пути на первом этапе, один путь на втором — всего 2 × 1 = 2 полных маршрута через четвёрку.
На деле тут в силу вступает комбинаторика. Это классическое правило: если первое действие можно выполнить m способами, а второе — n способами, то общее количество способов выполнить оба действия последовательно равно m × n. В нашем случае «первое действие» — это путь от старта до обязательной точки, а «второе действие» — путь от обязательной точки до финиша.
Теперь посмотрим, как это реализовать в коде. У нас была такая программа:
Теперь добавим обязательную точку нашего маршрута: число 4. То есть нужно найти количество способов получить из 1 число 8, при этом траектория вычислений должна содержать число 4. Для этого мы перемножим значения двух функций: f(1,4) и f(4,8):
В результате работы программы получаем ожидаемое число 2.
Теперь проверим этот подход на реальных заданиях. Начнём с такой формулировки:
«Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычесть 2
B. Найти целую часть от деления на 2
Сколько существует программ, для которых при исходном числе 32 результатом является число 1, и при этом траектория вычислений содержит число 14?»
Сразу отметим новую для нас операцию: «Найти целую часть от деления на 2». Да, звучит запутанно, но на деле это не что иное, как целочисленное деление, которое выполняется в Python с помощью оператора «//».
Первые два блока условий в наших функциях будут всегда одинаковы:
Далее добавляется третье условие, в котором применяем указанные операции к аргументу x функции:
И осталось лишь вывести на экран произведение двух функций — от 32 до 14 и от 14 до 1:
В результате получаем число 54, которое и будет ответом на это задание.
Пример 1
Рассмотрим похожее задание:
«Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами
A. Вычесть 1
B. Найти целую часть от деления на 2
Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 12?»
Здесь даже половина команд идентична прошлому заданию! Переписываем предыдущий код и меняем 2 на 1:
И добавляем вывод на экран произведения двух функций:
И получаем результат: число 376, которое и запишем в ответ.
Пример 2
Напоследок рассмотрим задание с такой формулировкой:
«Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Сколько существует программ, которые преобразуют исходное число 4 в число 15, и при этом траектория вычислений программы содержит числа 11 и 13? Траектория должна содержать оба указанных числа.»
Что же, теперь предстоит работать сразу с двумя числами в траектории. Но на деле это не добавит никаких сложностей, просто теперь будет произведение не двух, а трёх функций:
- От 4 до 11 — f(4, 11)
- От 11 до 13 — f(11, 13)
- От 13 до 15 — f(13, 15)
А в коде это записывается так:
Запускаем программу и получаем ответ — число 100.
Итоги
Как и в прошлой статье, давайте выведем шаблонный код для решения второго типа 23 заданий.
Здесь:
*1 — исходное число
*2 — число, которое должно быть в траектории
*3 — конечное число
*4 и *5 — команды из условия (+2, *3, **4 и так далее)
Не забудьте поменять знаки сравнения, если исходное число больше конечного!
На этом мы закончим работу со вторым типом 23 заданий. А в следующей статье разберём объединение обоих рассмотренных типов, где нам предстоит как исключать какие-то числа из траектории, так и, наоборот, обязательно включать числа в неё.
<<< Предыдущая статья Следующая статья >>>