![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Бинарный поиск в информационном массиве. ⇐ ПредыдущаяСтр 5 из 5
Цель работы: изучение метода бинарного поиска и его алгоритма. Методические указания. Бинарный поиск предполагает существование между элементами ИМ отношения упорядочения: К1<K2<,…,<Kn. Поэтому перед началом поиска необходимо провести сортировку массива. Алгоритм бинарного поиска состоит в следующем. Аргумент поиска сравнивается со средним элементом Км из массива ключей {K1, K2, …, Kм}, причем индекс М среднего элемента вычисляется по формуле.
где L – нижняя граница; K – верхняя граница; | Х | – ближайшее целое, меньшее или равное Х. Для исходного массива L=1, K=N. Результат сравнения позволит определить, в какой половине файла продолжать поиск. Если Км=z, то искомый элемент найден. Если Км<z, то L=M+1. Если Км>z, то K=M-1. К выбранной половине файла с границами L и К применяется та же процедура. Если интервал пустой, т.е. L>К, то поиск неудачен. Иначе процесс повторяется: пока средний элемент интервала не будет равен аргументу поиска. В данной работе в качестве ИМ используется упорядоченная последовательность целых чисел, разрядность которых с учетом знакового разряда не должна превышать 5, а количество элементов массива не должно превышать 50. Ключом элемента является само число. Значение границ, номер среднего элемента и сообщение о результатах поиска выводится на печать. Приведем пример бинарного поиска в массиве из 6 чисел. Дано: К={-50; -37; 2; 7; 559; 10001}, z=7. L=1 К=6 М=3 К(3)=2 2<7 L=4 К=6 М=5 К(5)=5 559>7 L=4 К=4 М=4 К(4)=7 7=7 Номер искомого элемента равен 4. Поиск окончен. Так как на исходное множество ключей накладывается требование строгого упорядочения, то возможность появления в нем одинаковых ключей исключается. Организацию бинарного поиска для анализа числа сравнений удобно представить в виде бинарного оптимального дерева. Бинарным деревом называется древовидная структура с двоичным ветвлением. В качестве оптимального (в смысле организации поиска) дерева определяют дерево, ветви которого имеют в высоту от h до h-1, где h – высота дерева. Тогда при 2h-1 £ N < 2h удачный поиск требует (min = 1, max = h) сравнений. Неудачный поиск требует h сравнений при N = 2h - 1, либо h-1 или h сравнений при 2h-1 £ N £ 2h-1-1.
Блок-схема, реализующая бинарный поиск, представлена в Приложении 5. Порядок выполнения работы. 1. Ознакомится с общими методическими указаниями и с описаниями данной работы. Ознакомиться по литературе с основными понятиями обработки ИМ, алгоритмами поиска и требованиями к ним. 2. Изучить блок-схему, реализующую бинарный поиск в ИМ (Приложение 6). 3. Каждому студенту взять из таблицы (лабораторная работа № 5) массив из n ключей {K1,K2, …,Kn} и набор значений аргумента поиска Z. 4. Из данного массива ключей {K1,K2, …,Kn} получить массив {К1’, К2’,…, Кj’} путем исключения дублирующих значений ключей. 5. Записать элементы массива {К1’, К2’,…, Кj’} в порядке возрастания их значений. Провести поиск в полученном массиве вручную, используя лишь одно (любое) из данных значений аргумента поиска (см. пример). 6. Провести сортировку массива {К1’, К2’,…, Кj’} любым из ранее изученных методов. 7. Провести поиск в отсортированном массиве на ЭВМ, задавая по очереди все данные значения аргумента поиска. 8. Построить бинарное дерево поиска в отсортированном массиве для всех значений аргумента поиска. Оценить число сравнений при поиске. Содержание отчета. 1. Краткое изложение целей и задач лабораторной работы, задачи поиска в ИМ и рассматриваемого метода поиска. 2. Схема алгоритма бинарного поиска. 3. Массив {К1’, К2’,…, Кj’} и результаты поиска вручную. 4. Результаты сортировки и поиска в отсортированном массиве на ЭВМ (распечатка с комментариями). 5. Бинарное дерево поиска в отсортированном массиве для всех значений аргумента поиска. Оценка числа сравнений при поиске. 6. Сравнительный анализ методов последовательного и бинарного поиска. Контрольные вопросы. 1. Что такое отношение упорядочения? 2. Что такое бинарное дерево? 3. Что такое оптимальное бинарное дерево? 4. Как определяется высота дерева? 5. Каково возможное минимальное и максимальное число сравнений при удачном поиске? Как оценить среднее число сравнений? 6. Почему при бинарном поиске в исходном массиве не допускается одинаковые значения ключей? 7. В чем заключается разница между первичным и вторичным ключами? Для каких целей используется каждый из них? Приведите примеры их использования.
Литература. 1. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. Т.3: Пер. с англ. – М.: Мир, 1978. – 843с. 2. Флорес И. Структуры и управление данными: Пер. с англ. – М.: Статистика, 1982. – 317с. 3. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: Пер. с англ. – М.: Мир, 1981. – 366с.
Содержание 1. Основные понятия сортировки и поиска........................................................................................ 3 1.1. Сортировка....................................................................................................................................... 3 1.2. Поиск................................................................................................................................................ 9 2. Методические указания к выполнению лабораторных работ..................................................... 11 2.1. Лабораторная работа № 1.............................................................................................................. 11 2.2. Лабораторная работа № 2.............................................................................................................. 15 2.3. Лабораторная работа № 3.............................................................................................................. 17 2.4. Лабораторная работа № 4.............................................................................................................. 20 2.5. Лабораторная работа № 5.............................................................................................................. 27 2.6. Лабораторная работа № 6.............................................................................................................. 30 3. Литература......................................................................................................................................... 33 Приложение 1. Сортировка методом “пузырька”............................................................................. 35 Приложение 2. Сортировка методом подсчета................................................................................. 36 Приложение 3. Сортировка методом вставок................................................................................... 37 Приложение 4. Сортировка методом Шелла..................................................................................... 38 Приложение 5. Бинарный поиск........................................................................................................ 39 Приложение 6. Последовательный поиск......................................................................................... 40
Приложение 1
Приложение 2
Сортировка методом вставок
Приложение 4. Сортировка методом Шелла
![]() ![]()
Приложение 5
Приложение 6
|
|||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-01-08; просмотров: 161; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.138.35.204 (0.022 с.) |