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

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

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

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

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

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

Пояснение

Решение:

Проследим путь. Направо 270 — это поворот налево на $90^\circ$ , голова смотрит вдоль отрицательного направления оси абсцисс. Первый цикл ведёт Черепаху из $(0;0)$ в $(-6;0)$ , затем поворот на $120^\circ$ — и отрезок длины 6 под углом $60^\circ$ к оси абсцисс. Команда Направо 120 и цикл Повтори 2 [Направо 120 Вперёд 3 Направо 240] сохраняют то же направление $60^\circ$ (каждый раз суммарный поворот кратен $360^\circ$ ) и добавляют ещё два отрезка по 3. Вместе получается один прямой отрезок длины $6+3+3=12$ из $(-6;0)$ в $(0;\,6\sqrt3)$ .

Наконец, Направо 240 и Повтори 2 [Вперёд 12 Направо 120] дают отрезок из $(0;\,6\sqrt3)$ в $(6;0)$ и отрезок из $(6;0)$ в $(-6;0)$ . Самый первый отрезок из $(0;0)$ в $(-6;0)$ лежит на этом основании и ничего нового не добавляет.

Итак, нарисован равносторонний треугольник со стороной 12 и вершинами $(-6;0)$ , $(0;\,6\sqrt3)$ , $(6;0)$ ; его площадь $\tfrac{\sqrt3}{4}\cdot 12^2=36\sqrt3\approx 62{,}4$ . Боковые стороны лежат на прямых $x=-6+\tfrac{y}{\sqrt3}$ и $x=6-\tfrac{y}{\sqrt3}$ , поэтому для каждой целой высоты $y$ от 1 до 10 годятся целые $x$ строго между этими границами:

$y=1$ : $|x|\lt 5{,}42$ — 11 точек;
$y=2$ и $y=3$ : $|x|\lt 4{,}85$ и $|x|\lt 4{,}27$ — по 9 точек;
$y=4$ и $y=5$ : $|x|\lt 3{,}69$ и $|x|\lt 3{,}11$ — по 7 точек;
$y=6$ : $|x|\lt 2{,}54$ — 5 точек;
$y=7$ и $y=8$ : $|x|\lt 1{,}96$ и $|x|\lt 1{,}38$ — по 3 точки;
$y=9$ и $y=10$ : $|x|\lt 0{,}81$ и $|x|\lt 0{,}23$ — по 1 точке.

Складываем: $11+9+9+7+7+5+3+3+1+1=56$ . Точки основания $y=0$ лежат на линии и не учитываются.

k = 3 ** 0.5
n = 0
for x in range(-6, 7):
    for y in range(1, 11):
        if -6 + y / k < x < 6 - y / k:
            n += 1
print(n)

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