Введение в рекурсивное программирование (5000,00 руб.)

Стр.5

Стр.7

Стр.8

Стр.9

Стр.10

Стр.11

Стр.12

УДК 004.02 ББК 32.972 Р82 Р82 Мануэль Рубио-Санчес Введение в рекурсивное программирование / пер. с англ. Е. В. Борисова. – М.: ДМК Пресс, 2019. – 436 с.: ил. ISBN 978-5-97060-703-9 Книга охватывает почти весь круг теоретических и практических вопросов, относящихся к рекурсии и рекурсивному программированию, что делает её прекрасным дополнением к уже существующим немногочисленным книгам на эту тему. На множестве примеров и задач – от простых к сложным – читатель постепенно погружается в рекурсию, учится мыслить рекурсивно и, отталкиваясь от декларативной парадигмы программирования, создавать рекурсивные алгоритмы с использованием пошаговой методики и специальных схем декомпозиции задач. При этом автор беспристрастно сопоставляет рекурсивные алгоритмы с итерационными, отмечая достоинства и недостатки тех и других. Все алгоритмы в книге реализованы на языке Python 3. Издание предназначено студентам вузов, преподавателям, а также широкому кругу разработчиков, желающих эффективно применять рекурсивные алгоритмы в своей работе. УДК 004.02 ББК 32.973 Copyright © 2018 by Taylor & Francis Group, LLC. CRC Press is an imprint of Taylor & Francis Group, an Informa business. All rights reserved. Russian-language edition copyright © 2019 by DMK Press. All rights reserved. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. ISBN 978-1-4987-3528-5 (англ.) ISBN 978-5-97060-703-9 (рус.) © 2018 by Taylor & Francis Group, LLC © Оформление, перевод на русский язык, издание, ДМК Пресс, 2019

Стр.5

Оглавление Предисловие .........................................................................................................................12 Целевая аудитория ..........................................................................................................................14 Содержание и структура книги ..................................................................................................15 Примерные учебные курсы .........................................................................................................17 Благодарности ...................................................................................................................................17 Глава 1. Основные понятия рекурсивного программирования ...................................19 1.1. Распознание рекурсии ...........................................................................................................19 1.2. Декомпозиция задачи ............................................................................................................25 1.3. Рекурсивный код ......................................................................................................................33 1.4. Индукция .....................................................................................................................................40 1.4.1. Математические доказательства методом индукции ................................................... 40 1.4.2. Рекурсивная убеждённость ..................................................................................................... 41 1.4.3. Императивное и декларативное программирование ................................................ 43 1.5. Рекурсия против итерации ...................................................................................................44 1.6. Типы рекурсии ...........................................................................................................................46 1.6.1. Линейная рекурсия ..................................................................................................................... 46 1.6.2. Хвостовая рекурсия .................................................................................................................... 46 1.6.3. Множественная рекурсия ......................................................................................................... 47 1.6.4. Взаимная рекурсия ..................................................................................................................... 47 1.6.5. Вложенная рекурсия .................................................................................................................. 48 1.7. Упражнения .................................................................................................................................48 Глава 2. Методика рекурсивного мышления ..................................................................51 2.1. Шаблон проектирования рекурсивных алгоритмов .................................................51 2.2. Размер задачи ...........................................................................................................................52 2.3. Начальные условия .................................................................................................................54 2.4. Декомпозиция задачи ............................................................................................................57 2.5. Рекурсивные условия, индукция и схемы ......................................................................61 2.5.1. Рекурсивное мышление посредством схем ..................................................................... 61 2.5.2. Конкретные экземпляры задачи ........................................................................................... 65 2.5.3. Альтернативные обозначения ................................................................................................ 66

Стр.7

Оглавление  7 2.5.4. Процедуры .......................................................................................................................................67 2.5.5. Несколько подзадач ................................................................................................................... 69 2.6. Тестирование..............................................................................................................................71 2.7. Упражнения .................................................................................................................................75 Глава 3. Анализ времени выполнения рекурсивных алгоритмов ...............................77 3.1. Предварительные математические соглашения .........................................................77 3.1.1. Степени и логарифмы ................................................................................................................ 78 3.1.2. Биномиальные коэффициенты .............................................................................................. 78 3.1.3. Пределы и правило Лопиталя ................................................................................................ 79 3.1.4. Суммы и произведения ............................................................................................................. 79 3.1.5. Верхняя и нижняя границы ..................................................................................................... 85 3.1.6. Тригонометрия .............................................................................................................................. 86 3.1.7. Векторы и матрицы ......................................................................................................................87 3.2. Временнáя сложность вычислений...................................................................................89 3.2.1. Порядок роста функций ............................................................................................................ 90 3.2.2. Асимптотические обозначения .............................................................................................. 92 3.3. Рекуррентные соотношения ................................................................................................95 3.3.1. Метод расширения ...................................................................................................................... 99 3.3.2. Общий метод решения разностных уравнений ............................................................107 3.4. Упражнения .............................................................................................................................119 Глава 4. Линейная рекурсия I: основные алгоритмы ...................................................122 4.1. Арифметические операции ...............................................................................................123 4.1.1. Степенная функция .................................................................................................................. 123 4.1.2. Медленное сложение.............................................................................................................. 127 4.1.3. Двойная сумма ........................................................................................................................... 131 4.2. Системы счисления ..............................................................................................................132 4.2.1. Двоичное представление неотрицательного целого числа .................................... 133 4.2.2. Приведение десятичного числа к другому основанию ............................................ 135 4.3. Строки ........................................................................................................................................136 4.3.1. Обращение строки ................................................................................................................... 137 4.3.2. Является ли строка палиндромом? ................................................................................... 137 4.4. Дополнительные задачи .....................................................................................................139 4.4.1. Сортировка выбором .............................................................................................................. 139 4.4.2. Схема Горнера ............................................................................................................................ 141 4.4.3. Треугольник Паскаля ............................................................................................................... 143 4.4.4. Резистивная цепь ...................................................................................................................... 145 4.5. Упражнения ............................................................................................................................. 147

Стр.8

8  Оглавление Глава 5. Линейная рекурсия II: хвостовая рекурсия ....................................................151 5.1. Логические функции ............................................................................................................152 5.1.1. Есть ли в неотрицательном целом числе заданная цифра? ................................... 152 5.1.2. Равны ли строки? ...................................................................................................................... 155 5.2. Алгоритмы поиска в списке ..............................................................................................156 5.2.1. Линейный поиск ........................................................................................................................ 157 5.2.2. Двоичный поиск в сортированном списке .................................................................... 159 5.3. Двоичные деревья поиска ................................................................................................161 5.3.1. Поиск элемента ......................................................................................................................... 163 5.3.2. Вставка элемента ...................................................................................................................... 165 5.4. Схемы разбиения ..................................................................................................................165 5.4.1. Основная схема разбиения .................................................................................................. 167 5.4.2. Метод разбиения Хоара ......................................................................................................... 168 5.5. Алгоритм quickselect ............................................................................................................173 5.6. Двоичный поиск корня функции ....................................................................................174 5.7. Задача лесоруба ..................................................................................................................... 177 5.8. Алгоритм Евклида .................................................................................................................182 5.9. Упражнения .............................................................................................................................184 Глава 6. Множественная рекурсия I: «разделяй и властвуй» .....................................188 6.1. Отсортирован ли список? ..................................................................................................189 6.2. Сортировка ..............................................................................................................................190 6.2.1. Алгоритм сортировки слиянием ......................................................................................... 191 6.2.2. Алгоритм быстрой сортировки ............................................................................................ 194 6.3. Мажоритарный элемент списка ...................................................................................... 197 6.4. Быстрое целочисленное умножение ............................................................................200 6.5. Умножение матриц ...............................................................................................................203 6.5.1. Умножение матриц методом «разделяй и властвуй» ................................................ 203 6.5.2. Алгоритм Штрассена умножения матриц ....................................................................... 207 6.6. Задача укладки тримино....................................................................................................208 6.7. Задача очертания ..................................................................................................................213 6.8. Упражнения .............................................................................................................................219 Глава 7. Множественная рекурсия II: пазлы, фракталы и прочее ..............................222 7.1. Путь через болото .................................................................................................................222 7.2. Ханойская башня ...................................................................................................................226

Стр.9

Оглавление  9 7.3. Обходы дерева .......................................................................................................................230 7.3.1. Внутренний обход..................................................................................................................... 231 7.3.2. Прямой и обратный обходы ................................................................................................. 233 7.4. Самый длинный палиндром в строке ...........................................................................234 7.5. Фракталы ..................................................................................................................................236 7.5.1. Снежинка Коха ........................................................................................................................... 236 7.5.2. Ковёр Серпиньского ................................................................................................................. 242 7.6. Упражнения ..............................................................................................................................245 Глава 8. Задачи подсчёта ..................................................................................................250 8.1. Перестановки ..........................................................................................................................251 8.2. Размещения с повторениями ...........................................................................................253 8.3. Сочетания .................................................................................................................................255 8.4. Подъём по лестнице ............................................................................................................256 8.5. Путь по Манхэттену ..............................................................................................................259 8.6. Триангуляция выпуклого многоугольника ..................................................................260 8.7. Пирамиды из кругов .............................................................................................................263 8.8. Упражнения .............................................................................................................................265 Глава 9. Взаимная рекурсия .............................................................................................268 9.1. Чётность числа .......................................................................................................................269 9.2. Игры со многими игроками ..............................................................................................270 9.3. Размножение кроликов ......................................................................................................271 9.3.1. Зрелые и незрелые пары кроликов .................................................................................. 272 9.3.2. Родовое дерево кроликов .................................................................................................... 273 9.4. Задача о станциях водоочистки...................................................................................... 277 9.4.1. Переток воды между городами .......................................................................................... 278 9.4.2. Сброс воды в каждом городе .............................................................................................. 280 9.5. Циклические ханойские башни ......................................................................................282 9.6. Грамматики и синтаксический анализатор на основе рекурсивного спуска .........................................................................................................................................288 9.6.1. Лексический анализ входной строки ............................................................................... 288 9.6.2. Синтаксический анализатор на основе рекурсивного спуска ............................... 293 9.7. Упражнения ..............................................................................................................................302 Глава 10. Выполнение программы ..................................................................................306 10.1. Поток управления между подпрограммами ...........................................................309 10.2. Деревья рекурсии...............................................................................................................312

Стр.10

10  Оглавление 10.2.1. Анализ времени выполнения ............................................................................................ 318 10.3. Программный стек .............................................................................................................320 10.3.1. Стековые кадры ...................................................................................................................... 320 10.3.2. Трассировка стека .................................................................................................................. 323 10.3.3. Пространственная сложность вычислений .................................................................. 325 10.3.4. Ошибки предельной глубины рекурсии и переполнения стека ......................... 326 10.3.5. Рекурсия как альтернатива стеку .....................................................................................327 10.4. Мемоизация и динамическое программирование ..............................................332 10.4.1 Мемоизация .............................................................................................................................. 332 10.4.2. Граф зависимости и динамическое программирование ....................................... 336 10.5. Упражнения ...........................................................................................................................340 Глава 11. Вложенная рекурсия и снова хвостовая .......................................................347 11.1. Хвостовая рекурсия и итерация ................................................................................... 347 11.2. Итерационный подход к хвостовой рекурсии .......................................................351 11.2.1. Факториал ................................................................................................................................. 352 11.2.2. Приведение десятичного числа к другому основанию .......................................... 353 11.3. Вложенная рекурсия .........................................................................................................356 11.3.1. Функция Аккермана .............................................................................................................. 356 11.3.2. Функция-91 Маккарти ...........................................................................................................357 11.3.3. Цифровой корень ....................................................................................................................357 11.4. К хвостовой и вложенной рекурсии через обобщённую функцию ..............359 11.4.1. Факториал ................................................................................................................................. 359 11.4.2. Приведение десятичного числа к к другому основанию ...................................... 363 11.5. Упражнения ...........................................................................................................................365 Глава 12. Множественная рекурсия III: перебор с возвратами .................................366 12.1. Введение ................................................................................................................................ 367 12.1.1. Частичные и полные решения .......................................................................................... 367 12.1.2. Рекурсивная структура ......................................................................................................... 369 12.2. Генерация комбинаторных объектов .........................................................................371 12.2.1. Подмножества ......................................................................................................................... 372 12.2.2. Перестановки ............................................................................................................................377 12.3. Задача n ферзей .................................................................................................................381 12.3.1. Поиск всех решений ............................................................................................................. 383 12.3.2. Поиск одного решения ........................................................................................................ 384 12.4. Задача о сумме элементов подмножества .............................................................. 387 12.5. Путь в лабиринте ................................................................................................................390

Стр.11

Оглавление  11 12.6. Судоку ......................................................................................................................................396 12.7. Задача о рюкзаке 0–1 ......................................................................................................402 12.7.1. Стандартный алгоритм перебора с возвратами ........................................................ 402 12.7.2. Алгоритм ветвей и границ ...................................................................................................407 12.8. Упражнения ...........................................................................................................................411 Что ещё почитать ...............................................................................................................416 Монографии о рекурсии ................................................................................................................... 416 Разработка и анализ алгоритмов .................................................................................................. 416 Функциональное программирование ......................................................................................... 417 Язык Python ............................................................................................................................................ 417 Исследования в обучении и изучении рекурсии .................................................................... 417 Дополнительная литература ............................................................................................418 Список рисунков .................................................................................................................420 Список таблиц .....................................................................................................................426 Список листингов ...............................................................................................................426 Предметный указатель .....................................................................................................432

Стр.12