🔁 Что такое рекурсия и почему она здесь нужна?
В программировании бывают задачи, где ответ нельзя угадать перебором и не вытащить формулой.
Где нужно не просто посчитать — а пройти все возможные пути, как будто сам становишься исполнителем, шаг за шагом выполняющим команды.
Именно так устроены задания, в которых речь идёт о последовательностях операций: прибавить, умножить, возвести в степень… Каждый выбор ведёт к новой ветке вычислений, и чтобы найти количество корректных программ, нужно обойти всё дерево возможностей.
Для этого есть один мощный инструмент — рекурсия.
Рекурсия — это когда функция вызывает саму себя.
В нашем случае — чтобы перебрать все возможные последовательности команд, которые ведут от начального числа к конечному.
Она позволяет не строить дерево вручную, а заставить программу саму спускаться по его ветвям, считая только то, что удовлетворяет условиям.
Далее — разбор всех типов задач номер 23 из ЕГЭ по информатике: как они устроены, какие «ловушки» ждут на экзамене, и почему даже небольшое изменение в условии требует полной перестройки логики.
🧩 Прототип 1: запрещённое число в траектории
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 2
B. Умножить на 3
C. Возвести в квадрат
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 49, при этом траектория вычислений не содержит числа 13?
Полный код решения:
Как это работает:
- F(3, 49) — старт.
- Если a == 13 — сразу возвращаем 0: такой путь запрещён.
- Иначе — пробуем все три команды: +2, *3, **2.
- Рекурсия идёт до тех пор, пока не достигнем 49 или не выйдем за пределы.
💡 Ловушка: если проверку a == 13 поставить после a > b, то при a = 13 и b = 10 условие a > b сработает первым, и запрет не учтётся.
Поэтому проверка на запрещённое число — сразу после равенства.
🧩 Прототип 2: обязательное число в траектории
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 1
B. Найти целую часть от деления на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является число 1 и при этом траектория вычислений содержит число 8?
Полный код решения:
Почему умножение?
Потому что:
- F(30, 8) — сколько программ ведут от 30 до 8,
- F(8, 1) — сколько программ ведут от 8 до 1,
- любая комбинация первой части и второй даёт полную программу через 8.
⚠️ Важно: если бы требовалось «содержать 8 и 5», пришлось бы разбивать на три отрезка: 30→5→8→1 или 30→8→5→1 — и суммировать оба варианта.
Но в этой задаче — только одно обязательное число → достаточно одного умножения.
🧩 Прототип 3: фиксированная последняя команда
У исполнителя есть три команды, которым присвоены номера:
A. Прибавить 2
B. Прибавить 3
C. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 20, а последняя в них команда - A или С?
Полный код решения:
⚠️ Важно: в условии сказано — последняя команда — A или C.
Это означает: если последняя команда — A (+2), то перед ней должно быть число 20 − 2 = 18, если последняя команда — C (×2), то перед ней — 20 / 2 = 10 (и 10 — целое, значит, допустимо), команда B (+3) исключена — поэтому 20 − 3 = 17 не учитывается.
Поэтому ответ — сумма:
- количества программ из 3 → 18,
- плюс количество программ из 3 → 10.
🧩 Прототип 4: ограничение на количество применений каждой команды
Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Умножь на 5
2. Умножь на 3
3. Прибавь 45
Первая команда умножает число на экране на 5, вторая – умножает на 3, третья – увеличивает на 45. Сколько существует различных программ, которые преобразуют исходное число 1 в число 2970, и при этом траектория вычислений не более 4 команд «умножь на 5», не менее 2 команд «умножь на 3», и ровно 5 команд «прибавь 45»?
Что делают параметры:
- p1 — сколько раз применили *5,
- p2 — сколько раз *3,
- p3 — сколько раз +45.
На финише (a == b) проверяем, соблюдены ли условия.
💡 Ловушка: если не передавать счётчики в рекурсию, вы не узнаете, сколько раз была использована каждая команда.
Обычная F(a, b) здесь не сработает.
Запись на занятия здесь: https://t.me/nka39
🧩 Прототип 5: ограничение на количество применений одной команды
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
А. Вычесть 2
В. Умножить на 2
С. Умножить на 3
Программа для исполнителя — это последовательность команд. Например, для программы СВА при исходном числе 3 траектория будет состоять из чисел 9, 18, 16.
Сколько существует программ, которые преобразуют исходное число 6 в число 48 и при этом содержат не более двух команд А?
Особенности:
- a > 52 — и-за того что есть возвратная команда (минус 2), мы можем немного превысит лимит b
- p > 2 — если уже использовали 3 команды «вычесть 2», дальше нет смысла идти.
⚠️ в отличие от предыдущей задачи, здесь только один счётчик — потому что ограничена только одна команда.
🧩 Прототип 6: запрет на две подряд идущие команды
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены буквами:
A. Вычесть 1
B. Умножить на 2
C. Умножить на 3
Программа для исполнителя – это последовательность команд. Например, программа BAC при исходном числе 2 последовательно получит числа 4, 3, 9
Сколько существует программ, которые преобразуют исходное число 3 в число 15 и при этом не содержат двух команд A подряд?
Как работает запрет:
- параметр s хранит последнюю выполненную команду,
- если s != 'A', можно использовать любую команду,
- если s == 'A', команду 'A' пропускаем.
✅ Это действенный способ учесть порядок команд, а не только их количество.
🧩 Прототип 7: очень большое число и кэширование
Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить последнюю цифру
B. Добавить остаток от деления на 68
C. Возвести в квадрат
Программа для исполнителя – это последовательность команд.
Команда А прибавляет к числу его последнюю цифру. Например, из числа 68 получится число 76.
Команда B прибавляет к числу его остаток от деления на 68. Например, из числа 10 получится число 20.
Команда C возводит число в квадрат. Например, из числа 9 получится число 81.
Если после выполнения команды получается такое же число, то команду нельзя применять к этому числу. Например, к числу 10 нельзя применить команду A, так как 10 + 0 = 10.
Сколько существует программ, для которых при исходном числе 2 результатом является число 680, при этом траектория вычислений содержит число 68 и не содержит числа 100?
Зачем @lru_cache?
Потому что без кэширования одни и те же значения F(a, b) будут вычисляться миллионы раз, и программа будет работать очень долго и может вообще зависнуть.
💡 Ловушка: если забыть про кэш, даже правильный код не успеет выполниться за время экзамена.
🔹 Условие применимости команд:
- Команда A (+ последняя цифра) нельзя применять, если последняя цифра = 0 → тогда a + 0 == a.
- Команда B (+ остаток от деления на 68) нельзя применять, если a % 68 == 0 → тогда a + 0 == a.
- Команда C (возвести в квадрат) всегда применима, кроме случая a == 1 (но в нашей задаче a ≥ 2, и 1² = 1, но у нас a = 2 и растёт, так что C всегда меняет число).
Если a % 10 == 0, но a % 68 != 0
→ команда A запрещена (последняя цифра 0 → a + 0 = a),
→ можно применить только B и C:
Если a % 10 != 0, но a % 68 == 0
→ команда B запрещена (остаток 0 → a + 0 = a),
→ можно применить только A и C:
Если a % 10 == 0 и a % 68 == 0
→ команды A и B обе запрещены,
→ можно применить только C:
📌 Главное — что запомнить
Все задачи №23 сводятся к рекурсивному перебору с разными условиями:
- запрет на число → if a == X: return 0,
- обязательное число → F(start, X) * F(X, finish),
- ограничение на количество команд → передавать счётчики,
- запрет на последовательность → передавать последнюю команду,
- большие числа → использовать @lru_cache.
И да — все эти задачи решаются одним и тем же шаблоном, только с разными деталями.
➕ А что насчёт второго типа задачи 23?
Есть и другой вид задания 23 — где вместо «сколько программ» спрашивают «сколько различных результатов можно получить за определенное число шагов».
Но это — тема для следующей статьи.
Если Вам информация была для Вас полезна, то можно поддержать автора, нажав на кнопку "Поддержать".
Подпишитесь на канал и научитесь решать все задания ЕГЭ по информатике!
Удачи на экзамене!
Записаться ко мне на занятия можно тут https://t.me/nka39