Искусство алгоритмизации (2000,00 руб.)

Стр.3

Стр.4

Стр.5

Стр.6

УДК 004.421 ББК 32.973.26-018 П64 Потопахин В. В. П64 Искусство алгоритмизации. – М.: ДМК Пресс, 2018. – 320 с.: ил. ISBN 978-5-97060-612-4 Эта книга для тех, кто хорошо, владея языком программирования и устойчивыми навыками решения задач, желает наработать свой программистский инструментарий. В книге, неформально и довольно детально, разобран значительный набор алгоритмов и методов. Большая часть представленных алгоритмов доведена до реализации на языке Компонентный Паскаль. Для большей прозрачности изложения реализация выполнена пошагово с четкой формулировкой задач каждого шага и записью программного фрагмента. Изложение сопровождается заданиями для самостоятельной работы, количество и сложность которых достаточны для хорошего усвоения материала. Требования к математическим знаниям минимальны, некоторые важные математические понятия и темы кратко изложены в приложении. На сайте издательства вы можете скачать бесплатную среду программирования Блэкбокс, запустив которую вы сразу начнете работу, а также сборник листингов к книге. УДК 004.421 ББК 32.973.26-018 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. © Потопахин В.В. ISBN 978-5-97060-612-4 © Оформление, издание, ДМК Пресс

Стр.3

Содержание Введение ....................................................................... 6 Глава1. Парадигма структурного программирования ............ 9 Зачем нужны общие принципы? ............................................................. 10 Нисходящее проектирование ................................................................ 12 Три базовых элемента структурного программирования ....................... 14 Пример разработки ............................................................................... 17 Глава 2. Вычислительные алгоритмы ................................26 Моделирование непрерывных процессов дискретными ........................ 27 Метод половинного деления. Общая задача поиска величины ............................................................................................... 31 Метод касательных ................................................................................ 34 Метод хорд ............................................................................................ 35 Метод итераций (последовательных приближений) ............................... 36 Обобщение метода половинного деления .............................................. 37 Метод наименьших квадратов ................................................................ 38 Задача вычисления площадей криволинейных фигур ............................. 42 Метод Симпсона .................................................................................... 45 Метод Монте-Карло ............................................................................... 48 Глава 3. Числовые алгоритмы ..........................................54 Алгоритм Евклида .................................................................................. 55 Алгоритмы факторизации и поиска простых .......................................... 57 Выделение полного квадрата (алгоритм Ферма) ......................................... 58 Квадратичное решето .................................................................................. 60 Алгоритм Полларда ..................................................................................... 66 Алгоритмы поиска простых чисел ................................................................ 69 Решето Аткина ............................................................................................. 71 Решето Сундарама . ..................................................................................... 72 Тесты простоты ...................................................................................... 73 Числа Мерсенна .......................................................................................... 75 Тест Люка-Лемера ....................................................................................... 76 Числа Ферма ............................................................................................... 78 Тест Пепина ....................................................................................... 78 Псевдослучайные числа ......................................................................... 78 Критерии правильности случайных чисел .................................................... 81 Критерий, основанный на квадратичном отклонении ................................... 81 Линейный конгруэнтный метод ................................................................... 81 Методы перемешивания ............................................................................. 85

Стр.4

4 Содержание Глава 4. Арифметика .......................................................89 Представление числа в позиционной системе счисления ...................... 90 Проблемы технической реализации арифметики ................................... 93 Двоичный сумматор .................................................................................... 94 Ускорение операции сложения .................................................................... 95 Представление чисел в форме с фиксированной и плавающей десятичной точкой ......................................................................................................... 96 Реализация арифметики на уровне алгоритмического языка ................. 97 Сложение двух чисел ................................................................................... 97 Вычитание из большего меньшего ............................................................... 99 Умножение ................................................................................................102 Деление ....................................................................................................107 Некоторые другие алгоритмы ............................................................... 115 Алгоритм быстрого возведения в степень .................................................115 Быстрый перевод из десятичной в двоичную систему счисления ...............116 Решение диофантовых уравнений ..............................................................117 Двоичная арифметика ......................................................................... 119 Сложение двоичных чисел . ........................................................................120 Как преобразовать в двоичное число дробную часть .................................122 Вычитание двоичных чисел ........................................................................124 Умножение в двоичной системе счисления ................................................125 Деление в двоичной системе счисления ....................................................126 Глава 5. Рекурсия и динамическое программирование ...........131 Общее определение ............................................................................. 132 Задача о ханойской башне ................................................................... 135 Переход от рекурсивного к нерекурсивному решению ......................... 138 Рекурсия как метод поиска ................................................................... 143 Динамическое программирование ....................................................... 144 Задача обхода конем шахматной доски .....................................................146 Факторизация числа ..................................................................................153 Глава 6. Сортировки ......................................................166 Общая постановка задачи .................................................................... 167 Обменные сортировки. Сортировка пузырьком .................................... 168 Шейкерная сортировка ........................................................................ 170 Анализ качеств алгоритма .................................................................... 171 Сортировка выбором ........................................................................... 174 Сортировка вставками ......................................................................... 176 Сортировка Шелла ............................................................................... 178 Быстрая сортировка ............................................................................. 181 Двоичная сортировка ........................................................................... 186 Сортировка слияниями ........................................................................ 191

Стр.5

Содержание 5 Глава 7. Комбинаторные задачи ......................................204 Общая постановка задачи .................................................................... 205 Оптимизация перебора ........................................................................ 207 Связь комбинаторики с алгоритмами на графах ................................... 209 Основные комбинаторные задачи ........................................................ 210 Задача получения перестановок на множестве из N элементов .................210 Построение сочетаний без повторений на множестве элементов ..............216 Сочетания с повторениями ........................................................................221 Задача получения размещений ..................................................................223 Глава 8. Динамические структуры данных ........................224 Понятие о динамической величине ....................................................... 225 Линейный связный список ................................................................... 226 Зачем рекурсивные структуры нужны? .......................................................229 Использование рекурсивных определений для создания деревьев данных ................................................................................................. 233 Глава 9. Алгоритмы принятия решений .............................237 Постановка задачи. Понятие эвристического алгоритма ...................... 238 Оценочная функция .............................................................................. 240 Метод минимакса ................................................................................ 241 Альфа-бета алгоритм ........................................................................... 245 Глава 10. Алгоритмы на графах .......................................250 Стратегии обхода ................................................................................. 251 Обход графа в ширину ...............................................................................251 Обход графа в глубину ...............................................................................253 Построение остовного дерева ............................................................. 253 Алгоритм Прима ........................................................................................254 Алгоритм Краскала ....................................................................................258 Алгоритм поиска компонент связности ................................................ 263 Волновой алгоритм .............................................................................. 265 Алгоритм Дейкстры .............................................................................. 269 Алгоритм Флойда ................................................................................. 276 Нахождение максимального потока ..................................................... 280 Глава 11. Приложения ...................................................296 Приложение 1. Элементы комбинаторики ............................................ 297 Приложение 2. Теория графов .............................................................. 301 Приложение 3. Элементы теории вероятности ..................................... 309 Приложение 4. Синтаксис языка Компонентный Паскаль ..................... 315 Список литературы .......................................................319

Стр.6