Информатика · объяснение и практика

Исполнитель на клетчатом поле: почему команду нельзя угадывать

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Алгоритм, исполнитель и проверка · Учебная карта

Главная мысль

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

Сначала договоримся о языке и состоянии

Рассмотрим собственный учебный язык из трёх команд: «шаг», «налево» и «направо». Шаг переводит робота в соседнюю клетку перед ним. Налево и направо означают поворот на четверть оборота на месте. Направление задаётся словами север, восток, юг и запад. Координата x растёт вправо, y — вверх. Эти соглашения нужно сообщить до программы: без них короткая запись ещё не определяет движение однозначно.

Начальная клетка не заменяет начального направления. Из одной точки робот, смотрящий на север, и робот, смотрящий на восток, после команды «шаг» попадут в разные клетки. Поэтому таблица трассировки должна иметь три поля: x, y и взгляд. Запись только пройденных клеток способна скрыть неверный поворот, который пока не изменил положение. После каждой команды проверяют именно те части состояния, которые она должна изменить.

Одна команда изменяет только предусмотренное

Пусть поле содержит клетки с координатами от одного до пяти по каждой оси. Все клетки в разобранной программе свободны. Начальное состояние — клетка (2; 2), взгляд на восток. Запишем последовательно команды и состояния. Робот не выполняет сразу весь ожидаемый маршрут: следующая команда читает результат предыдущей, включая уже изменённое направление. Для проверки удобно отмечать взгляд короткой стрелкой рядом с клеткой.

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

Пример

Выполним указанную программу из (2; 2) с начальным взглядом на восток.

После первого шага получаем (3; 2), восток. Поворот даёт север без перемещения. Следующий шаг приводит в (3; 3). Второй поворот даёт запад, последний шаг — (2; 3). Конечное состояние: (2; 3), запад.

Препятствие не разрешает придумывать новую команду

Если перед роботом край поля или закрытая клетка, заранее определяют реакцию. В нашей дополнительной модели попытка недопустимого шага останавливает выполнение с сообщением об ошибке; автоматического обхода нет. В другой учебной системе команда могла бы оставлять робота на месте, но тогда это правило нужно указать отдельно. Нельзя менять его во время проверки только ради желаемого результата программы.

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

От чтения к действию

А теперь — вы

На свободном поле x растёт вправо, y вверх. Робот стоит в (3; 2), смотрит на запад. Выполнены «направо, шаг». Каково конечное состояние?

Частые вопросы

Поворот на месте переводит в соседнюю клетку?

Нет. В указанном языке он меняет только взгляд. Чтобы переместиться после поворота, требуется отдельная команда шага.

Можно ли узнать итог только по начальной клетке?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться