Простейшие алгоритмы для исполнителей

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

«Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. Ей дали алгоритм:

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

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

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

Тема состоит из шести подтем — у каждой своя страница. Идём по ним по порядку:

1. Команды и след — ты сейчас здесь.
2. Точки внутри и на границе — сколько точек в одной фигуре.
3. Две фигуры — пересечение и ответ задачи темы: 30.
4. Рисунок программой — та же задача рисунком на turtle.
5. Наклонные стороны — фигуры, у которых стороны не по клеткам.
6. Подсчёт программой — дополнительный урок: считаем точки без рисунка.

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

Положение записывают координатами (x; y): x отсчитывают вправо от начала координат, y — вверх, отрицательные значения — влево и вниз. Когда хвост опущен, Черепаха оставляет за собой линию; когда поднят — перемещается без следа.

Начальное состояние в условии описано словами. Их нужно перевести:

Начальное направление важно: та же программа при старте вправо нарисует фигуру, повёрнутую на 90°.

«Вперёд» и «Назад» меняют положение, «Направо» и «Налево» — только направление.

«Вперёд n» перемещает Черепаху на n единиц туда, куда смотрит голова. «Назад n» — на n единиц в обратную сторону, а голова при этом продолжает смотреть туда же. «Направо m» поворачивает голову на m градусов по часовой стрелке, «Налево m» — против часовой; Черепаха остаётся на месте.

Пусть Черепаха в (2; 3) и смотрит вверх. Каждая команда из таблицы выполняется из этого состояния:

Поворот отсчитывают от текущего направления: если Черепаха уже смотрит вправо, «Направо 90» направит её вниз, а не вправо.

«Повтори k [ … ]» выполняет команды в скобках k раз подряд, в том же порядке.

Первая часть алгоритма темы — «Повтори 2 [Вперёд 6 Направо 90 Вперёд 8 Направо 90]». За первое повторение Черепаха проходит 6 вверх, поворачивает вправо, проходит 8 вправо и поворачивает вниз. За второе — 6 вниз и 8 влево. Получается прямоугольник 8 × 6 с вершинами (0; 0), (0; 6), (8; 6), (8; 0), а Черепаха снова в (0; 0) и смотрит вверх.

За одно повторение здесь рисуются две стороны, поэтому для четырёх сторон хватает двух повторений: число повторений не обязано совпадать с числом сторон.

Лишние повторения проходят по уже нарисованным линиям: фигура не меняется, а положение Черепахи — меняется. «Повтори 5 [Вперёд 3 Направо 90]» рисует квадрат 3 × 3, а пятое повторение ещё раз проходит его левую сторону — Черепаха заканчивает в (0; 3). Если после такого блока идут другие команды, они начнутся именно оттуда.

С поднятым хвостом Черепаха перемещается без линии: так она переходит к началу следующей фигуры.

После первого прямоугольника Черепаха в (0; 0) и смотрит вверх. Хвост поднимается, и выполняются четыре команды:

Хвост опускается в (3; 2), голова смотрит вверх. Второй блок рисует оттуда прямоугольник высотой 5 и шириной 7, поэтому вторая фигура занимает 3 ≤ x ≤ 10 и 2 ≤ y ≤ 7. Весь алгоритм по шагам:

Итак, первая фигура — прямоугольник 0 ≤ x ≤ 8, 0 ≤ y ≤ 6, вторая — 3 ≤ x ≤ 10, 2 ≤ y ≤ 7. Точки одной фигуры считаем в подтеме 2, общие точки двух — в подтеме 3.

• Состояниеположение (x; y), направление головы и хвост
• Вперёд, Назадменяют положение; «Назад» не поворачивает голову
• Направо, Налевоменяют только направление, от текущего
• Повтори kблок k раз по порядку; лишние повторы идут по тем же линиям
• Хвост поднятперемещение без линии — переход ко второй фигуре