Математика | ||||
С. А. Абрамов. Главная редакция физико-математической литературы изд-ва «Наука», М., 1978. В книге программирование рассматривается как дисциплина, имеющая дело с задачами на построение математических объектов. Построение проводится на базе некоторого фиксированного набора элементарных операций. Внимание читателя сосредоточивается на алгоритмической стороне математических задач. Имеется большое количество примеров и задач для самостоятельного решения. Книга рассчитана на школьников старших классов, студентов техникумов и втузов. | ||||
ОГЛАВЛЕНИЕ Предисловие .,.»..»...•••...... , . . 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 ПРЕДИСЛОВИЕ Эта книга — не учебник программирования. Здесь совершенно отсутствуют как сведения о современных вычислительных машинах, так и инструкции по составлению программ для этих машин. Предмет книги — разнообразные темы, обсуждение которых будет способствовать развитию алгоритмической интуиции читателя шдаст представление о характерных приемах решения алгоритмических задач. Каждый старшеклассник уже обладает минимальными алгоритмическими навыками. Например, геометрические задачи на построение — хорошая основа для приобретения таких навыков. Эта Школьная тема — одна из наиболее «алгоритмических» и, в частности, близких программированию. Поэтому изложение материала нани-, нается с разбора геометрических задач. Программирование может рассматриваться как математическая дисциплина, имеющая дело с задачами на построение математических объектов (не обязательно геометрических). Построение проводится на базе фиксированного набора элементарных операций: Одна из специфических сторон деятельности программиста — поиск по возможности более экономного решения. Этому вопросу в книге уделяется изрядное внимание. Автор надеется, что в книге найдет для себя нечто полезное и тот читатель, который уже приобрел начальный программистский опыт. Скорее всего, такому читателю будут интересны последние две главы. Автор с удовольствием выражает свою признательность Святославу Сергеевичу Лаврову за множество ценных советов и бесед при подготовке рукописи книги. С. А. Абрамов ВВЕДЕНИЕ Для решения геометрических задач на построение с помощью циркуля и линейки требуется указать способ построения необходимых объектов. Это не то же самое, что выполнить фактическое построение для некоторых конкретных данных, на самом деле нужно учесть и охватить все возможности взаимного расположения исходных точек, прямых, окружностей и т. д. Подобного рода задачи известны и из алгебры: решение систем линейных уравнений (скажем, второго и третьего порядков) с помощью четырех основных арифметических операций; решение квадратного уравнения с помощью тех же операций и операции извлечения корня и т. д. Правда, в алгебре обычно говорят не о построении, а о вычислении, но это не меняет сути дела. И в тех, и в других задачах задается множество объектов — геометрических фигур определенного вида или чисел, указываются операции, с помощью которых из данных объектов можно получать новые, и требуется указать способ построения объекта (совокупности объектов), удовлетворяющего некоторому условию. Мы будем заниматься задачами именно такого характера. Кроме геометрических и алгебраических задач, будут и другие — их условно можно назвать логическими. Каждый раз мы будем предлагать некоторый способ построения. Будут вырабатываться принципы оценки качества способов'построения. Различные способы будут сравниваться на основе этих принципов. Цена: 150руб. |
||||