Задание 23: Исполнитель. Подсчёт программ-траекторий

1. Общая информация о задании

• Уровень сложности: повышенный (Часть 1, последнее задание)
• Максимальный балл: 1
• Примерное время выполнения: около 8–15 минут
• Проверяемый навык: умение анализировать результат исполнения алгоритма с ветвлением и циклом; подсчёт количества программ для формального исполнителя

Задаётся исполнитель с набором арифметических команд. Нужно подсчитать количество программ (последовательностей команд), которые преобразуют исходное число в результат, возможно, с ограничениями на траекторию вычислений (последовательность промежуточных результатов после каждой команды).

Задания: N23.Исполнитель графов изи | N23.Исполнитель графов ЕГЭШНЫЕ | N23.Исполнитель графов хард

2. Типичное задание

Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

A. Вычесть 3 B. Вычесть 4 C. Найти целую часть от деления на 3

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 47 результат — число 6, при этом траектория вычислений не содержит число 25 и содержит число 15?

Траектория вычислений — последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 105 траектория: 35, 31, 28.

3. Решение на Python

Основа решения — рекурсивная функция F(x, y), которая считает количество путей от текущего числа x до целевого y, применяя все команды исполнителя.

def F(x, y):
    if x == y: return 1   # дошли до цели — засчитываем путь
    if x < y:  return 0   # промахнулись (при движении вниз) — тупик
    if x > y:             # ещё не дошли — применяем все команды
        return F(x - 3, y) + F(x - 4, y) + F(x // 3, y)

Знаки в базовых случаях (x < y или x > y) зависят от направления:

• Число уменьшается (–3, –4, //3): провал при x < y
• Число увеличивается (+1, ×2): провал при x > y

4. Четыре типа задач и алгоритм решения

Тип 0: без ограничений на траекторию

# Исполнитель: +3, ×2. Из 1 получить 25.

def F(x, y):
    if x == y: return 1
    if x > y:  return 0
    return F(x + 3, y) + F(x * 2, y)

print(F(1, 25))   # Ответ: 9

Тип 1: траектория НЕ должна содержать число X

Добавляем запрещённое число в условие провала:

# Исполнитель: +1, 2x+1. Из 1 получить 25. Траектория НЕ содержит 24.

def F(x, y):
    if x == y:           return 1
    if x > y or x == 24: return 0   # запрет через or
    return F(x + 1, y) + F(x * 2 + 1, y)

print(F(1, 25))   # Ответ: 10

Несколько запрещённых чисел — просто расширяем условие:

if x > y or x == 9 or x == 16: return 0

Тип 2: траектория ДОЛЖНА содержать число X

Разбиваем путь на два отрезка и перемножаем результаты:

# Исполнитель: +1, ×2. Из 38 получить 2 (движение вниз). Траектория СОДЕРЖИТ 16.

def F(x, y):
    if x == y: return 1
    if x < y:  return 0
    return F(x - 2, y) + F(x // 2, y)

print(F(38, 16) * F(16, 2))   # Ответ: 36

Логика перемножения: каждый путь 38→16 можно продолжить любым путём 16→2. Итого вариантов = (пути в X) × (пути из X). Правило произведения комбинаторики.

Два обязательных числа — три отрезка:

# Из 2 получить 12. Траектория содержит 9 и 11.
print(F(2, 9) * F(9, 11) * F(11, 12))   # Ответ: 50

Тип 3: содержит X и НЕ содержит Y (комбинированный)

Разбиваем по обязательному числу X и запрещаем Y в каждом отрезке. forbidden — обязательный позиционный аргумент (без default), так корректно работает @lru_cache.

# Исполнитель: –3, –4, //3. Из 47 получить 6.
# Траектория НЕ содержит 25, НО содержит 15.

from functools import lru_cache

@lru_cache(maxsize=None)
def F(x, y, forbidden):
    if x == y: return 1
    if x < y or x == forbidden: return 0
    return F(x - 3, y, forbidden) + F(x - 4, y, forbidden) + F(x // 3, y, forbidden)

# Запрет числа 25 действует на оба отрезка
print(F(47, 15, 25) * F(15, 6, 25))   # Ответ: 107

Ловушка: если определить вторую функцию F в том же файле — она перезапишет первую и ответ будет неверным. Одна функция на всё решение.

5. Направление движения: вверх или вниз

6. Мемоизация: когда рекурсия зависает

При больших числах или многих командах одни и те же значения вычисляются повторно. Добавляем @lru_cache:

from functools import lru_cache

@lru_cache(maxsize=None)
def F(x, y):
    if x == y: return 1
    if x > y:  return 0
    return F(x + 1, y) + F(x * 3, y) + F(x + 2, y)

print(F(3, 9) * F(9, 14))   # Ответ: 112

На экзамене: если программа «думает» дольше 5 секунд, добавь @lru_cache — это первый шаг.

7. Табличный метод (для ручного счёта или проверки)

Восходящий подход без рекурсии. Заполняем массив A от начального числа до конечного.

Правило: A[i] = сумма A[j] для всех j, из которых командой можно получить i.

Пример: Из 1 получить 25, команды +3 и ×2.

• Строка «+3»: число, которое увеличивается на 3 даёт i → берём i − 3
• Строка «×2»: число, которое умножается на 2 даёт i → берём i / 2 (только если i чётное)
• A[i] = A[i−3] + A[i/2] (если i чётное, иначе только первое слагаемое)

Важно при обязательном числе X: при заполнении ячеек после X нельзя использовать значения ячеек до X — иначе учитываем пути, которые X обходят.

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

9. Краткий чек-лист решения

1. Определить направление движения: команды увеличивают или уменьшают число?
2. Записать базовые случаи: x == y → 1, x > y или x < y → 0.
3. Записать рекуррентный шаг: применяем все команды и суммируем.
4. Разобрать ограничения на траекторию:
   • НЕ содержит X → добавить or x == X в условие провала
   • СОДЕРЖИТ X → F(start, X) * F(X, end)
   • НЕ содержит X и СОДЕРЖИТ Y → разбить по Y, запретить X в каждом отрезке
5. Добавить @lru_cache при больших числах.
6. Запустить и проверить на простом примере с известным ответом.