Черепаха, или задача 6 ЕГЭ по информатике

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне

 

 В задаче 6 ЕГЭ по информатике используется "исполнитель Черепаха", заимствованный из Кумира - системы для обучению детей программированию. Черепаха передвигается по координатной плоскости и чертит за собой линию. В задачах задается алгоритм её движения и требуется подсчитать, сколько точек с целочисленными координатами находится внутри замкнутого контура, который она нарисует. Ниже мы рассмотрим способы решения этих задач с помощью простых программ на Питоне. Однако для написания этих программ часто требуются некоторые сведения из алгебры, геометрии и тригонометрии (впрочем, не слишком-то обширные). 

На сайтах, посвященных ЕГЭ по информатике и в роликах на youtube часто предлагается решать эти задачи в Кумире или рисованием на листе в клеточку. Лично я не рекомендую такие способы: если линия проходит слишком близко к точке, то трудно точно установить, лежит ли эта точка внутри контура или вне его. Программное решение лишено этих недостатков.

Относительно программного решения данных задач хочу сделать важное предупреждение. На известном сайте "Решу ЕГЭ" приводятся решения задачи 6 на Питоне с использованием модуля turtle. Однако этот модуль в стандартную поставку Питона не входит, поэтому не надо надеяться на его наличие в том компьютере, который предоставят в ваше распоряжение для сдачи ЕГЭ. По этой причине в данной статье модуль turtle не используется.

Команды черепахи

Черепаха умеет исполниять всего четыре команды. Команда "вперед" - это продвижение на указанную в команде длину в текущем направлении её движения. Команда "направо" - поворот направо на указанный угол в градусах. (Очевидно, что угол между прежним и новым направлением движения - это угол, смежный с указанным в команде. Так, если выдана команда "Направо 120", то угол между отрезками, которые черепаха прочертит перед и после этой команды, составит 60 градусов.) Ещё есть команды "поднять/опустить хвост" - если хвост опущен, черепаха чертит за собой линию, если поднят, то нет. 

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

Как правило, перед выполнением программы черепаха находится в начале координат, начальное направление движения - в положительном направлении оси "Y" (строго вверх), хвост опущен (хотя возможны варианты).

Иногда используются также команды "Назад" и "Налево" - смысл их очевиден. 

Теперь перейдём к конкретным задачам.

Квадраты и прямоугольники

Если углы, на которые поворачивается черепаха, равны 90 градусам, то она рисует на плоскости квадрат или прямоугольник.  (Если вам попадется такая задача, то вам повезло: программу писать не придется, всё решается на бумаге за минуту-другую.)

Вот пример такой задачи. Черепахе дается алгоритм:

Повтори 4 [Вперёд 10 Направо 90]

Требуется подсчитать количество точек с целочисленными координатами внутри контура. Точки на линиях учитывать не следует.

При первом исполнении цикла черепаха двигается по оси "Y" вверх и останавливается в точке с координатами (0:10), после чего поворачивается на 90 градусов вправо - теперь она будет двигаться вправо параллельно оси "X". При втором она придет в точку с координатами (10;10), новое направление движения - вниз параллельно оси "Y". При третьем - она окажется  в точке на оси "X" с координатами (10;0). Наконец, при четвертом она вернется в исходную точку (в начало координат), нарисовав квадрат со стороной 10. Точки внутри этого квадрата имеют координаты 0<x<10 и 0<y<10. Точек с целочисленными координатами внутри квадрата, очевидно, 81 (9*9). Иногда требуется учитывать и точки на линиях. Таких точек 121 (11*11).

А вот пример алгоритма, который нарисует прямоугольник:

Повтори 4 [Вперёд 5 Направо 90 Вперёд 10 Направо 90]

Прямоугольник имеет высоту 5 и ширину 10. Заметим, что черепаха обойдёт этот прямоугольник дважды. При первом исполнении цикла будет нарисована его левая и верхняя стороны, при втором - правая и нижняя. Третье и четвёртое выполнение цикла - повторение действий при первом и втором выполнении. Число точек внутри этого прямоугольника без учета точек на границах - 36 (4*9), а с учетом - 66 (6*11). 

Треугольники

Следующий алгоритм рисует треугольник:

Повтори 7 [Вперёд 10 Направо 120]

 Сначала черепаха переместится на 10 единиц вверх и окажется в точке (0;10). Затем она повернется на 120 гредусов вправо. Новое направление движения - вправо и вниз, под углом 30 градусов к горизонтали (и под углом 60 градусов к отрезку, который она только что прочертила). Напишем уравнение линии, по которой будет двигаться черепаха:

y=10-x/sqrt(3) 

Пояснение: уравнение прямой линии записывается в виде y=kx+b, где k - это угловой коэффициент, он равен тангенсу наклона прямой к оси "X", а тангенс 30 градусов - это sqrt(3)/3 или 1/sqrt(3).  

Переместившись на 10 единиц вдоль этой линии, черепаха окажется в точке с координатами x=10*cos(30)=5*sqrt(3) и y=10-10*sin(30)=5: (10/sqrt(3):5). Там она снова повернется на угол 120 градусов, новое направление движения - влево и вниз под углом 30 градусов к горизонтали. Пройдя 10 единиц по этому направлению, черепаха снова окажется в начале координат, начертив равносторонний треугольник со стороной 10 елиниц, одна из сторон которого лежит на оси "Y". Далее черепаха пойдет по линиям, которые она уже прочертила. 

Уравнение для верхней стороны треугольника мы уже написали. Нижняя сторона выходит из начала координат под углом 30 градусов к горизонтали, её уравнение

y=x/sqrt(3)

Подсчитаем количество точек с целочисленными координатами внутри этого треугольника. Он лежит справа от оси "Y". Точки на границах не учитываются, поэтому x>=1. Координата y должна быть выше нижней линии и ниже верхней: x/sqrt(3)<y<10-x/sqrt(3).

Вот программа для подсчета:

k=0

for x in range(1,10):

for y in range(10):

if x/3**0.5<y<10-x/3**0.5: k += 1

print(k)

 

Ответ: 38 точек.

Параллелограммы и ромбы

Следующий алгоритм рисует ромб:

Повтори 4 [Вперёд 10 Направо 60 Вперёд 10 Направо 120]

 Сперва черепаха поднимается на 10 единиц по оси "Y" и оказывается в точке (0;10). Там направление движения изменяется: новое направление - направо и вверх под углом 30 градусов к горизонтали. Пройдя 10 единиц в этом направлении, она придет в точку (5*sqrt(3);15). Следующее направление движения - точно вниз параллельно оси "Y", конечная точка - (10/sqrt(3);5). Затем черепаха будет двигаться влево и вниз и вернется в начало координат, после чего пройдет по сторонам этого же ромба вторично.

Подсчитаем количество точек внутри данного ромба. Он ограничен двумя вертикальными сторонами: x=0, x=10/sqrt(3) и двумя наклонными: y=x/sqrt(3) (нижняя) и y=x/sqrt(3)+10 (верхняя). 

Программа для подсчета точек внутри этого рамба следующая:

 

k=0

for x in range(20):

for y in range(20):

if (0<x<5*3**0.5) and (x/3**0.5<y<x/3**0.5+10): k += 1

print(k)

 

Ответ: 80.

Вот ещё один пример ромба:

Повтори 4 [Вперёд 8 Направо 150 Вперёд 8 Направо 30]

В данной задаче начальное направление - не вдоль оси "Y", как обычно, а вдоль оси "X".

Сначала черепаха перемещается по оси "X" и оказывается в точке (8;0). Затем она движется влево и вниз под углом 30 градусов к горизонтали и оказывается в точке (8-4*sqrt(3);-4). Затем - горизонтально влево, до точки (-4*sqrt(3);-4). После этого она возвращается в исходную точку и проходит по ромбу второй раз.

В данной задаче лучше выражать уравнения наклонных прямых как функции x(y). Они таковы: левая прямая - x=y*sqrt(3), а правая - x=y*sqrt(3)+8.

Вот программа для подсчета точек:

k=0

for x in range(-8,8):

for y in range(-5,0):

if (-4<y<0) and (y*3**0.5<x<y*3**0.5+8): k += 1

print(k)

 

Ответ: 24

Многоугольники

В некоторых алгоритмах рисуемые фигуры - это многоугольники (обычно правильные).

Напомню, что угол правильного n-угольника можно вычислить по формуле (n-2)*180/n.  

В таблице приведены величины углов правильных n-угольников и смежных углов:

n	Угол	Смежный угол
3	60	120
4	90	90
5	108	72
6	120	60
8	135	45
9	140	40
10	144	36
12	150	30

Теперь ясно, что если мы увидим в алгоритме углы, например, 72 градуса, то скорее всего черепаха нарисует правильный пятиугольник.

Рассмотрим следующий алгоритм для черепахи:

Повтори 11 [Вперёд 36 Направо 72]

В задаче требуется найти расстояние между начальной и конечной точками маршрута черепахи.

Решение очень простое. Из сказанного выше ясно, что черепаха будет перемещаться по сторонам правильного пятиугольника со стороной 36. За 10 выполнений цикла она опишет этот пятиугольник дважды и вернется в исходную точку, а затем пройдет ещё один отрезок длиной 36. Следовательно, ответ - 36.

Можно также решить данную задачу с помощью простого имитатора черепахи на питоне (описание функций vpered и napravo см. в конце статьи):

x=0
y=0
a=0
for i in range(11):
    vpered(36)
    napravo(72)
print(round((x**2+y**2)**0.5,3))

 

Однако решение на бумаге - куда более простое и быстрое.

Так как в реальных задачах ЕГЭ 2023 г. задачи с многоугольниками не встречались, то оставляю  другие задачи с многоугольниками читателю в качестве упражнения. 

Реальные задачи из ЕГЭ 2023 г.

Задачи, предлагавшиеся в 2023 г. (а также задачи из демо-версий 2024 г.), можно разбить на три группы:

- треугольники;

- параллелограммы;

- объединение либо пересечение двух прямоугольников.

Задача с треугольником была рассмотрена ранее.

Параллелограмм

Вот типичная задача с параллелограммом:

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

Исходное направление - вверх вдоль оси "Y".

Команда "Направо 315" задает направление движения вверх и налево под углом 45 градусов к отрицательному направлению оси "X" (по биссектрисе 2-й четверти координатной плоскости). После этого черепаха перемещается по этому направлению на 16 единиц и оказывается в точке с координатами (-8*sqrt(2);8*sqrt(2)) или приближенно (-11,31;11,31). Затем она движется параллельно оси "Y" вверх на 8 единиц, потом параллельно исходному направлению на 16 единиц вправо и вниз и оказывается в точке (0;8). Потом она перемещается по оси "Y" в исходную точку. Затем она несколько раз проходит по уже пройденным отрезкам.

Внутри контура находится 11 вертикальных рядов точек с координатами X, равными -1, -2, -3, ... -11. В каждом ряду по 7 точек. Таким образом, ответ - 77.

Можно решить задачу и программно:

k=0

for x in range(0,-15,-1):

for y in range(0,30):

if (-8*2**0.5<x<0) and (-x<y<-x+8):

k += 1

print(k)

 

Прямоугольники

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

Рассмотрим одну из таких задач.

Исходное направление - вверх по оси "Y", алгоритм следующий:

Повтори 2 [Вперёд 10 Направо 90 Вперёд 18 Направо 90]
Поднять хвост
Вперёд 5 Направо 90 Вперёд 7 Налево 90
Опустить хвост
Повтори 2 [Вперёд 10 Направо 90 Вперёд 7 Направо 90]

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

Первый цикл чертит прямоугольник с высотой 10, шириной 18 и левым нижним углом в начале координат.

Затем черепаха с поднятым хвостом (не оставляя следа) движется вверх в точку (0;5), поворачивается направо и перемещается в точку (7;5), после чего восстанавливает направление движения вверх. 

Второй цикл чертит прямоугольник с высотой 10, шириной 7 и левым нижним углом в точке (7;5).

Теперь можно набросать эскиз с этими прямоугольниками и подсчитать точки.

Первый прямоугольник содержит 19*11 целочисленных точек. В той части второго прямоугольника, которая лежит вне первого, 8*5 точек.
Итого 19*11+8*5=249 точек.

Можно также подсчитать точки с помощью простой программы. 

Первый прямоугольник включает точки, для которых 0<=x<=18 и 0<=y<=10, а второй - точки, для которых 7<=x<=14 и 5<=y<=15 (точки на границах учитываем, т.к. используются нестрогие неравенства).

Программа следующая:

 

k=0

for x in range(20):

for y in range(20):

if (0<=x<=18 and 0<=y<=10) or (7<=x<=14 and 5<=y<=15 ):

k += 1

print(k)

Ответ: 249

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

Что использовать - эскиз или программу? Разумеется, использовать надо то, что понятнее и проще для вас.

Имитатор черепахи

Повторю уже сделанное ранее предупреждение. На известном сайте "Решу ЕГЭ" приводятся решения задачи 6 на Питоне с использованием модуля turtle. Однако этот модуль в стандартную поставку Питона не входит, поэтому не надо надеяться на его наличие в том компьютере, который предоставят в ваше распоряжение для сдачи ЕГЭ.

А если промоделировать работу черепахи программой на Питоне, используя только базовые средства языка? Это возможно и не очень сложно. 

Что нам даст такой имитатор? Довольно много: координаты точек, где будет останавливаться наша черепаха. По этим точкам можно набросать эскиз её пути и понять, какую фигуру (или фигуры) она нарисует.

Черепаха использует три переменные: координаты x и y и текущее направление - угол a, который отсчитывается в градусах против часовой стрелки от положительного направления оси "X". Потребуются функции: синус и косинус, которые придется импортировать из модуля math. Оттуда же надо взять функцию radians, переводящую градусы в радианы.

Вот функции, которые будут имитировать команды черепахи. Оператор global нужен, чтобы получить из функций доступ к переменным x, y и a в основной программе.

 

from math import sin,cos,radians

def vpered(n):
    global x,y,a
    ar=radians(a)
    x += n*cos(ar)
    y += n*sin(ar)
    print(round(x,3),round(y,3))

def nazad(n):
    global x,y,a
    ar=radians(a)
    x -= n*cos(ar)
    y -= n*sin(ar)
    print(round(x,3),round(y,3))

def napravo(n):
    global a
    a -= n

def nalevo(n):
    global a
    a += n

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

Функции nalevo и nazad необязательны: вместо, например, nalevo(90) можно писать napravo(-90), а вместо nazad(10) - vpered(-10).

 

Реализуем в данном имитаторе уже рассмотренный выше алгоритм (исходное положение - начало координат, начальное направление - вдоль оси "Y"):

Повтори 2 [Вперёд 10 Направо 90 Вперёд 18 Направо 90]
Поднять хвост
Вперёд 5 Направо 90 Вперёд 7 Налево 90
Опустить хвост
Повтори 2 [Вперёд 10 Направо 90 Вперёд 7 Направо 90]

Реализация - буквально "один в один":

 

x=0

y=0

a=90

for i in range(2):

vpered(10)

napravo(90)

vpered(18)

napravo(90)

vpered(5)

napravo(90)

vpered(7)

nalevo(90)

for i in range(2):

vpered(10)

napravo(90)

vpered(7)

napravo(90)

Получаем результат (исходная точка (0;0) не напечатана):

0.0 10.0
18.0 10.0
18.0 0.0
0.0 -0.0
-0.0 5.0
7.0 5.0
7.0 15.0
14.0 15.0
14.0 5.0
7.0 5.0

Мы видим, что черепаха нарисовала два прямоугольника: один с вершинами (0;0), (0;10), (18;10), (18;0), другой - с вершинами (7;5), (7;15), (14;15), (14;5). (Точка (0;5) - промежуточная точка её маршрута, когда хвост был поднят.)

Далее - "повторение пройденного". Напомню, что в данной задаче  требуется найти число точек с целочисленными координатами, которые находятся внутри объединения нарисованных фигур, включая точки на линиях. Это легко сделать, нарисовав эскиз либо с помощью несложной программы:

 

k=0
for x in range(20):
for y in range(20):
if (0<=x<=18 and 0<=y<=10) or (7<=x<=14 and 5<=y<=15): k += 1
print(k)

 

Ответ: 249

 

Надеюсь, что данная статья помогла вам разобраться с черепахой из 6-й задачи ЕГЭ по информатике. 

 

(c) Ю.Д.Красильников, 2024 г.