Алгоритмы поиска и выборки

Лабораторная работа 8.

Тема: Алгоритмы поиска и выборки.

Задания:

1. Написать программу реализующую алгоритм последовательного поиск целевого значения из выборки N чисел (использовать любой язык программирования).

2. Написать программу реализующую алгоритм двоичного поиска целевого значения из выборки N чисел (использовать любой язык программирования).

3. Провести анализ наихудшего и среднего случаев.

4. Оформить отчет в MSWord и показать работающую программу преподавателю.

Теоретический минимум.

Алгоритмы поиска и выборки

Поиск необходимой информации в списке — одна из фундаментальныхзадач теоретического программирования. При обсуждении алгорит­мов поиска мы предполагаем, что информация содержится в записях, составляющих некоторый список, который представляет собой массив данных в программе. Записи, или элементы списка, идут в массиве последовательно и между ними нет промежутков. Номера записей в списке идут от 1 до N — полного числа записей. В принципе записи могут быть составлены из полей, однако нас будут интересовать зна­чения лишь одного из этих полей, называемого ключом. Списки могут быть не отсортированными или отсортированными по значению ключе­вого поля. В не отсортированном списке порядок записей случаен, а в отсортированном они идут в порядке возрастания ключа.

Поиск нужной записи в не отсортированном списке сводится к про­смотру всего списка до того, как запись будет найдена. Это простей­ший из алгоритмов поиска. Мы увидим, что этот алгоритм не очень эффективен, однако он работает на произвольном списке.

В отсортированном списке возможен также двоичный поиск. Дво­ичный поиск использует преимущества, предоставляемые имеющимся упорядочиванием, для того, чтобы отбрасывать за одно сравнение боль­ше одного элемента. В результате поиск становится более эффективным.

С поиском конкретного значения связана задача выборки, в кото­рой требуется найти элемент, удовлетворяющий некоторым условиям. Скажем, нам может понадобиться пятый по величине элемент, седьмой с конца или элемент со средним значением. Мы обсудим два подхода к этой задаче.

1. Последовательный поиск

В алгоритмах поиска нас интересует процесс просмотра списка в поисках некоторого конкретного элемента, называемого целевым. При последовательном поиске мы всегда будем предполагать, хотя в этом и нет особой необходимости, что список не отсортирован, поскольку некоторые алгоритмы на отсортированных списках показывают луч­шую производительность. Обычно поиск производится не просто для проверки того, что нужный элемент в списке имеется, но и для того, чтобы получить данные, относящиеся к этому значению ключа. Напри­мер, ключевое значение может быть номером сотрудника или порядко­вым номером, или любым другим уникальным идентификатором. После того, как нужный ключ найден, программа может, скажем, частично изменить связанные с ним данные или просто вывести всю запись. Во всяком случае, перед алгоритмом поиска стоит важная задача опреде­ления местонахождения ключа. Поэтому алгоритмы поиска возвраща­ют индекс записи, содержащей нужный ключ. Если ключевое значение не найдено, то алгоритм поиска обычно возвращает значение индекса, превышающее верхнюю границу массива. Для наших целей мы будем предполагать, что элементы списка имеют номера от 1 до N . Это по­зволит нам возвращать 0 в случае, если целевой элемент отсутствует в списке. Для простоты мы предполагаем, что ключевые значения не повторяются.

Алгоритм последовательного поиска последовательно просматрива­ет по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. Очевидно, что чем дальше в списке находится конкретное значение ключа, тем больше времени уйдет на его поиск. Это следует помнить при анализе алгоритма последовательного поиска.

Вот как выглядит полный алгоритм последовательного поиска.

SequentialSearch(list.target,N)
listсписок для просмотра

target целевое значение
N число элементов в списке

for i=l to N do

if (target=list[i])

return i

end if

end for

return 0

Анализ наихудшего случая

У алгоритма последовательного поиска два наихудших случая. В первом случае целевой элемент стоит в списке последним. Во втором его вовсе нет в списке. Посмотрим, сколько сравнений выполняется в каждом из этих случаев. Мы предположили, что все ключевые значения в списке уникальны, и поэтому если совпадение произошло в последней записи, то все предшествующие сравнения были неудачными. Однако алгоритм проделывает все эти сравнения пока не дойдет до последнего элемента. В результате будет проделано N сравнений, где N — число элементов в списке.

Чтобы проверить, что целевое значение в списке отсутствует, его придется сравнить со всеми элементами списка. Если мы пропустим какой-то элемент, то не сможем выяснить, отсутствует ли целевое зна­чение в списке вообще или оно содержится в каком-то из пропущенных элементов. Это означает, что для выяснения того, что ни один из эле­ментов не является целевым, нам потребуется N сравнений.

Так что N сравнений необходимо как для того, чтобы найти значе­ние, содержащееся в последнем элементе списка, так и для того, что­бы выяс

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать