Сколько программ исполнителя: рекурсия и динамика
Коротко
Исполнитель преобразует число командами (например, «прибавить 1» и «умножить на 2»). Число программ, переводящих a в b, считают рекурсией: f(a, b) = f(a + 1, b) + f(2a, b), f = 1 при a = b, f = 0 при a > b. Если траектория обязана содержать число c, ответ — f(a, c)·f(c, b); если не должна содержать d, то в функции при a = d возвращают 0. В ЕГЭ 2027 эта тема — задание 13.
Рекурсия
def f(a, b):
if a > b:
return 0
if a == b:
return 1
return f(a + 1, b) + f(a * 2, b)
print(f(1, 20)) # все программы
print(f(1, 10) * f(10, 20)) # через 10
Ограничения
| Условие | Как учитывать |
|---|---|
| Траектория содержит c | f(a, c) · f(c, b) |
| Не содержит d | в функции: если a == d — вернуть 0 |
| Команда уменьшает число | добавить ограничение, чтобы не уйти в бесконечность |
Динамика вручную
Заполните таблицу от a до b: число способов прийти в x = сумма способов прийти во все числа, из которых x получается одной командой.
Типичные ошибки
- Забывают условие a > b → 0.
- Учитывают обязательное число дважды.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 13
Пример 1 из 2
Команды: +1 и ×2. Сколько программ переводят 2 в 12?
- Разбор
- Рекурсия f(2, 12) даёт 10.
- Ответ
- 10
Пример 2 из 2
Команды: +1 и ×2. Сколько программ переводят 1 в 20, если траектория содержит 10?
- Разбор
- f(1, 10)·f(10, 20) = 14·2 = 28 (проверено программой).
- Ответ
- 28
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Чему равно f(a, b) при a = b?
Показать ответ
Ответ: 1.
Пустая программа.
- Вопрос 2 из 5
Чему равно f(a, b) при a > b?
Показать ответ
Ответ: 0.
Команды только увеличивают число.
- Вопрос 3 из 5
Как учесть обязательное число c?
Показать ответ
Ответ: f(a, c)·f(c, b).
Произведение.
- Вопрос 4 из 5
Как исключить число d?
Показать ответ
Ответ: Вернуть 0 при a == d.
Траектория через d запрещена.
- Вопрос 5 из 5
Сколько программ переводят 3 в 12 (+1, ×2)?
Показать ответ
Ответ: 6.
Проверено перебором.
Проверьте всё задание 13, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти