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

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

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

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

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

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

Пояснение

Решение:

Поворот на $120^\circ$ — это внешний угол правильного треугольника, поэтому пара команд «Вперёд 10 Направо 120», выполненная три раза, возвращает Черепаху в исходную точку с исходным направлением. Семь повторений — это два полных обхода плюс ещё одна сторона поверх уже нарисованной, так что линия на плоскости — обычный равносторонний треугольник со стороной 10.

Найдём его вершины. Старт в точке $(0;0)$ , голова смотрит вверх, поэтому первая сторона идёт по оси ординат в точку $(0;10)$ . Дальше поворот и движение приводят в точку $(5\sqrt3;\ 5)$ , а третья сторона возвращает в начало координат. Итак, вершины: $(0;0)$ , $(0;10)$ и $(5\sqrt3;\ 5) \approx (8{,}66;\ 5)$ .

Левая сторона лежит на оси ординат, поэтому у внутренних точек $x \ge 1$ , а из $5\sqrt3 \approx 8{,}66$ следует $x \le 8$ . Нижняя сторона задаётся прямой $y = x/\sqrt3$ , верхняя — прямой $y = 10 - x/\sqrt3$ . Для каждого $x$ считаем целые $y$ строго между этими границами:

x	1	2	3	4	5	6	7	8
точек	9	7	7	5	5	3	1	1

В сумме $9 + 7 + 7 + 5 + 5 + 3 + 1 + 1 = 38$ . Для контроля: площадь треугольника равна $\frac{\sqrt3}{4} \cdot 10^2 \approx 43{,}3$ , что согласуется с полученным числом внутренних узлов.

from math import sqrt, ceil, floor

s = 10
total = 0
for x in range(1, floor(s * sqrt(3) / 2) + 1):
    lo, hi = x / sqrt(3), s - x / sqrt(3)
    total += len([y for y in range(ceil(lo), floor(hi) + 1) if lo < y < hi])
print(total)   # 38

Ответ: 38