РЕШУ ЕГЭ — информатика

Задания

Исполнитель Черепаха передвигается по плоскости и оставляет след в виде линии. Черепаха может выполнять три команды.

По команде Вперёд n Черепаха перемещается вперёд на n единиц.

По команде Направо m Черепаха поворачивается на месте на m градусов по часовой стрелке, при этом соответственно меняется направление дальнейшего движения.

По команде Налево m Черепаха поворачивается на месте на m градусов против часовой стрелки, при этом соответственно меняется направление дальнейшего движения.

В начальный момент Черепаха находится в начале координат и направлена вверх (вдоль положительного направления оси ординат), хвост опущен.

Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что заданная последовательность из S команд повторится k раз.

Черепахе был дан для исполнения следующий алгоритм:

Направо 315

Повтори 7 [Вперёд 16 Направо 45 Вперёд 8 Направо 135].

Определите, сколько точек с целочисленными координатами будет находиться внутри фигуры, ограниченной заданным алгоритмом линиями, не включая точки на линиях.

Решение. Воспользуемся средой КуМир, построим фигуру.

Посчитаем точки, находящиеся внутри фигуры. Получим 77.

Ответ: 77.

Приведём решение Евгения Джобса на языке Python.

Воспользуемся библиотекой turtle, предварительно направив голову черепахи вдоль оси ординат. Добавив две команды для быстрой отрисовки  — tracer(0) в начало алгоритма и update() в конец. Для большего масштаба увеличим каждое перемещение в 10 раз. После чего нанесем точки с целочисленными координатами. Так же не забудем унести команду update() в конец алгоритма.

from turtle import *

tracer(0)

left(90)

down()

right(315)

for _ in range(7):

forward(16*10)

right(45)

forward(8*10)

right(135)

for x in range(-15, 15):

for y in range(0, 25):

up()

goto(x*10, y*10)

down()

dot(3)

update()

Приведём решение Евгения Джобса (аналитическое).

Схематически построим след черепахи, последовательно выполнив команды из алгоритма до конца первой итерации.

Направо 315°

Вперед 16°

Направо 45°

Вперед 8°

Направо 135°

После первой итерации не находим замкнутую фигуру. Поэтому выполняем алгоритм для второй итерации.

Вперед 16°

Направо 45°

Вперед 8°

Направо 135°

Заметим, что исполнитель вернулся в точку, откуда началась первая итерация. Следовательно, остальные 5 итераций будут просто повторять рисунок поверх уже нарисованного следа.

При выполнении алгоритма стоит помнить текущие углы отклонения. Так, например, после первой команды исполнитель будет отклонен от оси Ox на 45 градусов, при следующем повороте отклонение будет на 90 градусов и так далее. Также из курса геометрии мы знаем, что линия, проведенная под углом 45 градусов, начинающаяся в точке (х, у) с целочисленными координатами, проходит через все точки с координатами (x + k, y + k), где k  — целое число. Также мы можем подсчитать количество точек с целочисленными координатами на правой вертикальной стороне  — точек всего 9. Теперь осталось найти количество вертикальных линий с шагом 1, которые пересекают фигуру. Для этого определим её длину через вычисления катетов равностороннего прямоугольного треугольника с гипотенузой длиной 16. Тогда:

$16 в квадрате =2 x в квадрате равносильно 128=x в квадрате ,$

откуда $x= корень из: начало аргумента: 128 конец аргумента \approx 11,3.$ Следовательно, количество точек внутри фигуры 7 · 11  =  77.

Приведём решение Ильи Андрианова на языке Python.

import turtle as t

t.left(90)

l = 20

t.begin_fill()

t.right(315)

for i in range(2):

t.forward(16 * l)

t.right(45)

t.forward(8 * l)

t.right(135)

t.end_fill()

count = 0

canvas = t.getcanvas()

for x in range(-100*l, 100*l, l):

for y in range(-100*l, 100*l, l):

z = canvas.find_overlapping(x, y, x, y)

if len(z) == 1 and z[0] == 5:

count += 1

print(count)

t.done()

Приведём решение Александра Козлова на языке Python.

from turtle import *

rt(225)

m = 10

begin_fill()

for i in range(2):

fd(16*m)

rt(45)

fd(8*m)

rt(135)

end_fill()

canvas = getcanvas()

k = 0

for x in range(-20,20):

for y in range(-20,20):

if canvas.find_overlapping(x*m,y*m,x*m,y*m) == (5,):

k+=1

print('Ответ:',k)

Приведём решение Сергея Донец на языке PascalABC.NET.

uses turtle;
begin
down;
TurnRight(315);
loop 7 do begin{Повтори 7
[Вперёд 16 Направо 45 Вперёд 8 Направо 135].}
Forw(16);TurnRight(45);Forw(8);TurnRight(135);
end;
end.

№ п/п	№ задания	Ответ
1	55802	77

Ключ