Опираясь на богатый соревновательный и эвристический опыт, автор предлагает оригинальные реализации классических алгоритмов Computer Science на языках Python и C++. Особое внимание уделено математическим и геометрическим алгоритмам, графовым алгоритмам, структурам данных (в особенности различным деревьям), комбинаторике и работе со строками. Книга поможет заложить и расширить алгоритмическую подготовку, познакомит с эффективными решениями вычислительных задач, а для обучающихся станет настольной. Поможет подготовиться к экзаменам, сертификации, олимпиадам по программированию.
Алгоритмы и структуры данных — основа профессиональной подготовки программиста. В библиотеке профессионала найдутся многотомные неустаревающие труды по этой теме. Но, чтобы выйти за рамки академической Computer Science и перейти к реальной практике, алгоритмы нужно быстро подбирать и применять. Автор этой книги работал над ней более 10 лет, опираясь на свой богатый опыт олимпиадного и спортивного программирования.
В книге собраны варианты реализации и применения важнейших алгоритмов в условиях быстрого принятия решений — что незаменимо на собеседованиях и конференциях. Также книга может быть полезна для подготовки к экзаменам, олимпиадам и соревнованиям по программированию. Но в большей степени она позиционируется как настольная книга для начинающих программистов, желающих быстро и интересно приобрести качественную алгоритмическую подготовку — и претендовать на достойное предложение о работе. Реализации всех алгоритмов даны на двух языках — Python и С++.
Книгу “Алгоритмический тренинг. Решения практических задач на Python и С++” можно купить со скидкой в интернет-магазине издательства “БХВ“.
Введение. 9
Глава 1. Для кого эта книга. 10
Глава 2. Чему обучит эта книга. 11
Глава 3. Спортивное и промышленное программирование. 12
Глава 4. Как пользоваться книгой. 14
Ступень I. Разминка. 15
Глава 5. Вводные задачи. 16
5.1. A+B. 16
5.2. Пример решения задачи. Числа Фибоначчи. 17
5.3. Пример решения задачи. Манхэттенское расстояние. 18
5.4. Пример решения задачи. Путь до ксерокса. 20
5.5. Пример решения задачи. Проверка перестановки. 22
5.6. Пример решения задачи. Циклы перестановки. 23
Глава 6. Разминочные конструктивные задачи. 25
6.1. Пример решения задачи. Пара с минимальным произведением. 25
6.2. Пример решения задачи. Тайная жизнь деревьев. 27
6.3. Пример решения задачи. Подписывание открыток. 28
6.4. Пример решения задачи. Исправление перестановки. 30
6.5. Пример решения задачи. Минимальный палиндром. 33
6.6. Пример решения задачи. Исключающее ИЛИ от 1 до n. 34
6.7. Пример решения задачи. Врачи и посетители. 37
6.8. Пример решения задачи. Минимизация перепадов. 40
6.9. Пример решения задачи. Одномерный геометрический центр. 42
Глава 7. Разминочные реализационные задачи. 45
7.1. Пример решения задачи. Морской бой. 45
7.2. Пример решения задачи. Стоимость интернет-связи. 47
7.3. Пример решения задачи. Пересечение двух прямоугольников. 50
7.4. Пример решения задачи. Проверка скобочной последовательности. 52
7.5. Пример решения задачи. Проверка скобочной последовательности
с двумя типами. 54
7.6. Пример решения задачи. Зеркальный лабиринт. 55
7.6. Пример решения задачи. Троичная сбалансированная система счисления. 58
Глава 8. Задачи для самостоятельного решения. 60
8.1. Примеры задач. 60
8.2. Задачи в онлайн-системах. 63
Итоги ступени I 64
Ступень II. Базовые алгоритмы.. 65
Глава 9. Оценка скорости работы алгоритмов. 66
9.1. Эмпирическая скорость процессора. 66
9.2. Асимптотическая оценка. Основы. 68
9.3. Практическая применимость асимптотических оценок. 75
9.4. Библиотечные реализации алгоритмов и их скорость. 76
Глава 10. Наибольший общий делитель. Алгоритм Евклида. 80
10.1. Постановка задачи. 80
10.2. Тривиальный алгоритм. 80
10.3. Алгоритм Евклида. 80
10.4. Доказательство алгоритма Евклида. 81
10.5. Реализация алгоритма Евклида. 81
10.6. Время работы алгоритма Евклида. 83
10.7. Пример решения задачи. Сокращение дроби. 84
10.8. Пример решения задачи. Наименьшее общее кратное. 84
10.9. Пример решения задачи. НОД нескольких чисел. 86
10.10. Пример решения задачи. Увеличение НОД массива. 87
10.11. Упражнения для самостоятельного решения. 88
Глава 11. Простые задачи на учет асимптотики. 91
11.1. Пример решения задачи. Префиксы перестановки. 91
11.2. Пример решения задачи. Парковочные места. 92
Глава 12. Объединение одномерных отрезков. 95
12.1. Постановка задачи. 95
12.2. Алгоритм объединения отрезков. 95
12.3. Реализация алгоритма объединения отрезков. 95
12.4. Пример решения задачи. Часы приема. 96
12.5. Пример решения задачи. Стрельба по отрезкам. 97
12.6. Пример решения задачи. Многослойная покраска. 99
Глава 13. Метод двух указателей. 102
13.1. Пример решения задачи. Пары фиксированной суммы. 102
13.2. Пример решения задачи. Длиннейший подотрезок без повторов. 104
13.3. Пример решения задачи. Подотрезки со всеми числами. 105
13.4. Пример решения задачи. Трехцветный забор. 107
Глава 14. Двоичный поиск. 110
14.1. Базовая задача: поиск в упорядоченном массиве. 110
14.2. Алгоритм двоичного поиска. 110
14.3. Реализация алгоритма двоичного поиска. 111
14.4. Библиотечные реализации. 112
14.5. Пример решения задачи. Подсчет меньших чисел. 112
14.6. Пример решения задачи. Грузовой лифт в отеле. 114
14.7. Пример решения задачи. Дисплеи для смартфонов. 116
14.8. Пример решения задачи. Прыжки лягушки. 118
14.9. Пример решения задачи. Корень уравнения. 120
14.10. Прочие применения двоичного поиска. 123
Глава 15. Проверка на простоту и факторизация. 124
15.1. Определения. 124
15.2. Общие сведения о простых числах и о факторизации. 124
15.3. Проверка числа на простоту. Базовый алгоритм. 125
15.4. Факторизация числа. Базовый алгоритм. 126
15.5. Пример решения задачи. Подсчет числа делителей. 127
15.6. Пример решения задачи. Иррациональный портной. 128
15.7. Пример решения задачи. Произведения-квадраты. 131
15.8. Пример решения задачи. Запросы числа делителей. 133
Глава 16. Динамическое программирование. Основы.. 136
16.1. Пример решения задачи. Сумма однообразных чисел. 136
16.2. Пример решения задачи. Наидлиннейшая возрастающая подпоследовательность. 138
16.3. Пример решения задачи. Подмножество с заданной суммой. 140
16.4. Пример решения задачи. Минимальное подмножество с заданной суммой. 143
16.5. Пример решения задачи. Получение суммы монетами заданных номиналов. 145
16.6. Пример решения задачи. Задача о рюкзаке. 146
16.7. Пример решения задачи. Кладоискатель. 148
16.8. Пример решения задачи. Путь в матрице. 151
16.9. Пример решения задачи. Расстояние редактирования. 153
Глава 17. Задачи для самостоятельного решения. 156
17.1. Примеры задач. 156
17.2. Задачи в онлайн-системах. 161
Итоги ступени II 163
Ступень III. Расширение базового арсенала. 163
Глава 18. Техники предварительного подсчета на массивах. 164
18.1. Указатели до ближайших элементов. 164
18.2. Частичные суммы. 165
18.3. Указатели до ближайших меньших элементов. 166
18.4. Списки позиций. 167
18.5. Сжатие значений. 168
18.6. Пример решения задачи. Поиск начала слова. 168
18.7. Пример решения задачи. Два подотрезка заданной длины с максимальной суммой. 170
18.8. Пример решения задачи. Подсчет чисел в подотрезках. 172
18.9. Пример решения задачи. Подотрезок с максимальной суммой. 175
18.10. Пример решения задачи. Проекционная реклама. 180
18.11. Пример решения задачи. Подотрезок с максимальным средним
арифметическим. 182
18.12. Пример решения задачи. Сумма в прямоугольнике. 186
Глава 19. Графы. Обход в глубину. 190
19.1. Что такое граф. 190
19.2. Ориентированные и неориентированные графы. 191
19.3. Способы представления графов в компьютере. 191
19.4. Алгоритм обхода в глубину. 198
19.5. Реализация обхода в глубину. 199
19.6. Пример решения задачи. Проверка наличия пути. 202
19.7. Пример решения задачи. Конная прогулка. 204
19.8. Пример решения задачи. Проверка связности. 207
19.9. Пример решения задачи. Проверка двудольного графа. 209
19.10. Пример решения задачи. Проверка орграфа на ацикличность. 213
19.11. Пример решения задачи. Топологическая сортировка. 218
19.12. Пример решения задачи. Диаметр дерева 221
Глава 20. Графы. Обход в ширину. 223
20.1. Алгоритм обхода в ширину. 223
20.2. Свойства обхода в ширину. 224
20.3. Реализация обхода в ширину. 225
20.4. Пример решения задачи. Кластер компьютеров. 228
20.5. Пример решения задачи. Робот в лабиринте. 230
20.6. Пример решения задачи. Наводнение. 234
Глава 21. Решето Эратосфена. 236
21.1. Алгоритм решета Эратосфена. 236
21.2. Демонстрация работы алгоритма. 236
21.3. Доказательство корректности решета Эратосфена. 237
21.4. Время работы решета Эратосфена. 237
21.5. Базовые оптимизации решета Эратосфена. 238
21.6. Реализация решета Эратосфена. 239
21.7. Дальнейшие оптимизации решета Эратосфена. 240
21.8. Пример решения задачи. Подсчет простых чисел в отрезке. 243
Глава 22. Двоичное возведение в степень. 246
22.1. Ключевая идея. 246
22.2. Алгоритм двоичного возведения в степень. 247
22.3. Иллюстрация работы алгоритма. 247
22.4. Время работы двоичного возведения в степень. 248
22.5. Реализация двоичного возведения в степень. 248
22.6. Пример решения задачи. Последние цифры степени. 249
22.7. Пример решения задачи. Обратное по простому модулю. Малая теорема Ферма. 251
22.8. Пример решения задачи. Быстрое вычисление чисел Фибоначчи.
Двоичное возведение матриц в степень. 252
22.9. Пример решения задачи. Физический движок. 255
22.10. Пример решения задачи. Подсчет путей фиксированной длины. 261
Глава 23. Структуры данных. Дерево отрезков. 265
23.1. Базовый вариант. Дерево для минимумов. 265
23.2. Дерево отрезков для максимумов. 272
23.3. Дерево отрезков с запросами модификации. 273
23.4. Дерево отрезков для сумм. 274
23.5. Прочие виды операций в дереве отрезков. 274
23.6. Запросы обновления на отрезке. 275
23.7. Дальнейшие обобщения дерева отрезков. 279
23.8. Пример решения задачи. Наидлиннейшая возрастающая
подпоследовательность (быстрый вариант) 280
23.9. Пример решения задачи. Наименьший общий предок. 281
Глава 24. Задачи для самостоятельного решения. 284
24.1. Примеры задач. 284
24.2. Задачи в онлайн-системах. 288
Ступень IV. Разносторонняя подготовка. 291
Глава 25. Производительность ввода-вывода. 292
25.1. Производительность ввода-вывода в Python. 292
25.2. Производительность ввода-вывода в C++. 294
Глава 26. Графы. Алгоритм Дейкстры.. 298
26.1. Постановка задачи поиска кратчайших путей. 298
26.2. Пример. 298
26.3. Алгоритм Дейкстры. 299
26.4. Ограничения алгоритма Дейкстры. 300
26.5. Пример работы алгоритма Дейкстры. 300
26.6. Восстановление кратчайшего пути. 302
26.7. Доказательство алгоритма Дейкстры. 303
26.8. Квадратичная реализация алгоритма Дейкстры. 304
26.9. Алгоритм Дейкстры для разреженных графов. 308
26.10. Пример решения задачи. Оптимальный путь четной длины. 312
26.11. Пример решения задачи. Ребра кратчайших путей. 315
Глава 27. Графы. Компоненты сильной связности. 318
27.1. Определения. 318
27.2. Алгоритм поиска компонент сильной связности. 320
27.3. Доказательство алгоритма. 320
27.4. Демонстрация работы алгоритма. 323
27.5. Временная сложность алгоритма. 324
27.6. Реализация алгоритма. 324
27.7. Дополнительные свойства алгоритма. 327
27.8. Пример решения задачи. Железнодорожный вокзал. 327
27.9. Пример решения задачи. Задача умозаключенного. 328
27.10. Пример решения задачи. Сбор дани. 329
Глава 28. Работа с вещественными числами. 335
28.1. Формат чисел с плавающей запятой. 335
28.2. Проблемы чисел с плавающей запятой. 337
28.3. Приемы работы с числами с плавающей запятой. 342
Глава 29. Геометрия на плоскости. Основы.. 346
29.1. Расстояние между точками. 346
29.2. Косое произведение векторов. 347
29.3. Скалярное произведение векторов. 348
29.4. Площадь треугольника. 349
29.5. Направление поворота. Ориентированная площадь треугольника. 350
29.6. Площадь многоугольника. 351
29.7. Проверка точки на принадлежность прямой. 353
29.8. Проверка точки на принадлежность отрезку. 353
29.9. Проверка двух отрезков на пересечение. 355
29.10. Расстояние от точки до прямой. 358
29.11. Расстояние от точки до отрезка. 359
29.12. Точка пересечения двух прямых. 362
29.13. Точка пересечения двух отрезков. 365
29.14. Матрица поворота. 368
29.15. Пример решения задачи. Проверка окружностей на пересечение. 369
29.16. Пример решения задачи. Пересечение окружности и прямой. 371
29.17. Пример решения задачи. Сортировка точек по углу. 375
Глава 30. Расширенный алгоритм Евклида. 380
30.1. Алгоритм. 380
30.2. Доказательство. 380
30.3. Реализация расширенного алгоритма Евклида. 381
30.4. Пример решения задачи. Прыжки вперед и назад. 382
30.5. Пример решения задачи. Линейное диофантово уравнение с двумя переменными. 384
30.6. Пример решения задачи. Обратное по составному модулю.. 386
Глава 31. Задачи для самостоятельного решения. 389
31.1. Примеры задач. 389
Заключение. 395
Методики решения задач. 396
Благодарности. 397
Послесловие. 398
Приложение. Решения задач. 399
Задачи из главы 8. 399
Задачи из главы 10. 401
Задачи из главы 17. 402
Задачи из главы 24. 406
Задачи из главы 31. 411
Предметный указатель. 415
Максим Иванов профессионально занимается системным программированием, долгое время увлекается изучением Windows API, подробно исследовал ядро Windows. Несколько лет участвовал в олимпиадах по программированию, серебряный призёр чемпионата мира 2011 г. в составе команды Саратовского государственного университета. Автор сайта об алгоритмах https://e-maxx.ru, на основе которого написана эта книга.
