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

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

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

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

Черепахе был дан для исполнения следующий алгоритм:
Направо 180
Повтори 3 [Направо 45 Вперёд 11 Направо 45]
Направо 315 Вперёд 11 Направо 90 Вперёд 22
Повтори 2 [Направо 90 Вперёд 11].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом. Точки на линии учитывать не следует.

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

353

Пояснение

Решение:

Черепаха проводит семь отрезков: 11, 11, 11, 11, 22, 11 и 11. Повороты между соседними отрезками равны $90^\circ$ везде, кроме стыка циклов, где поворот $45^\circ+315^\circ=360^\circ$ ничего не меняет: третий и четвёртый отрезки продолжают друг друга и дают одну сторону длины 22.

Получается замкнутая шестиугольная «уголковая» фигура с вершинами $(0;0)$ , $(-5{,}5\sqrt2;\,-5{,}5\sqrt2)$ , $(-11\sqrt2;\,0)$ , $(0;\,11\sqrt2)$ , $(11\sqrt2;\,0)$ , $(5{,}5\sqrt2;\,-5{,}5\sqrt2)$ и сторонами 11, 11, 22, 22, 11, 11. По существу это повёрнутый на $45^\circ$ квадрат со стороной 22, из которого вырезан угловой квадрат со стороной 11; площадь равна $22^2-11^2=363$ .

Все стороны наклонены под $45^\circ$ , поэтому перейдём к «косым» координатам $s=x+y$ , $a=y-x$ . Большой квадрат превращается в $|s|\le 11\sqrt2$ , $|a|\le 11\sqrt2$ , а вырезанный угол — в четверть $s\le 0$ , $a\le 0$ . Строго внутри фигуры лежат точки с $|s|\lt 11\sqrt2\approx 15{,}56$ и $|a|\lt 15{,}56$ , для которых не выполняются одновременно $s\le 0$ и $a\le 0$ .

Для узла решётки $s$ и $a$ — целые числа одной чётности, и пара $(s;a)$ однозначно задаёт точку. Если оба нечётные, то каждое пробегает 16 значений от $-15$ до 15, это $16\cdot 16=256$ пар, из которых $8\cdot 8=64$ попадают в вырезанный угол — остаётся 192. Если оба чётные, то каждое пробегает 15 значений от $-14$ до 14, это $15\cdot 15=225$ пар, из них в углу $8\cdot 8=64$ — остаётся 161. Итого $192+161=353$ .

c = 11 * 2 ** 0.5                # 15.5563 -- длина 11*sqrt(2)
n = 0
for x in range(-25, 26):
    for y in range(-25, 26):
        s, a = x + y, y - x
        if -c < s < c and -c < a < c and not (s <= 0 and a <= 0):
            n += 1
print(n)

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