Формальное исполнение алгоритмов (Робот, Черепаха, Чертёжник)

Зачем на экзамене

Формальный исполнитель выполняет команды буквально и не исправляет замысел автора. В заданиях 5, 6 и 12 нужно проследить изменение числа, строки, положения на поле или рисунка. Главный навык: отделить смысл команды от порядка ее выполнения.

Что нужно уметь

• определять начальное состояние исполнителя;
• выполнять команды строго слева направо;
• раскрывать циклы и учитывать точное число повторений;
• отслеживать координаты, направление и состояние пера;
• проверять допустимость движения Робота возле стен;
• восстанавливать исходное число обратными действиями;
• применять правила строкового редактора до остановки алгоритма.

База

Исполнитель и состояние

Исполнитель умеет выполнять конечный набор команд. Состояние содержит все данные, которые могут повлиять на следующий шаг: число, строку, координаты, направление, положение пера или стен вокруг клетки.

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

Робот

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

Черепаха и Чертёжник

Для графического исполнителя важны координаты, направление движения и состояние пера. Команда движения меняет положение. Поворот меняет только направление. При поднятом пере след не рисуется, но исполнитель продолжает перемещаться.

Если направление задается углом α, а исполнитель проходит расстояние d, изменение координат можно записать так:

После нескольких команд итоговое смещение равно сумме всех векторов перемещения. Для замкнутой фигуры исполнитель возвращается в начальную точку. Это не означает, что площадь фигуры равна нулю.

В цикле вида "повтори n раз" поворот выполняется столько же раз, сколько остальные команды тела. Если за один проход поворот равен β, общий поворот равен n * β. Для полного обхода замкнутого выпуклого многоугольника сумма внешних поворотов равна 360 градусам.

Числовой и строковый исполнитель

Числовой исполнитель применяет арифметические команды к текущему числу. Запись программы читается как последовательность номеров команд. Например, программа 121 означает: выполнить команду 1, затем 2, затем снова 1.

Если нужно найти исходное число по результату, двигайся от конца программы к началу и применяй обратные операции. Для команды "прибавь 4" обратной будет "вычти 4", для "умножь на 3": "раздели на 3". Деление должно давать допустимое значение из области исполнителя.

Строковый редактор заменяет фрагменты текста. Одна замена обычно меняет первое найденное вхождение, если условие не говорит иначе. В конструкции "пока нашлось" после каждой замены поиск начинается заново в уже измененной строке.

Как решать

Трассировка команд

1. Выпиши начальное состояние и расшифруй каждую команду.
2. Раздели программу на одиночные команды и циклы.
3. После каждого шага записывай новое состояние. Не считай несколько разных действий в уме.
4. Перед новой итерацией цикла снова проверь его условие.
5. Сверь итог с тем, что спрашивается: координата, число клеток, длина, площадь, число или строка.

Если есть длинный цикл

1. Найди изменение состояния за одну итерацию.
2. Проверь, не зависит ли следующая итерация от нового направления, стены или измененной строки.
3. Если все итерации одинаковы, умножь изменение на число повторений.
4. Если состояние повторилось, выдели полный период и отдельно обработай остаток.
5. Для рисунка проверь не только конечную точку, но и линии, проведенные между точками.

Если нужно подобрать вход

1. Начни с конечного результата.
2. Читай программу справа налево.
3. Заменяй каждую команду обратной операцией.
4. Проверь ограничения: целое ли число, нет ли запрещенного деления или недопустимого состояния.
5. Выполни исходную программу вперед и сравни результат с условием.

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

• Ошибка: выполнять программу в порядке, удобном для вычислений. Как избежать: не переставляй команды, даже если сложение и умножение выглядят знакомо.
• Ошибка: считать проверку условия частью тела цикла. Как избежать: отдельно отмечай момент проверки и момент выполнения команд.
• Ошибка: забывать поворот в последней итерации. Как избежать: раскрывай весь цикл как единый повторяемый блок.
• Ошибка: считать длину пути расстоянием между началом и концом. Как избежать: складывай длины всех пройденных отрезков.
• Ошибка: продолжать движение Робота через стену. Как избежать: проверяй границу перед каждой командой сдвига.
• Ошибка: заменять сразу все вхождения в строке. Как избежать: уточни семантику команды и после одной замены построй новую строку.

Проверь себя

1. Исполнитель выполнил команды "прибавь 3", затем "умножь на 2" над числом 4. Какой результат получился?
2. Черепаха четыре раза повторила команды "вперед 5", "направо 90". Вернулась ли она в начальную точку?
3. Что меняется после поворота Черепахи: координаты или направление?
4. Почему в строковом цикле нужно искать фрагмент заново после каждой замены?

Ответы: 1) 14; 2) да; 3) только направление; 4) замена меняет строку и положение следующих вхождений.

Связь с заданиями

В задании 5 обычно требуется проследить числовой алгоритм или подобрать входные данные. В задании 6 важны координаты, повороты, повторения и свойства построенного рисунка. Задание 12 проверяет буквальное выполнение правил строкового редактора. Во всех трех заданиях помогает таблица состояний после каждого шага.