Задание 6 ЕГЭ по информатике: результаты работы алгоритмов Черепахи

Что проверяет задание

Задание 6 проверяет умение «прокрутить» в уме или на бумаге работу простого алгоритма для учебного исполнителя (чаще всего это Черепаха на координатной плоскости, реже — Робот или Чертёжник) и получить числовой результат: координаты конечной точки, длину пройденного пути, площадь фигуры или, чаще всего, количество точек с целочисленными координатами внутри и/или на границе фигуры, которую вычерчивает исполнитель. По сути это задание на аккуратное пошаговое исполнение алгоритма плюс элементарную геометрию на клетчатой плоскости.

Как выглядит формулировка и сколько баллов

Стандартная формулировка описывает исполнителя Черепаха: он стоит в начале координат, смотрит вдоль оси $Oy$, умеет выполнять команды «Вперёд $n$» (сдвиг на $n$ единиц в текущем направлении) и «Направо $m$» (поворот по часовой стрелке на $m$ градусов), а конструкция «Повтори $k$ [...]» повторяет блок команд $k$ раз. Дальше приводится конкретная программа, и требуется определить число точек с целочисленными координатами внутри области, ограниченной построенной линией, или внутри и на границе одновременно. Задание относится к базовому уровню сложности, оценивается в 1 первичный балл, на его решение стоит закладывать не более 2–3 минут.

Что нужно знать

• Направление движения задаётся углом $\theta$ относительно оси $Ox$; поворот «Направо $m$» уменьшает угол на $m$: $\theta_{new} = \theta_{old} - m$; поворот «Налево $m$» увеличивает угол на $m$.
• Переход к смещению по осям при движении «Вперёд $n$» в направлении $\theta$: $\Delta x = n\cos\theta,\ \Delta y = n\sin\theta$.
• Ломаная линия из цикла «Повтори $k$» замкнётся в правильный (возможно, звёздчатый) многоугольник только тогда, когда суммарный угол поворота кратен $360°$: $k\cdot m = 360°\cdot d$ для некоторого целого $d$.
• Если $d\ge 2$, вычерчивается звёздчатый многоугольник вида $\{k/d\}$; если $d=1$ — обычный выпуклый правильный $k$-угольник.
• Площадь многоугольника по координатам вершин (формула «шнурков», формула Гаусса): $S=\dfrac12\left|\sum_{i=1}^{n}\left(x_i y_{i+1}-x_{i+1} y_i\right)\right|$.
• Теорема Пика для многоугольника с вершинами в целочисленных точках: $S = I + \dfrac{B}{2} - 1$, где $I$ — число внутренних целых точек, $B$ — число целых точек на границе.
• Для прямоугольника со сторонами $a$ и $b$ (целые, стороны параллельны осям): число целых точек строго внутри равно $(a-1)(b-1)$; число целых точек внутри и на границе равно $(a+1)(b+1)$.
• Число целых точек на отрезке между целыми точками $(x_1,y_1)$ и $(x_2,y_2)$, включая концы, равно $\gcd(|x_2-x_1|,|y_2-y_1|)+1$.

Методы решения

1. Пошаговая симуляция. Универсальный способ: последовательно вычисляем координаты каждой вершины ломаной по формулам смещения. Подходит для любой программы, но требует аккуратности с тригонометрией — обычно достаточно углов, кратных $30°,45°,60°,90°$. Мини-пример: «Повтори 4 [Вперёд 10 Направо 90]» — после каждого шага угол меняется на $90°$, координаты вершин: $(0,0)\to(0,10)\to(10,10)\to(10,0)\to(0,0)$ — квадрат $10\times10$.

2. Готовые формулы для прямоугольника/квадрата. Если фигура — прямоугольник со сторонами, параллельными осям, не нужно ничего считать через теорему Пика — сразу применяем формулы $(a-1)(b-1)$ или $(a+1)(b+1)$. Мини-пример: квадрат $10\times10\Rightarrow(10-1)^2=81$ точек строго внутри.

3. Теорема Пика. Когда все вершины многоугольника — целочисленные точки, находим площадь по формуле «шнурков» и число граничных точек (через $\gcd$ для каждой стороны), затем выражаем $I$ из равенства $S=I+\dfrac{B}{2}-1$. Мини-пример: прямоугольный треугольник с катетами 3 и 4, вершины $(0,0),(3,0),(0,4)$: $S=6$, $B=\gcd(3,0)+\gcd(0,4)+\gcd(3,4)=3+4+1=8$, отсюда $I=6-4+1=3$.

4. Метод «срезов по столбцам». Если вершины фигуры не являются целыми точками (например, вершина правильного треугольника с иррациональной координатой), теорема Пика неприменима напрямую. Тогда выписываем уравнения ограничивающих прямых, и для каждого целого $x$ из области определения находим диапазон допустимых $y$, считая целые значения в нём, а затем суммируем по всем $x$. Мини-пример разобран ниже (пример 1).

5. Анализ периодичности программы. Перед вычислениями стоит проверить, не «зацикливается» ли фигура раньше, чем закончится «Повтори $k$»: если после $p<k$ повторов исполнитель вернулся в исходную точку с исходным направлением, то дальше он просто повторяет тот же контур. Это сильно упрощает построение и подсчёт.

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

1. Зафиксировать стартовую точку $(0,0)$ и стартовое направление (обычно вдоль $Oy$, угол $90°$).
2. Пошагово применить команды «Вперёд»/«Направо» (или «Налево»), вычисляя координаты каждой новой точки.
3. Проверить, не повторяется ли контур раньше окончания цикла: сравнить текущее положение и направление с начальными.
4. Определить тип получившейся фигуры (прямоугольник, правильный или звёздчатый многоугольник) и выписать координаты всех различных вершин.
5. Выбрать метод подсчёта: готовая формула для прямоугольника, теорема Пика для многоугольника с целыми вершинами, либо перебор по столбцам, если вершины нецелые.
6. Внимательно прочитать вопрос: считать нужно точки строго внутри, или внутри и на границе.
7. Выполнить вычисления и проверить результат прикидкой — сравнить полученное число с приближённой площадью фигуры (они должны быть близки).

Разбор примеров

Пример 1. Программа: «Повтори 7 [Вперёд 10 Направо 120]». Начинаем с точки $(0,0)$, направление $90°$. Шаг 1: движение на 10 в направлении $90°$ даёт точку $(0,10)$; поворот на $120°$ по часовой стрелке даёт новое направление $90-120=-30°$. Шаг 2: смещение $(10\cos(-30°),10\sin(-30°))=(5\sqrt3,-5)$, новая точка $(5\sqrt3,5)$; направление становится $-150°$. Шаг 3: смещение $(10\cos(-150°),10\sin(-150°))=(-5\sqrt3,-5)$, новая точка $(0,0)$ — черепаха вернулась в старт, а направление стало $-270°\equiv90°$ — совпадает с исходным! Значит, уже через 3 шага фигура замкнулась в равносторонний треугольник с вершинами $A(0,0)$, $B(0,10)$, $C(5\sqrt3,5)$, а оставшиеся 4 повторения просто заново обводят тот же треугольник. Так как вершина $C$ имеет иррациональную координату, теорема Пика неприменима — используем метод срезов по столбцам. Стороны треугольника: $AB$: $x=0$; $AC$: $y=\dfrac{x}{\sqrt3}$; $BC$: $y=10-\dfrac{x}{\sqrt3}$. Внутренняя область: $\dfrac{x}{\sqrt3}<y<10-\dfrac{x}{\sqrt3}$, $0<x<5\sqrt3\approx8{,}66$. Перебираем целые $x=1,\dots,8$: $x=1$: 9 значений $y$; $x=2$: 7; $x=3$: 7; $x=4$: 5; $x=5$: 5; $x=6$: 3; $x=7$: 1; $x=8$: 1. Сумма: $9+7+7+5+5+3+1+1=38$. Ответ: 38.

Пример 2. Программа: «Повтори 4 [Вперёд 10 Направо 90]». Сумма поворотов $4\times90=360°$ — фигура замыкается в квадрат. Координаты вершин: $(0,0)\to(0,10)\to(10,10)\to(10,0)\to(0,0)$, сторона 10, стороны параллельны осям. Число целых точек строго внутри квадрата со стороной $a$: $(a-1)^2=(10-1)^2=81$. Ответ: 81.

Пример 3. Программа: «Повтори 4 [Вперёд 5 Направо 90 Вперёд 10 Направо 90]». Старт $(0,0)$, направление $90°$.

1. Вперёд 5 → $(0,5)$; Направо 90 → направление $0°$.
2. Вперёд 10 → $(10,5)$; Направо 90 → направление $-90°$.
3. Вперёд 5 → $(10,0)$; Направо 90 → направление $-180°$.
4. Вперёд 10 → $(0,0)$; Направо 90 → направление $-270°\equiv90°$. Уже после двух повторений цикла черепаха вернулась в начало координат с исходным направлением — фигура замкнулась в прямоугольник $10\times5$ с вершинами $(0,0),(0,5),(10,5),(10,0)$, а оставшиеся два повторения обводят тот же прямоугольник ещё раз. Нужно найти точки внутри и на границе: для прямоугольника со сторонами $a=10$, $b=5$ общее число целых точек $(a+1)(b+1)=11\times6=66$. Ответ: 66.

Типичные ошибки и ловушки

• Путают направление поворота: «Направо» — по часовой стрелке (угол уменьшается), «Налево» — против часовой (угол увеличивается).
• Считают, что «Повтори $k$» всегда рисует простой $k$-угольник, не проверяя, не замыкается ли контур раньше, и ошибаются с числом реально различных вершин.
• Применяют теорему Пика к фигуре, у которой хотя бы одна вершина не является целочисленной точкой.
• Путают «строго внутри» и «внутри и на границе»: используют формулу $(a-1)(b-1)$ там, где нужно $(a+1)(b+1)$, и наоборот.
• Ошибаются в подсчёте точек на стороне отрезка, забывая использовать $\gcd$ длин проекций.
• Допускают арифметические промахи при переборе по столбцам — пропускают строку или дважды учитывают границу.
• Не сверяют ответ прикидкой площади фигуры, из-за чего пропускают явно завышенный или заниженный результат.

Как готовиться

Регулярно тренируйтесь вручную вычислять координаты по шагам для разных углов поворота — $30°,45°,60°,72°,90°,120°$ — чтобы быстро узнавать типичные фигуры (квадрат, треугольник, звёзды). Разберите не менее десятка задач из открытого банка заданий с разными командами исполнителя (Черепаха, Робот, Чертёжник), чтобы отработать оба сценария подсчёта — через теорему Пика и через перебор по столбцам. Обязательно выучите наизусть формулу Пика, формулу площади многоугольника по координатам и формулу числа точек на отрезке через $\gcd$ — на экзамене не будет времени их выводить. Полезно рисовать фигуру на черновике по клеточкам: визуальный контроль резко снижает число ошибок в знаке угла и в том, какие точки считать. Наконец, всегда делайте прикидку: площадь фигуры и полученное число точек должны быть сопоставимы по порядку величины — если ответ в разы больше или меньше площади, где-то допущена ошибка.