ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ

Стр.1

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

Стр.7

Стр.1

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ БУРЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ ДОРЖИ БАНЗАРОВА С. П. Мальцев ОЛИМПИАДНОЕ ПРОГРАММИРОВАНИЕ Рекомендовано УМС БГУ в качестве учебно-методического пособия для обучающихся по направлениям подготовки 01.03.02 Прикладная математика и информатика, 02.03.01 Математика и компьютерные науки, 02.03.03 Математическое обеспечение и администрирование информационных систем, 09.03.03 Прикладная информатика Улан-Удэ Издательство Бурятского госуниверситета 2019

Стр.2

УДК 004.421 ББК 22.183.49 М 215 Утверждено к печати редакционно-издательским советом Бурятского госуниверситета Рецензенты старший преподаватель кафедры информационных технологий, заведующий лабораторией программных систем Бурятского государственного университета Б. В. Хабитуев кандидат физико-математических наук, доцент, заведующий кафедрой высшей математики и общеобразовательных дисциплин Бурятского института инфокоммуникаций Сибирского государственного университета телекоммуникаций и информатики С. Г. Баргуев Мальцев С. П. М 215 Олимпиадное программирование : учебно-методическое пособие. ― Улан-Удэ: Бурятского госуниверситета, 2019. ― 135 с. ISBN 978-59793-1396-2 В учебно-методическом пособии приведены некоторые алгоритмы компьютерной обработки данных и структуры, встречающиеся на олимпиадах по программированию. Пособие предназначено для бакалавриата по направлениям подготовки 02.03.03 Математическое обеспечение и администрирование информационных систем, 02.03.01 Математика и компьютерные науки, 01.03.02 Прикладная математика и информатика, 09.03.03 Прикладная информатика, 01.03.01 Математика. © С. П. Мальцев, 2019 ISBN 978-59793-1396-2 © Бурятский госуниверситет им. Д. Банзарова, 2019

Стр.3

СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ ......................................................................................... 6 1. ОБ ОЛИМПИАДАХ И ОЛИМПИАДНОМ ПРОГРАММИРОВАНИИ ..... 8 Контрольные вопросы к параграфу ................................................ 10 2. СИСТЕМА АВТОМАТИЧЕСКОЙ ПРОВЕРКИ РЕШЕНИЙ EJUDGE ....... 11 Контрольные вопросы к параграфу ................................................ 15 3. ТЕОРЕТИЧЕСКИЙ МИНИМУМ. ОСНОВЫ ЯЗЫКА С++ ...................... 17 Контрольные вопросы к параграфу ................................................ 39 4. ГЕНЕРАТОР ТЕСТОВ ДЛЯ НАПИСАНИЯ КОМПЛЕКТОВ ЗАДАЧ. ....... 40 Контрольные вопросы к параграфу ................................................ 44 5. ПРИМЕРЫ АЛГОРИТМОВ КОМПЬЮТЕРНОЙ ОБРАБОТКИ ДАННЫХ. ................................................................................................................ 45 5.1 Алгоритм Евклида нахождения НОД (наибольшего общего делителя) ........................................................................................... 45 5.2 Решето Эратосфена ..................................................................... 46 5.3 Числа Фибоначчи ........................................................................ 47 5.4 Поиск в ширину ........................................................................... 50 5.5 Поиск в глубину ........................................................................... 54 5.6Топологическая сортировка ........................................................ 56 5.7 Алгоритм поиска компонент связности в графе ...................... 58 5.8 Поиск мостов ............................................................................... 59 5.9 Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом Дейкстры для разреженных графов ................................................................................................ 61 5.10 Алгоритм Флойда-Уоршелла нахождения кратчайших путей между всеми парами вершин ......................................................... 64 3

Стр.4

5.11 Минимальное остовное дерево. Алгоритм Крускала с системой непересекающихся множеств ........................................ 66 5.12 Нахождение Эйлерова пути за O (M) ...................................... 68 5.13 Алгоритм Куна нахождения наибольшего паросочетания в двудольном графе ............................................................................ 69 5.14 Знаковая площадь треугольника и предикат "По часовой стрелке" ............................................................................................. 76 5.15 Пересечение двух отрезков ..................................................... 77 5.15 Пересечение окружности и прямой ........................................ 80 5.16 Построение выпуклой оболочки обходом Грэхэма............... 83 5.17 Префикс-функция. Алгоритм Кнута-Морриса-Пратта ............ 85 5.18 Алгоритмы хэширования в задачах на строки ....................... 89 5.19 Алгоритм Ахо-Корасик .............................................................. 90 5.20 Sqrt-декомпозиция ................................................................... 96 5.21 Система непересекающихся множеств .................................. 99 5.22 Дерево отрезков ..................................................................... 107 5.23 Нахождение наибольшей нулевой подматрицы ................. 113 5.24 Числа Каталана ........................................................................ 117 6. ЛАБОРАТОРНЫЕ РАБОТЫ ............................................................... 120 ЗАКЛЮЧЕНИЕ ....................................................................................... 125 БИБЛИОГРАФИЧЕСКИЙ СПИСОК ........................................................ 126 ПРИЛОЖЕНИЕ ...................................................................................... 130 Приложение №1. Примерное содержание файла statement.xml .......................................................................................................... 130 Приложение №2. Пример файла statement.xml конкретной задачи .............................................................................................. 130 4

Стр.5

Приложение №3. Пример решения задачи из приложения 2. .. 132 Приложение №4. Пример чекера для задачи из приложения №2 .......................................................................................................... 133 Приложение №5. Шаблон отчёта по лабораторной работе ....... 134 Приложение №6. Критерии оценки лабораторной работы ....... 134 5

Стр.6

ПРЕДИСЛОВИЕ Настоящее учебное издание представляет собой учебнометодическое пособие для дисциплин «Олимпиадное программирование», «Курс по программированию», «Дискретная математика и теория графов», «Спортивное программирование», «Структуры и алгоритмы компьютерной обработки данных» в рамках реализации образовательной программы высшего образования по направлениям подготовки бакалавров 02.03.03 Математическое обеспечение и администрирование информационных систем, 02.03.01 Математика и компьютерные науки, 01.03.02 Прикладная математика и информатика, 09.03.03 Прикладная информатика очной и заочной формы обучения и подготовлено в соответствии с требованиями Федерального государственного образовательного стандарта высшего образования. Компетенции обучающегося, формируемые в результате освоения дисциплины: Данная дисциплина способствует формированию следующих компетенций, предусмотренных ФГОС ВО 3+ по направлениям подготовки 02.03.03 Математическое обеспечение и администрирование информационных систем, 02.03.01 Математика и компьютерные науки, 01.03.02 Прикладная математика и информатика, 09.03.03 Прикладная информатика: способность программировать приложения и создавать программные прототипы решения прикладных задач (ПК-8). В результате освоения дисциплины студент должен: основные идиомы разработки алгоритмов; Знать: основные структуры данных, используемые для представления типовых информационных объектов (STL); основные алгоритмы и характеристики их сложности для типовых задач, часто встречающихся и ставших «классическими» в области информатики Уметь: доказывать корректность составленного алгоритма и оценивать основные характеристики его сложности; реализовывать алгоритмы и используемые структуры данных средствами языков программирования высокого уровня; экспериментально (с 6

Стр.7