Презентация Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств абсолютно бесплатно. Урок-презентация на эту тему содержит всего 20 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:20 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:194.00 kB
- Просмотров:67
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Поиск информации
Задача поиска:
где в заданной совокупности данных находится элемент, обладающий заданным свойством?
Большинство задач поиска сводится к поиску в таблице элемента с заданным значением.
№2 слайд
Содержание слайда: Алгоритмы поиска информации
Линейный поиск
№3 слайд
Содержание слайда: Пример:
Написать программу поиска элемента х в массиве из n элементов. Значение элемента х вводится с клавиатуры.
Решение:
Дано:
Const n= 10;
Var a: Array[1..n] of integer;
x: integer;
№4 слайд
Содержание слайда:
№5 слайд
Содержание слайда:
№6 слайд
Содержание слайда:
№7 слайд
Содержание слайда: Задание
оформить программу и проследить ее работу в режиме пошагового просмотра при различных значениях х;
модифицировать программу для поиска элемента массива, равного х, с максимально возможным индексом.
№8 слайд
Содержание слайда: Линейный поиск с использованием барьера
Недостатком нашей программы является то, что в заголовке цикла записано достаточно сложное условие, которое проверяется перед каждым увеличением индекса, что замедляет поиск. Чтобы ускорить его необходимо максимально упростить логическое выражение.
Для этого используем искусственный прием!
№9 слайд
Содержание слайда:
№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.
Найдем номер среднего элемента:
№16 слайд
Содержание слайда:
№17 слайд
Содержание слайда:
№18 слайд
Содержание слайда: Фрагмент программной реализации бинарного поиска:
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:=0
else if a[m] < x then L:= m + 1
else R:= m - 1
until a[m]= x;
ans:= m;
End;
№20 слайд
Содержание слайда: Задание:
Использование идеи двоичного поиска позволяет значительно улучшить алгоритм сортировки массива методом простого включения. Учитывая, что готовая последовательность, в которую надо вставлять элемент, является упорядоченной, можно методом деления пополам определить позицию включения нового элемента в неё. Такой модифицированный алгоритм сортировки называется методом двоичного включения.
Написать программу, реализующую этот метод.
Скачать все slide презентации Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств одним архивом:
