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