Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 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 Сортировка методом подсчета
Приложение 3. Сортировка методом вставок
Приложение 4. Сортировка методом Шелла
Приложение 5 Бинарный поиск
Приложение 6 Последовательный поиск
|
|||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-01-08; просмотров: 152; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.141.47.221 (0.023 с.) |