Информационный сервер для программистов: Исходники со всего света. Паскальные исходники со всего света
  Powered by Поисковый сервер Яndex: Найдется ВСЁ!
На Главную Pascal Форум Информер Страны мира
   Документация по Программированию    >>    sortalg
   
 
 Описание Комбинаторных Алгоритмов  Б.А. Кукушкин 18.02.95

Методические рекомендации для выполнения лабораторных работ по курсу "Комбинаторные алгоритмы" для студентов Института Точной Механики и Оптики (С.Петербург). Подробно рассмотрено 17 алгоритмов сортировки (методы вставки, обмена, выбора, слияния, распределения) и 11 алгоритмов последовательного и бинарного поиска. Формат: Plain Text.



37k 
 

ИНСТИТУТ ТОЧНОЙ МЕХАНИКИ И ОПТИКИ (САНКТ-ПЕТЕРБУРГ) Кафедра прикладной математики ОПИСАНИЯ КОМБИНАТОРНЫХ АЛГОРИТМОВ для выполнения лабораторных работ по курсу "Комбинаторные алгоритмы" составил доц. Кукушкин Б.А. 1994 - 1995 г. СОДЕРЖАНИЕ ЧАСТЬ 1. АЛГОРИТМЫ СОРТИРОВКИ .............................4 1. Методы вставки. Алгоритм простых вставок. .............4 1.1. Бинарные вставки ...................................5 1.2. Двухпутевые вставки ................................6 1.3. Вставки одновременно нескольких элементов. ............6 1.4. Вставки с убывающим шагом (метод Шелла) .............7 1.5. Вставки в связанный список .............9 1.6. Вставки в несколько связанных списков ............10 2. Обменная сортировка ...................................12 2.1. Метод пузырька ...................................12 2.2. Модификация метода пузырька .......................13 2.3. Быстрая сортировка. ...........................14 2.4. Обменная поразрядная сортировка ......................17 2.5. Параллельная сортировка Бэтчера ......................20 3. Сортировка посредством выбора .........................24 3.1. Использование связанного списка для хранения информации о промежуточных максимумах. ...............24 3.2. Пирамидальная сортировка. ..........................26 4. Сортировка посредством слияния ......................31 4.1. Естественное двухпутевое слияние .....................31 4.2. Простое двухпутевое слияние. .........................34 4.3. Слияние связанных списков ...........................36 5. Распределяющая сортировка .............................38 ЧАСТЬ 2. АЛГОРИТМЫ ПОИСКА ..............................42 6. Последовательный поиск ..............................42 6.1. Последовательный поиск в неупорядоченном файле........42 6.2. Последовательный поиск по связанному списку ........43 6.3. Последовательный поиск в упорядоченном файле .....44 6.4. Бинарный поиск в упорядоченном файле. ...............44 6.5. Однородный бинарный поиск ....................45 6.6. Интерполяционный поиск ....................46 7. Поиск по бинарным деревьям .......................47 7.1. Поиск по бинарному дереву. .......................47 7.2. Удаление из бинарного дерева .......................48 7.3. Построение оптимальных бинарных деревьев поиска ......48 7.4. Цифровой поиск по дереву .........................52 7.5. Цифровой поиск для длинных ключей, хранимых в текстовом массиве (Патриция) .......................52 8. ЛАБОРАТОРНЫЕ ЗАДАНИЯ ...............................57 8.1. Сортировка .......................................57 8.2. Поиск .............................................59 Обозначения, использованные в данном пособии. log логарифм по основанию 2 + + | А | наименьшее целое значение, большее или равное А | А | наибольшее целое значение, меньшее или равное А + + ЛИТЕРАТУРА 1. Д.Кнут,Искусство программирования, М.:Мир,1978. 2. Рейнгольд, Нивергельт, Део, Комбинаторные алгоритмы. Теория и практика, М.:Мир, 1982.