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

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

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

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

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

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

Пояснение

Решение:

За один проход тела цикла Черепаха поворачивает на $150^\circ + 30^\circ = 180^\circ$ , поэтому линия замыкается уже за два прохода, а остальные повторения обводят ту же фигуру. Стороны идут в порядке 7, 15, 7, 15, значит нарисован параллелограмм со сторонами 7 и 15 и углами $30^\circ$ и $150^\circ$ .

Проследим за движением. После «Направо 30» и «Направо 150» голова смотрит вниз, отрезок длины 7 ведёт из $(0;0)$ в $(0;-7)$ . Поворот на $30^\circ$ и отрезок длины 15 дают вершину $\left(-7{,}5;\ -7 - \frac{15\sqrt3}{2}\right)$ , затем сторона длины 7 поднимает Черепаху в $\left(-7{,}5;\ -\frac{15\sqrt3}{2}\right)$ , и последняя сторона возвращает её в начало координат.

Значит, две стороны параллелограмма вертикальны и имеют длину 7 — они лежат на прямых $x = 0$ и $x = -7{,}5$ , а две наклонные стороны лежат на прямых $y = \sqrt3\,x$ и $y = \sqrt3\,x - 7$ .

Точки на линиях не учитываем, поэтому $-7{,}5 \lt x \lt 0$ , то есть $x$ принимает 7 целых значений: от $-7$ до $-1$ . При каждом таком $x$ нужно $\sqrt3\,x - 7 \lt y \lt \sqrt3\,x$ . Это интервал длины ровно 7 с иррациональными концами, поэтому целых точек в нём всегда ровно 7. Итого $7 \cdot 7 = 49$ точек. Контроль: площадь параллелограмма равна $7 \cdot 15 \cdot \sin 30^\circ = 52{,}5$ .

from math import sqrt

total = 0
for x in range(-7, 0):
    lo, hi = sqrt(3) * x - 7, sqrt(3) * x
    total += len([y for y in range(-30, 5) if lo < y < hi])
print(total)   # 49

Ответ: 49