Тема 05. Алгоритмы для формальных исполнителей

🏠 Главная / Теория / Тема 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 повторяются), можно вычислить результат одного цикла и потом применить его нужное число раз.

Назад к списку