Конспект

Формальное исполнение алгоритмов

Трассировка Робота, Черепахи, Чертёжника и строкового редактора.

На экзамене

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

Исполнитель	Состояние	Что проверять
Робот	Клетка, стены, закрашенные клетки	Проходимость перед каждым сдвигом
Черепаха, Чертёжник	Координаты, направление, перо	Поворот не меняет координаты; поднятое перо не рисует
Числовой исполнитель	Текущее число	Порядок арифметических команд
Редактор	Текущая строка	Какое вхождение заменяется и когда цикл останавливается

\Delta x = d\cos\alpha,\quad \Delta y = d\sin\alpha

Итоговое смещение: сумма векторов всех перемещений.
Полный внешний поворот замкнутого выпуклого многоугольника: 360 градусов.
Обратные команды выполняются с конца программы: +a заменяется на -a, *a на /a.
В цикле "пока нашлось" поиск начинается заново после каждой замены.

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

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