Исполнители и оптимальные программы

Главное

Задачи с исполнителями проверяют умение строить программу по системе команд. Часто требуется найти программу минимальной длины.

Правила

1. Исполнитель имеет строго заданную систему команд
2. Решение ищут перебором или обратным ходом от результата
3. Часто помогает динамическое программирование по числу способов
4. Важно точно учитывать порядок команд

Разберём пример

Как искать программу минимальной длины?

Удобно идти от конечного числа назад к начальному, на каждом шаге выбирая операцию, которая быстрее сокращает разрыв, и проверяя варианты.

Частые ошибки

• Применять команды, отсутствующие в системе исполнителя
• Не проверять все ветви перебора

Потренироваться

Задания с проверкой и подсказками, схема темы и разбор ошибок с ИИ-репетитором — в уроке на платформе.