Алгоритмы поиска в фиксированной группе данных

(4 часа)

Цель работы: Освоить на практике алгоритмы поиска элемента в фиксированной группе данных, а также представление фиксированных групп данных; научиться анализировать применяемые алгоритмы поиска.

Домашнее задание:

1. Изучить алгоритмы поиска по ключу в статических массивах: линейный поиск, бинарный поиск.

2. Изучить поиск в таблице, как разновидность поиска в массиве, когда ключ является составным объектом – строкой. Освоить алгоритмы поиска подстроки в строке: прямой, использующий метод деления пополам, алгоритм Кнута, Морриса и Пратта (КМП).

Теоретические сведения.

Задачи поиска элемента, обладающего заданными свойствами, достаточно часто приходится решать применительно к массивам. С развитием информационных и информационно-поисковых систем рационализация алгоритмов поиска является актуальной задачей. В зависимости от информации об элементах сортируемого массива, существует принципиально два подхода к реализации алгоритма поиска.

1. Следует заметить, что если массив не отсортирован, то поиск линейный: последовательный просмотр элементов массива и сравнение каждого ,в процессе просмотра ,с ключом поиска до тех пор, пока либо не будет найдено совпадение с ключом, либо массив просмотрен до конца, а совпадений нет.

2. второй простейший алгоритм поиска -- для отсортированного массива (для определенности пусть элементы массива расположены по возрастанию).

Алгоритм носит название двоичного (бинарного) поиска, т.к. на каждом шаге область поиска уменьшается вдвое.

Пусть в отсортированном массиве требуется найти элемент со значением x, или указать, что такого элемента там нет. Выберем средний элемент. Для этого элемента относительно значения x возможны три случая:

1. элемент равен x (поиск завершен);

2. элемент больше x (поиск необходимо продолжить в левой части массива);

3. элемент меньше x (поиск необходимо продолжить в правой части массива).

В случаях 2-3 поиск (если это ещё возможно) продолжается. Для этого в выделенной части массива вновь выбирается средний элемент и проводятся аналогичные рассуждения. И т.д., до тех пор, пока поиск не будет завершен.

Поиск завершается в одном из двух случаев:

1. элемент найден;

2. элемент не найден (это констатируется в том случае, когда длина области поиска уменьшилась до нуля, т.е. левая и правая границы области поиска сомкнулись).

Рассмотрим программную реализацию алгоритма.

 L := 1; R := n; {изначально область поиска - весь массив}

repeat

c := (L + R) div 2; {индекс среднего элемента}

if a[c] > x then R := c - 1; {случай 2}

if a[c] < x then L := c + 1; {случай 3}

until (a[c]=x) or (L > R);

if a[c]=x then find:=c else find := 0; {возвращем индекс элемента или нуль, если элемент не найден}

Порядок выполнения работы.

1. Открыть проект Delphi Structures.

2. Добавить в управляющее главное меню пункт «Лабораторная работа №2», при выборе которого должно появляться окно модуля «Poisk» (модуль «Poisk» с формой добавить в проект).

3. Установить на форму модуля Poisk компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №2.1.

4. В обработчике события onClick управляющей кнопки на языке

Object Pascal написать фрагмент программы для реализации алгоритма поиска в соответствии с вариантом.

Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.

5. произвести анализ запрограммированного алгоритма (по количеству сравнений).

6. Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.

Таблица 2.1

Контрольные вопросы

1. Линейный поиск. Условия окончания поиска.

2. Линейный поиск с барьером.

3. Алгоритм поиска делением пополам (двоичный поиск). Анализ алгоритма.

4. Представление строк переменного размера без динамического распределения памяти.

5. Алгоритм поиска строки в таблице строк.

6. Прямой поиск образа в КМП-алгоритме.

7. предтрансляция образа в КМП-алгоритме.

8. Сравнительный анализ алгоритмов поиска образа в строке (по количеству требуемых сравнений).

9. Особенности работы алгоритмов поиска образа в строке, если строка читается из вторичной памяти.

Лабораторная работа № 3

Алгоритмы базовых и улучшенных сортировок.

Порядковые статистики

Цель работы: изучение и практическое применение алгоритмов сортировок:

- основных базовых алгоритмов;

- улучшенных эффективных алгоритмов, построенных на основе базовых.

Домашнее задание:

1. Изучить базовые алгоритмы сортировок:

а) с помощью прямого включения и его модификация двоичным включением;

б) сортировка с помощью прямого выбора;

в) сортировка с помощью прямого обмена (пузырьковая) и его модификация – шейкерная сортировка.

2. Освоить эффективные алгоритмы улучшенных методов сортировок:

а) сортировка Шелла (с помощью включений с уменьшением расстояний);

б) сортировка с помощью дерева (пирамидальная HeapSort), базируется на прямом выборе;

в) сортировка с помощью разделения (QuickSort), основанная на прямом обмене; особенности реализаций рекурсивным и итеративным алгоритмами;

3. Освоить применение алгоритмов сортировок для вычисления значения i-той порядковой статистики.

Теоретические сведения.

Обычно сортировку подразделяют на два класса: внутреннюю и внешнюю. При внутренней сортировке все элементы хранятся в оперативной памяти, таким образом, как правило, это сортировка массивов. При внешней сортировке — элементы хранятся на внешнем запоминающем устройстве, это сортировка файлов.

Одно из Основных требований к методам сортировки — экономное использование памяти. Это означает, что переупорядочение нужно выполнять «на том же месте», то есть методы пересылки элементов из одного массива в другой не представляют интереса.

Удобной мерой эффективности является подсчет числа С — сравнений элементов и М — присваиваний элементов. Достаточно хороший алгоритм затрачивает на сортировку N элементов время порядка N×log₂(N). Простейшие алгоритмы сортировки, которые мы рассмотрим в этом разделе, обладают характеристикой порядка N². Если N достаточно мало, то простые алгоритмы выгодно использовать в силу простоты их реализации.

Сортировка выбором

Сортировка методом простого выбора сводится к следующим шагам:
1. Установить номер наибольшего элемента массива.
2. Поменять местами наибольший и последний элементы массива.
3. Оставив в покое последний элемент, выполнить пункты 1 и 2 над остатком массива (массивом без последнего элемента). Пункт 3 повторять, пока остаток массива не сократится до одного элемента.

Опишем процедуру сортировки на языке проектирования программ (псевдокоде).

Вот как изменяется значение массива из пяти элементов (30,20,10,50,40)

Подчеркнута область поиска наибольшего элемента