Задание №6 — Анализ алгоритмов для исполнителя
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост поднят. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует три команды: Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке; Опустить хвост, означающая переход в режим рисования.
Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последователность из S команд повторится k раз.
Черепахе был дан для исполнения следующий алгоритм:
Вперёд 100 Направо 90 Вперёд 100 Направо 30 Опустить хвост Повтори 10 [Вперёд 25 Направо 90].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.
Правильный ответ
625
Пояснение
Решение:
Сначала проследим за движением с поднятым хвостом — эта часть пути ничего не рисует. Из точки Черепаха идёт вверх на 100 и оказывается в ; поворот направо на 90° направляет голову вдоль оси ; ещё 100 единиц вперёд — и она в точке . Поворот направо на 30° отклоняет голову на 30° ниже оси .
Здесь хвост опускается. В команде Повтори 10 [Вперёд 25 Направо 90] каждые четыре шага замыкают квадрат со стороной 25, поэтому за 10 повторений Черепаха обходит один и тот же квадрат два с половиной раза — новых линий не появляется. Нарисованная фигура — квадрат со стороной 25, повёрнутый на 30°, с вершиной в точке .
Стороны квадрата направлены вдоль двух взаимно перпендикулярных единичных векторов:
Точка лежит строго внутри квадрата тогда и только тогда, когда обе её проекции на эти направления строго между 0 и 25:
Остаётся перебрать целые точки в окрестности квадрата:
from math import sqrt
c = 0
for x in range(70, 131):
for y in range(60, 111):
a = (x - 100) * sqrt(3) / 2 - (y - 100) / 2
b = -(x - 100) / 2 - (y - 100) * sqrt(3) / 2
if 0 < a < 25 and 0 < b < 25:
c += 1
print(c)
Программа выводит 625. Отметим, что теорема Пика здесь неприменима: вершины повёрнутого квадрата (кроме ) не попадают в узлы решётки. Тем не менее ответ совпал с площадью квадрата .
Ответ: 625