Задача: AC1933

У исполнителя Вычислитель две команды, которым присвоены номера: **1. умножь на 4** **2. вычти 2** Первая из них увеличивает число на экране в 4 раза, вторая уменьшает его на 2. Составьте алгоритм получения **из числа 4 числа 28**, содержащий не более 5 команд. В ответе запишите только номера команд. *(Например, 11221 – это алгоритм:* *умножь на 4* *умножь на 4* *вычти 2* *вычти 2* *умножь на 4,* *который преобразует число 1 в 48.)* Если таких алгоритмов более одного, то запишите любой из них. --- Номер задачи: AC1933 📚 # Тема 05. Алгоритмы для формальных исполнителей На ОГЭ эта тема проверяет умение читать и выполнять алгоритмы вручную (исполнитель "Счётчик" или линейный вычислитель), а также восстанавливать начальные данные по результату. --- ## 1. Что такое формальный исполнитель **Формальный исполнитель** — абстрактный "робот", который выполняет команды строго по алгоритму, без понимания смысла. На ОГЭ обычно встречается исполнитель **"Счётчик"** с двумя командами: - **Команда 1:** прибавить число (например, +3) - **Команда 2:** умножить на число (например, ×2) --- ## 2. Прямая задача: найти результат **Дано:** начальное число X и последовательность команд. **Найти:** итоговое число. **Алгоритм:** 1. Запишите начальное число. 2. Применяйте команды строго по порядку. 3. Записывайте промежуточные результаты. **Пример:** Команды: 1 = "+5", 2 = "×3". Начало: X = 2. Программа: 1, 2, 1. | Шаг | Команда | Результат | |-----|---------|-----------| | Начало | — | 2 | | 1 | +5 | 7 | | 2 | ×3 | 21 | | 3 | +5 | **26** | --- ## 3. Обратная задача: найти начальное число **Дано:** последовательность команд и итоговое число. **Найти:** начальное число X. **Метод — идти с конца (обратный порядок):** - Вместо "+A" применяем "−A" - Вместо "×B" применяем "÷B" **Пример:** Команды: 1 = "+5", 2 = "×3". Программа: 1, 2, 1. Результат: 26. | Шаг (с конца) | Обратная команда | Результат | |---------------|-----------------|-----------| | Начало (с конца) | — | 26 | | Отменяем "+5" | −5 | 21 | | Отменяем "×3" | ÷3 | 7 | | Отменяем "+5" | −5 | **2** | Ответ: начальное число X = **2**. > **Совет:** Всегда применяйте обратные операции в **обратном порядке**. Сначала отменяем последнюю команду, потом предпоследнюю и т.д. --- ## 4. Задача: найти пропущенную команду **Дано:** начальное число, программа с одной пропущенной командой, результат. **Найти:** какая команда пропущена. **Метод:** 1. Выполните все известные команды до пропущенной → получите промежуточное число M. 2. После пропущенной продолжайте с "неизвестного" результата и дойдите до конца. 3. Составьте уравнение: M + X = результат (если пропущена "+X") или M × X = результат. --- ## 5. Алгоритм с циклом (линейная программа) Иногда программа записана числами, каждое из которых — номер команды: **Пример:** Программа `12112`, команда 1 = "+3", команда 2 = "×2". Начало: X = 1. | Шаг | Команда | Действие | Результат | |-----|---------|---------|-----------| | 1 | 1 | +3 | 4 | | 2 | 2 | ×2 | 8 | | 3 | 1 | +3 | 11 | | 4 | 1 | +3 | 14 | | 5 | 2 | ×2 | **28** | --- ## 6. Подсчёт количества способов ("путей") Задача: сколькими способами исполнитель может перейти от значения A к значению B, используя только разрешённые операции? **Метод динамического программирования:** 1. Создаём таблицу всех возможных значений от A до B. 2. Ставим 1 в ячейку A (один способ начать). 3. Для каждого значения X, если X → Y разрешено (применением команды), добавляем к Y количество путей до X. 4. Ответ — значение в ячейке B. **Пример:** Команды "+2" и "×3". Из 1 в 9. Диапазон: 1, 3, 7, 9... | Значение | Пути | |----------|------| | 1 | 1 | | 3 | 1 (из 1 × 3) | | 5 | 0 (недостижимо) | | 7 | 0 | | 9 | 1 (из 3 × 3) | --- ## 7. Типичные ошибки - **Выполнять команды не в том порядке.** Порядок важен: "×2 потом +3" ≠ "+3 потом ×2". - **При обратной задаче не инвертировать порядок.** Нужно идти с конца, а не с начала. - **Забыть один шаг.** Тщательно считайте шаги, особенно при длинных программах. - **Деление с остатком.** При обратном умножении убедитесь, что число делится без остатка — иначе начальное число нецелое (и задание поставлено иначе). --- ## 8. Лайфхаки для ОГЭ > **Совет:** Пишите все промежуточные результаты столбиком — это исключает арифметические ошибки. > **Совет:** В обратной задаче начните с конца и применяйте обратные операции. "Умножить на 2" обращается в "разделить на 2". > **Совет:** Если программа повторяет паттерн (например, команды 1, 2 повторяются), можно вычислить результат одного цикла и потом применить его нужное число раз.