Предисловие .,.»..»...•••...... , . . 4
Введение ... **-..••...............• °
Глава I. Построения и алгоритмы ;,........» 7
§ 1. Примеры задач на построение. Данные, операции 7
§ 2. Логический анализ ситуации ......... 15
§ 3. Запись алгоритмов, которые содержат проверки . . 21
§ 4. Различные наборы операций ,......... 26
§ 5. Избыточность набора операций .,.,..**... 34
Глава II. Цикл . . г *.»... >......... 39
§ 1. Ограниченность поля зрения ......... 39
§ 2. Логические выражения............. 46
§ 3. Повторение действий t ,............ 53
§ 4. Массивы . .'..,**#..,,......... 58
§ 5. Алгоритм Евклида . . ш ,*,......... 62
Глава III. Рекурсия ...»,»»»,......... 70
§ 1. Упрощение исходных данных ,.......... 70
§ 2. Рекуррентные соотношения............. 75
§ 3. Анализ рекурсивных алгоритмов ........ 82
§ 4. Как выполнять рекурсивные алгоритмы , s ,. « 89
§ 5. Пример избавления от рекурсий , . -* t г г t t * 95
Г л а в а IV. Поиск . . ,»,...,., , , 5 , % « * 104
§ 1. Справочник и поиск сведений в нем ...... 104
§ 2. Подмножества конечных множеств ........ 113
§ 3. Бектрекинг........,.......... 120
§ 4. Восемь ферзей и лабиринт I .......... 126
§ 5. Графы и деревья . . , . s . ,_ ........ * 135
Глава V. Дальнейшие рассмотрения......... 147
§ 1. Подстановки....... ............ 147
§ 2. Вычисление а" .........,...;.,. 156
§ 3. Алгоритмы с логарифмической трудоемкостью , , * 164
Дополнение I.' Переходы ...-....'...,,.. 173
Дополнение II. Об одном полезном качестве рекурсии 178
Заключение ....... 187
ПРЕДИСЛОВИЕ
Эта книга — не учебник программирования. Здесь совершенно отсутствуют как сведения о современных вычислительных машинах, так и инструкции по составлению программ для этих машин. Предмет книги — разнообразные темы, обсуждение которых будет способствовать развитию алгоритмической интуиции читателя шдаст представление о характерных приемах решения алгоритмических задач.
Каждый старшеклассник уже обладает минимальными алгоритмическими навыками. Например, геометрические задачи на построение — хорошая основа для приобретения таких навыков. Эта Школьная тема — одна из наиболее «алгоритмических» и, в частности, близких программированию. Поэтому изложение материала нани-, нается с разбора геометрических задач.
Программирование может рассматриваться как математическая дисциплина, имеющая дело с задачами на построение математических объектов (не обязательно геометрических). Построение проводится на базе фиксированного набора элементарных операций: Одна из специфических сторон деятельности программиста — поиск по возможности более экономного решения. Этому вопросу в книге уделяется изрядное внимание.
Автор надеется, что в книге найдет для себя нечто полезное и тот читатель, который уже приобрел начальный программистский опыт. Скорее всего, такому читателю будут интересны последние две главы.
Автор с удовольствием выражает свою признательность Святославу Сергеевичу Лаврову за множество ценных советов и бесед при подготовке рукописи книги.
С. А. Абрамов
ВВЕДЕНИЕ
Для решения геометрических задач на построение с помощью циркуля и линейки требуется указать способ построения необходимых объектов. Это не то же самое, что выполнить фактическое построение для некоторых конкретных данных, на самом деле нужно учесть и охватить все возможности взаимного расположения исходных точек, прямых, окружностей и т. д.
Подобного рода задачи известны и из алгебры: решение систем линейных уравнений (скажем, второго и третьего порядков) с помощью четырех основных арифметических операций; решение квадратного уравнения с помощью тех же операций и операции извлечения корня и т. д. Правда, в алгебре обычно говорят не о построении, а о вычислении, но это не меняет сути дела. И в тех, и в других задачах задается множество объектов — геометрических фигур определенного вида или чисел, указываются операции, с помощью которых из данных объектов можно получать новые, и требуется указать способ построения объекта (совокупности объектов), удовлетворяющего некоторому условию.
Мы будем заниматься задачами именно такого характера. Кроме геометрических и алгебраических задач, будут и другие — их условно можно назвать логическими. Каждый раз мы будем предлагать некоторый способ построения. Будут вырабатываться принципы оценки качества способов'построения. Различные способы будут сравниваться на основе этих принципов.
