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

Предисловие
Благодарности
От издательства
Введение
Онлайн-ресурсы
Для кого эта книга
Язык программирования
Почему 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. Понятная рекурсия
Приложение В. Сводка по задачам