Алгоритмы на практике

Description

«Алгоритмы на практике» научат решать самые трудные и интересные программистские задачи, а также разрабатывать собственные алгоритмы. В качестве примеров для обучения взяты реальные задания с международных соревнований по программированию. Вы узнаете, как классифицировать задачи, правильно подбирать структуру данных и выбирать алгоритм для решения. Поймете, что выбор структуры данных — будь то хеш-таблица, куча или дерево — влияет на скорость выполнения программы и на эффективность алгоритма. Разберетесь, как применять рекурсию, динамическое программирование, двоичный поиск. Никакого условного псевдокода, все примеры сопровождаются исходным кодом на языке Си с подробными объяснениями. Предисловие Благодарности От издательства Введение Онлайн-ресурсы Для кого эта книга Язык программирования Почему Cи? Ключевое слово Static Добавление файлов Освобождение памяти Темы Сайты с задачами Структура описания задачи Задача. Очереди за продуктами Условие Решение Примечания Глава 1. Хеш-таблицы Задача 1. Уникальные снежинки Условие Упрощаем задачу Решение основной задачи Решение 1: последовательное сравнение Решение 2: сокращение числа вычислений Хеш-таблицы Проектирование хеш-таблицы Зачем использовать хеш-таблицы? Задача 2. Сложносоставные слова Условие Определение сложносоставных слов Решение Задача 3. Проверка орфографии: удаление буквы Условие Размышление о хеш-таблицах Ad hoc-подход Выводы Примечания Глава 2. Деревья и рекурсия Задача 1. Трофеи Хэллоуина Условие Двоичные деревья Решаем пример Представление двоичных деревьев Сбор конфет Принципиально другое решение Обход минимального количества улиц Считывание входных данных Когда использовать рекурсию? Задача 2. Расстояние до потомка Условие Считывание входных данных Количество потомков одного узла Количество потомков всех узлов Упорядочивание узлов Вывод информации Функция main Выводы Примечания Глава 3. Мемоизация и динамическое программирование Задача 1. Страсть к бургерам Условие Разработка плана Описание оптимальных решений Решение 1. Рекурсия Решение 2. Мемоизация Решение 3. Динамическое программирование Мемоизация и динамическое программирование Шаг 1. Структура оптимальных решений Шаг 2. Рекурсивное решение Шаг 3. Мемоизация Шаг 4. Динамическое программирование Задача 2. Экономные покупатели Условие Описание оптимального решения Решение 1. Рекурсия Функция main Решение 2. Мемоизация Задача 3. Хоккейное соперничество Условие О принципиальных матчах Описание оптимальных решений Решение 1. Рекурсия Решение 2. Мемоизация Решение 3. Динамическое программирование Оптимизация пространства Задача 4. Учебный план Условие Решение. Мемоизация Выводы Примечания Глава 4. Графы и поиск в ширину Задача 1. Погоня за пешкой Условие Оптимальное перемещение Лучший результат коня Блуждающий конь Оптимизация времени Графы и BFS Что такое графы? Графы и деревья BFS в графах Задача 2. Лазание по канату Условие Решение 1. Поиск возможностей Решение 2. Модификация Задача 3. Перевод книги Условие Построение графа BFS Общая стоимость Выводы Примечания Глава 5. Кратчайший путь во взвешенных графах Задача 1. Мышиный лабиринт Условие BFS не подходит Быстрейшие пути во взвешенных графах Построение графа Реализация алгоритма Дейкстры Две оптимизации Алгоритм Дейкстры Время выполнения алгоритма Дейкстры Ребра с отрицательными весами Задача 2. Дорога к бабушке Условие Матрица смежности Построение графа Странные пути Подзадача 1: кратчайшие пути Подзадача 2: количество кратчайших путей Выводы Примечания Глава 6. Двоичный поиск Задача 1. Кормление муравьев Условие Новая форма задачи с деревом Считывание входных данных Проверка пригодности решения Поиск решения Двоичный поиск Время выполнения двоичного поиска Определение допустимости Поиск по упорядоченному массиву Задача 2. Прыжки вдоль реки Условие Жадная идея Проверка допустимости Поиск решения Считывание входных данных Задача 3. Качество жизни Условие Упорядочивание прямоугольников Двоичный поиск Проверка допустимости Ускоренная проверка допустимости Задача 4. Двери пещеры Условие Решение подзадачи Использование линейного поиска Использование двоичного поиска Выводы Примечания Глава 7. Кучи и деревья отрезков Задача 1. Акция в супермаркете Условие Решение 1. Максимум и минимум в массиве Max-куча Min-кучи Решение 2. Кучи Кучи Два дополнительных варианта применения Выбор структуры данных Задача 2. Построение декартовых деревьев Условие Рекурсивный вывод декартовых поддеревьев Сортировка по меткам Решение 1. Рекурсия Запросы максимума на отрезке Деревья отрезков Решение 2. Дерево отрезков Деревья отрезков Задача 3. Сумма двух элементов Условие Заполнение дерева отрезков Запрос к дереву отрезков Обновление дерева отрезков Функция main Выводы Примечания Глава 8. Система непересекающихся множеств Задача 1. Социальная сеть Условие Моделирование в виде графа Решение 1. BFS Система непересекающихся множеств Решение 2. Система непересекающихся множеств Оптимизация 1. Объединение по размеру Оптимизация 2. Сжатие пути Система непересекающихся множеств Три требования к связям Применение системы непересекающихся множеств Оптимизации Задача 2. Друзья и враги Условие Аугментация: враги Функция main Поиск и объединение SetFriends и SetEnemies AreFriends и AreEnemies Задача 3. Уборка комнаты Условие Равнозначные ящики Функция main Поиск и объединение Выводы Примечания Послесловие Приложение A. Приложение A. Время выполнения алгоритма Оценка скорости выполнения... и не только Нотация О-большое Линейное время Постоянное время Дополнительный пример Квадратичное время О-большое на страницах книги Приложение Б. Потому что не могу удержаться Уникальные снежинки: неявные связные списки Страсть к бургерам: реконструкция решения Погоня за пешкой: кодирование ходов Алгоритм Дейкстры и использование куч Мышиный лабиринт: отслеживание с помощью куч Мышиный лабиринт: реализация с кучами Сжатие сжатия пути Шаг 1. Больше никаких тернарных «если» Шаг 2. Более понятный оператор присваивания Шаг 3. Понятная рекурсия Приложение В. Сводка по задачам