Алгоритмический тренинг. Решения практических задач на Python и С++

СОДЕРЖАНИЕ....4

ВВЕДЕНИЕ....10

Глава 1. Для кого эта книга....11

Глава 2. Чему обучит эта книга....12

Глава 3. Спортивное и промышленное программирование....13

Глава 4. Как пользоваться книгой....15

СТУПЕНЬ I. РАЗМИНКА....16

Глава 5. Вводные задачи....17

5.1. A+B....17

5.2. Пример решения задачи. Числа Фибоначчи....18

5.3. Пример решения задачи. Манхэттенское расстояние....19

5.4. Пример решения задачи. Путь до ксерокса....21

5.5. Пример решения задачи. Проверка перестановки....23

5.6. Пример решения задачи. Циклы перестановки....24

Глава 6. Разминочные конструктивные задачи....26

6.1. Пример решения задачи. Пара с минимальным произведением....26

6.2. Пример решения задачи. Тайная жизнь деревьев....28

6.3. Пример решения задачи. Подписывание открыток....29

6.4. Пример решения задачи. Исправление перестановки....31

6.5. Пример решения задачи. Минимальный палиндром....34

6.6. Пример решения задачи. Исключающее ИЛИ от 1 до n....35

6.7. Пример решения задачи. Врачи и посетители....38

6.8. Пример решения задачи. Минимизация перепадов....41

6.9. Пример решения задачи. Одномерный геометрический центр....43

Глава 7. Разминочные реализационные задачи....46

7.1. Пример решения задачи. Морской бой....46

7.2. Пример решения задачи. Стоимость интернет-связи....48

7.3. Пример решения задачи. Пересечение двух прямоугольников....51

7.4. Пример решения задачи. Проверка скобочной последовательности....53

7.5. Пример решения задачи. Проверка скобочной последовательностис двумя типами....55

7.6. Пример решения задачи. Зеркальный лабиринт....56

7.6. Пример решения задачи. Троичная сбалансированная система счисления....59

Глава 8. Задачи для самостоятельного решения....61

8.1. Примеры задач....61

8.2. Задачи в онлайн-системах....64

Итоги ступени I....65

СТУПЕНЬ II. БАЗОВЫЕ АЛГОРИТМЫ....66

Глава 9. Оценка скорости работы алгоритмов....67

9.1. Эмпирическая скорость процессора....67

9.2. Асимптотическая оценка. Основы....69

9.3. Практическая применимость асимптотических оценок....76

9.4. Библиотечные реализации алгоритмов и их скорость....77

Глава 10. Наибольший общий делитель. Алгоритм Евклида....81

10.1. Постановка задачи....81

10.2. Тривиальный алгоритм....81

10.3. Алгоритм Евклида....81

10.4. Доказательство алгоритма Евклида....82

10.5. Реализация алгоритма Евклида....82

10.6. Время работы алгоритма Евклида....84

10.7. Пример решения задачи. Сокращение дроби....85

10.8. Пример решения задачи. Наименьшее общее кратное....85

10.9. Пример решения задачи. НОД нескольких чисел....87

10.10. Пример решения задачи. Увеличение НОД массива....88

10.11. Упражнения для самостоятельного решения....89

Глава 11. Простые задачи на учет асимптотики....92

11.1. Пример решения задачи. Префиксы перестановки....92

11.2. Пример решения задачи. Парковочные места....93

Глава 12. Объединение одномерных отрезков....96

12.1. Постановка задачи....96

12.2. Алгоритм объединения отрезков....96

12.3. Реализация алгоритма объединения отрезков....96

12.4. Пример решения задачи. Часы приема....97

12.5. Пример решения задачи. Стрельба по отрезкам....98

12.6. Пример решения задачи. Многослойная покраска....100

Глава 13. Метод двух указателей....103

13.1. Пример решения задачи. Пары фиксированной суммы....103

13.2. Пример решения задачи. Длиннейший подотрезок без повторов....105

13.3. Пример решения задачи. Подотрезки со всеми числами....106

13.4. Пример решения задачи. Трехцветный забор....108

Глава 14. Двоичный поиск....111

14.1. Базовая задача: поиск в упорядоченном массиве....111

14.2. Алгоритм двоичного поиска....111

14.3. Реализация алгоритма двоичного поиска....112

14.4. Библиотечные реализации....113

14.6. Пример решения задачи. Грузовой лифт в отеле....115

14.7. Пример решения задачи. Дисплеи для смартфонов....117

14.8. Пример решения задачи. Прыжки лягушки....119

14.9. Пример решения задачи. Корень уравнения....121

14.10. Прочие применения двоичного поиска....124

Глава 15. Проверка на простоту и факторизация....125

15.1. Определения....125

15.2. Общие сведенияо простых числах и о факторизации....125

15.3. Проверка числа на простоту. Базовый алгоритм....126

15.4. Факторизация числа. Базовый алгоритм....127

15.5. Пример решения задачи. Подсчет числа делителей....128

15.6. Пример решения задачи. Иррациональный портной....129

15.7. Пример решения задачи. Произведения-квадраты....132

15.8. Пример решения задачи. Запросы числа делителей....134

Глава 16. Динамическое программирование.Основы....137

16.1. Пример решения задачи. Сумма однообразных чисел....137

16.2. Пример решения задачи. Наидлиннейшая возрастающая подпоследовательность....139

16.3. Пример решения задачи. Подмножество с заданной суммой....141

16.4. Пример решения задачи. Минимальное подмножество с заданной суммой....144

16.5. Пример решения задачи. Получение суммы монетами заданных номиналов....146

16.6. Пример решения задачи. Задача о рюкзаке....147

16.7. Пример решения задачи. Кладоискатель....149

16.8. Пример решения задачи. Путь в матрице....152

16.9. Пример решения задачи. Расстояние редактирования....154

Глава 17. Задачи для самостоятельного решения....157

17.1. Примеры задач....157

17.2. Задачи в онлайн-системах....162

Итоги ступени II....163

СТУПЕНЬ III. РАСШИРЕНИЕ БАЗОВОГО АРСЕНАЛА....164

Глава 18. Техники предварительногоподсчета на массивах....165

18.1. Указатели до ближайших элементов....165

18.2. Частичные суммы....166

18.3. Указатели до ближайших меньших элементов....167

18.4. Списки позиций....168

18.5. Сжатие значений....169

18.6. Пример решения задачи. Поиск начала слова....169

18.7. Пример решения задачи. Два подотрезка заданной длины с максимальной суммой....171

18.8. Пример решения задачи. Подсчет чисел в подотрезках....173

18.9. Пример решения задачи. Подотрезок с максимальной суммой....176

18.10. Пример решения задачи. Проекционная реклама....181

18.11. Пример решения задачи. Подотрезок с максимальным средним арифметическим....183

18.12. Пример решения задачи. Сумма в прямоугольнике....187

Глава 19. Графы. Обход в глубину....191

19.1. Что такое граф....191

19.2. Ориентированные и неориентированные графы....192

19.3. Способы представления графов в компьютере....192

19.4. Алгоритм обхода в глубину....199

19.5. Реализация обхода в глубину....200

19.6. Пример решения задачи. Проверка наличия пути....203

19.7. Пример решения задачи. Конная прогулка....205

19.8. Пример решения задачи. Проверка связности....208

19.9. Пример решения задачи. Проверка двудольного графа....210

19.10. Пример решения задачи. Проверка орграфа на ацикличность....214

19.11. Пример решения задачи. Топологическая сортировка....219

19.12. Пример решения задачи. Диаметр дерева....222

Глава 20. Графы. Обход в ширину....224

20.1. Алгоритм обхода в ширину....224

20.2. Свойства обхода в ширину....225

20.3. Реализация обхода в ширину....226

20.4. Пример решения задачи. Кластер компьютеров....229

20.5. Пример решения задачи. Робот в лабиринте....231

20.6. Пример решения задачи. Наводнение....235

Глава 21. Решето Эратосфена....237

21.1. Алгоритм решета Эратосфена....237

21.2. Демонстрация работы алгоритма....237

21.3. Доказательство корректности решета Эратосфена....238

21.4. Время работы решета Эратосфена....238

21.5. Базовые оптимизации решета Эратосфена....239

21.6. Реализация решета Эратосфена....240

21.7. Дальнейшие оптимизации решета Эратосфена....241

21.8. Пример решения задачи. Подсчет простых чисел в отрезке....244

Глава 22. Двоичное возведение в степень....247

22.1. Ключевая идея....247

22.2. Алгоритм двоичного возведения в степень....248

22.3. Иллюстрация работы алгоритма....248

22.4. Время работы двоичного возведения в степень....249

22.5. Реализация двоичного возведения в степень....249

22.6. Пример решения задачи. Последние цифры степени....250

22.7. Пример решения задачи. Обратное по простому модулю. Малая теорема Ферма....252

22.8. Пример решения задачи. Быстрое вычисление чисел Фибоначчи. Двоичное возведение матриц в степень....253

22.9. Пример решения задачи. Физический движок....256

22.10. Пример решения задачи. Подсчет путей фиксированной длины....262

Глава 23. Структуры данных. Дерево отрезков....266

23.1. Базовый вариант.Дерево для минимумов....266

23.2. Дерево отрезков для максимумов....273

23.3. Дерево отрезков с запросами модификации....274

23.4. Дерево отрезков для сумм....275

23.5. Прочие виды операций в дереве отрезков....275

23.6. Запросы обновления на отрезке....276

23.7. Дальнейшие обобщения дерева отрезков....280

23.8. Пример решения задачи. Наидлиннейшая возрастающая подпоследовательность (быстрый вариант)....281

23.9. Пример решения задачи. Наименьший общий предок....282

Глава 24. Задачи для самостоятельного решения....285

24.1. Примеры задач....285

24.2. Задачи в онлайн-системах....289

СТУПЕНЬ 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.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

ЗАКЛЮЧЕНИЕ....394

Методики решения задач....395

Благодарности....396

Послесловие....397

Приложение. Решения задач....398

Задачи из главы 8....398

Задачи из главы 10....400

Задачи из главы 17....401

Задачи из главы 24....405

Задачи из главы 31....410

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ....414

Опираясь на богатый соревновательный и эвристический опыт, автор предлагает оригинальные реализации классических алгоритмов Computer Science на языках Python и C++. Особое внимание уделено математическим и геометрическим алгоритмам, графовым алгоритмам, структурам данных (в особенности различным деревьям), комбинаторике и работе со строками. Книга поможет заложить и расширить алгоритмическую подготовку, познакомит с эффективными решениями вычислительных задач, а для обучающихся станет настольной. Поможет подготовиться к экзаменам, сертификации, олимпиадам по программированию.