Поиск данных

Поисковые системы Скачать презентацию
<< Поисковые системы		Поиск в интернете >>

Фотографий нет

Фото из презентации «Поиск данных» к уроку информатики на тему «Поисковые системы»

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

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

Поиск данных

содержание презентации «Поиск данных»

Сл	Текст	Эф	Сл	Текст	Эф
1	Поиск информации. Задача поиска: где в заданной	0	9	номером.	0
	совокупности данных находится элемент, обладающий		10	Задание. Изменить программу так, чтобы был найден	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) and	0	15	Пример: Массив а: 3 5 6 8 12 15 17 18 20 25 х = 6	10
	(a[i] <> x) do inc(i); В результате: либо будет			Шаг 1. Найдем номер среднего элемента: Так как 6 <
	найден искомый элемент, т.е. найдется такой индекс i,			a[5]. 3 5 6 8 12 15 17 18 20 25.
	что a[i] = x; либо будет просмотрен весь массив, и		16	A[3] = 6! Его номер – 3. Шаг 2. Рассмотрим лишь	9
	искомый элемент не обнаружится. Поскольку поиск			первые 4 элемента массива. Индекс среднего элемента:
	заканчивается только в случае, когда i = n + 1 или			Аналогично: Шаг 3. Рассматриваем два элемента.
	когда искомый элемент найден, то из этого следует, что		17	В общем случае формула поиска значения среднего	0
	если в массиве есть несколько элементов, совпадающих с			элемента m: Где L – индекс первого, а R – индекс
	элементом х, то в результате работы программы будет			последнего элемента рассматриваемой части массива.
	найден первый из них, т.е. элемент с наименьшим		18	Begin 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; Фрагмент
	Недостатком нашей программы является то, что в			программной реализации бинарного поиска:
	заголовке цикла записано достаточно сложное условие,		19	Begin a[0]:=x; L:= 1; R:= n; Repeat m:= (L + R) div	1
	которое проверяется перед каждым увеличением индекса,			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