Формальные исполнители алгоритмов: команды и блок-схемы (ЕГЭ)

Коротко о главном

Формальный исполнитель — объект (реальный или воображаемый: Робот, Черепаха, Чертёжник, вычислитель чисел), который выполняет только команды из своей строго заданной системы команд (СКИ), точно и без «понимания смысла». Каждая команда меняет состояние исполнителя (позицию, значение переменной, содержимое поля) по чётко описанному правилу. Алгоритм для исполнителя записывается либо линейной последовательностью команд, либо блок-схемой с циклами и условиями. Задача ЕГЭ — трассировать выполнение: применить команды к начальным данным и получить результат, либо восстановить/подобрать алгоритм по заданному результату.

Определения и правила

Понятие	Суть
Исполнитель	Объект с конечным набором допустимых команд (СКИ) и средой (обстановкой)
Команда	Элементарное действие, меняющее состояние среды/исполнителя
СКИ	Полный список команд, которые исполнитель понимает; вне СКИ команды недопустимы
Алгоритм	Конечная последовательность команд, приводящая от начальных данных к результату
Цикл ПОКА <условие> ... КОНЦ	Тело выполняется, пока условие истинно; проверка — перед выполнением тела
Цикл ДЛЯ i от a до b	Тело выполняется фиксированное число раз (при a≤b — b−a+1 раз)
Ветвление ЕСЛИ...ТО...ИНАЧЕ	Выбор одной из двух ветвей по условию
Блок-схема	Графическое представление алгоритма: прямоугольник — действие, ромб — условие, стрелки — порядок выполнения

Типовые СКИ на экзамене:

• Робот: закрасить клетку; переместиться вверх/вниз/влево/вправо (шаг выполняется только если нет стены, иначе — авария/останов); проверка условий «сверху свободно», «слева стена» и т.п.
• Чертёжник/Черепаха: сместиться на вектор $(dx, dy)$; повернуть на угол; при движении рисуется отрезок.
• Вычислитель чисел: команды вида «умножить на $a$», «прибавить $b$»; часто нужно найти минимальную длину программы, переводящей число $A$ в $B$, или все различные результаты при обходе всех цепочек команд заданной длины.

Общее правило трассировки: состояние $S_0 \to$ (команда 1) $\to S_1 \to$ (команда 2) $\to S_2 \to \dots \to S_n$ — результат.

Для циклов «ПОКА» число итераций заранее неизвестно и зависит от данных, поэтому важно на каждом шаге проверять условие до входа в тело.

Как применять (примеры)

Пример 1. Вычислитель. СКИ: 1) прибавить 1; 2) умножить на 2. Найти кратчайшую программу, переводящую 3 в 16. Решение: работаем от конца к началу. $16=2\cdot 8$, $8=2\cdot 4$, $4=2\cdot 2$? — но проще от начала: $3\to4(+1)\to8(\times2)\to16(\times2)$ — 3 команды. Проверка альтернатив длиной 2 невозможна ($3\times2=6$, $3+1=4$; из этих чисел за один шаг 16 не получить). Ответ: 3 команды — «+1, ×2, ×2».

Пример 2. Робот, цикл ПОКА. Команда «вправо» перемещает робота на 1 клетку, если справа нет стены. Алгоритм:

ПОКА справа свободно
  вправо
КОНЦ
закрасить

Робот сдвигается вправо, пока не встретит стену, затем закрашивает клетку у стены. Если изначально справа стена — сразу закрашивается стартовая клетка.

Пример 3. Блок-схема с ветвлением (аналог задания 6/18). Дано: переменная $x$. Блок-схема: ромб «$x>10$?» → ветка «да»: $x:=x-5$; ветка «нет»: $x:=x+3$; далее выход. При $x=8$: условие ложно → $x:=8+3=11$. При $x=12$: условие истинно → $x:=12-5=7$.

Типичные ошибки

• Применять команду, не входящую в СКИ, или игнорировать условие применимости (например, шаг «вправо» при стене справа — это не движение, а авария/невозможность выполнения).
• Путать порядок проверки условия и тела цикла: в цикле «ПОКА» условие проверяется перед каждым выполнением тела, а не после.
• Ошибка в подсчёте числа итераций «ДЛЯ»: забывают, что диапазон включает обе границы, число повторов — $b-a+1$.
• При поиске кратчайшей программы для вычислителя перебирают не все ветки дерева команд или не учитывают, что порядок команд влияет на результат (умножение и сложение не коммутируют относительно друг друга).
• Неверное чтение блок-схемы: путают ветви «да»/«нет» у ромба, забывают про циклический возврат стрелки к условию.
• Механическая ошибка при трассировке — потеря промежуточного значения переменной на одном из шагов.

Где встречается на экзамене

• Задание 5 — определить результат выполнения короткого алгоритма (часто вычислитель чисел или Робот) для заданных исходных данных.
• Задание 6 — трассировка программы/алгоритма с циклами и условиями, часто на псевдокоде, аналогичном блок-схеме.
• Задание 12 — работа с исполнителем на поле (Робот, Чертёжник): подобрать или проанализировать алгоритм, определить итоговое состояние обстановки.
• Задание 18 — сложные алгоритмы с циклами и ветвлениями, включая перебор вариантов и поиск числа возможных результатов или количества команд.