Поисковые системы Скачать
презентацию
<<  Поиск Поиск в интернете  >>
Поиск информации
Поиск информации
Линейный поиск
Линейный поиск
Пример:
Пример:
В данном случае известно только значение разыскиваемого элемента,
В данном случае известно только значение разыскиваемого элемента,
Прервем просмотр сразу же после обнаружения заданного элемента
Прервем просмотр сразу же после обнаружения заданного элемента
Используем цикл с предусловием
Используем цикл с предусловием
Задание
Задание
Линейный поиск с использованием барьера
Линейный поиск с использованием барьера
В массиве на n + 1 место запишем искомый элемент х, который будет
В массиве на n + 1 место запишем искомый элемент х, который будет
Задание
Задание
Если никаких дополнительных сведений о массиве, в котором хранится
Если никаких дополнительных сведений о массиве, в котором хранится
Бинарный поиск
Бинарный поиск
Задача
Задача
Идея бинарного метода
Идея бинарного метода
Пример:
Пример:
A[3] = 6
A[3] = 6
В общем случае формула поиска значения среднего элемента m:
В общем случае формула поиска значения среднего элемента m:
Begin L:= 1; R:= n; {на первом шаге – весь массив} f:= false; {признак
Begin L:= 1; R:= n; {на первом шаге – весь массив} f:= false; {признак
Begin a[0]:=x; L:= 1; R:= n; Repeat m:= (L + R) div 2; if L > R then m
Begin a[0]:=x; L:= 1; R:= n; Repeat m:= (L + R) div 2; if L > R then m
Задание:
Задание:
Слайды из презентации «Поиск данных» к уроку информатики на тему «Поисковые системы»

Автор: BLV. Чтобы увеличить слайд, нажмите на его эскиз. Чтобы использовать презентацию на уроке, скачайте файл «Поиск данных.ppt» бесплатно в zip-архиве размером 51 КБ.

Скачать презентацию

Поиск данных

содержание презентации «Поиск данных.ppt»
СлайдТекст
1 Поиск информации

Поиск информации

Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинство задач поиска сводится к поиску в таблице элемента с заданным значением.

2 Линейный поиск

Линейный поиск

Алгоритмы поиска информации

3 Пример:

Пример:

Написать программу поиска элемента х в массиве из n элементов. Значение элемента х вводится с клавиатуры. Решение: Дано: Const n= 10; Var a: Array[1..n] of integer; x: integer;

4 В данном случае известно только значение разыскиваемого элемента,

В данном случае известно только значение разыскиваемого элемента,

никакой дополнительной информации о нем или о массиве, в котором его надо искать, нет. Поэтому для решения задачи разумно применить последовательный просмотр массива и сравнение значения очередного рассматриваемого элемента с данным. Если значение очередного элемента совпадает с х, то запомним его номер в переменной k. For i:=1 to n do if a[i] = x then k:=i;

5 Прервем просмотр сразу же после обнаружения заданного элемента

Прервем просмотр сразу же после обнаружения заданного элемента

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

6 Используем цикл с предусловием

Используем цикл с предусловием

While (i<=n) and (a[i] <> x) do inc(i); В результате: либо будет найден искомый элемент, т.е. найдется такой индекс i, что a[i] = x; либо будет просмотрен весь массив, и искомый элемент не обнаружится. Поскольку поиск заканчивается только в случае, когда i = n + 1 или когда искомый элемент найден, то из этого следует, что если в массиве есть несколько элементов, совпадающих с элементом х, то в результате работы программы будет найден первый из них, т.е. элемент с наименьшим индексом.

7 Задание

Задание

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

8 Линейный поиск с использованием барьера

Линейный поиск с использованием барьера

Недостатком нашей программы является то, что в заголовке цикла записано достаточно сложное условие, которое проверяется перед каждым увеличением индекса, что замедляет поиск. Чтобы ускорить его необходимо максимально упростить логическое выражение. Для этого используем искусственный прием!

9 В массиве на n + 1 место запишем искомый элемент х, который будет

В массиве на n + 1 место запишем искомый элемент х, который будет

являться барьерным. Тогда если в процессе работы программы a[n + 1] := x; i := 1; While a[i] <> x do inc(i); обнаружится такой индекс i, что a[i] = x, то элемент будет найден. Но если a[i] = x будет только при i = n + 1, то, значит, интересующего нас элемента в массиве нет. В случае наличия в массиве нескольких элементов, удовлетворяющих заданному свойству, будет также найден элемент с наименьшим номером.

10 Задание

Задание

Изменить программу так, чтобы был найден элемент с максимально возможным индексом.

11 Если никаких дополнительных сведений о массиве, в котором хранится

Если никаких дополнительных сведений о массиве, в котором хранится

массив нет, то ускорить поиск нельзя. Если же известна некоторая информация о данных, среди которых ведется поиск, например, массив данных отсортирован, удается существенно сократить время поиска, применяя непоследовательные методы поиска.

12 Бинарный поиск

Бинарный поиск

Иначе двоичный поиск или метод половинного деления. При его использовании на каждом шаге область поиска сокращается вдвое.

13 Задача

Задача

Дано целое число х и массив а[1..n], отсортированный в порядке неубывания чисел, то есть для любого k: 1 ? k < n: a[k-1] ? a[k]. Найти такое i, что a[i] = x или сообщить, что элемента х в массиве нет.

14 Идея бинарного метода

Идея бинарного метода

- проверить, является ли х средним элементом массива. Если да, то ответ получен. Если нет, то возможны два случая: х меньше среднего элемента. Следовательно, после этого данный метод можно применить к левой половине массива. х больше среднего элемента. Аналогично, теперь этот метод следует применить к правой части массива.

15 Пример:

Пример:

Массив а: 3 5 6 8 12 15 17 18 20 25 х = 6 Шаг 1. Найдем номер среднего элемента:

Так как 6 < a[5]

3 5 6 8 12 15 17 18 20 25

16 A[3] = 6

A[3] = 6

Его номер – 3.

Шаг 2. Рассмотрим лишь первые 4 элемента массива. Индекс среднего элемента: Аналогично:

Шаг 3. Рассматриваем два элемента

17 В общем случае формула поиска значения среднего элемента m:

В общем случае формула поиска значения среднего элемента m:

Где L – индекс первого, а R – индекс последнего элемента рассматриваемой части массива.

18 Begin L:= 1; R:= n; {на первом шаге – весь массив} f:= false; {признак

Begin L:= 1; R:= n; {на первом шаге – весь массив} f:= false; {признак

того, что х не найден} while ( L<=R) and not f do begin m:= (L + R) div 2; if a[m] = x then f:= true { элемент найден. Поиск надо прекратить} else if a[m] < x then L:= m + 1 {отбрасывается левая часть} else R:= m – 1 {отбрасывается правая часть} end End;

Фрагмент программной реализации бинарного поиска:

19 Begin a[0]:=x; L:= 1; R:= n; Repeat m:= (L + R) div 2; if L > R then m

Begin a[0]:=x; L:= 1; R:= n; Repeat m:= (L + R) div 2; if L > R then m

=0 else if a[m] < x then L:= m + 1 else R:= m - 1 until a[m]= x; ans:= m; End;

Бинарный поиск с использованием фиктивного «барьерного» элемента.

(Списать в тетрадь. Добавить комментарий)

20 Задание:

Задание:

Использование идеи двоичного поиска позволяет значительно улучшить алгоритм сортировки массива методом простого включения. Учитывая, что готовая последовательность, в которую надо вставлять элемент, является упорядоченной, можно методом деления пополам определить позицию включения нового элемента в неё. Такой модифицированный алгоритм сортировки называется методом двоичного включения. Написать программу, реализующую этот метод.

«Поиск данных»
http://900igr.net/prezentatsii/informatika/Poisk-dannykh/Poisk-dannykh.html
cсылка на страницу
Урок

Информатика

126 тем
Слайды
Презентация: Поиск данных.ppt | Тема: Поисковые системы | Урок: Информатика | Вид: Слайды