Алгоритм решения задания 6. Часть 1

О задании

Задание 6 ЕГЭ по информатике проверяет умение работать с алгоритмами управления исполнителями. С точки зрения программирования задача несложная – нужно переписать алгоритм из условия и построить по нему фигуры.

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

До 2024 года существовало три подхода к решению:

Исполнитель Черепаха в среде Кумир
Графический модуль turtle в Python
Аналитический метод

Среда Кумир больше не входит в обязательное ПО на ЕГЭ – практически гарантировано, что её не будет на экзамене.

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

Мы сосредоточимся на визуализации алгоритмов через модуль turtle в Python. Метод нагляднее и проще для восприятия, а код для решения – типовой. Даже забыв часть кода, вы сможете восстановить решение, используя документацию модуля (доступна по умолчанию в Python).

Формулировки

Условие задания 6 начинается с описания команд исполнителя и информации о записи циклов с примером алгоритма.

Затем следует алгоритм для реализации. Чаще всего его можно разделить на три части: отрисовка первой фигуры, перемещение ко второй фигуре без рисования и отрисовка второй фигуры.

После алгоритма указывается искомая величина. По ней задания делятся на:

Подсчитать целочисленные точки в пересечении фигур
Подсчитать целочисленные точки в объединении фигур
Найти площадь или периметр области пересечения
Найти площадь или периметр области объединения

С точки зрения написания кода введём другую типизацию:

Задания первого типа – работа с целочисленными точками
Задания второго типа – вычисление площади или периметра

Каждому типу посвятим отдельную статью. В этой статье разберём базовые формулировки, вспомним пересечение и объединение фигур, выведем типовой алгоритм и научимся решать задания первого типа.

Начнём с ключевых понятий – объединения и пересечения фигур.

Пересечение и объединение фигур

Представим расчерченное поле, где сторона клетки – одна условная единица. На поле есть две фигуры:

Оранжевый прямоугольник с номером 1
Зелёный прямоугольник с номером 2

Сдвинем каждую фигуру на одну клетку к центру (оранжевую – вправо, зелёную – влево). Получим три части: часть первой фигуры, часть второй и область «наложения» (обозначена жёлтым цветом и цифрой 3).

Область наложения – это пересечение фигур 1 и 2. Пересечение двух прямоугольников – часть плоскости, принадлежащая обоим прямоугольникам одновременно.

Слово «одновременно» здесь ключевое – оно поможет понять разницу с объединением фигур.

Объединение двух фигур – это множество всех точек, принадлежащих хотя бы одной из них. Все три части вместе: область 1, область 2 и их пересечение 3 – образуют объединение фигур.

Теперь посмотрим на ту же картину через призму точек, принадлежащих фигурам.

Для пересечения всё понятно: есть область, принадлежащая обеим фигурам (жёлтая). Подсчитаем точки пересечения – получаем 9 точек.

С объединением интереснее. Каждому прямоугольнику принадлежат 20 целочисленных точек: 5 по одной стороне и 4 по другой. При этом 9 точек принадлежат обоим прямоугольникам одновременно.

Если просто сложить 20 и 20, общие точки будут посчитаны дважды. Поэтому один раз вычитаем 9 точек пересечения.

Количество точек объединения вычисляется по формуле: точки первой фигуры плюс точки второй фигуры минус точки их пересечения.

Давайте подсчитаем здесь количество точек объединения:

5 · 4 + 5 · 4 – 3 · 3 = 20 + 20 – 9 = 31.

Теперь вернёмся к формулировкам задания 6.

Точки внутри пересечения

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

Здесь нужно найти пересечение фигур и подсчитать количество точек, которые ему принадлежат. Можно считать вручную или использовать геометрические формулы для соответствующих фигур.

Сложнее формулировка, в которой требуется найти количество точек внутри пересечения, не включая точки на его границе.

Например, на изображении только одна точка внутри пересечения не лежит на линии (отмечена синим).

Для большей наглядности рассмотрим другую фигуру: зелёный прямоугольник с 9 точками на одной стороне и 5 на другой.

Нужно найти количество точек, не лежащих на линиях. Таких «внутренних» точек будет 7 × 3 = 21.

Если точки на границе не учитываются, на каждой стороне исключаем две крайние точки. Поэтому из 9 получаем 9 − 2 = 7 внутренних координат, а из 5 – 5 − 2 = 3.

Точки внутри объединения

Некоторые задания требуют найти точки внутри объединения.

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

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

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

Площадь и периметр фигуры

Некоторые варианты задания 6 требуют найти площадь или периметр области пересечения либо объединения фигур.

Пример: «Определите площадь области пересечения фигур, ограниченных заданными алгоритмом линиями».

Здесь важны не сами точки, а единичные отрезки между соседними точками. Поэтому поверх линий удобно поставить точки цвета фона – белые. Они разделят стороны на хорошо заметные отрезки.

Чтобы получить, к примеру, нечто такое:

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

То есть сначала строим прямоугольник по заданному алгоритму. Затем расставляем белые точки: 9 по одной стороне и 5 по другой. Этим действием делим стороны прямоугольника на отрезки: 8 на одной стороне и 4 на другой.

Теперь легко вычислить площадь и периметр. Площадь: 8 × 4 = 32. Периметр: 8 + 4 + 8 + 4 = 24.

С базовой теорией разобрались, переходим к алгоритму решения.

Алгоритм решения

Программный код для решения задания 6 будет состоять из нескольких основных блоков, многие из которых повторяются от примера к примеру:

Импорт модуля turtle
Базовая настройка
Алгоритм из условия
Расстановка точек

Давайте разберём каждый блок отдельно. Начнём с импорта. В Python существует несколько способов импортировать модуль. Мы воспользуемся короткой конструкцией, которая сразу импортирует все функции turtle:

from turtle import *

Теперь поговорим о базовой настройке отображения окна с графикой. Для начала, отключим анимацию отрисовки командой tracer(0).

Далее нам необходимо ввести переменную, отвечающую за масштаб изображения, чтобы более отчётливо видеть нарисованные фигуры.

Значение этой переменной нужно будет подбирать вручную, ведь для каждого задания необходим разный масштаб. Можете установить её на значение 20, запустить весь код и проверить, насколько хорошо отображаются все необходимые фигуры.

От масштаба зависят и остальные параметры отображения. Например, можно изменить толщину пера с помощью pensize(), размер холста с помощью screensize(), а также размер и цвет точек, которые расставляются поверх фигур.

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

И последний момент: в Python Черепаха изначально направлена вдоль положительного направления оси абсцисс, то есть вправо. В условии ЕГЭ её голова обычно направлена вдоль положительного направления оси ординат, то есть вверх.

Для полного соблюдения условия можем дописать поворот черепахи влево на 90 градусов, чтобы её голова смотрела вверх.

lt(90)

Для численного ответа поворот всей картины на 90 градусов обычно ничего не меняет. Но команду лучше добавить, чтобы рисунок и координаты полностью соответствовали условию.

Весь шаблонный код базовой настройки вместе с импортом можно записать так:

from turtle import *

tracer(0)
scale = 20
pensize(5)
screensize(2000, 2000)
dot_color = "#696969" # Тёмно-серый
dot_size = 4

lt(90) # Не обязательно

Перейдём к алгоритму движения черепахи из условия. Рассмотрим такой пример:

«Повтори 8 [Вперёд 16 Направо 90 Вперёд 22 Направо 90]

Поднять хвост
Вперёд 5 Направо 90 Вперёд 5 Налево 90
Опустить хвост

Повтори 8 [Вперёд 52 Направо 90 Вперёд 77 Направо 90]»

Здесь чётко можно выделить 3 блока:

После первого «Повтори 8» черепаха рисует первую фигуру. Немного поразмыслив над алгоритмом, мы поймём, что рисует она прямоугольник.
Между «Поднять хвост» и «Опустить хвост» идёт блок перемещения черепахи без рисования. То есть она переходит к началу следующей фигуры.
После второго «Повтори 8», очевидно, рисуется второй прямоугольник.

Повторение заданной последовательности действий удобно записать с помощью цикла for и функции range(), в которую передаётся количество повторений.

Так, описанный выше алгоритм построения первой фигуры можно записать следующим образом:

# Повтори 8
for _ in range(8): 
    fd(16) # Вперёд 16
    rt(90) # Направо 90
    fd(22) # Вперёд 22
    rt(90) # Направо 90

Если вы еще не знакомы с командами из модуля turtle, то настоятельно рекомендуем сначала прочитать статьи по ссылкам:

Теперь реализуем второй блок – перемещение Черепахи без рисования:

pu() # Поднять хвост
fd(5) # Вперёд 5
rt(90) # Направо 90
fd(5) # Вперёд 5
lt(90) # Налево 90
pd() # Опустить хвост

По аналогии с первым, напишем и третий блок кода:

# Повтори 8
for _ in range(8):
    fd(52) # Вперёд 52
    rt(90) # Направо 90
    fd(77) # Вперёд 77
    rt(90) # Направо 90

Остался последний шаг – расставить точки на поле и завершить программу. Для расстановки точек воспользуемся простым алгоритмом:

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

В конце нужно корректно завершить выполнение программы. Команда done() оставит графическое окно открытым, чтобы рисунок можно было рассмотреть.

Предположим, что нужно расставить точки от начала координат (0, 0) до точки (10, 10). В коде это записывается так:

pu()  # Поднять хвост
for x in range(0, 11):
    for y in range(0, 11):
        goto(x, y) # Переместиться к x, y
        dot(dot_size, dot_color) # Поставить точку

done()

На этом почти всё. Если составить из описанных блоков единую программу и запустить её, фигуры окажутся очень маленькими. Дело в том, что мы пока не применили масштаб.

В заданиях будем умножать линейные перемещения Черепахи на переменную scale: значения в fd() и bk(), а также обе координаты в goto(). Углы поворота и границы циклов умножать на scale не нужно.

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

Пример 1

Разберём такое задание:

Исполнитель Черепаха действует на плоскости с декартовой системой координат.

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

У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n — целое число), вызывающая перемещение в противоположном голове направлении; Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке; Налево m (где m — целое число), вызывающая изменение направления движения на m градусов против часовой стрелки.

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

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

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

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

Открыть задание

Составляем блок кода с базовыми настройками черепахи:

from turtle import *

tracer(0)
scale = 20
pensize(5)
screensize(2000, 2000)
dot_color = "#696969" # Тёмно-серый
dot_size = 4

lt(90) # Не обязательно

И переходим к циклу с отрисовкой первой фигуры: Повтори 2 [Вперёд 10 Направо 90 Вперёд 18 Направо 90]. Перенесём все эти команды на язык Python.

Сразу отметим, что для наглядности мы каждую фигуру будем раскрашивать в свой цвет: первую в зелёный, вторую – в оранжевый.

Определим цвет линии с помощью функции color() и перепишем алгоритм из условия, не забывая умножать линейные величины на переменную scale:

color("#A7D380")
# Повтори 2
for _ in range(2):
    fd(10 * scale) # Вперёд 10
    rt(90) # Направо 90
    fd(18 * scale) # Вперёд 18
    rt(90) # Направо 90

Теперь переходим к перемещению черепахи с поднятым хвостом:

Поднять хвост
Назад 6 Направо 90 Вперёд 9 Налево 90
Опустить хвост

В коде это будет выглядеть так:

pu() # Поднять хвост
bk(6 * scale) # Назад 6
rt(90) # Направо 90
fd(9 * scale) # Вперёд 9
lt(90) # Налево 90
pd() # Опустить хвост

Вторая фигура задана алгоритмом: Повтори 2 [Вперёд 17 Направо 90 Вперёд 5 Направо 90]. По аналогии с первой перепишем его на Python:

color("#F76D47")
# Повтори 2
for _ in range(2):
    fd(17 * scale) # Вперёд 17
    rt(90) # Направо 90
    fd(5 * scale) # Вперёд 5
    rt(90) # Направо 90

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

pu()  # Поднять хвост
for x in range(9, 15):
    for y in range(0, 11):
        goto(x * scale, y * scale) # Переместиться к x, y
        dot(dot_size, dot_color) # Поставить точку

done()

Полный код нашей программы будет таким:

from turtle import *

tracer(0)
scale = 20
pensize(5)
screensize(2000, 2000)
dot_color = "#696969" # Тёмно-серый
dot_size = 4

lt(90) # Не обязательно

color("#A7D380")
# Повтори 2
for _ in range(2):
    fd(10 * scale) # Вперёд 10
    rt(90) # Направо 90
    fd(18 * scale) # Вперёд 18
    rt(90) # Направо 90


pu() # Поднять хвост
bk(6 * scale) # Назад 6
rt(90) # Направо 90
fd(9 * scale) # Вперёд 9
lt(90) # Налево 90
pd() # Опустить хвост

color("#F76D47")
# Повтори 2
for _ in range(2):
    fd(17 * scale) # Вперёд 17
    rt(90) # Направо 90
    fd(5 * scale) # Вперёд 5
    rt(90) # Направо 90

pu()  # Поднять хвост
for x in range(9, 15):
    for y in range(0, 11):
        goto(x * scale, y * scale) # Переместиться к x, y
        dot(dot_size, dot_color) # Поставить точку

done()

Запускаем её и видим на экране следующее изображение.

Приступим к подсчёту точек. Мы не стали заполнять точками обе фигуры целиком: считать их «пальцем по экрану» совсем не хочется. Вместо этого воспользуемся размерами прямоугольников. Вспомните простой пример:

Для его отрисовки черепаха двигалась 8 единиц в одну сторону и 4 в другую. Код был таким:

from turtle import *
scale = 10

fd(8 * scale)
lt(90)
fd(4 * scale)
lt(90)
fd(8 * scale)
lt(90)
fd(4 * scale)

done()

Как видим, вдоль одной стороны расположено 9 точек, а вдоль другой – 5. Если учитывать границу, количество целочисленных точек на единицу больше длины стороны: 8 + 1 = 9 и 4 + 1 = 5.

По этой логике первой фигуре принадлежат 11 × 19 целочисленных точек, а второй – 18 × 6.

Теперь смотрим именно на область пересечения. По рисунку её размеры в целочисленных точках равны 11 и 6: первая величина берётся от первой фигуры, вторая – от второй.

Перемножив эти два значения, получаем ответ – число 66.

Пример 2

Теперь поработаем с объединением фигур. Формулировка здесь будет следующая:

Исполнитель Черепаха действует на плоскости с декартовой системой координат.

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

Повтори 2 [Вперёд 14 Налево 270 Назад 12 Направо 90]
Поднять хвост
Вперёд 9 Направо 90 Назад 7 Налево 90
Опустить хвост
Повтори 2 [Вперёд 13 Направо 90 Вперёд 6 Направо 90]

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

Открыть задание

Первый блок кода будет шаблонным:

from turtle import *

tracer(0)
scale = 20
pensize(5)
screensize(2000, 2000)
dot_color = "#696969" # Тёмно-серый
dot_size = 4

lt(90) # Не обязательно

Далее реализуем цикл отрисовки первой фигуры.

color("#A7D380")
# Повтори 2
for _ in range(2):
    fd(14 * scale) # Вперёд 14
    lt(270) # Налево 270
    bk(12 * scale) # Назад 12
    rt(90) # Направо 90

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

pu() # Поднять хвост
fd(9 * scale) # Вперёд 9
rt(90) # Направо 90
bk(7 * scale) # Назад 7
lt(90) # Налево 90
pd() # Опустить хвост

И нарисуем вторую фигуру:

color("#F76D47")
# Повтори 2
for _ in range(2):
    fd(13 * scale) # Вперёд 13
    rt(90) # Направо 90
    fd(6 * scale) # Вперёд 6
    rt(90) # Направо 90

Осталось добавить точки.

pu()  # Поднять хвост
for x in range(-12, 1):
    for y in range(0, 23):
        goto(x * scale, y * scale) # Переместиться к x, y
        dot(dot_size, dot_color) # Поставить точку

done()

Вся наша программа выглядит так:

from turtle import *

tracer(0)
scale = 20
pensize(5)
screensize(2000, 2000)
dot_color = "#696969" # Тёмно-серый
dot_size = 4

lt(90) # Не обязательно

color("#A7D380")
# Повтори 2
for _ in range(2):
    fd(14 * scale) # Вперёд 14
    lt(270) # Налево 270
    bk(12 * scale) # Назад 12
    rt(90) # Направо 90


pu() # Поднять хвост
fd(9 * scale) # Вперёд 9
rt(90) # Направо 90
bk(7 * scale) # Назад 7
lt(90) # Налево 90
pd() # Опустить хвост

color("#F76D47")
# Повтори 2
for _ in range(2):
    fd(13 * scale) # Вперёд 13
    rt(90) # Направо 90
    fd(6 * scale) # Вперёд 6
    rt(90) # Направо 90

pu()  # Поднять хвост
for x in range(-12, 1):
    for y in range(0, 23):
        goto(x * scale, y * scale) # Переместиться к x, y
        dot(dot_size, dot_color) # Поставить точку

done()

После запуска видим на экране следующие прямоугольники.

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

Сначала вычислим количество точек, принадлежащих каждой фигуре, включая границу. Для первой получаем 15 × 13 точек, для второй – 14 × 7.

Теперь подсчитаем точки пересечения. Одна величина уже известна – 7. Чтобы найти вторую, проанализируем движение Черепахи. Первый цикл возвращает её в начало координат и снова направляет вверх. В этом можно убедиться, временно включив анимацию командой tracer(1).

Следовательно, подняв хвост, она переместилась вперёд на 9 единиц по команде fd(9 * scale).

Отсюда легко определить, насколько оранжевая фигура заходит на зелёную: из 15 точек по стороне зелёной фигуры вычитаем смещение на 9 единиц и получаем 6 точек.

Значит, на пересечении находятся: 7 × 6 = 42 точки.

Вычислим ответ простым выражением: 15 × 13 + 14 × 7 — 7 × 6 = 251.

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