Задание 23 ЕГЭ по информатике — количество программ исполнителя

О чём задание

Задание 23 — это классика динамического программирования в лёгкой форме. Тебе дан исполнитель (обычно он называется «Вычислитель»), который умеет делать несколько арифметических операций над натуральным числом. Нужно посчитать, сколько существует программ, преобразующих начальное число A в конечное число B.

Типовые формулировки:

• «Сколько существует программ, которые число 3 преобразуют в число 25?»
• «Сколько программ переводят 2 в 30, причём траектория проходит через 10?»
• «Сколько программ переводят 1 в 20, причём траектория не проходит через 7?»
• «Сколько программ из 1 в 12, которые содержат команду ×2 ровно один раз?»

В КЕГЭ 2026 всего 27 заданий, 29 первичных баллов и 235 минут; задание 23 стоит 1 балл (повышенный уровень). Полный обзор изменений — в статье ЕГЭ по информатике 2026 — что изменилось.

Почему тут ДП

Ключевая идея: каждое промежуточное число достигается из меньших. Если исполнитель умеет +1, ×2, +3, то число n можно получить:

• из n − 1 командой +1,
• из n / 2 командой ×2 (только если n чётное),
• из n − 3 командой +3.

Обозначим f(n) — количество программ, приводящих из A в n. Тогда:

f(n) = f(n − 1) + f(n / 2) [если n чётное и n/2 ≥ A] + f(n − 3) [если n − 3 ≥ A]

Это и есть рекуррентное соотношение. Считаем значения по порядку от A до B — получаем f(B), ответ.

Базовый шаблон на Python

Выучи наизусть. 90% задач 23 решаются именно в этой форме:

A, B = 3, 25           # подставь из условия

f = [0] * (B + 1)      # f[n] = количество программ из A в n
f[A] = 1               # единственная "пустая" программа в самом A

for n in range(A + 1, B + 1):
    f[n] = f[n - 1]                                   # команда +1
    if n % 2 == 0 and n // 2 >= A:
        f[n] += f[n // 2]                             # команда ×2
    if n - 3 >= A:
        f[n] += f[n - 3]                              # команда +3

print(f[B])

Разбор по строкам:

• f = [0] * (B + 1) — массив из B+1 нулей, индексы 0..B. Нули означают «пока ни одной программы не найдено».
• f[A] = 1 — в стартовой точке у нас одна программа: пустая (ничего не делать).
• Цикл for n in range(A + 1, B + 1) — заполняем таблицу от следующего после A до B включительно.
• Для каждой операции добавляем вклад предшественника, если он достижим и существует.

Почему f[A] = 1, а не 0

Потому что «достичь A из A» можно одним способом — ничего не делая (пустая программа). Если поставить f[A] = 0, все последующие значения тоже окажутся нулями. Это самая массовая ошибка новичков.

Разбор задачи 1: простая

Условие. Исполнитель умеет прибавлять 1 и умножать на 2. Сколько существует программ, которые число 3 преобразуют в число 12?

Моделируем

• Операция +1: n ← n+1
• Операция ×2: n ← n×2

Переход: в число n можно прийти из n − 1 (команда +1) или из n / 2 (команда ×2, если n чётное).

Ручной расчёт таблицы

Заполним таблицу по шагам:

n	откуда	f(n)
3	старт	1
4	3 (+1) + 2? (нет, 2 < 3)	1
5	4 (+1)	1
6	5 (+1) + 3 (×2)	1 + 1 = 2
7	6 (+1)	2
8	7 (+1) + 4 (×2)	2 + 1 = 3
9	8 (+1)	3
10	9 (+1) + 5 (×2)	3 + 1 = 4
11	10 (+1)	4
12	11 (+1) + 6 (×2)	4 + 2 = 6

Ответ: 6 программ.

Решение на Python

A, B = 3, 12

f = [0] * (B + 1)
f[A] = 1

for n in range(A + 1, B + 1):
    f[n] = f[n - 1]
    if n % 2 == 0 and n // 2 >= A:
        f[n] += f[n // 2]

print(f[B])  # 6

На КЕГЭ достаточно этих 8 строк. За 10 секунд ты уже имеешь ответ.

Разбор задачи 2: с обязательной точкой

Условие. Исполнитель умеет +1, ×2, +3. Сколько существует программ, переводящих число 2 в число 20, траектория которых содержит число 9?

Идея

Любая программа, проходящая через 9, разбивается на две независимые части:

1. Программа из 2 в 9 — считаем f(2 → 9).
2. Программа из 9 в 20 — считаем f(9 → 20).

Ответ: f(2 → 9) × f(9 → 20). Почему умножение? Потому что каждой программе первой части соответствует любая программа второй части — классический комбинаторный принцип произведения.

Решение

def count(A, B):
    f = [0] * (B + 1)
    f[A] = 1
    for n in range(A + 1, B + 1):
        f[n] = f[n - 1]
        if n % 2 == 0 and n // 2 >= A:
            f[n] += f[n // 2]
        if n - 3 >= A:
            f[n] += f[n - 3]
    return f[B]

print(count(2, 9) * count(9, 20))

Одна функция, два вызова, ответ готов. Если в условии несколько обязательных точек — просто цепляй ещё один множитель: count(A, X1) * count(X1, X2) * count(X2, B).

Разбор задачи 3: обход точки

Условие. Тот же исполнитель (+1, ×2, +3). Сколько программ переводят 2 в 20, не проходя через число 9?

Идея

Принцип включений-исключений:

ответ = (все программы из 2 в 20) − (программы из 2 в 20 через 9)

Первое слагаемое — count(2, 20). Второе — count(2, 9) × count(9, 20), как в предыдущей задаче.

total = count(2, 20)
through_9 = count(2, 9) * count(9, 20)
print(total - through_9)

Альтернатива: зануление

Можно сделать иначе — посчитать динамику, но в точке 9 обнулить значение. Тогда никакая программа, ведущая в 9, не сможет распространиться дальше.

A, B = 2, 20
forbidden = {9}

f = [0] * (B + 1)
f[A] = 1

for n in range(A + 1, B + 1):
    if n in forbidden:
        f[n] = 0
        continue
    f[n] = f[n - 1]
    if n % 2 == 0 and n // 2 >= A:
        f[n] += f[n // 2]
    if n - 3 >= A:
        f[n] += f[n - 3]

print(f[B])

Оба способа дают одинаковый ответ. Зануление удобнее, если запрещённых точек несколько — просто добавь их в forbidden и всё.

Таблица типов задач 23

Формулировка	Формула
Из A в B без ограничений	count(A, B)
Обязательно через X	count(A, X) × count(X, B)
Обязательно через X, потом Y (X < Y)	count(A, X) × count(X, Y) × count(Y, B)
Не проходит через X	count(A, B) − count(A, X) × count(X, B)
Обязательно через X, не проходит через Y	сложнее: комбинация умножения и зануления

Последний случай разбирай отдельно: удобнее всего через зануление forbidden = {Y} внутри двух вызовов count(A, X) и count(X, B).

Общий алгоритм подхода к задаче 23

1. Прочитать условие, выписать набор операций и числа A, B.
2. Определить тип задачи: «обычная», «через X», «не через Y», «через X, не через Y».
3. Написать функцию count(A, B) по шаблону.
4. Скомпоновать ответ формулой из таблицы выше.
5. Запустить, выписать результат на бланк.

Типичные ошибки

1. Забытый переход

Исполнитель умеет +1, +2, ×3 — а ты в коде учёл только +1 и ×3. Ответ будет занижен. Перед запуском кода прочитай условие ещё раз и сверь все операции с условиями в коде.

2. Не тот диапазон

Написал range(A, B + 1) вместо range(A + 1, B + 1) — и в первой итерации ты перезаписываешь f[A], обнуляя старт. Или наоборот, range(A + 1, B) — не досчитал последнее значение.

3. Неверная проверка «предшественник в диапазоне»

Операция ×2 даёт переход n/2 → n. Это значит, что предшественник n/2 должен быть ≥ A. Если написать n // 2 > A, ты пропустишь случай n // 2 == A. Правильно — n // 2 >= A.

4. f[A] = 0 вместо 1

Тогда вся таблица заполнится нулями. Типичная ошибка при копировании шаблона «из памяти».

5. Неправильный учёт чётности для ×2

Команда ×2 доступна, только если n чётное — иначе n / 2 не является целым. Проверка if n % 2 == 0 обязательна.

6. Перепутал обязательное и обход

«Через X» — умножаешь. «Не через X» — вычитаешь через включения-исключения. Если перепутать — ответ будет сильно отличаться (обычно в разы).

7. Несколько точек учёл как одну формулу

«Обязательно через X и Y» (X < Y) = count(A, X) × count(X, Y) × count(Y, B). Не надо писать count(A, X) × count(X, B) и забывать про Y.

Когда операции содержат вычитание

Иногда в условии исполнитель умеет −1 или /2. Это редкий, но неприятный случай: если есть операция уменьшения числа, динамика «слева направо» уже не работает — порядок заполнения зависит от того, как определяются траектории.

В реальных задачах ЕГЭ операции почти всегда монотонно возрастающие (+k, ×k). Если вдруг встретилась смешанная задача — ищи ограничения: «программа не проходит числа больше C», «длина программы не больше L» — они превращают задачу в ДП по парам (число, длина).

Тайминг на экзамене

Этап	Время
Прочитать условие, выписать операции и A, B	1-2 мин
Написать функцию count(A, B)	2-3 мин
Скомпоновать ответ (умножения, вычитания)	1-2 мин
Проверить на маленьком примере	1 мин
Выписать ответ	30 сек
Итого	6-10 мин

Если на задачу уходит 15 минут — не зацикливайся, перейди к следующему и вернись в конце. У тебя впереди задание 26 и задание 27, они дороже.

Шпаргалка: проверь шаблон на контрольной задаче

Перед экзаменом потренируйся на этой задаче и сверь: исполнитель умеет +1 и ×2, A = 1, B = 10. Сколько программ?

Правильный ответ: 55.

A, B = 1, 10
f = [0] * (B + 1)
f[A] = 1
for n in range(A + 1, B + 1):
    f[n] = f[n - 1]
    if n % 2 == 0:
        f[n] += f[n // 2]
print(f[B])  # 55

Получил 55 — шаблон правильный. Получил другое — ищи, где опечатался.

Как тренироваться

1. Реши 10-15 задач 23 разных типов из банка ФИПИ. Запиши в отдельный файл, какие операции встречаются чаще (опыт: +1, ×2, +3, иногда +2, ×3).
2. Для каждой задачи сначала попробуй руками построить первые 5-8 строк таблицы. Это тренирует понимание рекуррентности.
3. Затем проверяй себя кодом. Если ответы расходятся — ищи, где ошибся (обычно в ручном расчёте, но иногда в коде).
4. Через 2-3 недели такой практики шаблон будет отпечатываться в голове, и задание 23 станет автоматической «1 балл за 6 минут».

Подробнее о системе подготовки — в планах Подготовка за 3 месяца и за 6 месяцев.

Связанные задания

• Задание 22 — анализ программы с циклами — соседнее задание, часто тренируется в паре.
• Задание 27 — программирование на Python — там динамика усложняется, но принципы те же.
• Типичные ошибки на ЕГЭ по информатике — общий разбор провалов, в том числе на задании 23.

Если ты только начинаешь готовиться и база Python ещё шатает — пройди курс с нуля, а потом возвращайся к задачам 22-23. Без уверенного Python этот блок не вытянуть.

Короткий итог

Задание 23 — идеальная ситуация, когда выученный шаблон решает почти всё. У тебя есть функция count(A, B), есть 4-5 типов формулировок, и любая задача раскладывается в комбинацию из них. Зазубри код, разбери 10 задач разных типов — и на экзамене это будет гарантированный балл за 7-8 минут.

Главное — не забудь f[A] = 1 и правильные границы диапазона. Остальное — механическая сборка из блоков.