Алгоритмы и программы. Решение олимпиадных задач

Содержание книги «Алгоритмы и программы. Решение олимпиадных задач»:

• 13 Предисловие
  • 15 От издательства «Диалектика»
• 17 Глава 1. Разминка (понемногу о разном)
  • 17 1.1. Три простые задачи
    • 17 1.1.1. Совпадения стрелок часов
    • 18 1.1.2. Последовательности с одинаковыми суммами
    • 19 1.1.3. Ребус
  • 23 1.2. Знакомство со сложностью алгоритмов
    • 23 1.2.1. Простые и составные числа
    • 25 1.2.2. Понятие сложности алгоритма
    • 27 1.2.3. Характер возрастания сложности
    • 28 1.2.4. Алгоритм Евклида и его современная версия
    • 29 1.2.5. Бинарный алгоритм
    • 30 1.2.6. Понятие сложности задачи
    • 31 1.2.7. Что выбирать?
  • 31 1.3. Несколько технических вопросов
    • 31 1.3.1. Проектирование сверху вниз, подпрограммы и структурное кодирование
    • 32 1.3.2. Когда уместны безусловные переходы
    • 34 1.3.3. Несколько замечаний о стиле
    • 35 1.3.4. Отладка программы
    • 37 1.3.5. Директивы компилятору
    • 38 1.3.6. Проверка программы
  • 40 1.4. Ввод последовательностей данных
    • 40 1.4.1. Организация данных и вид цикла ввода
    • 43 1.4.2. Изменение источника данных
  • 44 Упражнения
• 47 Глава 2. Однопроходные алгоритмы
  • 47 2.1. Попутные вычисления
    • 47 2.1.1. Три простых примера
    • 49 2.1.2. Максимальная сумма отрезка числовой последовательности
    • 50 2.1.3. Инопланетная армия
    • 53 2.1.4. Стрельба из двуствольной пушки
  • 55 2.2. Чтение и обработка символов
    • 55 2.2.1. Удаление пробелов
    • 57 2.2.2. Удаление комментариев
    • 59 2.2.3. Чтение и вычисление многочлена
    • 67 2.2.4. Языки скобок
    • 72 2.2.5. Линейный поиск подстроки в тексте
  • 76 Упражнения
• 79 Глава 3. Рекурсия
  • 79 3.1. Основные понятия
    • 79 3.1.1. Рекурсивные определения
    • 80 3.1.2. Простейший пример рекурсивной подпрограммы
    • 81 3.1.3. Глубина рекурсии и общее количество рекурсивных вызовов
    • 83 3.1.4. Косвенная рекурсия
  • 85 3.2. Быстрое возведение в степень
  • 88 3.3. Рисование самоподобных ломаных
    • 89 3.3.1. Снежинка Коха
    • 90 3.3.2. Треугольник Серпиньского
    • 93 3.3.3. Драконова ломаная
  • 95 Упражнения
• 97 Глава 4. Нестандартная обработка чисел
  • 97 4.1. Длинная целочисленная арифметика
    • 98 4.1.1. Представление длинных чисел
    • 100 4.1.2. Сравнение, сложение и вычитание длинных целых
    • 102 4.1.3. Организация ввода-вывода
    • 103 4.1.4. Умножение длинных целых
    • 105 4.1.5. Деление длинных целых
    • 107 4.1.6. Целая часть квадратного корня длинного числа
  • 109 4.2. Два магических числа
    • 109 4.2.1. Число e
    • 112 4.2.2. Число π
  • 112 4.3. Остатки от деления
    • 113 4.3.1. Плиты в треугольнике
    • 115 4.3.2. Кратное число с одинаковыми цифрами
  • 116 4.4. Отслеживание циклических повторений
    • 116 4.4.1. Десятичное представление дроби ρ-алгоритм
    • 119 4.4.2. Остатки от деления чисел Фибоначчи
  • 121 4.5. Нули в конце факториала
  • 124 Упражнения
• 127 Глава 5. Бинарный поиск, слияние и сортировка
  • 127 5.1. Бинарный поиск
    • 127 5.1.1. Идея бинарного поиска
    • 128 5.1.2. «Оптический танк»
  • 130 5.2. Слияние упорядоченных последовательностей
    • 130 5.2.1. Слияние двух участков массива
    • 131 5.2.2. Слияние файлов
  • 135 5.3. Основные способы сортировки
    • 135 5.3.1. Два простейших алгоритма
    • 137 5.3.2. Сортировка слиянием
    • 140 5.3.3. Быстрая сортировка
    • 142 5.3.4. Пирамидальная сортировка
    • 145 5.3.5. Линейная сортировка подсчетом
    • 148 5.3.6. Поразрядная сортировка
  • 150 5.4. Применение сортировки
    • 150 5.4.1. Проверка уникальности
    • 151 5.4.2. Проход в заборе
    • 153 5.4.3. Транзитивность
  • 154 Упражнения
• 159 Глава 6. Вычислительная геометрия на плоскости
  • 159 6.1. Точки, векторы, прямые, отрезки
    • 159 6.1.1. Точки, векторы, углы и ориентированная площадь
    • 162 6.1.2. Представление прямых и отрезков
    • 164 6.1.3. Взаимное расположение прямых, отрезков и точек
    • 169 6.1.4. Две задачи о треугольниках
  • 173 6.2. Многоугольники (полигоны)
    • 173 6.2.1. Основные определения
    • 174 6.2.2. Площадь полигона
    • 176 6.2.3. Принадлежность точки полигону
    • 177 6.2.4. Принадлежность точки выпуклому полигону
    • 178 6.2.5. Построение полигонов
    • 182 6.2.6. Сумма и разность полигонов
  • 185 6.3. Окружности и круги
    • 185 6.3.1. Прямая и круг
    • 186 6.3.2. Отрезок и окружность
    • 187 6.3.3. Общие касательные
    • 188 6.3.4. Пересечение двух кругов
  • 191 Упражнения
• 195 Глава 7. Выметание
  • 195 7.1. Интернет-провайдер
  • 199 7.2. Мера объединения отрезков
  • 201 7.3. Линия горизонта
  • 205 7.4. Мера объединения треугольников
  • 209 Упражнения
• 211 Глава 8. Графы
  • 211 8.1. Графы и способы их представления
    • 211 8.1.1. Неориентированные графы: основные понятия
    • 213 8.1.2. Ориентированные графы
    • 214 8.1.3. Представления графа
    • 215 8.1.4. Пример: задача о центре дерева
  • 221 8.2. Алгоритмы обхода графов
    • 221 8.2.1. Обход в глубину
    • 224 8.2.2. Обход в ширину
    • 225 8.2.3. Реализация очереди
  • 226 8.3. Применение алгоритмов обхода
    • 226 8.3.1. Построение остовного дерева и остовного леса
    • 228 8.3.2. Расстояния между вершинами
    • 230 8.3.3. Проверка ацикличности и топологическая сортировка ациклического орграфа
    • 233 8.3.4. Эйлеровы циклы и цепи
    • 236 8.3.5. Обход графа достижимых состояний
  • 240 Упражнения
• 243 Глава 9. Графы клеток и графы с нагруженными ребрами
  • 243 9.1. Графы на клетчатых полях
    • 243 9.1.1. Фигуры на клетчатом поле
    • 246 9.1.2. Минимальный путь в лабиринте
    • 252 9.1.3. Подсчет клеток в областях
  • 258 9.2. Остовное дерево минимального веса
  • 261 9.3. Алгоритм Дейкстры и его применение
    • 261 9.3.1. Задача с одним источником и положительным весом ребер
    • 264 9.3.2. Максимальный груз
    • 265 9.3.3. Зал Круглых Столов
  • 270 9.4. Скоростная алхимия
  • 274 Упражнения
• 279 Глава 10. Комбинаторика
  • 280 10.1. «Амебы» комбинаторики
    • 280 10.1.1. Правила суммы и произведения
    • 281 10.1.2. Перестановки, размещения и сочетания без повторений
    • 282 10.1.3. Перестановки, размещения и сочетания с повторениями
    • 284 10.1.4. Размещения и сочетания как отображения
    • 285 10.1.5. Биномиальные коэффициенты
  • 286 10.2. Рекуррентные соотношения и таблицы
    • 286 10.2.1. Пути в квадратных кварталах
    • 288 10.2.2. Правильные скобочные выражения
    • 289 10.2.3. Счастливые билеты
    • 292 10.2.4. Белые и черные кубики
    • 295 10.2.5. Велосипедные гонки
  • 296 10.3. Рекурсия в задаче о русском лото
  • 299 10.4. Включения и исключения
    • 299 10.4.1. Принцип включений и исключений
    • 301 10.4.2. «Батарея, огонь!»
    • 303 10.4.3. Беспорядок в шляпах
  • 304 10.5. Количество раскладок и разбиений
    • 304 10.5.1. Разбиения множества
    • 305 10.5.2. Разбиения множества с учетом порядка классов
    • 306 10.5.3. Разбиения числа на слагаемые
  • 307 Упражнения
• 309 Глава 11. Перебор вариантов
  • 309 11.1. Порождение подмножеств
    • 309 11.1.1. Все подмножества
    • 313 11.1.2. Подмножества с заданным числом элементов
  • 315 11.2. Порождение последовательностей
    • 315 11.2.1. Размещения ферзей
    • 317 11.2.2. Дерево размещений и его обход
    • 318 11.2.3. Обход дерева с помощью магазина
    • 320 11.2.4. Порождение всех перестановок
  • 322 11.3. Попытки сократить перебор
    • 323 11.3.1. Подмножества положительных чисел с заданной суммой
    • 324 11.3.2. Псевдополиномиальный приближенный алгоритм поиска подмножества
    • 325 11.3.3. Идея метода ветвей и границ в задаче коммивояжера
    • 326 11.3.4. Решение задачи коммивояжера методом ветвей и границ
    • 327 11.3.5. Упрощенный алгоритм
  • 328 11.4. Послесловие
  • 329 Упражнения
• 333 Глава 12. Жадные алгоритмы
  • 333 12.1. Знакомство с жадными алгоритмами
    • 333 12.1.1. Быстрый выбор упорядоченных вариантов
    • 335 12.1.2. Сортировка и выбор в динамическом множестве
    • 338 12.1.3. Понятие жадного алгоритма
  • 339 12.2. Матроиды и жадные алгоритмы
    • 339 12.2.1. Понятие матроида
    • 340 12.2.2. Жадный поиск допустимого подмножества с максимальным весом
    • 340 12.2.3. Взвешенный матроид и жадный алгоритм
    • 341 12.2.4. Матричный матроид
  • 342 12.3. Некорректная «жадность» вместо перебора
    • 342 12.3.1. Поспешная укладка рюкзака
    • 343 12.3.2. Распределение заданий
  • 344 Упражнения
• 347 Глава 13. Динамическое программирование
  • 347 13.1. Принцип оптимальности
    • 347 13.1.1. Путь по клеткам с максимальной суммой
    • 351 13.1.2. Общие замечания по методологии динамического программирования
    • 353 13.1.3. Количество путей с суммой, близкой к максимальной
  • 358 13.2. Монотонная подпоследовательность
    • 358 13.2.1. Поиск монотонной подпоследовательности
    • 362 13.2.2. Бинарный поиск начала подпоследовательности
    • 365 13.2.3. Вложенные коробки
  • 366 13.3. Табличная техника и рекурсия с запоминанием
    • 366 13.3.1. Расстановка скобок в произведении матриц
    • 372 13.3.2. Минимальное количество монет
    • 374 13.3.3. Разбиение алфавита
    • 376 13.3.4. Абзац с блоками разной высоты
    • 378 13.3.5. Максимальное значение выражения
    • 381 13.3.6. Вычеркивание из строки
  • 383 Упражнения
• 387 Глава 14. Игры двух лиц
  • 388 14.1. Анализ позиций и выбор хода
    • 388 14.1.1. Выигрышные и проигрышные позиции
    • 390 14.1.2. Золотое сечение
    • 394 14.1.3. Ним
    • 397 14.1.4. Таблица ходов
  • 398 14.2. Оценивание позиций: максимальная сумма
  • 399 Упражнения
• 403 Глава 15. Японский кроссворд
  • 403 15.1. Итерационный анализ линий
    • 403 15.1.1. Постановка задачи и основные идеи решения
    • 407 15.1.2. Ввод, вывод и основные структуры данных
    • 409 15.1.3. Реализация итерационного анализа линий
  • 410 15.2. Анализ линии на основе конечного автомата
    • 410 15.2.1. Описание линии в виде конечного автомата
    • 412 15.2.2. Обработка линии и уточнение клеток
    • 414 15.2.3. Реализация
  • 419 15.3. Решение задачи с помощью перебора
    • 419 15.3.1. Итерационный анализ линий не решает задачу
    • 421 15.3.2. Перебор и исследование состояний клеток с помощью ИАЛ
    • 423 15.3.3. Решение задачи и анализ решения
• 427 Приложение А. Указания по решению упражнений
  • 427 Глава 1
  • 429 Глава 2
  • 431 Глава 3
  • 433 Глава 4
  • 436 Глава 5
  • 440 Глава 6
  • 442 Глава 7
  • 443 Глава 8
  • 446 Глава 9
  • 450 Глава 10
  • 455 Глава 11
  • 459 Глава 12
  • 461 Глава 13
  • 464 Глава 14
• 469 Список литературы
• 471 Предметный указатель