О задании
В прошлой статье мы познакомились с динамическим программированием и научились находить количество способов преобразовать одно число в другое.
Эти знания пригодятся нам для решения задания 23 ЕГЭ по информатике. В таких заданиях представлен исполнитель с заданным набором команд — как правило, это арифметические действия: сложение, умножение, извлечение корня и другие.
В условии указано начальное число, к которому применяются команды, и конечное число, которое нужно получить определённой комбинацией этих команд. Последовательность промежуточных результатов при выполнении команд называется траекторией вычислений.
Кроме того, на траекторию накладываются ограничения. Здесь стоит рассмотреть типы заданий 23:
- Первый тип: траектория не должна содержать определённое число.
- Второй тип: траектория обязательно должна содержать определённое число.
- Третий тип: траектория должна содержать одно число и не содержать другое.
- Четвёртый тип: ограничения накладываются на количество команд. Но, обычно, это авторские задачи, которые на реальном экзамене не встречаются. Так что разбирать их решение мы не будем.
Сейчас же мы вспомним код из предыдущей статьи и научимся решать задания первого типа.
Алгоритм решения
Начнём с небольшой ретроспективы. Ранее мы искали количество способов преобразовать число 1 в 8, используя две команды:
- Прибавить 3
- Умножить на 2
Для решения мы написали такую функцию:
Здесь x — начальное число (1), y — конечное (8). В коде реализованы два базовых случая и рекуррентное соотношение:
- Базовый случай 1 (x == y): мы достигли цели — функция возвращает 1.
- Базовый случай 2 (x > y): мы «перескочили» нужное число — этот путь не ведёт к цели, возвращаем 0.
- Рекуррентное соотношение (x < y): применяем к x каждое действие и суммируем результаты: f(x + 3, y) + f(x * 2, y). Здесь использовать оператор if необязательно, можно просто написать return f(x + 3, y) + f(x * 2, y)
Почему именно сумма — мы разбирали ранее.
Итак, функция проверяет все возможные пути изменения числа. Например, при двукратном вызове f(x + 3, y) траектория будет такой: 1 → 4 → 7.
Давайте подумаем, как запретить программе проходить по траектории с нежелательным числом? Допустим, траектория не должна содержать число 4.
Логично добавить это ограничение ко второму базовому случаю: как траектория с «перескоком» нас не устраивает, также не подходит и траектория с запрещённым числом.
Следовательно, в нашей задаче мы бы изменили код таким образом:
Таким образом, у нас теперь есть два случая, когда траектория нам не подходит и функция должна возвращать 0:
- Если число х оказывается больше конечного
- Если число х является запрещённым
Давайте теперь на практике проверим данную логику. Рассмотрим задание с такой формулировкой:
«Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11?»
Начало у функции будет всегда одинаковым:
Далее нам необходимо определить два условия базового случая:
- Когда x > y
- Когда x = 11
Теперь, если x всё еще меньше y будем вызывать функцию f() с каждой из заданных команд:
Осталось лишь добавить вывод на экран результата работы функции с аргументами 2 и 20:
В результате получаем число 37.
Пример 1
Рассмотрим еще одно задание:
«Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
А. Вычесть 1
В. Вычесть 2
С. Найти целую часть от деления на 3
Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит чисел 9 и 16?»
В этом задании нам необходимо добавить сразу два числа в условие. Но сложностей в этом нет никаких, просто также через оператор or проверяем равенство переменной x числам 9 и 16.
И еще один момент: раньше мы всегда двигались по возрастанию: исходное число было меньше конечного. Здесь же обратная ситуация. Следовательно, все знаки сравнения (< и >) нам следует поменять на обратные!
Таким образом, если наше проверяемое число x будет либо меньше конечного (3), либо по траектории вычисления примет значения 9 или 16, то будет возвращаться 0. Это будет означать, что данная траектория вычислений нам не подходит.
А продолжать рекурсивно вызывать функцию f() мы будем только, если переменная x больше конечного числа (y).
В остальном – без изменений. Код будет таким:
В конце работы программы получаем число 180.
Пример 3
В заключение рассмотрим задание с такой формулировкой:
«Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 3
С. Умножить на 5
Сколько существует программ, для которых при исходном числе 2 результатом является число 90, при этом траектория вычислений не содержит чисел 18 и 30?»
Снова работаем с двумя числами и движемся «вверх».
И решается данное задание следующим образом:
В результате получаем число 145, которое и запишем в ответ.
Итоги
Давайте выведем шаблонный код для решения 23 заданий первого типа.
Начнём с ситуации, когда исходное число меньше конечного:
Здесь:
*1 — исходное число
*2 — конечное число
*3 — число, которое не должно быть в траектории
*4 и *5 — команды из условия (+2, *3, **4 и так далее)
Если же исходное число больше конечного, то знаки сравнения меняются на противоположные:
Условные обозначения без изменений.
На этом завершаем разбор первого типа задания 23. В следующей статье научимся решать задания, где определённое число должно присутствовать в траектории.