ЕГЭ информатика 23 задание разбор, теория, как решать.
ЕГЭ-Информатика — Задание 23: Полный разбор и готовые шаблоны
Задание 23 сводится к подсчёту количества программ (путей) из числа x в число y по разрешённым
командам. Часто добавляются условия: «не содержит …», «обязательно содержит …», «A раньше B», «хотя бы одно из множества», и т. п.
Идея: используем рекурсию с мемоизацией (
functools.lru_cache) или динамику «снизу-вверх»; запреты и обязательные точки учитываем в базах/флагах.1) База: считаем число программ
Монóтонно вверх (например +1, +2, *2)
|
1 2 3 4 5 |
def f(x, y): if x == y: return 1 if x > y: return 0 # перепрыгнули цель return f(x+1, y) + f(x+2, y) + f(x*2, y) |
Монóтонно вниз (например -1, -4, //3)
|
1 2 3 4 5 |
def f(x, y): if x == y: return 1 if x < y: return 0 # идём вниз return f(x-1, y) + f(x-4, y) + f(x//3, y) # целая часть от деления на 3 |
Смешанные команды (и вверх, и вниз): задайте разумные границы (например, если x сильно вырос — вернуть 0) и обязательно используйте
lru_cache.2) Запрет «не содержит K»
|
1 2 3 4 5 6 7 |
BAD = {7} # запрещённые числа def f(x, y): if x in BAD: return 0 if x == y: return 1 if x > y: return 0 return f(x+1, y) + f(x+2, y) + f(x*2, y) |
3) Обязательная точка «содержит A»
Разбиваем маршрут и перемножаем: количество путей x → … → A → … → y равно f(x,A) * f(A,y).
|
1 2 3 |
ans = f(19, 13) * f(13, 2) # прошли через 13 print(ans) |
4) «Содержит A и не содержит B»
Запрет — в теле f, обязательную точку учитываем умножением сегментов.
|
1 2 3 4 5 6 7 8 9 |
BAD = {7} def f(x, y): if x in BAD: return 0 if x == y: return 1 if x < y: return 0 return f(x-1, y) + f(x-4, y) + f(x//3, y) ans = f(19, 13) * f(13, 2) |
5) «Содержит хотя бы одно из {A, B}»
Вариант A. Включения–исключения (коротко и быстро)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
def f(x, y): if x == y: return 1 if x > y: return 0 return f(x+1, y) + f(x*2, y) + f(x*3, y) def through(k): # x → k → y return f(6, k) * f(k, 48) def through_both(a, b): # x → a → b → y (в порядке) return f(6, a) * f(a, b) * f(b, 48) ans = through(14) + through(18) - through_both(14, 18) |
Вариант B. Счётчик посещений (универсально)
|
1 2 3 4 5 6 7 8 9 |
T = {14, 18} def g(x, y, seen=False): if x in T: seen = True if x == y: return 1 if seen else 0 if x > y: return 0 return g(x+1, y, seen) + g(x*2, y, seen) + g(x*3, y, seen) ans = g(6, 48) |
6) Порядок «A раньше B»
Последовательно перемножаем сегменты:
|
1 2 |
ans = f(12, 40) * f(40, 72) * f(72, 89) # через 40, затем 72 |
Если есть запрет (например, «не содержит 56»), добавьте if x == 56: return 0 в f.
7) «Хотя бы одно из T, но не содержит Z»
|
1 2 3 4 5 6 7 8 9 10 11 |
BAD = {56} T = {40, 72} def f(x, y, seen=False): if x in BAD: return 0 if x in T: seen = True if x == y: return 1 if seen else 0 if x > y: return 0 return f(x+3, y, seen) + f(x+7, y, seen) + f(x*3, y, seen) ans = f(12, 89) |
8) Готовые «боевые» примеры
Демо-2026: 19 → 2, команды -1, -4, //3, не содержит 7, обязательно 13
|
1 2 3 4 5 6 7 8 9 |
BAD = {7} def f(x, y): if x in BAD: return 0 if x == y: return 1 if x < y: return 0 return f(x-1, y) + f(x-4, y) + f(x//3, y) print(f(19, 13) * f(13, 2)) |
ФИПИ 2025 (пример): 3 → 18, команды +1, +2, *2, обяз. 14, запрет 8
|
1 2 3 4 5 6 7 8 9 |
BAD = {8} def f(x, y): if x in BAD: return 0 if x == y: return 1 if x > y: return 0 return f(x+1, y) + f(x+2, y) + f(x*2, y) print(f(3, 14) * f(14, 18)) |
«Хотя бы одно из {14,18}»: два способа
Используйте включения–исключения (короче) или счётчик посещений (гибче).
9) Динамика «снизу-вверх» (без рекурсии)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
# пример: +1, +2, *2 — считаем путей из 3 в 18, запрещая 8 N = 100 dp = [0]*(N+1) dp[3] = 1 for x in range(3, 19): if x == 8: dp[x] = 0 continue if x+1 <= N: dp[x+1] += dp[x] if x+2 <= N: dp[x+2] += dp[x] if x*2 <= N: dp[x*2] += dp[x] print(dp[18]) |
10) Частые ошибки
- Неверные базы. Для «вверх» задач:
if x > y: return 0, для «вниз»:if x < y: return 0; совпадение:if x == y: return 1(с учётом флагов). - Запрет/условие проверяют поздно. Ставьте проверку сразу при входе в
f. //путают с «делится на 3». Команда «найти целую часть от деления на 3» — это всегдаx//3, разрешена всегда.- Смешанные операции без ограничений приводят к блужданию. Вводите лимиты и используйте
@lru_cache. - Обязательные точки удобнее учитывать умножением сегментов:
f(x,A)*f(A,y),f(x,A)*f(A,B)*f(B,y).
11) Мини-шпаргалка: условие → код
- Не содержит K:
if x == K: return 0 - Не содержит множество:
if x in BAD: return 0 - Содержит A:
f(x,A)*f(A,y) - Содержит A раньше B:
f(x,A)*f(A,B)*f(B,y) - Содержит хотя бы одно из T: включения–исключения или флаг
seen - Содержит A, но не содержит B: запрет в
f+ умножение сегментов - Содержит хотя бы k из T: счётчик
cntи базаreturn 1 if cnt >= k else 0
Эти шаблоны покрывают большинство формулировок 23-го задания: подставьте свои команды, границы и условия — получите короткое и надёжное решение.