Практическая работа № 5,6,7 Тема: Алгоритмы поиска Цель работы: 1. Изучение основных…
- User
Практическая работа № 5,6,7 Тема: Алгоритмы поиска
Цель работы:
- Изучение основных алгоритмов поиска информации.
- Овладение практическими навыками разработки программ, реализующие алгоритмы поиска информации.
Теоретические сведения Общая классификация алгоритмов поиска. Поиск – нахождение какойнибудь конкретной информации в большом объеме ранее созданных данных. Данные делятся на записи, каждая из которых имеет хотя бы один ключ. Ключи используются для отличия одних записей от других. Цель поиска – нахождение всех записей подходящих к ключу. Кроме поиска по совпадению аргумента и ключа, существует поиск по близости аргумента и ключа. Логически сложные условия поиска могут быть конъюнктивными (обязательно выполнение всех условий), дизъюнктивные (выполнение хотя бы одного условия). Все методы поиска делятся на статические (массив значений не меняется) и динамические (массив может изменять размер или перестраиваться). Последовательный поиск. Последовательный поиск заключается в просмотре элементов списка в порядке расположения, пока не будет найден необходимый элемент, если неизвестно есть ли такой элемент в списке, необходимо следить чтобы поиск не вышел за пределы списка. Для упорядоченных списков существует более эффективные алгоритмы поиска. Бинарный поиск. Он состоит в том, что ключ сравнивается со средним элементом, если значения равны, то элемент найден, если нет поиск продолжается в одной из половин массива.
Фибоначчиев поиск (Поиск по дереву Фибоначчи). Суть алгоритма состоит в том, что сравнивая искомое число с очередным значением в массиве мы не делим его по полам, а отступаем от предыдущего значения в нужную сторону на число Фибоначчи.
Интерполяционный поиск. Суть алгоритма заключается в том, что мы предполагаем, что исходные данные находятся в некоторой зависимости друг от друга. Тогда если предположить, что такая зависимость арифметическая, то можно вычислить на какое расстояние необходимо перейти при поиске необходимого элемента. Так же методы поиска можно разделить на методы, использующие истинные ключи и на методы, работающие по преобразованным ключам.
Ну и еще вариант классификации – методы основанные на сравнении самих значений и методы, основанные на их цифровых свойствах. Так называемые методы хэширования.
Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хешфункциями, а их результаты называют хешем или хеш-кодом. Существует множество алгоритмов хеширования с различными характеристиками. Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшим примером хеш-функции может служить контрольная сумма.Дихотомический (бинарный) поиск Бинарный поиск (binary search) впервые упомянут Джоном Мочли в 1946 году. Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован. Суть метода заключается в следующем. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m=(l+r) div 2. Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска. В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны. На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска. Запишем все сказанное в виде программы: int l = 0; // левая граница int r = n-1; // правая граница int mid;
while ((l <= r) && (flag != true)) { mid=(l + r)/2; //считываем срединный индекс отрезка [l,r]if (a[mid] == key) flag = true; //проверяем ключ со серединным элементом if (a[mid] > key) r = mid - 1; // проверяем, какую часть нужно отбросить else l = mid + 1;}
Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность алгоритма O(log(n)).
Задание для самостоятельной работы: Реализовать алгоритм дихотомического (бинарного) поиска заданной информации в исходном массиве размерностью N (25<N<1000).
Фибоначчиев поиск Фибоначчиев поиск изобретен Дэвидом Э. Фергюсоном (David Е. Ferguson)в 1960 году. Поиск делением по числам Фибоначчи. Метод поиска, отличающийся от метода половинного деления (binary search) тем, что область поиска делится не пополам, а в точках, являющийся числами Фибоначчи.
Рассмотрим работу алгоритма на примере. Пусть задан массив: 1 4 5 7 9 11 13 16 18 20 25 27 30 32 33 36 39 41 44 47 51 53 55 и число x=27, которое необходимо найти в данном массиве.
Рассматриваем только те элементы массива, которые находятся на позициях с номерами равными числам Фибоначчи.
Это числа: 1 4 5 9 16 30 и 51. Определяем диапазон в котом находится заданное число, т.е. [16,30]. Все числа в этом диапазоне нумеруем и вновь рассматриваем только те позиции которые равны числам Фибоначчи. И так далее пока позиции которые равны числам Фибоначчи не окажется искомое число или пока диапазон не уменьшится до одного числа (в этом случае можно констатировать, что поиск завершился неудачей). Такой поиск по нашему массиву будет иметь три этапа:1 4 5 7 9 11 13 16 18 20 25 27 30 32 33 36 39 41 44 47 51
1 2 3 5 8 13 21
8 13
1 1 2 3 5 3 5 1 1 2
1Алгоритм поиска по числам Фибоначчи можно описать следующими шагами: Шаг 1. Определим k как начало интервала на котором будем производить поиск на данной итерации. Шаг 2. Если k=0 то необходимо предусмотреть выход и определить неудачный поиск (искомый элемент не принадлежит массиву). Шаг 3. Если x=a[k] то необходимо предусмотреть выход и определить удачный поиск. Шаг 4. Определяем новый диапазон поиска и определяем новое значение k. Для этого к числу k последовательно прибавляем числа Фибоначчи, пока результат не станет больше чем искомое значение x. Шаг 5. Повторяем алгоритм с шага 2.
Такой алгоритм можно представить следующей функцией: int fibonaccianSearch(int arr[], int n, int x){ /* Инициализация чисел Фибоначчи */ int fibMMm2 = 0; // (m-2)-е число Фибоначчи int fibMMm1 = 1; // (m-1)-е число Фибоначчи int fibM = fibMMm2 + fibMMm1; // m-е число Фибоначчи
/* Находим диапазон чисел Фибоначчи, в котором находится число n */ while (fibM < n){ fibMMm2 = fibMMm1; fibMMm1 = fibM; fibM = fibMMm2 + fibMMm1; } // отмечаем выбранный диапазон int offset = -1; while (fibM > 1){ // Проверяем, является ли fibMm2 допустимым местоположением int i = min(offset+fibMMm2, n-1); /* Если X больше, чем значение индекса fibMm2, исключить подмассив массива от offset to i */ if (arr[i] < x){ fibM = fibMMm1; fibMMm1 = fibMMm2; fibMMm2 = fibM - fibMMm1; offset = i; } /* Если X меньше, чем значение индекса fibMm2, исключить подмассив массива после i+1 */ else if (arr[i] > x) { fibM = fibMMm2; fibMMm1 = fibMMm1 - fibMMm2; fibMMm2 = fibM - fibMMm1; } /* Элемент найден. Возвращаем индекс */ else return i; } /* сравнение последнего элемента с x */ if(fibMMm1 && arr[offset+1]==x)return offset+1; /*Элемент не найден. Возвращаем -1 */ return -1;}
Примечание: Размерность массива не обязательно равна числу Фибоначчи. В этом случае можно легко выйти за пределы массива (необходимо делать проверку на выход из массива). Чтобы этого избежать рекомендую заполнить массив до ближайшего числа Фибоначчи максимально возможным значением.
Данный метод является достаточно трудным для восприятия, поэтому он получил меньшее распространение, чем бинарный поиск. Однако эффективность этого метода немного выше, чем у поиска по бинарному дереву, хотя так же пропорциональна Log2 (N).
Задание для самостоятельной работы: Реализовать алгоритм Фибоначчиевого поиска заданной информации в исходном массиве размерностью N (25<N<1000).
Интерполяционный поиск Рассмотрим еще один метод, имеющий хорошую теоретическую сложность. Интерполяционный поиск был предложен В. В. Петерсоном (W. W. Peterson) в 1957 году, однако корректный анализ этого метода был сделан значительно.
Как и предыдущий, этот метод предполагает, что множество хранится в массиве и массив отсортирован. Как и предыдущий метод, этот на каждом шаге своей работы сокращает область поиска. Но в отличие от предыдущего метода проба берется не в середине рассматриваемой области.
Пусть имеется область поиска (l, r). Предположим, что элементы множества – целые числа, возрастающие в арифметической прогрессии. Тогда искомый элемент должен находиться в массиве (если он вообще там есть) под индексом(Это следует из свойств арифметической прогрессии)
В этом элементе и будем брать пробу. Процедура такого поиска будет иметь следующий вид:
int interpolatingSearch (int a[], int n, int key) { //изначально устанавливаем нижний индекс на начало массива, //а верний на конец массива int lo = 0; int hi = n - 1; int mid = -1; int index = -1;
while(lo <= hi) { mid = lo + (((double)(hi - lo) / (a[hi] - a[lo])) * (key - a[lo]));
if(a[mid] == key) {index = mid; break;} else { if(a[mid] < key) { // если значение в ячейке с индексом mid меньше, то смещаем нижнюю границу lo = mid + 1; } else { //в случае, если значение больше, то смещаем верхнюю границу hi = mid - 1; } }} return index; }
Мы сделали очень большое допущение, предположив, что элементы массива представляют собой возрастающую арифметическую прогрессию. В реальности такая ситуация встречается редко. Но этот метод хорошо работает для любых пусть не идеально, но более-менее равномерно распределенных данных. Если же мы имеем дело с неравномерно распределенными данными, то интерполяционный поиск может увеличить число шагов по сравнению с дихотомическим поиском. Теоретическая сложность интерполяционного поиска – O(log(log(n))). Это, конечно, лучше, чем сложность дихотомического поиска, но эти преимущества становятся достаточно заметными лишь при очень больших значениях n. Практически на всех реальных n разница между дихотомическим и интерполяционным поиском по скорости не существенна.
Задание для самостоятельной работы: Реализовать алгоритм интерполяционного поиска заданной информации в исходном массиве размерностью N (25<N<1000).
на основе данной работы напиши код для pyton
- Assistant
Конечно! Ниже представлены реализации алгоритмов бинарного, фибоначчиева и интерполяционного поиска на языке Python.
1. Бинарный поиск
def binary_search(arr, key): l = 0 r = len(arr) - 1 while l <= r: mid = (l + r) // 2 if arr[mid] == key: return mid elif arr[mid] < key: l = mid + 1 else: r = mid - 1 return -1 # элемент не найден # Пример использования бинарного поиска arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] key = 6 result = binary_search(arr, key) print(f"Элемент {key} найден на индексе: {result}")2. Фибоначчиев поиск
def fibonacci_search(arr, x): n = len(arr) fibMMm2 = 0 # (m-2) -е число Фибоначчи fibMMm1 = 1 # (m-1) -е число Фибоначчи fibM = fibMMm2 + fibMMm1 # m-е число Фибоначчи # Находим наибольшее число Фибоначчи меньше нового размера массива while fibM < n: fibMMm2 = fibMMm1 fibMMm1 = fibM fibM = fibMMm2 + fibMMm1 offset = -1 while fibM > 1: i = min(offset + fibMMm2, n-1) if arr[i] < x: fibM = fibMMm1 fibMMm1 = fibMMm2 fibMMm2 = fibM - fibMMm1 offset = i elif arr[i] > x: fibM = fibMMm2 fibMMm1 = fibMMm1 - fibMMm2 fibMMm2 = fibM - fibMMm1 else: return i if fibMMm1 and arr[offset + 1] == x: return offset + 1 return -1 # элемент не найден # Пример использования фибоначчиева поиска arr = [1, 4, 5, 7, 9, 11, 13, 16, 18, 20, 25, 27, 30, 32, 33, 36, 39, 41, 44, 47, 51, 53, 55] x = 27 result = fibonacci_search(arr, x) print(f"Элемент {x} найден на индексе: {result}")3. Интерполяционный поиск
def interpolating_search(arr, key): lo = 0 hi = len(arr) - 1 while lo <= hi and key >= arr[lo] and key <= arr[hi]: if lo == hi: if arr[lo] == key: return lo return -1 # элемент не найден # вычисляем индекс для поиска mid = lo + ((hi - lo) // (arr[hi] - arr[lo])) * (key - arr[lo]) if arr[mid] == key: return mid elif arr[mid] < key: lo = mid + 1 else: hi = mid - 1 return -1 # элемент не найден # Пример использования интерполяционного поиска arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] key = 7 result = interpolating_search(arr, key) print(f"Элемент {key} найден на индексе: {result}")Заключение
В примерах выше представлена реализация трех алгоритмов поиска: бинарного, фибоначчиева и интерполяционного. Каждый из них ищет элемент в отсортированном массиве и возвращает его индекс или -1, если элемент не найден. Вы можете изменить массив и ключ для проверки работы алгоритмов на своих данных.