Презентация Двоичный поиск в упорядоченном массиве онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Двоичный поиск в упорядоченном массиве абсолютно бесплатно. Урок-презентация на эту тему содержит всего 30 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Двоичный поиск в упорядоченном массиве
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:30 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:722.21 kB
- Просмотров:68
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№4 слайд
![Алгоритм на псевдокоде первая](/documents_6/f2f69d634887215583a20c8c7e2af85a/img3.jpg)
Содержание слайда: Алгоритм на псевдокоде
(первая версия)
Обозначим
L, R – правая и левая границы рабочей части массива,
Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска.
L: = 1, R: = n, Найден: = нет
DO ( L ≤ R )
m: = ⌊(L+R)/2⌋
IF (am=X) Найден: =да OD FI
IF (am < X) L: = m+1
ELSE R: = m-1
FI
OD
№8 слайд
![а б б б в г д е ж з и к Х б L](/documents_6/f2f69d634887215583a20c8c7e2af85a/img7.jpg)
Содержание слайда: 1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
а б б б в г д е ж з и к Х=б
L=1, R=12
1 2 3 4 5 6
а б б б в г L=1, R=6
1 2 3
а б б L=1, R=3
1 2
а б L=1, R=2
2
б L=2, R=2
Преимущества второй версии алгоритма:
1) на каждой итерации цикла одно сравнение,
2) находит самый левый элемент среди тех, которые удовлетворяют ключу.
№9 слайд
![Трудоемкость двоичного поиска](/documents_6/f2f69d634887215583a20c8c7e2af85a/img8.jpg)
Содержание слайда: Трудоемкость двоичного поиска
Сначала определим
максимальное количество итераций (k).
Рассмотрим худший случай, когда
1) часть массива aL , … , aR содержит нечетное количество элементов
2) в начале каждой итерации
слева элементов на один больше
3) на каждом шаге выбирается левая часть массива.
№14 слайд
![Сортировка данных со сложной](/documents_6/f2f69d634887215583a20c8c7e2af85a/img13.jpg)
Содержание слайда: Сортировка данных
со сложной структурой
Пример. Struct abonent { char name[10];
long phone;
} A[n];
Попытка сортировки:
DO ( i = 1, 2, …, n-1 )
DO ( j = n, n-1, …, i+1)
IF ( Aj < Aj-1 ) Aj ↔ Aj-1 FI
OD
OD
Эта запись не будет верной, т.к. компилятор не знает как сравнивать элементы типа структура, т.к. они не являются встроенными элементами языка.
№15 слайд
![Чтобы реализовать операцию](/documents_6/f2f69d634887215583a20c8c7e2af85a/img14.jpg)
Содержание слайда: Чтобы реализовать операцию сравнения для структур, необходимо вспомнить, что любая операция отношения есть булева функция двух аргументов.
Чтобы реализовать операцию сравнения для структур, необходимо вспомнить, что любая операция отношения есть булева функция двух аргументов.
X<Y
меньше (X, Y) =
Логическая функция Less (меньше)
может выглядеть следующим образом:
Int less ( struct abonent X, struct abonent Y)
{ … ? … }
№16 слайд
![Логическая функция Less](/documents_6/f2f69d634887215583a20c8c7e2af85a/img15.jpg)
Содержание слайда: Логическая функция Less (меньше)
Логическая функция Less (меньше)
При сортировке по имени абонента:
int less ( struct abonent X, struct abonent Y)
{ if ( X.name<Y.name) return 1;
else return 0;
}
При сортировке по номеру телефона абонента:
int less ( struct abonent X, struct abonent Y)
{ if ( X.phone<Y.phone) return 1;
else return 0;
}
№18 слайд
![При сортировке по сложному](/documents_6/f2f69d634887215583a20c8c7e2af85a/img17.jpg)
Содержание слайда: При сортировке по сложному ключу так же легко определить функцию less.
При сортировке по сложному ключу так же легко определить функцию less.
Для сортировки по фамилии абонента и (дополнительно) по номеру телефона:
int less ( struct abonent X, struct abonent Y)
{ if ( X.name < Y.name) return 1;
else if ( X.name > Y.name) return 0;
else if ( X.phone < Y.phone) return 1;
else return 0;
}
№19 слайд
![Тогда в алгоритмах сортировок](/documents_6/f2f69d634887215583a20c8c7e2af85a/img18.jpg)
Содержание слайда: Тогда в алгоритмах сортировок вместо оператора сравнения используем вызов функции less.
Тогда в алгоритмах сортировок вместо оператора сравнения используем вызов функции less.
Например, в пузырьковой сортировке:
DO ( i = 1, 2, …, n-1)
DO ( j = n, n-1, …, i+1)
IF ( less ( Aj , Aj-1 ) ) Aj ↔ Aj-1 FI
OD
OD
№20 слайд
![Вывод Вывод Если структура](/documents_6/f2f69d634887215583a20c8c7e2af85a/img19.jpg)
Содержание слайда: Вывод:
Вывод:
Если структура сортируемых данных
не соответствует
простым (встроенным) типам языка, то
операции отношения необходимо переопределить
с помощью соответствующих булевых функций.
Аналогичное переопределение операций сравнений требуется и для организации поиска!
№21 слайд
![Преимущества Преимущества](/documents_6/f2f69d634887215583a20c8c7e2af85a/img20.jpg)
Содержание слайда: Преимущества:
Преимущества:
1) Операции отношения могут быть определены различными способами в зависимости от ключа сортировки и условия упорядочения данных.
2) Изменение направления упорядочения массива легко достигается с помощью изменения знака в операции отношения на противоположный.
Операции пересылки не требуют переопределения,
т.к. выполняются путем побайтового копирования.
№23 слайд
![Сортировка по множеству](/documents_6/f2f69d634887215583a20c8c7e2af85a/img22.jpg)
Содержание слайда: Сортировка по множеству ключей
Пусть рассмотренный телефонный справочник хранится в виде базы данных в памяти компьютера и мы хотим использовать его для эффективного решения двух задач:
1) Быстро искать запись по заданной фамилии (справочник должен быть отсортирован по фамилиям абонентов);
2) Быстро искать запись по заданному номеру телефона (справочник должен быть отсортирован по номерам телефонов абонентов);
Для одновременного решения этих задач рассмотрим прием, называемый индексацией.
№24 слайд
![Индексация данных Рассмотрим](/documents_6/f2f69d634887215583a20c8c7e2af85a/img23.jpg)
Содержание слайда: Индексация данных
Рассмотрим суть индексации на массиве целых чисел:
1 2 3 4 5 6 7 8 - физические номера
А: 5 7 3 4 2 6 1 8
В: 7 5 3 4 1 6 2 8
1 2 3 4 5 6 7 8 - логические номера
Массив В - индексный массив (индекс) массива А.
А [ B[i] ] – обращение к элементу массива А
через индекс В.
С: 8 2 6 1 4 3 5 7 - номера элементов массива А по убыванию
Массив С – индексный массив (индекс) массива А.
А [ С[i] ] – обращение к элементу массива А
через индекс С.
№25 слайд
![Чтобы упорядочить массив А по](/documents_6/f2f69d634887215583a20c8c7e2af85a/img24.jpg)
Содержание слайда: Чтобы упорядочить массив А (по возрастанию),
Чтобы упорядочить массив А (по возрастанию),
мы построили индексный массив В,
в него записали номера элементов массива А (по возрастанию элементов) и
обращаемся к элементам массива А
через индекс В.
При доступе к массиву А через индекс
мы работаем с ним как с упорядоченным
(например, можем производить быстрый двоичный поиск), в то время как
сами элементы физически не переставляются.
№26 слайд
![Пример. Вывод элементов](/documents_6/f2f69d634887215583a20c8c7e2af85a/img25.jpg)
Содержание слайда: Пример. Вывод элементов массива (по возрастанию):
Пример. Вывод элементов массива (по возрастанию):
DO ( i = 1, …, n)
вывод ( А [ В[i] ] )
OD
Пример. Двоичный поиск (вторая версия):
L: = 1, R: = n
DO ( L<R )
m: = ⌊(L+R)/2⌋
IF (А[В[m]] < X) L: = m+1
ELSE R: = m
FI
OD
IF (А[В[R]] = X) Найден: = да
ELSE Найден: = нет
FI
№27 слайд
![Построение индексного массива](/documents_6/f2f69d634887215583a20c8c7e2af85a/img26.jpg)
Содержание слайда: Построение индексного массива
Построение индексного массива выполняется
на базе любого алгоритма сортировки.
*Вначале в массив В записываются физические номера элементов массива А.
*Затем производится любая сортировка
при условии, что:
1) В операциях сравнения элементы массива А индексируются через В;
2) Перестановки делаются только в массиве В;
№30 слайд
![Преимущества индексации](/documents_6/f2f69d634887215583a20c8c7e2af85a/img29.jpg)
Содержание слайда: Преимущества индексации
Определение. Фильтрация – использование при работе только тех элементов, которые отвечают некоторым условиям.
Совокупность условий называется фильтром.
Пример. Из массива А выбираем только четные элементы по возрастанию.
1 2 3 4 5 6 7 8
А : 5 7 3 4 2 6 1 8
D : 5 4 6 8 - только четные, по возрастанию
Скачать все slide презентации Двоичный поиск в упорядоченном массиве одним архивом:
Похожие презентации
-
Разработка и реализация алгоритма создания и балансировки двоичного дерева поиска со взвешенными узлами
-
Сбалансированное дерево двоичного поиска. АВЛ-дерево, красно-чёрное дерево
-
Массивы. Алгоритмы поиска информации
-
Сортировки. Двоичный поиск
-
Рекурсия, быстрая сортировка, двоичный поиск
-
Сортировка строкового массива на Delphi
-
Одномерные массивы в языке программирования Паскаль. Составление программ
-
Массивы. Понятие массива. Заполнение массива. Печать массива
-
Массивы. (Тема 6)
-
Способы описания и обработки одномерных массивов