Пару дней назад с моим учеником наткнулись на сложную вариацию задачи №6 из ЕГЭ по информатике. Предполагаю, что у многих учащихся школ эта задача вызовет трудности, поэтому в этой заметке мы с вами максимально подробно разберем все способы решения данной проблемы. И порисуем геометрию, и покодим алгоритмы... Готовы? Тогда приятного чтения.
Задача
Исполнитель Черепаха действует на плоскости с декартовой системой координат. В начальный момент Черепаха находится в начале координат, её голова направлена вдоль положительного направления оси ординат, хвост опущен. При опущенном хвосте Черепаха оставляет на поле след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды: Вперёд n (где n — целое число), вызывающая передвижение Черепахи на n единиц в том направлении, куда указывает её голова, и Направо m (где m — целое число), вызывающая изменение направления движения на m градусов по часовой стрелке. Запись Повтори k [Команда1 Команда2 … КомандаS] означает, что последовательность из S команд повторится k раз. Черепахе был дан для исполнения следующий алгоритм:
Повтори 4 [Вперёд 8 Направо 90]
Повтори 3 [Вперёд 12 Направо 120].
Определите, сколько точек с целочисленными координатами будут находиться внутри области, ограниченной линией, заданной данным алгоритмом: Повтори 4 [Вперёд 8 Направо 90], и находиться вне области, ограниченной линией, заданной данным алгоритмом: Повтори 3 [Вперёд 12 Направо 120]. Точки на линии учитывать не следует.
Решение:
Итак, у нас две фигуры. Первый цикл «Повтори 4 [Вперёд 8 Направо 90]» рисует фигуру квадрат. Второй цикл «Повтори 3 [Вперёд 12 Направо 120]» рисует треугольник, ведь если направление меняется на угол в 120° относительно исходного направления, то новый отрезок образует угол 60° с предыдущим нарисованным отрезком.
1 способ
По сути мы можем построить эти области на одном клетчатом графики. Клетка нам понадобится для лучшего понимания координат. Нам достаточно будет первой положительной четверти в декартовой системе координат. Минимальный размер области, в которую мы сможем всё это уместить, будет 12х12.
У нас есть наложение треугольной области на квадрат и мы должны посчитать количество точек, имеющих целые координаты, которые лежат внутри квадрата, но не попадают в треугольник. Плюс не попадают на границы областей.
И вот тут возникает проблема... Ручная оценка дает нам 13 точек, но последняя 13-ая точка очень близко лежит к границе. Как тогда определить, подходит ли она нам или нет? Для этого нам понадобится уточнить фигуру: перейти от качественной к количественной оценке.
С квадратом всё понятно. Сложности возникают с треугольником из-за наклона отрезков. Изначально мы не знаем координаты вершины C. Но, судя по алгоритмы, мы знаем, что треугольник равносторонний. В равностороннем треугольнике Y-координата точки C будет находиться на значении a/2 = 12/2 = 6, а X-координата точки C будет совпадать со значением высоты, проведенной из точки C к основанию AB равностороннего треугольника (все высоты равны).
Вспомним немножко геометрии и найдем, что:
💡 Для аналитической проверки проблемной 13-ой точки [её координаты (7;4)] нам нужно сравнить Y-координаты точки и соответствующего значения Y(x = 7) прямой AC. А если точнее, чтобы точка принадлежала нужной нам области, должно выполнять неравенство Y(x = 7) > 4.
Составим уравнения прямых AC и BC:
Теперь, подставляя координату x = 7 в уравнение прямой AC, получаем:
Т.е. мы подтвердили ответ: 13 точек с целочисленными координатами в нужной нам области.
2 способ
Второй способ может быть полезен как для решения, так и для уточнения решения. У нас есть сетка целочисленных точек, значит двумя вложенными циклами мы можем пробежаться по равномерной сетке. На алгоритмическом языке у нас бы получилось что-то вроде такого:
for (int x = 0; x <= 13; ++x) {
__for (int y = 0; y <= 13; ++y) {
______Если точка POINT(x, y) ∈ КВАДРАТ AND
____________точка POINT(x, y) ∉ ТРЕУГОЛЬНИК то
______________увеличиваем счётчик точек
__ }
}
Теперь можно реализовать это на любом языке программирования. Для лучшего понимания я напишу для вас алгоритм на трех языках программирования.
Решение на языке Python
Решение на языке C
Решение на языке Pascal
Все ответы сходятся с нашим аналитическим решением из первого способа.
3 способ
В интернете гуляет еще один способ.. Что реализовать решение можно через графику внутри приложения Word:
1. Построить таблицу размером 14x14 и отрегулировать размер ячеек, например, чтобы высота ячейки и ширина ячейки были по 1 см.
2. Перейти на вкладку Вставка → Фигуры → выбрать прямоугольник и равнобедренный треугольник.
Треугольник можно повернуть на 90 градусов и отрегулировать его высоту, чтобы она были примерно равна 10.4. Можно это сделать мышкой, а можно высоту отрегулировать в размерах, если кликнуть на фигуру.
3. Далее фигуры нужно разместить на таблице как на декартовой сетке координат. Чтобы за фигурами мы видели точки (пересечение ячеек таблицы, ту самую сетку), нужно в конструкторе задать прозрачный стиль фигур:
4. Получится у нас рисунок, который будет чуть лучше, чем на черновике, но проблемные точки на нем также могут остаться. Поэтому придется руками проверять их на пригодность определенной области.
Мораль
Выбирать нужно тот способ, который вам наиболее понятен и прост в реализации. Для кого-то это аналитическое решение, а для другого человека — это может быть перебор всех вариантов с помощью доступного языка программирования.
Понравилась статья? Поставьте лайк, подпишитесь на канал, напишите комментарий! Вам не сложно, а мне очень приятно :)
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Лучший канал для физиков, математиков и программистов
Репетитор IT mentor в telegram