Задание 5 ОГЭ: как посчитать количество программ исполнителя?
В задании 5 бывает версия, где спрашивают не саму программу, а сколько всего программ переводят число A в число B. Как посчитать количество программ исполнителя, не перебирая все вручную? Это другой подход, чем обычное задание 5?
2 ответа
Да, «сколько программ» — отдельный подтип. Здесь не подбирают одну цепочку, а считают все возможные. Удобнее всего — методом динамического программирования (таблица количеств).
Идея. Для каждого числа считаем, сколькими способами в него можно попасть из старта. Количество способов попасть в число X = сумма способов попасть во все числа, из которых X получается одной командой.
Пример. Исполнитель: 1) +1, 2) ×2. Сколько программ переводят 1 в 6?
Идём от 1 вверх, для каждого числа пишем число способов K:
- K(1) = 1 (старт)
- K(2): из 1 (+1) и из 1 (×2) → K(1)+K(1) = 2
- K(3): из 2 (+1) → K(2) = 2 (×2 в 3 не попадает)
- K(4): из 3 (+1) и из 2 (×2) → K(3)+K(2) = 2+2 = 4
- K(5): из 4 (+1) → K(4) = 4
- K(6): из 5 (+1) и из 3 (×2) → K(5)+K(3) = 4+2 = 6
Ответ: 6 программ.
Алгоритм:
- Выпишите числа от старта до финиша.
- K(старт) = 1.
- Для каждого следующего числа сложите способы из всех «предшественников» (число, из которого оно получается одной командой).
- Ответ — K(финиша).
Частая ошибка: учитывают команду, которая в данное число не попадает (например, ×2 не даёт нечётное число). Проверяйте, действительно ли предшественник целый и допустимый.
Можно и деревом перебора, если чисел мало: рисуете от старта все ветви команд, пока не дойдёте до финиша, и считаете листья-финиши. Но при 5–6 шагах дерево разрастается, и легко сбиться.
Таблица «число способов на каждое число» (как выше) надёжнее и быстрее: один проход слева направо. Это классическая динамика, и тот же приём работает в более сложных задачах ЕГЭ про исполнителей.