Фибоначчи Поиск в Python [с легким примером]

Поиск FIBONACCI – это еще один алгоритм деления и завоевания, который используется для поиска элемента в данном списке. В этом руководстве мы увидим, как это работает, как он отличается от бинарного поиска, и мы будем реализовать его в Python.

Предпосылки

Есть две темы, которые нам нужно сначала понять, прежде чем перейти на поиск Fibonacci.

1. Бинарный поиск

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

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

Таким образом, в каждой итерации мы сократили половину нашего списка, чтобы найти N элементов, нам нужно только журнал ₂ и итерации.

2. Фибоначчи

Числа Фибоначчи – это цифры, которые образуют серию Fibonacci. Итак, давайте сначала определим сериал Фибоначчи. Мы можем определить сериал рекурсивно, как:

F(n) = F(n-1) + F(n-2)
F(1) = 1
F(0) = 0

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

В вышеуказанном определении F (N) означает «NTH FIBONACCI номер».

Таким образом, число 0-го фибоначчи 0, число 1-го фибоначчи составляет 1, 2-й номер Fibonacci – это сумма чисел 1-й и 0-го фибоначчи, номер 3-го фибоначчи является суммой 2-го и 1-го числа фибоначчи и так далее.

Наконец, номер NTH FIBONACCI – это сумма двух чисел фибоначчи до нее, то есть сумма (N-1) Th и (N-2) чисел Фибоначчи.

Вот расчет первых 10 чисел фибоначчи.

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = 3 + 2 = 5
F(6) = 5 + 3 = 8
F(7) = 8 + 5 = 13
F(8) = 21
F(9) = 34
F(10) = 55
...

Итак, серия Fibonacci, начиная с 0-го:

F, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Реализация поиска фибоначчи в Python

Подобно бинарному поиску, поиск Fibonacci также является алгоритмом разделения и завоевания и нуждается в отсортированном списке. Он также делит список на две части, проверяет цель с элементом в центре двух частей и устраняет одну сторону на основе сравнения. Так как именно это отличается от бинарного поиска?

В поисках Fibonacci мы используем номера Фибоначчи для разделения списка на две части, поэтому он будет разделить список на две части разных длин. Кроме того, вместо того, чтобы исполнять деление, чтобы сделать это, он выполняет дополнение, которое меньше налога на ЦП. Теперь давайте погрузимся в детали.

Во-первых, нам нужно иметь длину данного списка. Затем мы находим наименьшее число фибоначчи, больше или равно размеру списка. Это означает, что если размер списка составляет 100, то наименьшее число Fibonacci больше 100 составляет 144. Давайте скажем, что это число NTH FIBONACCI. В приведенном выше примере 144 – 12-й номер фибоначчи.

После этого мы переходим в два раза в серии Фибоначчи из этого числа. По сути, мы находим (N-2) Th Fibonacci номер. Таким образом, в приведенном выше примере мы нашли 12-й номер Фибоначчи, который составляет 144, поэтому нам нужно 10-й, который составляет 55.

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

Теперь давайте погрузимся в код для этого алгоритма:

def fibonacci_search(lst, target):
    size = len(lst)
    
    start = -1
    
    f0 = 0
    f1 = 1
    f2 = 1
    while(f2 < size):
        f0 = f1
        f1 = f2
        f2 = f1 + f0
    
    
    while(f2 > 1):
        index = min(start + f0, size - 1)
        if lst[index] < target:
            f2 = f1
            f1 = f0
            f0 = f2 - f1
            start = index
        elif lst[index] > target:
            f2 = f0
            f1 = f1 - f0
            f0 = f2 - f1
        else:
            return index
    if (f1) and (lst[size - 1] == target):
        return size - 1
    return None

Теперь давайте попробуем запустить его и увидеть его вывод:

Заключение

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