PPt4Web Хостинг презентаций

Главная / Информатика / Поиск информации
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Поиск информации


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

Презентация на тему: Поиск информации


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

№ слайда 1 Поиск информации Задача поиска:где в заданной совокупности данных находится элем
Описание слайда:

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

№ слайда 2 Алгоритмы поиска информации Линейный поиск
Описание слайда:

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

№ слайда 3 Пример: Написать программу поиска элемента х в массиве из n элементов. Значение
Описание слайда:

Пример: Написать программу поиска элемента х в массиве из 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
Описание слайда:

Используем цикл с предусловием.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], отсортированный в порядке неубывания
Описание слайда:

Задача Дано целое число х и массив а[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.Найдем номер среднего элем
Описание слайда:

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

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

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

№ слайда 17 В общем случае формула поиска значения среднего элемента m:Где L – индекс первог
Описание слайда:

В общем случае формула поиска значения среднего элемента m:Где L – индекс первого, а R – индекс последнего элемента рассматриваемой части массива.

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

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

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

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

№ слайда 20 Задание: Использование идеи двоичного поиска позволяет значительно улучшить алго
Описание слайда:

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

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

Презентации по предмету
Презентации из категории
Лучшее на fresher.ru