ГЭ-2024, Демо-2025) Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена…
ГЭ-2024, Демо-2025) Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси абсцисс, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует 6 команд: Поднять хвост, означающая переход к перемещению без рисования; Опустить хвост, означающая переход в режим рисования; Вперёд n (где n – целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова; Назад n (где n – целое число), вызывающая передвижение в противоположном голове направлении; Направо m (где m – целое число), вызывающая изменение направления 8) 9) движения на m градусов по часовой стрелке, Налево m (где m – целое число), вызывающая изменение направления движения на m градусов против часовой стрелки. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм: Повтори 3 [Вперёд 7 Направо 90 Вперёд 12 Направо 90] Поднять хвост Вперёд 4 Направо 90 Вперёд 6 Налево 90 Опустить хвост Повтори 4 [Вперёд 83 Направо 90 Вперёд 77 Направо 90] Определите, сколько точек с целочисленными координатами будут находиться внутри объединения фигур, ограниченных заданными алгоритмом линиями, включая точки на границах этого объединения.
Решение с объяснениями
Цель: понять и посчитать количество точек с целочисленными координатами, лежащих внутри объединения фигуры, образованной линиями, drawn по данному алгоритму (включая границы).
- Первая часть алгоритма (повтор 3 [Вперёд 7, Направо 90, Вперёд 12, Направо 90])
- Начало: точка A = (0, 0), голова направлена вдоль +x, хвост опущен (рисует).
- Итерация 1: A -> (7, 0) (F7), поворот вправо, движение на (7, -12), затем поворот вправо. Итерация 2: (7, -12) -> (0, -12) -> (0, 0) и т.д.
- Итог после трех повторений: песчинка нарисовала прямоугольник со сторонами 7 по x и 12 по y: Контуры: (0,0) -> (7,0) -> (7,-12) -> (0,-12) -> (0,0). То есть область, ограниченная этой линией, — прямоугольник R1 с границами: x ∈ [0, 7], y ∈ [-12, 0].
- Вторая часть алгоритма после подъёма хвоста
- Поднять хвост: перемещение без рисования.
- Далее: Вперёд 4, Направо 90, Вперёд 6, Налево 90 — все без рисования (до следующей операции).
- Затем Опустить хвост: снова начинаем рисовать.
- Третий блок рисования
- Сейчас положение: (3, -6), heading = West (последний поворот в предыдущем блоке привёл к этому положению).
- Повтори 4 [ Вперёд 83, Направо 90, Вперёд 77, Направо 90 ] Каждый вложенный цикл из двух внутренних шагов рисует прямоугольник. После двух таких вложений вы возвращаетесь в исходную точку (3, -6).
- Итак, после полного повторения 4 раза нарисован второй прямоугольник R2 со сторонами: нижняя граница y = -6, верхняя граница y = 71; правая граница x = 3, левая граница x = -80. Контуры R2: (3,-6) -> (-80,-6) -> (-80,71) -> (3,71) -> (3,-6).
- Что получилось в итоге
- Были нарисованы две прямоугольники: R1: x ∈ [0, 7], y ∈ [-12, 0]. R2: x ∈ [-80, 3], y ∈ [-6, 71].
- Объединение фигур — это R1 ∪ R2. Они пересекаются: Их пересечение имеет x ∈ [0, 3] и y ∈ [-6, 0], то есть прямоугольник размером 4 на 7 по целочисленным координатам.
- Подсчёт целочисленных точек
- Количество целочисленных точек внутри R1 (включая границу): x от 0 до 7: 8 значений; y от -12 до 0: 13 значений. Всего: 8 · 13 = 104 точек.
- Количество целочисленных точек внутри R2 (включая границу): x от -80 до 3: 84 значения; y от -6 до 71: 78 значений. Всего: 84 · 78 = 6552 точек.
- Пересечение R1 и R2: x от 0 до 3: 4 значения; y от -6 до 0: 7 значений. Всего пересечение: 4 · 7 = 28 точек.
- По правилу включения-исключения количество точек в объединении: |R1 ∪ R2| = |R1| + |R2| - |R1 ∩ R2| = 104 + 6552 - 28 = 6628.
Ответ: 6628 точек с целочисленными координатами лежат внутри объединения областей, ограниченных линиями алгоритма (включая границы).
