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

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

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

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

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

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

150

Пояснение

Решение:

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

Итог — прямоугольник $18\times 9$ , повёрнутый на $45^\circ$ , с вершинами $(4{,}5\sqrt2;\,4{,}5\sqrt2)$ , $(-4{,}5\sqrt2;\,-4{,}5\sqrt2)$ , $(-9\sqrt2;\,0)$ , $(0;\,9\sqrt2)$ , то есть примерно $(6{,}36;\,6{,}36)$ , $(-6{,}36;\,-6{,}36)$ , $(-12{,}73;\,0)$ , $(0;\,12{,}73)$ .

Так как все стороны наклонены под $45^\circ$ , удобно перейти к «косым» координатам $s=x+y$ и $a=y-x$ . Подставив вершины, получаем, что прямоугольник задаётся условиями $0\le a\le 9\sqrt2$ и $|s|\le 9\sqrt2$ , а строго внутри лежат точки с $0\lt a\lt 9\sqrt2\approx 12{,}73$ и $|s|\lt 12{,}73$ .

Для узла решётки числа $s$ и $a$ целые и всегда одной чётности, а по паре $(s;a)$ точка $(x;y)$ восстанавливается однозначно, поэтому достаточно посчитать подходящие пары. Величина $a$ принимает значения от 1 до 12. Если $a$ нечётно (6 вариантов), то $s$ нечётно и $|s|\le 11$ — это 12 вариантов; если $a$ чётно (6 вариантов), то $s$ чётно и $|s|\le 12$ — это 13 вариантов. Всего $6\cdot 12+6\cdot 13=72+78=150$ .

c = 9 * 2 ** 0.5                 # 12.7279 -- длина 9*sqrt(2)
n = 0
for x in range(-20, 21):
    for y in range(-20, 21):
        s, a = x + y, y - x
        if 0 < a < c and -c < s < c:
            n += 1
print(n)

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