Для быстрого и правильного написания решений рекомендуется написать следующий набор стандартных подпрограмм, из которых программы для большей части геометрических задач составляются, как из кубиков:
1. Отношения вещественных чисел:
2. Работа с прямыми и точками:
3. Работа с многоугольниками:
4. Работа с векторами:
5. Дополнительно:
При решении геометрических задач данные подпрограммы следует реализовывать наиболее простым способом. Например, принадлежность точки треугольнику можно проверить, сравнив его площадь с суммой площадей трех других треугольников, образованных парой вершин рассматриваемого треугольника и проверяемой точкой. Равенство означает, что точка лежит внутри либо на стороне треугольника.
Во многих геометрических задачах естественное применения находят вектора и операции над ними: сложение, вычитание, умножение на число, поиск угла между векторами и т.д. Полезно знать свойства скалярного, векторного и смешанного произведений. В тех задачах, в которых требуется найти наилучший по какому-либо критерию геометрический объект, нужно придумать, каким образом ограничиться перебором конечного числа объектов рассматриваемого типа. Для этого следует задаться вопросом, как должно быть устроено оптимальное или локально оптимальное решение.
Пусть, например, нам необходимо найти окружность минимального радиуса, охватывающую заданные N различных точек плоскости (N > 1). Представим себе, что в этих точках вбиты гвоздики, и проведем вокруг них окружность достаточно большого радиуса. Теперь заставим эту окружность сжиматься, но так, чтобы все гвоздики по-прежнему оставались внутри нее. Ясно, что перестать сжиматься окружность может лишь в том случае, когда она окажется жестко зафиксированной либо тремя гвоздями, лежащими на ней, либо двумя гвоздями, лежащими на ее диаметре. Тем самым мы свели задачу «бесконечного перебора» всех возможных окружностей на плоскости к «конечному перебору» окружностей, описанных вокруг всех троек точек, и окружностей, построенных на отрезках, соединяющих все пары рассматриваемых точек, как на диаметрах.
Решения некоторых задач основаны на нахождении площади многоугольника и полярного угла точки. Поэтому имеет смысл привести здесь формулы для их вычисления. Пусть (x1, y1), (x2, y2), …, (xN, yN) — координаты вершин заданного многоугольника в порядке обхода по или против часовой стрелки. Тогда его ориентированная площадь S равна
При использовании этой формулы не случится ничего страшного, если какие-то две вершины многоугольника будут совпадать или какие-то три — лежать на одной прямой. Если координаты вершин были заданы в порядке обхода против часовой стрелки, то число S, вычисленное по этой формуле, получится положительным. В противном случае оно будет отрицательным, и для получения обычной геометрической площади нам необходимо взять его абсолютное значение.
Комбинаторные алгоритмы
Рассмотрим теперь решение задач по комбинаторике. В качестве примеров наиболее простых и часто встречающихся классов комбинаторных объектов можно привести подмножества множеств, перестановки, размещения и сочетания их элементов (с повторениями или без), разбиения множеств на подмножества и чисел на слагаемые, двоичные и подвешенные деревья и т.д. Кроме того, можно рассмотреть аналогичные классы объектов для мультимножеств, т.е. для множеств, в которые каждый элемент входит некоторое количество раз, называемое кратностью этого элемента.
Основными вопросами, которые при этом могу возникнуть, являются следующие:
Комбинаторные алгоритмы обычно нужны не сами по себе, а как часть решения более сложной задачи. Для успешного решения олимпиадных задач, предполагающих использование комбинаторных алгоритмов, необходимо хорошо освоить такие алгоритмы, как генерирование перестановок и подсчет разбиений числа N на сумму от K до L слагаемых, каждое из которых принадлежит диапазону от A до B. Первые из них необходимы для выработки умения программировать наиболее часто встречающиеся алгоритмы. Вторые — для развития умения придумывать такого рода комбинаторные алгоритмы самостоятельно.
Как правило, решение задач по комбинаторике требует знания динамического программирования и умения реализовать длинную арифметику. Для этого достаточно уметь запрограммировать сложение и вычитание длинных чисел, а также умножение и деление длинного числа на короткое.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 3)
Моделирование
Решение задач с использованием методов моделирования предполагают обычно знание многих разделов информатики и умение аккуратно программировать большое количество несложных подзадач, компонуя их вместе для получения решения. Обычно такие задачи не представляют трудности с алгоритмической точки зрения, испытывая лишь программистскую технику.
В чистом виде задачи на построение моделей встречаются на олимпиадах по информатике не так часто. Как правило, понятие модели используется здесь для сохранения целостности моделируемой системы, которая декомпозируется в процессе решения на более простые компоненты. В качестве примера такой задачи можно привести следующую: по последовательности команд ОС Unix cd, mkdir, ls, rmdir требуется построить вывод на экран интерпретатора этих команд.
Решение этой задачи сводится к моделированию выполнения входящих в условие задачи команд. После декомпозиции задачи получается несколько подзадач, не представляющих особой алгоритмической сложности:
Решение этих подзадач является делом техники.
Достаточно часто среди олимпиадных задач по информатике встречаются задачи, не подпадающие под упомянутые выше разделы. Можно выделить две группы таких задач. Первая группа — это так называемые задачи «на идею», когда основная сложность решения заключается в придумывании нестандартного, неожиданного алгоритма их решения. Чисто техническая сложность таких задач обычно невелика. Трудно дать какие-либо рекомендации по решению такого рода задач; необходима интуиция, вырабатываемая только частыми тренировками на задачах повышенной сложности и олимпиадных задачах. Кроме того, необходим талант алгоритмиста.
Задачи второй группы — это такие подзадачи, умение решать которые часто необходимо для решения более сложных задач, и которые могут встретиться в любой из задач перечисленных ранее групп. Такими задачами, например, являются нестандартные задачи на комбинаторику, задачи по манипулированию строковыми данными; задачи на длинную арифметику и т.п. При решении таких задач поможет знание быстрых алгоритмов поиска подстроки в строке, алгоритмов реализации основных операций длинной арифметики и вычисления с их помощью некоторых комбинаторных формул и т.п. Важно довести их реализацию до автоматизма, так как в качестве подзадач эти алгоритмы встречаются очень часто, и реализовывать их надо в процессе решения олимпиадной задачи, не задумываясь.
Чтобы успешно выступать на олимпиадах по информатике, необходимо иметь не только хорошие знания в этой области, но и владеть современными информационными технологиями и доведенными до автоматизма практическими навыками решения задач с использованием компьютеров. Да, без опыта программирования и совершенной техники работы с компьютерами на олимпиадах высокого уровня победить не возможно, и тренинг играет в этом случае не последнюю роль. Но в олимпиадах по информатике не это подчас является главным.
Очень важно — за ограниченное время понять смысл задачи, формализовать ее и предложить оптимальный алгоритм ее решения с учетом заданных ограничений. А здесь начинается самое интересное. Практически каждая задача, предлагаемая на олимпиадах высокого уровня, является уникальной, и в чистом виде ее решение нельзя прочитать в каких-либо источниках. Даже знание большого количества опубликованных в литературе алгоритмов не гарантирует ее решение, не говоря о том, что число таких алгоритмов достаточно велико, и знать школьникам их практически невозможно.
Как следствие, школьникам при решении олимпиадных задач приходится не только оперировать типовыми алгоритмами, но и уметь распознать ситуацию, для которой этот алгоритм применим, а также адаптировать этот алгоритм для решения конкретной задачи. О «натаскивании» школьников здесь речь не может идти. Участникам не известно, какие задачи будут на конкретной олимпиаде и что необходимо знать школьнику, чтобы известный алгоритм приспособить для решения предложенной задачи. Если бы в какой-либо стране кто-то знал, как сделать даже самого талантливого школьника абсолютным победителем международной олимпиады, то эта страна надолго монополизировала бы это звание.