Задание №6 — Анализ алгоритмов для исполнителя

#69778Задание №6ФИПИ

Анализ алгоритмов и исполнители

Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори k [Команда1 Команда2 ... КомандаS] означает, что последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:
Направо 30 Повтори 10 [Вперёд 30 Направо 60 Вперёд 30 Направо 120].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

Правильный ответ

750

Пояснение

Решение:

За один повтор Черепаха поворачивает на $60^{\circ}+120^{\circ}=180^{\circ}$ , значит после двух повторов направление возвращается в исходное и контур замыкается. Остальные восемь повторов лишь обводят ту же линию заново.

Начальная команда Направо 30 направляет голову под углом $60^{\circ}$ к оси $Ox$ . Получаем четырёхугольник с вершинами $(0;0)$ , $(15;\,15\sqrt{3})$ , $(45;\,15\sqrt{3})$ , $(30;0)$ — это ромб со стороной 30 и углами $60^{\circ}$ и $120^{\circ}$ , его высота равна $15\sqrt{3}\approx 25{,}98$ .

Считаем по горизонтальным строкам. Нижняя и верхняя стороны горизонтальны ( $y=0$ и $y=15\sqrt{3}$ ), поэтому у внутренних точек $y=1,2,\dots,25$ — всего 25 строк.

Боковые стороны лежат на прямых $x=\dfrac{y}{\sqrt{3}}$ и $x=30+\dfrac{y}{\sqrt{3}}$ ; расстояние между ними по горизонтали ровно 30, а число $\dfrac{y}{\sqrt{3}}$ при целом $y\ge 1$ иррационально. Значит в каждой строке строго между границами лежит ровно 30 целых точек.

Итого $25\cdot 30=750$ . Проверим программой:

from math import sin, cos, radians

P = [(0.0, 0.0)]
x = y = 0.0
a = 90.0                      # голова смотрит вдоль оси Oy

def F(n):                     # Вперёд n
    global x, y
    x = round(x + n * cos(radians(a)), 9)   # round убирает шум float
    y = round(y + n * sin(radians(a)), 9)
    P.append((x, y))

def R(m):                     # Направо m
    global a
    a -= m

R(30)
for i in range(2):            # контур замыкается за 2 повторения
    F(30); R(60); F(30); R(120)

def inside(px, py):           # фигура выпуклая, обход по часовой стрелке
    for i in range(len(P) - 1):
        x1, y1 = P[i]; x2, y2 = P[i + 1]
        if (x2 - x1) * (py - y1) - (y2 - y1) * (px - x1) >= -1e-9:
            return False      # точка на линии или снаружи
    return True

xs = [p[0] for p in P]; ys = [p[1] for p in P]
print(sum(inside(px, py)
          for px in range(int(min(xs)) - 1, int(max(xs)) + 2)
          for py in range(int(min(ys)) - 1, int(max(ys)) + 2)))

Ответ: 750