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

Поисковые системы

другие презентации о поисковых системах

«Круговая диаграмма» - Этапы построения круговой диаграммы. В контекстном меню выберите - Поворот объемной фигуры – измените положение диаграммы. http://www.unesco.ru/ http://www.tolerance.ru/index.html. Заголовок диаграммы. С чего начинается воспитание толерантности? Постройте диаграмму по данным на Листе2 (название страны в раздаточных материалах).

«Развитие баз данных» - Первый этап — базы данных на больших ЭВМ. 1. Избыточность данных. Недостатки файловых систем. Особенности третьего этапа. Четвертый этап - перспективы развития систем управления базами данных. Особенности первого этапа. 3. Зависимость структур данных и прикладных программ. Значительная роль отводится администрированию данных.

«Информация и данные» - Базы данных. Access (продолжение). Access базы данных. Технология работы 1.Запустите СУБД. 2.Создайте новую базу данных. Объекты базы данных. Введите в структуру базы данных поля Номер и Пол. Информационная система (по законодательству РФ) - организационно- упорядоченная совокупность документов. Информация в БД должна быть: непротиворечивой; неизбыточной; целостной.

«Информация базы данных» - В плане экзаменационной работы ЕГЭ 2009 года – задание А14. Задачник-практикум. Том 2. под ред. БИНОМ, 2006 Макарова Н.В. и др. Семакин И. Г. и др. Информатика и ИКТ. 11 класс. ПИТЕР, 2006 Макарова Н.В. и др. Базовый уровень. Учебная и методическая литература. Базовый курс. 9 класс.

«Передача данных» - Сеансовый уровень устанавливает порядок взаимодействия двух удаленных процессов (программ). Пример прямой блокировки приведен на рис. 14. Адрес назначения. Управление потоком данных. Структура таблицы маршрутизации приведена на рис. 12. Пример неэффективного использования ресурсов приведён на рис. 13.

«Диаграммы» - Столбиковая диаграмма. Диаграммы используются для наглядного, запоминающегося изображения и сопоставления данных. Постройте столбиковую диаграмму, показывающую число кирпичей, купленных каждый год. 6. «Лучше один раз увидеть, чем сто раз услышать». Таблицы удобны для упорядочивания и поиска данных. 2.

Урок

Информатика

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