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

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

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

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

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

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

123

Пояснение

Решение:

После Направо 30 голова Черепахи направлена под углом $60^\circ$ к оси абсцисс. Первый цикл даёт два отрезка длины 12 с поворотом на $120^\circ$ между ними, затем Направо 300 — это поворот налево на $60^\circ$ , и второй цикл добавляет ещё два таких же отрезка. Всего четыре стороны длины 12, а суммарный поворот $120^\circ+60^\circ+120^\circ+60^\circ=360^\circ$ , то есть линия замыкается.

Это ромб со стороной 12 и углами $60^\circ$ и $120^\circ$ ; его вершины $(0;0)$ , $(6;\,6\sqrt3)$ , $(12;\,0)$ , $(6;\,-6\sqrt3)$ . Горизонтальная диагональ равна 12, вертикальная — $12\sqrt3\approx 20{,}78$ , площадь $12^2\sin 60^\circ=72\sqrt3\approx 124{,}7$ .

Считать удобно по вертикалям. Стороны ромба лежат на прямых $y=\pm\sqrt3\,x$ и $y=\pm\sqrt3\,(12-x)$ , поэтому точка $(x;y)$ лежит строго внутри тогда и только тогда, когда $0\lt x\lt 12$ и $|y|\lt \sqrt3\cdot\min(x,\,12-x)$ . Перебираем $x=1,\dots,11$ ; по симметрии столбцы $x$ и $12-x$ дают одинаковое количество точек:

$x=1$ и $x=11$ : $|y|\lt 1{,}73$ — по 3 точки;
$x=2$ и $x=10$ : $|y|\lt 3{,}46$ — по 7 точек;
$x=3$ и $x=9$ : $|y|\lt 5{,}20$ — по 11 точек;
$x=4$ и $x=8$ : $|y|\lt 6{,}93$ — по 13 точек;
$x=5$ и $x=7$ : $|y|\lt 8{,}66$ — по 17 точек;
$x=6$ : $|y|\lt 10{,}39$ — 21 точка.

Складываем: $2\cdot(3+7+11+13+17)+21=102+21=123$ . Вершины $(0;0)$ и $(12;0)$ в подсчёт не попали — они лежат на линии.

k = 3 ** 0.5
n = 0
for x in range(1, 12):
    for y in range(-21, 22):
        if abs(y) < k * min(x, 12 - x):
            n += 1
print(n)

Программа выводит 123. Ответ: 123