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

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

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

X

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

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

Кнопки:

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


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

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


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



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

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

№ слайда 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

№ слайда 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. Найдем номер среднего элемента: Так как 6 < a[5] 3 5 6 8 12 15 17 18 20 25

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

Шаг 2. Рассмотрим лишь первые 4 элемента массива. Индекс среднего элемента: Аналогично: Шаг 3. Рассматриваем два элемента A[3] = 6! Его номер – 3

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

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

№ слайда 18 Фрагмент программной реализации бинарного поиска: Begin L:= 1; R:= n; {на первом
Описание слайда:

Фрагмент программной реализации бинарного поиска: Begin L:= 1; R:= n; {на первом шаге – весь массив} f:= false; {признак того, что х не найден} while ( L

№ слайда 19 Бинарный поиск с использованием фиктивного «барьерного» элемента. Begin a[0]:=x;
Описание слайда:

Бинарный поиск с использованием фиктивного «барьерного» элемента. 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 Задание: Использование идеи двоичного поиска позволяет значительно улучшить алго
Описание слайда:

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

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


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