Задание №6 — Анализ алгоритмов для исполнителя
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 5 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.
Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Повтори 6 [Направо 90 Вперёд 1 Направо 90 Вперёд 11]
Поднять хвост
Вперёд 3 Направо 90 Вперёд 5
Опустить хвост
Повтори 10 [Вперёд 12 Направо 90].
Определите, сколько точек с целочисленными координатами будут находиться внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на линиях.
Правильный ответ
193
Пояснение
Решение:
Первый цикл: две итерации [Направо 90 Вперёд 1 Направо 90 Вперёд 11] уже возвращают Черепаху в исходную точку с исходным направлением, поэтому шесть итераций — это один и тот же прямоугольник, обведённый три раза. Его вершины: , , , , то есть , . Целых точек в нём вместе с границей .
При поднятом хвосте Черепаха переходит: Вперёд 3 — в , Направо 90 — голова смотрит вправо, Вперёд 5 — в . Второй цикл Повтори 10 [Вперёд 12 Направо 90] рисует квадрат со стороной 12, который замыкается уже после четырёх итераций; десять итераций обводят тот же квадрат два с половиной раза. Его вершины: , , , , то есть , , и целых точек в нём .
Фигуры не пересекаются и даже не касаются: у первой , у второй . Поэтому в объединении точки.
Ответ: 193