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

Категория: Информатика
Нажмите для полного просмотра!
Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №1Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №2Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №3Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №4Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №5Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №6Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №7Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №8Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №9Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №10Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №11Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №12Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №13Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №14Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №15Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №16Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №17Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №18Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №19Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №20
Скачать
Вы можете ознакомиться и скачать Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств. Презентация содержит 20 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


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

Слайд 2


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

Слайд 3


Пример: Написать программу поиска элемента х в массиве из n элементов. Значение элемента х вводится с клавиатуры. Решение: Дано: Const n= 10; Var a: Array[1..n] of integer; x: integer;
Описание слайда:
Пример: Написать программу поиска элемента х в массиве из n элементов. Значение элемента х вводится с клавиатуры. Решение: Дано: Const n= 10; Var a: Array[1..n] of integer; x: integer;

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


Линейный поиск с использованием барьера Недостатком нашей программы является то, что в заголовке цикла записано достаточно сложное условие, которое проверяется перед каждым увеличением индекса, что замедляет поиск. Чтобы ускорить его необходимо максимально упростить логическое выражение. Для этого используем искусственный прием!
Описание слайда:
Линейный поиск с использованием барьера Недостатком нашей программы является то, что в заголовке цикла записано достаточно сложное условие, которое проверяется перед каждым увеличением индекса, что замедляет поиск. Чтобы ускорить его необходимо максимально упростить логическое выражение. Для этого используем искусственный прием!

Слайд 9


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

Слайд 10


Задание Изменить программу так, чтобы был найден элемент с максимально возможным индексом.
Описание слайда:
Задание Изменить программу так, чтобы был найден элемент с максимально возможным индексом.

Слайд 11


Если никаких дополнительных сведений о массиве, в котором хранится массив нет, то ускорить поиск нельзя. Если никаких дополнительных сведений о массиве, в котором хранится массив нет, то ускорить поиск нельзя. Если же известна некоторая информация о данных, среди которых ведется поиск, например, массив данных отсортирован, удается существенно сократить время поиска, применяя непоследовательные методы поиска.
Описание слайда:
Если никаких дополнительных сведений о массиве, в котором хранится массив нет, то ускорить поиск нельзя. Если никаких дополнительных сведений о массиве, в котором хранится массив нет, то ускорить поиск нельзя. Если же известна некоторая информация о данных, среди которых ведется поиск, например, массив данных отсортирован, удается существенно сократить время поиска, применяя непоследовательные методы поиска.

Слайд 12


Бинарный поиск Иначе двоичный поиск или метод половинного деления. При его использовании на каждом шаге область поиска сокращается вдвое.
Описание слайда:
Бинарный поиск Иначе двоичный поиск или метод половинного деления. При его использовании на каждом шаге область поиска сокращается вдвое.

Слайд 13


Задача Дано целое число х и массив а[1..n], отсортированный в порядке неубывания чисел, то есть для любого k: 1 ≤ k < n: a[k-1] ≤ a[k]. Найти такое i, что a[i] = x или сообщить, что элемента х в массиве нет.
Описание слайда:
Задача Дано целое число х и массив а[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


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

Слайд 17


Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинств, слайд №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;
Описание слайда:
Фрагмент программной реализации бинарного поиска: 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;
Описание слайда:
Бинарный поиск с использованием фиктивного «барьерного» элемента. 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


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию