Предисловие 13
От издательства "Диалектика" 15
Глава 1. Разминка (понемногу о разном) 17
1.1. Три простые задачи 17
1.1.1. Совпадения стрелок часов 17
1.1.2. Последовательности с одинаковыми суммами 18
1.1.3. Ребус 19
1.2. Знакомство со сложностью алгоритмов 23
1.2.1. Простые и составные числа 23
1.2.2. Понятие сложности алгоритма 25
1.2.3. Характер возрастания сложности 27
1.2.4. Алгоритм Евклида и его современная версия 28
1.2.5. Бинарный алгоритм 29
1.2.6. Понятие сложности задачи 30
1.2.7. Что выбирать? 31
1.3. Несколько технических вопросов 31
1.3.1. Проектирование сверху вниз, подпрограммы
и структурное кодирование 31
1.3.2. Когда уместны безусловные переходы 32
1.3.3. Несколько замечаний о стиле 34
1.3.4. Отладка программы 35
1.3.5. Директивы компилятору 37
1.3.6. Проверка программы 38
1.4. Ввод последовательностей данных 40
1.4.1. Организация данных и вид цикла ввода 40
1.4.2. Изменение источника данных 43
Упражнения 44
Глава 2. Однопроходные алгоритмы 47
2.1. Попутные вычисления 47
2.1.1. Три простых примера 47
2.1.2. Максимальная сумма отрезка числовой последовательности 49
2.1.3. Инопланетная армия 50
2.1.4. Стрельба из двуствольной пушки 53
2.2. Чтение и обработка символов 55
2.2.1. Удаление пробелов 55
2.2.2. Удаление комментариев 57

2.2.3. Чтение и вычисление многочлена 59
2.2.4. Языки скобок 67
2.2.5. Линейный поиск подстроки в тексте 72
Упражнения 76
Глава 3. Рекурсия 79
3.1. Основные понятия 79
3.1.1. Рекурсивные определения 79
3.1.2. Простейший пример рекурсивной подпрограммы 80
3.1.3. Глубина рекурсии и общее количество рекурсивных вызовов 81
3.1.4. Косвенная рекурсия 83
3.2. Быстрое возведение в степень 85
3.3. Рисование самоподобных ломаных 88
3.3.1. Снежинка Коха 89
3.3.2. Треугольник Серпиньского 90
3.3.3. Драконова ломаная 93
Упражнения 95
Глава 4. Нестандартная обработка чисел 97
4.1. Длинная целочисленная арифметика 97
4.1.1. Представление длинных чисел 98
4.1.2. Сравнение, сложение и вычитание длинных целых 100
4.1.3. Организация ввода-вывода 102
4.1.4. Умножение длинных целых 103
4.1.5. Деление длинных целых 105
4.1.6. Целая часть квадратного корня длинного числа 107
4.2. Два магических числа 109
4.2.1. Число е 109
4.2.2. Число PI 112
4.3. Остатки от деления 112
4.3.1. Плиты в треугольнике 113
4.3.2. Кратное число с одинаковыми цифрами 115
4.4. Отслеживание циклических повторений 116
4.4.1. Десятичное представление дроби и RO-алгоритм 116
4.4.2. Остатки от деления чисел Фибоначчи 119
4.5. Нули в конце факториала 121
Упражнения 124
Глава 5. Бинарный поиск, слияние и сортировка 127
5.1. Бинарный поиск 127
5.1.1. Идея бинарного поиска 127
5.1.2. "Оптический танк" 128
5.2. Слияние упорядоченных последовательностей 130
5.2.1. Слияние двух участков массива 130
5.2.2. Слияние файлов 131

5.3. Основные способы сортировки 135
5.3.1. Два простейших алгоритма 135
5.3.2. Сортировка слиянием 137
5.3.3. Быстрая сортировка 140
5.3.4. Пирамидальная сортировка 142
5.3.5. Линейная сортировка подсчетом 145
5.3.6. Поразрядная сортировка 148
5.4. Применение сортировки 150
5.4.1. Проверка уникальности 150
5.4.2. Проход в заборе 151
5.4.3. Транзитивность 153
Упражнения 154
Глава 6. Вычислительная геометрия на плоскости 159
6.1. Точки, векторы, прямые, отрезки 159
6.1.1. Точки, векторы, углы и ориентированная площадь 159
6.1.2. Представление прямых и отрезков 162
6.1.3. Взаимное расположение прямых, отрезков и точек 164
6.1.4. Две задачи о треугольниках 169
6.2. Многоугольники (полигоны) 173
6.2.1. Основные определения 173
6.2.2. Площадь полигона 174
6.2.3. Принадлежность точки полигону 176
6.2.4. Принадлежность точки выпуклому полигону 177
6.2.5. Построение полигонов 178
6.2.6. Сумма и разность полигонов 182
6.3. Окружности и круги 185
6.3.1. Прямая и круг 185
6.3.2. Отрезок и окружность 186
6.3.3. Общие касательные 187
6.3.4. Пересечение двух кругов 188
Упражнения 191
Глава 7. Выметание 195
7.1. Интернет-провайдер 195
7.2. Мера объединения отрезков 199
7.3. Линия горизонта 201
7.4. Мера объединения треугольников 205
Упражнения 209
Глава 8. Графы 211
8.1. Графы и способы их представления 211
8.1.1. Неориентированные графы: основные понятия 211
8.1.2. Ориентированные графы 213
8.1.3. Представления графа 214

8.1.4. Пример: задача о центре дерева 215
8.2. Алгоритмы обхода графов 221
8.2.1. Обход в глубину 221
8.2.2. Обход в ширину 224
8.2.3. Реализация очереди 225
8.3. Применение алгоритмов обхода 226
8.3.1. Построение остовного дерева и остовного леса 226
8.3.2. Расстояния между вершинами 228
8.3.3. Проверка ацикличности и топологическая сортировка
ациклического орграфа 230
8.3.4. Эйлеровы циклы и цепи 233
8.3.5. Обход графа достижимых состояний 236
Упражнения 240
Глава 9. Графы клеток и графы с нагруженными ребрами 243
9.1. Графы на клетчатых полях 243
9.1.1. Фигуры на клетчатом поле 243
9.1.2. Минимальный путь в лабиринте 246
9.1.3. Подсчет клеток в областях 252
9.2. Остовное дерево минимального веса 258
9.3. Алгоритм Дейкстры и его применение 261
9.3.1. Задача с одним источником и положительным весом ребер 261
9.3.2. Максимальный груз 264
9.3.3. Зал Круглых Столов 265
9.4. Скоростная алхимия 270
Упражнения 274
Глава 10. Комбинаторика 279
10.1. "Амебы" комбинаторики 280
10.1.1. Правила суммы и произведения 280
10.1.2. Перестановки, размещения и сочетания без повторений 281
10.1.3. Перестановки, размещения и сочетания с повторениями 282
10.1.4. Размещения и сочетания как отображения 284
10.1.5. Биномиальные коэффициенты 285
10.2. Рекуррентные соотношения и таблицы 286
10.2.1. Пути в квадратных кварталах 286
10.2.2. Правильные скобочные выражения 288
10.2.3. Счастливые билеты 289
10.2.4. Белые и черные кубики 292
10.2.5. Велосипедные гонки 295
10.3. Рекурсия в задаче о русском лото 296
10.4. Включения и исключения 299
10.4.1. Принцип включений и исключений 299
10.4.2. "Батарея, огонь!" 301
10.4.3. Беспорядок в шляпах 303
10.5. Количество раскладок и разбиений 304

10.5.1. Разбиения множества 304
10.5.2. Разбиения множества с учетом порядка классов 305
10.5.3. Разбиения числа на слагаемые 306
Упражнения 307
Глава 11. Перебор вариантов 309
11.1. Порождение подмножеств 309
11.1.1. Все подмножества 309
11.1.2. Подмножества с заданным числом элементов 313
11.2. Порождение последовательностей 315
11.2.1. Размещения ферзей 315
11.2.2. Дерево размещений и его обход 317
11.2.3. Обход дерева с помощью магазина 318
11.2.4. Порождение всех перестановок 320
11.3. Попытки сократить перебор 322
11.3.1. Подмножества положительных чисел с заданной суммой 323
11.3.2. Псевдополиномиальный приближенный алгоритм
поиска подмножества 324
11.3.3. Идея метода ветвей и границ в задаче коммивояжера 325
11.3.4. Решение задачи коммивояжера методом ветвей и границ 326
11.3.5. Упрощенный алгоритм 327
11.4. Послесловие 328
Упражнения 329
Глава 12. Жадные алгоритмы 333
12.1. Знакомство с жадными алгоритмами 333
12.1.1. Быстрый выбор упорядоченных вариантов 333
12.1.2. Сортировка и выбор в динамическом множестве 335
12.1.3. Понятие жадного алгоритма 338
12.2. Матроиды и жадные алгоритмы 339
12.2.1. Понятие матроида 339
12.2.2. Жадный поиск допустимого подмножества с максимальным весом 340
12.2.3. Взвешенный матроид и жадный алгоритм 340
12.2.4. Матричный матроид 341
12.3. Некорректная "жадность" вместо перебора 342
12.3.1. Поспешная укладка рюкзака 342
12.3.2. Распределение заданий 343
Упражнения 344
Глава 13. Динамическое программирование 347
13.1. Принцип оптимальности 347
13.1.1. Путь по клеткам с максимальной суммой 347
13.1.2. Общие замечания по методологии динамического программирования 351
13.1.3. Количество путей с суммой, близкой к максимальной 353
13.2. Монотонная подпоследовательность 358

13.2.1. Поиск монотонной подпоследовательности 358
13.2.2. Бинарный поиск начала подпоследовательности 362
13.2.3. Вложенные коробки 365
13.3. Табличная техника и рекурсия с запоминанием 366
13.3.1. Расстановка скобок в произведении матриц 366
13.3.2. Минимальное количество монет 372
13.3.3. Разбиение алфавита 374
13.3.4. Абзац с блоками разной высоты 376
13.3.5. Максимальное значение выражения 378
13.3.6. Вычеркивание из строки 381
Упражнения 383
Глава 14. Игры двух лиц 387
14.1. Анализ позиций и выбор хода 388
14.1.1. Выигрышные и проигрышные позиции 388
14.1.2. Золотое сечение 390
14.1.3. Ним 394
14.1.4. Таблица ходов 397
14.2. Оценивание позиций: максимальная сумма 398
Упражнения 399
Глава 15. Японский кроссворд 403
15.1. Итерационный анализ линий 403
15.1.1. Постановка задачи и основные идеи решения 403
15.1.2. Ввод, вывод и основные структуры данных 407
15.1.3. Реализация итерационного анализа линий 409
15.2. Анализ линии на основе конечного автомата 410
15.2.1. Описание линии в виде конечного автомата 410
15.2.2. Обработка линии и уточнение клеток 412
15.2.3. Реализация 414
15.3. Решение задачи с помощью перебора 419
15.3.1. Итерационный анализ линий не решает задачу 419
15.3.2. Перебор и исследование состояний клеток с помощью ИАЛ 421
15.3.3. Решение задачи и анализ решения 423
Приложение А. Указания по решению упражнений 427
Глава 1 427
Глава 2 429
Глава 3 431
Глава 4 433
Глава 5 436
Глава 6 440
Глава 7 442
Глава 8 443
Глава 9 446

Глава 10 450
Глава 11 455
Глава 12 459
Глава 13 461
Глава 14 464
Список литературы 469
Предметный указатель 471

#
/>-алгоритм, 117
А
Алгоритм
возведения в степень, 86
индийский, 87
Гаусса, 342
Дейкстры, 262
динамического
программирования, 353
Евклида, 29
жадный, 338; 340
Краскала, 260
недетерминированный, 328
обхода
графа в глубину, 222; 223
дерева поиска, 318
связного графа
в глубину, 221
в ширину, 224
однопроходный, 47
поиска
зацикливания, 117
логарифмический, 127
полиномиальный, 28
приближенный, 324
Прима, 259
псевдополиномиальный, 28; 324;
373
сортировки
быстрый, 140
выбором,136
деревом, 142
пирамидальный, 142
пузырьком, 136
слиянием,137
Флойда-Уоршалла, 229
числовой волны, 247
экспоненциальный, 28
Арифметика
длинная
дробная, 110
целая, 98
Б
Бином Ньютона, 285
Биномиальные коэффициенты, 285
В
Вектор, 160
Выметание, 196
Вычисление булевых выражений
полное и сокращенное, 37
Г
Глубина рекурсии, 81
Граф, 211
ориентированный, 213
ациклический, 230
эйлеров, 234
Графика, 88
черепашья, 88
д
Действие элементарное, 25
Дерево, 213
остовное, 213; 227
минимального веса, 258
сортирующее, 142
Динамическое программирование,
353
Директива компилятору, 37
Директивы компилятору, 37; 67
Дробь
длинная, 110
представление
с плавающей точкой, 110
с фиксированной точкой, 110

3
Задача
NP-полная, 328
коммивояжера, 325
о выпуклой оболочке, 180
о вычеркивании из строки, 381
о кенигсбергских мостах, 234
о количестве
правильных скобочных
выражений, 288
о количестве сюръекций, 305
о коробках, 365
о кратчайших путях в графе, 262
о максимальном
грузе, 264
значении выражения, 378
о минимальном числе монет, 344;
372
о площади полигона, 174
о подмножествах, 309; 313
о подмножестве, 323; 324; 329
о подпоследовательности, 359; 365
о почтовых марках, 331
о разбиении
алфавита, 374
множества, 304
числа, 306
о размещении ферзей, 315
о расстановке скобок, 366
о русском лото, 296
о сокровищнице, 347; 353
о счастливых билетах, 289
о триангуляции выпуклого
многоугольника, 384
о центре дерева, 215
о черных и белых кубиках, 292
об абзаце с блоками разной
высоты, 376
об инверсиях, 303
об остовном дереве минимального
веса, 258
об укладке рюкзака, 331; 343
поиска подстроки, 72
с одним источником, 261
топологической сортировки, 232
труднорешаемая, 328
факторизации, 24
Золотое сечение, 393
И
Игра Ним, 395
К
Код Грея, 312
Конечный автомат, 57; 411
Конструкция forward, 84
Л
Лексический анализ, 62
м
Маршрут
в графе, 212
в орграфе, 213
Матрица, 367
оптимизация умножений, 367
смежности, 214
Матроид, 339
взвешенный, 340
Метод
ветвей и границ, 326
выметания, 196
Кнута-Морриса-Пратта, 72
минимакса, 399
Многоугольник, 173
Множество
тип данных, 23
частично упорядоченное, 80
Монотонная ломаная, 179
н
Направление поворота, 161
О
Обратный ход, 249; 349; 370
Обход
графа
в глубину, 221
в ширину, 224

дерева
в глубину, 317
Определение
рекурсивное, 79
Отображение, 305
Оценка
позиции,399
функции,26
Очередь, 224
с приоритетами, 272
п
Перебор
с возвращениями, 317
сокращение, 20
Перестановка, 281; 303
с повторениями, 283
Площадь
полигона, 174
Подзадачи
аналогичной структуры, 352
независимые, 352
оптимальные, 352
перекрывающиеся, 352
тривиальные, 352
Подпоследовательность, 359
Подпрограмма
рекурсивная, 80
Подстановка, 308
Позиция в игре
выигрышная, 389
проигрышная, 389
Поиск
в графе, 221
дихотомический, 127
логарифмический, 128
Полигон, 173
Порядок
лексикографический, 148
Правило
произведения, 280
суммы, 280
Принцип
включений и исключений, 299
Дирихле, 42
оптимальности динамического
программирования, 352; 353
сокращения перебора с помощью
ограничений, 20
Прямая, 162
Псевдокод, 32
Р
Разбиение
множества, 304
числа, 306
Размер экземпляра задачи, 25
Размещение, 281
с повторениями, 282
Разность Минковского, 184
Расстояние, 160
от точки до прямой, 165
Рекурсия, 79
косвенная, 84; 381
прямая, 84
с запоминанием, 353; 370; 425
С
Самоподобная ломаная, 88
Синтаксический анализ, 62
Скалярное произведение векторов, 161
Скобочные выражения
оптимальная расстановка скобок,
367; 378
Слияние упорядоченных
последовательностей, 130
Сложность
алгоритма, 26
задачи, 30
полиномиальная, 28
Снежинка Коха, 89
Событие
в методе выметания, 196
Сортировка
массива
быстрая, 140
выбором, 136
деревом, 142
пирамидальная, 142
пузырьковая, 136

слиянием, 130; 138
подсчетом, 146
поразрядная, 148
топологическая, 232; 366
устойчивая, 140
цифровая, 148
Состав, 283
Сочетание, 281
с повторениями, 283
Список
ребер, 214
Средства отладки, 64
Статус выметания, 197
Структура смежности, 214
Сумма Минковского, 184
Сюръекция, 305
т
Табличная техника, 368
динамического
программирования, 352
Тождество
Вандермонда, 286
Коши, 286
Точка плоскости, 160
Точки событий, 196
Транзитивное замыкание, 241
Треугольник
Паскаля, 285
Серпиньского, 90
Треугольные числа, 286
Триангуляция, 269
выпуклого многоугольника, 384
Делоне, 269
У
Умножение матриц, 366
Уравнение прямой, 162
Условная компиляция, 67
Ф
Формула
включений и исключений, 300
ориентированной площади, 161
Функция
91 Мак-Карта, 95
возвратов, 73
ц
Цепь
эйлерова, 236
Цикл, 212
гамильтонов, 325
подстановки, 308
эйлеров, 234
ч
Числа
Фибоначчи, 119; 393; 450; 451
Число
Белла, 304
Каталана, 289
простое, 23
составное, 23
Стерлинга второго рода, 304
Я
Японский кроссворд, 403