Поисковые системы Скачать
презентацию
<<  Поисковые системы Поиск в интернете  >>
Фотографий нет
Фото из презентации «Поиск данных» к уроку информатики на тему «Поисковые системы»

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

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

Поиск данных

содержание презентации «Поиск данных»
Сл Текст Эф Сл Текст Эф
1Поиск информации. Задача поиска: где в заданной0 9номером.0
совокупности данных находится элемент, обладающий 10Задание. Изменить программу так, чтобы был найден0
заданным свойством? Большинство задач поиска сводится к элемент с максимально возможным индексом.
поиску в таблице элемента с заданным значением. 11Если никаких дополнительных сведений о массиве, в0
2Линейный поиск. Алгоритмы поиска информации.0 котором хранится массив нет, то ускорить поиск нельзя.
3Пример: Написать программу поиска элемента х в0 Если же известна некоторая информация о данных, среди
массиве из n элементов. Значение элемента х вводится с которых ведется поиск, например, массив данных
клавиатуры. Решение: Дано: Const n= 10; Var a: отсортирован, удается существенно сократить время
Array[1..n] of integer; x: integer; поиска, применяя непоследовательные методы поиска.
4В данном случае известно только значение0 12Бинарный поиск. Иначе двоичный поиск или метод0
разыскиваемого элемента, никакой дополнительной половинного деления. При его использовании на каждом
информации о нем или о массиве, в котором его надо шаге область поиска сокращается вдвое.
искать, нет. Поэтому для решения задачи разумно 13Задача. Дано целое число х и массив а[1..n],0
применить последовательный просмотр массива и сравнение отсортированный в порядке неубывания чисел, то есть для
значения очередного рассматриваемого элемента с данным. любого k: 1 ? k < n: a[k-1] ? a[k]. Найти такое i,
Если значение очередного элемента совпадает с х, то что a[i] = x или сообщить, что элемента х в массиве
запомним его номер в переменной k. For i:=1 to n do if нет.
a[i] = x then k:=i; 14Идея бинарного метода. - проверить, является ли х0
5Прервем просмотр сразу же после обнаружения0 средним элементом массива. Если да, то ответ получен.
заданного элемента! Недостатки данного метода: если Если нет, то возможны два случая: х меньше среднего
значение х встречается в массиве несколько раз, то элемента. Следовательно, после этого данный метод можно
найдено будет последнее из них; после того, как нужное применить к левой половине массива. х больше среднего
значение уже найдено, массив просматривается до конца, элемента. Аналогично, теперь этот метод следует
т.е. всегда выполняется n сравнений. применить к правой части массива.
6Используем цикл с предусловием. While (i<=n) and0 15Пример: Массив а: 3 5 6 8 12 15 17 18 20 25 х = 610
(a[i] <> x) do inc(i); В результате: либо будет Шаг 1. Найдем номер среднего элемента: Так как 6 <
найден искомый элемент, т.е. найдется такой индекс i, a[5]. 3 5 6 8 12 15 17 18 20 25.
что a[i] = x; либо будет просмотрен весь массив, и 16A[3] = 6! Его номер – 3. Шаг 2. Рассмотрим лишь9
искомый элемент не обнаружится. Поскольку поиск первые 4 элемента массива. Индекс среднего элемента:
заканчивается только в случае, когда i = n + 1 или Аналогично: Шаг 3. Рассматриваем два элемента.
когда искомый элемент найден, то из этого следует, что 17В общем случае формула поиска значения среднего0
если в массиве есть несколько элементов, совпадающих с элемента m: Где L – индекс первого, а R – индекс
элементом х, то в результате работы программы будет последнего элемента рассматриваемой части массива.
найден первый из них, т.е. элемент с наименьшим 18Begin L:= 1; R:= n; {на первом шаге – весь массив}0
индексом. f:= false; {признак того, что х не найден} while (
7Задание. Оформить программу и проследить ее работу0 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
8Линейный поиск с использованием барьера.0 {отбрасывается правая часть} end End; Фрагмент
Недостатком нашей программы является то, что в программной реализации бинарного поиска:
заголовке цикла записано достаточно сложное условие, 19Begin a[0]:=x; L:= 1; R:= n; Repeat m:= (L + R) div1
которое проверяется перед каждым увеличением индекса, 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;
максимально упростить логическое выражение. Для этого Бинарный поиск с использованием фиктивного «барьерного»
используем искусственный прием! элемента. (Списать в тетрадь. Добавить комментарий).
9В массиве на n + 1 место запишем искомый элемент х,0 20Задание: Использование идеи двоичного поиска0
который будет являться барьерным. Тогда если в процессе позволяет значительно улучшить алгоритм сортировки
работы программы a[n + 1] := x; i := 1; While a[i] массива методом простого включения. Учитывая, что
<> x do inc(i); обнаружится такой индекс i, что готовая последовательность, в которую надо вставлять
a[i] = x, то элемент будет найден. Но если a[i] = x элемент, является упорядоченной, можно методом деления
будет только при i = n + 1, то, значит, интересующего пополам определить позицию включения нового элемента в
нас элемента в массиве нет. В случае наличия в массиве неё. Такой модифицированный алгоритм сортировки
нескольких элементов, удовлетворяющих заданному называется методом двоичного включения. Написать
свойству, будет также найден элемент с наименьшим программу, реализующую этот метод.
20 «Поиск данных» | Поиск данных 20
http://900igr.net/fotografii/informatika/Poisk-dannykh/Poisk-dannykh.html
cсылка на страницу
Урок

Информатика

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