МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 1)
В.М.Кирюхин
За годы проведения олимпиад школьников по информатике было разработано и опубликовано в различных изданиях, в том числе и в интернете, достаточно большое количество задач. Наряду с этим, в последнее время решения всех задач, предлагавшихся на заключительном этапе всероссийских олимпиад школьников по информатике, печатаются в периодических изданиях, с которыми центральная методическая комиссия по информатике тесно сотрудничает. Тем не менее, полноценных методических изданий, способных оказать существенную помощь учителям и школьникам в подготовке к олимпиадам и систематизирующих весь накопленный опыт в решении олимпиадных задач по информатике нет.
Формат данной статьи не позволяет рассмотреть в полном объеме теорию и практику решения олимпиадных задач по информатике. Поэтому ограничимся здесь только методическими указаниями, которые будут полезными в понимании содержания олимпиадных задач и основных подходов к их решению.
Несмотря на то, что на олимпиадах по информатике предлагаются самые разнообразные задачи, тем не менее, можно выделить наиболее часто встречающиеся разделы информатики, которые необходимо знать, чтобы успешно выступать на этих олимпиадах. К таким основным разделам можно отнести:
динамическое программирование;
алгоритмы перебора с возвратом;
алгоритмы на графах;
вычислительная геометрия;
комбинаторные алгоритмы;
моделирование.
Рассмотрим краткое содержание этих разделов и особенности использования присущих им подходов и методов при решении олимпиадных задач по информатике.
Динамическое программирование
Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач с меньшей размерностью и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размерности — от меньшей к большей. Преимущество динамического программирования заключается в том, что любая подзадача решается один раз, ее решение сохраняется и никогда не вычисляется заново.
В том случае, когда исходная задача определяется одним параметром N
, определяющим размерность задачи, идея метода динамического программирования очень похожа на идею метода математической индукции. А именно, предположим, что мы уже знаем решение Fk
задачи размерности k
для всех k
, меньших N
, и хотим получить решение для k
, равного N
. Если нам удастся выразить это решение через уже известные, то тем самым будет получен алгоритм решения задачи для произвольного N.
В частности, зная решения задач F
0
, F
1
, …, Fs
, вычисляем в цикле решения F
s+1
, F
s+2
и т.д. до искомого решения FN
.
Задачи, решение которых основано на использовании метода динамического программирования, зачастую требуют только правильного применения основной идеи этого метода. После этого нужна только аккуратная реализация алгоритма. Сложно выделить какие-то общие ошибки или проблемы, возникающие в таких задачах. Все же отметим, что часто «лобовое» применение принципа динамического программирования не укладывается в ограничения, например, по памяти (такие задачи требовательны к памяти, ведь мы экономим время работы, в том числе за счет хранения промежуточных результатов). Поэтому, возможно, потребуется аккуратная реализация хранения большого количества данных (динамическая память, структуры данных).
Перебор с возвратом
Метод перебора с возвратом (backtracking
) более правильно назвать методом поиска с деревом решений. Классическими задачами, на которых обычно демонстрируется этот подход, являются обход конем доски размером N
´N
, расстановка N
ферзей на доске N
´N
и задача коммивояжера.
Решаемые методом перебора с возвратом задачи, как правило, принадлежат одному из трех классов — требуется либо найти произвольное из решений, либо перечислить все возможные решения, либо найти решение, оптимальное по заданному критерию.
Основной принцип, на котором базируется рассматриваемый метод, состоит в следующем. Рассмотрим, для определенности, задачу P
0
оптимизационного типа. Декомпозируем задачу P
0
на некоторое число подзадач P
1
, …, Pk
, представляющих в целом всю задачу P
0
. Далее попытаемся по очереди решить каждую из этих подзадач. Под решением подзадачи обычно подразумевается:
либо показать, что подзадача Pi
не является допустимой;
либо показать, что решать задачу Pi
не имеет смысла, поскольку значение оптимального решения для Pi
заведомо хуже, чем для наилучшего из ранее найденных решений;
либо определить оптимальное решение задачи Pi
, если эта задача настолько проста, что оптимальное решение находится очевидным образом;
либо разбить задачу Pi
на подзадачи Pi
1
, …, Pis
и рекурсивно перейти к рассмотрению задачи Pi
1
.
Смысл описанного разбиения задачи на некоторое число подзадач состоит в том, что или эти подзадачи проще разрешить, или они имеют меньшую размерность, или обладают какой-то дополнительной структурой, не присущей первоначальной задаче. Поскольку мы должны отсекать те ветви дерева решений, которые заведомо не могут содержать решения, лучшего уже найденного, то становится важным как можно раньше найти хорошее приближение к оптимальному решению. Поэтому бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма) и организовать перебор таким образом, чтобы наиболее «перспективные» варианты рассматривались первыми. Кроме того, можно найти несколько начальных решений с помощью различных эвристик, а затем выбрать из них наилучшее.
Часто бывает так, что все время работы переборного алгоритма уходит на попытки разрешить подзадачу P
1
исходной задачи P
0
, в то время как оптимальное решение P
0
находится в другой подзадаче Pi
. В этом случае полезно использовать метод локальной оптимизации
. Его идея заключается в том, что для каждого решения рассматриваемой задачи определяются «близкие» к нему решения. При нахождении алгоритмом перебора с возвратом более хорошего решения, чем наилучшее из ранее найденных, вызывается подпрограмма, которая перебирает все близкие решения в надежде еще более улучшить полученное. Эта схема перебора уже не является простым обходом дерева вариантов, поскольку близкие решения могут располагаться в этом дереве далеко друг от друга.
Для решения оптимизационных задач наряду с точными методами, обходящими все дерево вариантов и действительно определяющими экстремум, используются разнообразные приближенные и эвристические методы, в которых поиск тем или иным способом ограничивается. При этом, однако, нет гарантии, что полученное решение окажется оптимальным.
При программировании переборных задач обязательно нужно предусмотреть возможность прерывания программы пользователем, выдавая наилучшее из найденных на данный момент решений и завершая работу программы. В некоторых случаях следует использовать отсечение по времени
.
Подытоживая сказанное, можно отметить, что наиболее важными техническими моментами при решении таких задач является правильная организация обхода дерева вариантов, умение хранить это дерево в памяти компьютера и умение завершать работу программы по истечению некоторого промежутка времени.
Алгоритмы на графах
Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек (вершин
), представляющих основные элементы ситуации, и линий (ребер
), соединяющих определенные пары этих вершин и представляющих связи между ними. Такая формализация приводит нас к понятию графа
и возможности использования теории графов для решения исходной задачи.
При решении задач на графы полезно знать, что эти задачи относятся к одному из двух больших классов задач. Первый класс составляют задачи, которые решаются эффективно
, т.е. за время, полиномиальное от длины входных данных, и про такие задачи говорят, что они принадлежат P
-классу. Ко второму классу относятся, так называемые, NP-полные
задачи и те задачи, к которым они сводятся (они не менее сложные и потому называются NP-трудными
). Все NP
-полные задачи эквивалентны по вычислительной сложности в том смысле, что если одна из них имеет эффективное решение, то все они имеют эффективные решения. Так как этот класс содержит много практически важных и долго изучавшихся специалистами задач, то есть основания подозревать, что ни одну из задач этого класса нельзя решить эффективно. Однако, несмотря на огромное число эмпирических свидетельств, эта гипотеза (называемая «P
¹ NP
») до сих пор остается недоказанной.
Среди задач первого класса рассмотрим подробнее обхода графа в ширину, по той причине, что те или иные его модификации используются для нахождения кратчайших путей во многих задачах. Для простоты опишем его для случая неориентированного графа, так как изменения, которые необходимо внести для работы с ориентированными графами, достаточно очевидны.
Итак, пусть задан граф с двумя выделенными вершинами s
и t
, которые мы будем называть начальной
и конечной,
и нам необходимо найти кратчайший путь из s
в t
. Суть алгоритма состоит в том, чтобы пометить сначала меткой 1 те вершины графа, которые находятся на расстоянии одного ребра от вершины s
, затем меткой 2 те вершины, которые отстоят от s
на расстояние двух ребер, и т.д. При этом на очередном шаге k
мы помечаем те и только те вершины, которые еще не были помечены и которые связаны ребром с какой-либо вершиной, имеющей метку k
–1. Рано или поздно описанный алгоритм остановится, поскольку окажутся помеченными все вершины, достижимые из начальной. Если при этом вершина t
останется непомеченной, то путей из s
в t
не существует. В противном случае метка вершины t
равна длине кратчайшего такого пути.
Чтобы найти сам кратчайший путь (а не только его длину), необходимо при обходе в ширину для каждой обрабатываемой вершины v
запоминать ту вершину u
(помеченную на предыдущем шаге), из которой мы пришли в v
. Восстановление пути начинается с конца: по последней вершине находим предпоследнюю, затем по ней — пред-предпоследнюю и т.д. В результате мы получим вершины кратчайшего пути, записанные в обратном порядке. Поэтому зачастую более выгодно начинать алгоритм обхода в ширину с конечной, а не с начальной вершины.
Следует также отметить, что некоторые графы могут быть естественным образом заданы множеством своих вершин {u
} и итератором f
(u
), который для каждой вершины u перечисляет все соседние ей вершины графа (такого рода итераторы называются перечислителями
). В этом случае нет никакой необходимости в хранении самих ребер графа — обрабатывая вершину u
, алгоритм просто вызывает перечислитель f
(u
) и помещает все вершины, выданные им, в очередь для обработки на следующем шаге. Поэтому выражение «построим граф всех возможных состояний», употребляемое при решении различных задач, означает, что мы строим этот граф лишь мысленно (зачастую соответствующая структура данных потребовала бы слишком большого объема оперативной памяти), а при программировании используем перечислитель. Описанные выше алгоритмы легко обобщаются на случай, когда имеется несколько начальных и/или несколько конечных вершин.
Некоторые задачи для своего решения требуют построения наибольшего паросочетания в двудольном графе. Для этого можно применить известный алгоритм чередующихся цепочек. Конечно, наибольшее паросочетание можно найти и с помощью алгоритма построения максимального потока во вспомогательной сети, но этот способ более трудоемок.
При решении задач на графах второго класса широко используется метод перебора с возвратом
. Поскольку этот метод был описан выше, ограничимся здесь лишь краткими комментариями.
Наиболее часто встречаются следующие задачи второго класса:
Гамильтонов путь и задача коммивояжера;
максимальное независимое множество;
минимальное доминирующее множество;
раскраска графа в минимальное число цветов.
Формулировки приведенных задач и методы их решения (основанные на переборе с возвратом и использовании отсечений) содержатся в соответствующей литературе. Общая идея здесь достаточно простая — следует отсекать те ветви дерева вариантов, которые заведомо не могут привести к решению, лучшему уже найденного. В этом случае часто бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма). Можно использовать эвристический подход и в целом — ограничить множество перебираемых вариантов, руководствуясь теми или иными разумными соображениями. Естественно, что при этом мы можем случайно отсечь ту часть дерева, где содержалось оптимальное решение, и полученное нами решение оптимальным не будет. Также, при программировании этих задач, следует предусмотреть возможность прерывания программы пользователем (или использовать отсечение по времени), выдавая наилучшее из найденных за отведенное время решений.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 1)
В.М.Кирюхин
За годы проведения олимпиад школьников по информатике было разработано и опубликовано в различных изданиях, в том числе и в интернете, достаточно большое количество задач. Наряду с этим, в последнее время решения всех задач, предлагавшихся на заключительном этапе всероссийских олимпиад школьников по информатике, печатаются в периодических изданиях, с которыми центральная методическая комиссия по информатике тесно сотрудничает. Тем не менее, полноценных методических изданий, способных оказать существенную помощь учителям и школьникам в подготовке к олимпиадам и систематизирующих весь накопленный опыт в решении олимпиадных задач по информатике нет.
Формат данной статьи не позволяет рассмотреть в полном объеме теорию и практику решения олимпиадных задач по информатике. Поэтому ограничимся здесь только методическими указаниями, которые будут полезными в понимании содержания олимпиадных задач и основных подходов к их решению.
Несмотря на то, что на олимпиадах по информатике предлагаются самые разнообразные задачи, тем не менее, можно выделить наиболее часто встречающиеся разделы информатики, которые необходимо знать, чтобы успешно выступать на этих олимпиадах. К таким основным разделам можно отнести:
динамическое программирование;
алгоритмы перебора с возвратом;
алгоритмы на графах;
вычислительная геометрия;
комбинаторные алгоритмы;
моделирование.
Рассмотрим краткое содержание этих разделов и особенности использования присущих им подходов и методов при решении олимпиадных задач по информатике.
Динамическое программирование
Метод динамического программирования часто помогает эффективно решить задачу, переборный алгоритм для которой потребовал бы экспоненциального времени. Идея этого метода состоит в сведении исходной задачи к решению некоторых ее подзадач с меньшей размерностью и использовании табличной техники для сохранения уже найденных ответов. Решение подзадач при этом происходит в порядке возрастания их размерности — от меньшей к большей. Преимущество динамического программирования заключается в том, что любая подзадача решается один раз, ее решение сохраняется и никогда не вычисляется заново.
В том случае, когда исходная задача определяется одним параметром N
, определяющим размерность задачи, идея метода динамического программирования очень похожа на идею метода математической индукции. А именно, предположим, что мы уже знаем решение Fk
задачи размерности k
для всех k
, меньших N
, и хотим получить решение для k
, равного N
. Если нам удастся выразить это решение через уже известные, то тем самым будет получен алгоритм решения задачи для произвольного N.
В частности, зная решения задач F
0
, F
1
, …, Fs
, вычисляем в цикле решения F
s+1
, F
s+2
и т.д. до искомого решения FN
.
Задачи, решение которых основано на использовании метода динамического программирования, зачастую требуют только правильного применения основной идеи этого метода. После этого нужна только аккуратная реализация алгоритма. Сложно выделить какие-то общие ошибки или проблемы, возникающие в таких задачах. Все же отметим, что часто «лобовое» применение принципа динамического программирования не укладывается в ограничения, например, по памяти (такие задачи требовательны к памяти, ведь мы экономим время работы, в том числе за счет хранения промежуточных результатов). Поэтому, возможно, потребуется аккуратная реализация хранения большого количества данных (динамическая память, структуры данных).
Перебор с возвратом
Метод перебора с возвратом (backtracking
) более правильно назвать методом поиска с деревом решений. Классическими задачами, на которых обычно демонстрируется этот подход, являются обход конем доски размером N
´N
, расстановка N
ферзей на доске N
´N
и задача коммивояжера.
Решаемые методом перебора с возвратом задачи, как правило, принадлежат одному из трех классов — требуется либо найти произвольное из решений, либо перечислить все возможные решения, либо найти решение, оптимальное по заданному критерию.
Основной принцип, на котором базируется рассматриваемый метод, состоит в следующем. Рассмотрим, для определенности, задачу P
0
оптимизационного типа. Декомпозируем задачу P
0
на некоторое число подзадач P
1
, …, Pk
, представляющих в целом всю задачу P
0
. Далее попытаемся по очереди решить каждую из этих подзадач. Под решением подзадачи обычно подразумевается:
либо показать, что подзадача Pi
не является допустимой;
либо показать, что решать задачу Pi
не имеет смысла, поскольку значение оптимального решения для Pi
заведомо хуже, чем для наилучшего из ранее найденных решений;
либо определить оптимальное решение задачи Pi
, если эта задача настолько проста, что оптимальное решение находится очевидным образом;
либо разбить задачу Pi
на подзадачи Pi
1
, …, Pis
и рекурсивно перейти к рассмотрению задачи Pi
1
.
Смысл описанного разбиения задачи на некоторое число подзадач состоит в том, что или эти подзадачи проще разрешить, или они имеют меньшую размерность, или обладают какой-то дополнительной структурой, не присущей первоначальной задаче. Поскольку мы должны отсекать те ветви дерева решений, которые заведомо не могут содержать решения, лучшего уже найденного, то становится важным как можно раньше найти хорошее приближение к оптимальному решению. Поэтому бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма) и организовать перебор таким образом, чтобы наиболее «перспективные» варианты рассматривались первыми. Кроме того, можно найти несколько начальных решений с помощью различных эвристик, а затем выбрать из них наилучшее.
Часто бывает так, что все время работы переборного алгоритма уходит на попытки разрешить подзадачу P
1
исходной задачи P
0
, в то время как оптимальное решение P
0
находится в другой подзадаче Pi
. В этом случае полезно использовать метод локальной оптимизации
. Его идея заключается в том, что для каждого решения рассматриваемой задачи определяются «близкие» к нему решения. При нахождении алгоритмом перебора с возвратом более хорошего решения, чем наилучшее из ранее найденных, вызывается подпрограмма, которая перебирает все близкие решения в надежде еще более улучшить полученное. Эта схема перебора уже не я
Для решения оптимизационных задач наряду с точными методами, обходящими все дерево вариантов и действительно определяющими экстремум, используются разнообразные приближенные и эвристические методы, в которых поиск тем или иным способом ограничивается. При этом, однако, нет гарантии, что полученное решение окажется оптимальным.
При программировании переборных задач обязательно нужно предусмотреть возможность прерывания программы пользователем, выдавая наилучшее из найденных на данный момент решений и завершая работу программы. В некоторых случаях следует использовать отсечение по времени
.
Подытоживая сказанное, можно отметить, что наиболее важными техническими моментами при решении таких задач является правильная организация обхода дерева вариантов, умение хранить это дерево в памяти компьютера и умение завершать работу программы по истечению некоторого промежутка времени.
Алгоритмы на графах
Часто бывает полезно и наглядно изобразить некоторую ситуацию в виде рисунка, состоящего из точек (вершин
), представляющих основные элементы ситуации, и линий (ребер
), соединяющих определенные пары этих вершин и представляющих связи между ними. Такая формализация приводит нас к понятию графа
и возможности использования теории графов для решения исходной задачи.
При решении задач на графы полезно знать, что эти задачи относятся к одному из двух больших классов задач. Первый класс составляют задачи, которые решаются эффективно
, т.е. за время, полиномиальное от длины входных данных, и про такие задачи говорят, что они принадлежат P
-классу. Ко второму классу относятся, так называемые, NP-полные
задачи и те задачи, к которым они сводятся (они не менее сложные и потому называются NP-трудными
). Все NP
-полные задачи эквивалентны по вычислительной сложности в том смысле, что если одна из них имеет эффективное решение, то все они имеют эффективные решения. Так как этот класс содержит много практически важных и долго изучавшихся специалистами задач, то есть основания подозревать, что ни одну из задач этого класса нельзя решить эффективно. Однако, несмотря на огромное число эмпирических свидетельств, эта гипотеза (называемая «P
¹ NP
») до сих пор остается недоказанной.
Среди задач первого класса рассмотрим подробнее обхода графа в ширину, по той причине, что те или иные его модификации используются для нахождения кратчайших путей во многих задачах. Для простоты опишем его для случая неориентированного графа, так как изменения, которые необходимо внести для работы с ориентированными графами, достаточно очевидны.
Итак, пусть задан граф с двумя выделенными вершинами s
и t
, которые мы будем называть начальной
и конечной,
и нам необходимо найти кратчайший путь из s
в t
. Суть алгоритма состоит в том, чтобы пометить сначала меткой 1 те вершины графа, которые находятся на расстоянии одного ребра от вершины s
, затем меткой 2 те вершины, которые отстоят от s
на расстояние двух ребер, и т.д. При этом на очередном шаге k
мы помечаем те и только те вершины, которые еще не были помечены и которые связаны ребром с какой-либо вершиной, имеющей метку k
–1. Рано или поздно описанный алгоритм остановится, поскольку окажутся помеченными все вершины, достижимые из начальной. Если при этом вершина t
останется непомеченной, то путей из s
в t
не существует. В противном случае метка вершины t
равна длине кратчайшего такого пути.
Чтобы найти сам кратчайший путь (а не только его длину), необходимо при обходе в ширину для каждой обрабатываемой вершины v
запоминать ту вершину u
(помеченную на предыдущем шаге), из которой мы пришли в v
. Восстановление пути начинается с конца: по последней вершине находим предпоследнюю, затем по ней — пред-предпоследнюю и т.д. В результате мы получим вершины кратчайшего пути, записанные в обратном порядке. Поэтому зачастую более выгодно начинать алгоритм обхода в ширину с конечной, а не с начальной вершины.
Следует также отметить, что некоторые графы могут быть естественным образом заданы множеством своих вершин {u
} и итератором f
(u
), который для каждой вершины u перечисляет все соседние ей вершины графа (такого рода итераторы называются перечислителями
). В этом случае нет никакой необходимости в хранении самих ребер графа — обрабатывая вершину u
, алгоритм просто вызывает перечислитель f
(u
) и помещает все вершины, выданные им, в очередь для обработки на следующем шаге. Поэтому выражение «построим граф всех возможных состояний», употребляемое при решении различных задач, означает, что мы строим этот граф лишь мысленно (зачастую соответствующая структура данных потребовала бы слишком большого объема оперативной памяти), а при программировании используем перечислитель. Описанные выше алгоритмы легко обобщаются на случай, когда имеется несколько начальных и/или несколько конечных вершин.
Некоторые задачи для своего решения требуют построения наибольшего паросочетания в двудольном графе. Для этого можно применить известный алгоритм чередующихся цепочек. Конечно, наибольшее паросочетание можно найти и с помощью алгоритма построения максимального потока во вспомогательной сети, но этот способ более трудоемок.
При решении задач на графах второго класса широко используется метод перебора с возвратом
. Поскольку этот метод был описан выше, ограничимся здесь лишь краткими комментариями.
Наиболее часто встречаются следующие задачи второго класса:
Гамильтонов путь и задача коммивояжера;
максимальное независимое множество;
минимальное доминирующее множество;
раскраска графа в минимальное число цветов.
Формулировки приведенных задач и методы их решения (основанные на переборе с возвратом и использовании отсечений) содержатся в соответствующей литературе. Общая идея здесь достаточно простая — следует отсекать те ветви дерева вариантов, которые заведомо не могут привести к решению, лучшему уже найденного. В этом случае часто бывает выгодно найти начальное решение с помощью эвристики (например, жадного алгоритма). Можно использовать эвристический подход и в целом — ограничить множество перебираемых вариантов, руководствуясь теми или иными разумными соображениями. Естественно, что при этом мы можем случайно отсечь ту часть дерева, где содержалось оптимальное решение, и полученное нами решение оптимальным не будет. Также, при программировании этих задач, следует предусмотреть возможность прерывания программы пользователем (или использовать отсечение по времени), выдавая наилучшее из найденных за отведенное время решений.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 2)
Вычислительная геометрия
Геометрические задачи обычно редко встречаются при обучении школьников, поэтому основная часть школьников не представляет, как быстро и эффективно их решать. Но поскольку многие из них хорошо владеют школьным курсом геометрии, они, увидев геометрическую задачу, немедленно берутся за нее. Как правило, это приводит к плачевным результатам. Причина в том, что вычислительная геометрия имеет свою специфику и сильно отличается от школьной геометрии, на которую опирается.
Опишем основные геометрические объекты, используемые при программировании решений к задачам этого раздела:
Точка
— задается двумя (на плоскости) или тремя (в пространстве) координатами.
Прямая
– в отличие от школьного курса, где используется уравнение y
= kx
+ b
, в вычислительной геометрии обычно следует применять более общее уравнение Ax
+ By
+ C
= 0. Тройка чисел (A
, B
, C
) определяется прямой с точностью до коэффициента.
Вектор
— задается своими координатами.
Отрезок
— задается координатами своих концов.
Многоугольник
— задается количеством вершин N
и массивом из N
точек. Часто удобно ввести (N
+1)-ую точку, равную первой.
Окружность
— задается координатами центра и радиусом.
Углы
— задаются в радианах. Обыкновенно берут значение из диапазона [0, 2p) или диапазона (–p, p].
В программах, решающих геометрические задачи, обычно используются вещественные числа. При проведении с ними операций необходимо учитывать погрешность вычислений, вызванную накоплением ошибок в последних разрядах. Это приводит к тому, что вещественные числа, как правило, нельзя сравнивать обычным образом — их нужно сравнивать с какой-то заданной точностью eps
. Например, для выяснения, равно ли вещественное число a
нулю вместо условия a
=0 следует записать abs(a)
.
Также необходимо избегать ошибок, связанных с переполнением целых типов. Например, для вычисления расстояния между двумя целочисленными точками многие используют выражение
sqrt
((x
2
-x
1
)*(x
2
-x
1
)+(y
2
-y1
)*(y
2
-y
1
).
Хотя полученный результат и будет вещественным, преобразование в вещественный тип из целого происходит только при извлечении корня, что делает возможным переполнение целого типа при предыдущих операциях вычитания, умножения и сложения.
Для быстрого и правильного написания решений рекомендуется написать следующий набор стандартных подпрограмм, из которых программы для большей части геометрических задач составляются, как из кубиков:
1. Отношения вещественных чисел:
a) больше;
b) меньше;
c) больше либо равно;
d) меньше либо равно;
e) равно.
2. Работа с прямыми и точками:
a) построение прямой по двум точкам;
b) построение точки пересечения двух прямых;
c) построение прямой, перпендикулярной (параллельной) данной, и проходящей через заданную точку;
d) проверка принадлежности точки отрезку.
3. Работа с многоугольниками:
a) построение выпуклой оболочки;
b) проверка принадлежности точки многоугольнику;
c) вычисление площади треугольника;
d) вычисление площади многоугольника.
4. Работа с векторами:
a) вычисление угла между векторами;
b) вычисление скалярного, векторное и смешанного произведений;
c) сложение и вычитание векторов, умножение вектора на число.
5. Дополнительно:
a) вычисление полярного угла точки;
b) построение точек пересечения двух окружностей;
c) решение квадратного уравнения.
При решении геометрических задач данные подпрограммы следует реализовывать наиболее простым способом. Например, принадлежность точки треугольнику можно проверить, сравнив его площадь с суммой площадей трех других треугольников, образованных парой вершин рассматриваемого треугольника и проверяемой точкой. Равенство означает, что точка лежит внутри либо на стороне треугольника.
Во многих геометрических задачах естественное применения находят вектора и операции над ними: сложение, вычитание, умножение на число, поиск угла между векторами и т.д. Полезно знать свойства скалярного, векторного и смешанного произведений. В тех задачах, в которых требуется найти наилучший по какому-либо критерию геометрический объект, нужно придумать, каким образом ограничиться перебором конечного числа объектов рассматриваемого типа. Для этого следует задаться вопросом, как должно быть устроено оптимальное или локально оптимальное решение.
Пусть, например, нам необходимо найти окружность минимального радиуса, охватывающую заданные N
различных точек плоскости (N
> 1). Представим себе, что в этих точках вбиты гвоздики, и проведем вокруг них окружность достаточно большого радиуса. Теперь заставим эту окружность сжиматься, но так, чтобы все гвоздики по-прежнему оставались внутри нее. Ясно, что перестать сжиматься окружность может лишь в том случае, когда она окажется жестко зафиксированной либо тремя гвоздями, лежащими на ней, либо двумя гвоздями, лежащими на ее диаметре. Тем самым мы свели задачу «бесконечного перебора» всех возможных окружностей на плоскости к «конечному перебору» окружностей, описанных вокруг всех троек точек, и окружностей, построенных на отрезках, соединяющих все пары рассматриваемых точек, как на диаметрах.
Решения некоторых задач основаны на нахождении площади многоугольника и полярного угла точки. Поэтому имеет смысл привести здесь формулы для их вычисления. Пусть (x
1
, y
1
), (x
2
, y
2
), …, (xN
, yN
) — координаты вершин заданного многоугольника в порядке обхода по или против часовой стрелки. Тогда его ориентированная площадь S
равна
При использовании этой формулы не случится ничего страшного, если какие-то две вершины многоугольника будут совпадать или какие-то три — лежать на одной прямой. Если координаты вершин были заданы в порядке обхода против часовой стрелки, то число S
, вычисленное по этой формуле, получится положительным. В противном случае оно будет отрицательным, и для получения обычной геометрической площади нам необходимо взять его абсолютное значение.
Комбинаторные алгоритмы
Рассмотрим теперь решение задач по комбинаторике. В качестве примеров наиболее простых и часто встречающихся классов комбинаторных объектов можно привести подмножества множеств, перестановки, размещения и сочетания их элементов (с повторениями или без), разбиения множеств на подмножества и чисел на слагаемые, двоичные и подвешенные деревья и т.д. Кроме того, можно рассмотреть аналогичные классы объектов для мультимножеств, т.е. для множеств, в которые каждый элемент входит некоторое количество раз, называемое кратностью этого элемента.
Основными вопросами, которые при этом могу возникнуть, являются следующие:
Как подсчитать количество элементов в множестве M
?
Как эффективно перечислить (сгенерировать) все элементы множества M
, каждое ровно один раз?
Пусть на множестве M
определен некоторый порядок. Как эффективно перечислить элементы M
именно в этом порядке?
Как по объекту x
Î M
получить следующий или предыдущий в заданном порядке? Как определить порядок, чтобы соседние объекты отличались бы как можно меньше?
Как по объекту x
Î M
найти его номер для заданного порядка и наоборот, по номеру — элемент? Как определить порядок, чтобы эти операции выполнялись эффективно?
Комбинаторные алгоритмы обычно нужны не сами по себе, а как часть решения более сложной задачи. Для успешного решения олимпиадных задач, предполагающих использование комбинаторных алгоритмов, необходимо хорошо освоить такие алгоритмы, как генерирование перестановок и подсчет разбиений числа N
на сумму от K
до L
слагаемых, каждое из которых принадлежит диапазону от A
до B
. Первые из них необходимы для выработки умения программировать наиболее часто встречающиеся алгоритмы. Вторые — для развития умения придумывать такого рода комбинаторные алгоритмы самостоятельно.
Как правило, решение задач по комбинаторике требует знания динамического программирования и умения реализовать длинную арифметику. Для этого достаточно уметь запрограммировать сложение и вычитание длинных чисел, а также умножение и деление длинного числа на короткое.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО РЕШЕНИЮ ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ (ЧАСТЬ 3)
Моделирование
Решение задач с использованием методов моделирования предполагают обычно знание многих разделов информатики и умение аккуратно программировать большое количество несложных подзадач, компонуя их вместе для получения решения. Обычно такие задачи не представляют трудности с алгоритмической точки зрения, испытывая лишь программистскую технику.
В чистом виде задачи на построение моделей встречаются на олимпиадах по информатике не так часто. Как правило, понятие модели используется здесь для сохранения целостности моделируемой системы, которая декомпозируется в процессе решения на более простые компоненты. В качестве примера такой задачи можно привести следующую: по последовательности команд ОС Unix cd, mkdir, ls, rmdir требуется построить вывод на экран интерпретатора этих команд.
Решение этой задачи сводится к моделированию выполнения входящих в условие задачи команд. После декомпозиции задачи получается несколько подзадач, не представляющих особой алгоритмической сложности:
организация хранения создаваемых каталогов системы;
организация требуемых элементарных операций над структурами данных, построенными в предыдущем шаге;
корректный ввод входных данных (именно, распознавание команды и преобразование параметра команды — задаваемого каталога — к некоторому стандартному виду, в котором они хранятся в нашей структуре);
вывод требуемых данных (как результат одной из операций + обработка ошибок остальных операций).
Решение этих подзадач является делом техники.
Достаточно часто среди олимпиадных задач по информатике встречаются задачи, не подпадающие под упомянутые выше разделы. Можно выделить две группы таких задач. Первая группа — это так называемые задачи «на идею», когда основная сложность решения заключается в придумывании нестандартного, неожиданного алгоритма их решения. Чисто техническая сложность таких задач обычно невелика. Трудно дать какие-либо рекомендации по решению такого рода задач; необходима интуиция, вырабатываемая только частыми тренировками на задачах повышенной сложности и олимпиадных задачах. Кроме того, необходим талант алгоритмиста.
Задачи второй группы — это такие подзадачи, умение решать которые часто необходимо для решения более сложных задач, и которые могут встретиться в любой из задач перечисленных ранее групп. Такими задачами, например, являются нестандартные задачи на комбинаторику, задачи по манипулированию строковыми данными; задачи на длинную арифметику и т.п. При решении таких задач поможет знание быстрых алгоритмов поиска подстроки в строке, алгоритмов реализации основных операций длинной арифметики и вычисления с их помощью некоторых комбинаторных формул и т.п. Важно довести их реализацию до автоматизма, так как в качестве подзадач эти алгоритмы встречаются очень часто, и реализовывать их надо в процессе решения олимпиадной задачи, не задумываясь.
Чтобы успешно выступать на олимпиадах по информатике, необходимо иметь не только хорошие знания в этой области, но и владеть современными информационными технологиями и доведенными до автоматизма практическими навыками решения задач с использованием компьютеров. Да, без опыта программирования и совершенной техники работы с компьютерами на олимпиадах высокого уровня победить не возможно, и тренинг играет в этом случае не последнюю роль. Но в олимпиадах по информатике не это подчас является главным.
Очень важно — за ограниченное время понять смысл задачи, формализовать ее и предложить оптимальный алгоритм ее решения с учетом заданных ограничений. А здесь начинается самое интересное. Практически каждая задача, предлагаемая на олимпиадах высокого уровня, является уникальной, и в чистом виде ее решение нельзя прочитать в каких-либо источниках. Даже знание большого количества опубликованных в литературе алгоритмов не гарантирует ее решение, не говоря о том, что число таких алгоритмов достаточно велико, и знать школьникам их практически невозможно.
Как следствие, школьникам при решении олимпиадных задач приходится не только оперировать типовыми алгоритмами, но и уметь распознать ситуацию, для которой этот алгоритм применим, а также адаптировать этот алгоритм для решения конкретной задачи. О «натаскивании» школьников здесь речь не может идти. Участникам не известно, какие задачи будут на конкретной олимпиаде и что необходимо знать школьнику, чтобы известный алгоритм приспособить для решения предложенной задачи. Если бы в какой-либо стране кто-то знал, как сделать даже самого талантливого школьника абсолютным победителем международной олимпиады, то эта страна надолго монополизировала бы это звание.