Числа фибоначчи python поиск

Последовательность Фибоначчи в Python

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

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

У неизменяемой последовательность должно быть две основные возможности:

• Возвращать количество элементов последовательности.
• Возвращать элемент по заданному индексу или вызывать ошибку IndexError, если индекс выходит за границы последовательности.

Если объект удовлетворяет вышеуказанным требованиям, получится производить следующие действия:

• Использовать синтаксис квадратных скобок [] для получения элемента по индексу.
• Перебирать элементы последовательности: например, с помощью цикла for.

Чтобы реализовать перечисленные выше возможности, нужно создать следующие методы:

• __getitem__ — возвращает элемент по заданному индексу.
• __len__ — возвращает длину последовательности.

1) Метод __getitem__

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

Диапазон значений index : от нуля до length — 1 . Если индекс выходит за границы, метод __getitem__ должен выдать исключение IndexError.

Метод __getitem__ может принимать объект среза для слайсинга.

2) The __len__ method

Если у пользовательской последовательности есть метод __len__ , вы можете использовать встроенную функцию len() , чтобы получить количество элементов последовательности.

Последовательность Фибоначчи

Последовательность Фибоначчи примерно в 1170 году открыл Леонардо Фибоначчи, итальянский математик.

В последовательности Фибоначчи каждое число является суммой двух предшествующих ему чисел. Например:

Последовательность Фибоначии можно задать следующей формулой:

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) если n > 2

В некоторые источниках сказано, что последовательность Фибоначчи начинается с нуля, а не с 1, как сейчас. То есть вот так:

Но мы будем придерживаться исходной последовательности Фибоначчи, которая начинается с единицы.

Чтобы вычислить число Фибоначчи в Python, нужно создать такую рекурсивную функцию:

В этой рекурсивной функции fib(1) и fib(2) всегда возвращают 1. А когда n больше 2, fib(n) = fib(n-2) — fib(n-1) .

Добавим print() в начало функции, чтобы посмотреть, как она работает, и вызовем функцию fib() с аргументом 6.

def fib(n): print(f'Считаю число Фибоначчи') if n < 2: return 1 return fib(n-2) + fib(n-1) fin(6)

Считаю 6 число Фибоначчи
Считаю 4 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 5 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 4 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи

Как вы видите, функция fib() часто повторяется.

Например, ей приходится трижды вычислять 3 число Фибоначчи. Это неэффективно.

Чтобы решить эту проблему, в Python есть декоратор под названием lru_cache из модуля functools .

lru_cache позволяет кэшировать результат работы функции. Когда вы передаете тот же аргумент функции, функция просто получает результат из кэша вместо того, чтобы пересчитывать его.

Ниже показано, как использовать декоратор lru_cache для ускорения работы функции fib() :

from functools import lru_cache @lru_cache def fib(n): print(f'Считаю число Фибоначчи') if n < 2: return 1 return fib(n-2) + fib(n-1) fib(6)

Считаю 6 число Фибоначчи
Считаю 4 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 5 число Фибоначчи

Как вы видите, количество вычислений значительно уменьшилось.

Создаем последовательность Фибоначии

1. Сначала определим класс, реализующий последовательность Фибоначчи:

class Fibonacci: def __init__(self, n): self.n = n

Метод __init__ принимает целое число n , которое задает длину последовательности.

2. Теперь определим статический метод, который вычисляет значение определенного числа Фибоначчи:

@staticmethod @lru_cache(2**16) def fib(n): if n < 2: return 1 return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)

3. Реализуем метод __len__ , чтобы мы могли использовать встроенную функцию len() для получения количества элементов из последовательности Фибоначчи:

def __len__(self): return self.n 

4. Реализуем метод __getitem__ для поддержки индексации с помощью синтаксиса квадратных скобок []:

def __getitem__(self, index): if isinstance(index, int): if index < 0 or index >self.n - 1: raise IndexError return Fibonacci.fib(index)

Метод __getitem__ принимает целое число index. Метод __getitem__ проверяет, является ли индекс целым числом, используя функцию isinstance() .

Если index выходит за границы последовательности, __getitem__ вызовет исключение IndexError. В противном случае он вернет число Фибоначчи индекса.

Соединим все вместе:

from functools import lru_cache class Fibonacci: def __init__(self, n): self.n = n def __len__(self): return self.n def __getitem__(self, index): if isinstance(index, int): if index < 0 or index >self.n - 1: raise IndexError return Fibonacci.fib(index) @staticmethod @lru_cache(2**16) def fib(n): if n < 2: return 1 return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)

Кастомная последовательность Фибоначчи в виде Python-класса готова. Однако вы не сможете просто сохранить этот код в модуле fibonacci.py и использовать его в другом скрипте.

Давайте разберемся, как использовать созданную последовательность.

Используем последовательность Фибоначии

Ниже показано, как использовать последовательность Фибоначчи из модуля fibonacci.py :

from fibonacci import Fibonacci fibonacci = Fibonacci(10) # используем [] print('Используем последовательность Фибоначчи с помощью []:') print(fibonacci[0]) print(fibonacci[1]) print(fibonacci[2]) print('Используем последовательность Фибоначчи с помощью цикла for:') # используем for for f in fibonacci: print(f)

Используем последовательность Фибоначии с помощью []:
1
1
2
Используем последовательность Фибоначчи с помощью цикла for:
1
1
2
3
5
8
13
21
34
55

Как это работает

1. Создаем новый экземпляр последовательности Фибоначчи, в котором содержится 10 элементов.
2. Получаем доступ к элементам последовательности Фибначчи с помощью квадратных скобок [].
3. Используем последовательность Фибоначии в цикле for.

Добавляем поддержку срезов

Чтобы можно было делать срезы нашей последовательности, как показано ниже,

. нужно добавить соответсвующую логику, которая будет обрабатывать объект среза.

В fibonacci[1:5] аргументом index метода __getitem__ является объект среза, начало которого равно 1, а конец — 5.

Вы можете использовать метод indices() объекта среза, чтобы получить индексы элементов для возврата из последовательности:

indices = index.indices(self.n)

self.n — это длина последовательности, которая будет «нарезана». В данном случае это количество элементов в последовательности Фибоначчи.

Чтобы вернуть список Фибоначчи из среза, вы можете передать индексы в функцию range() и сделать вот так:

[Fibonacci.fib(k) for k in range(*indices)] 

Соберем все вместе:

from functools import lru_cache class Fibonacci: def __init__(self, n): self.n = n def __len__(self): return self.n def __getitem__(self, index): if isinstance(index, int): if index < 0 or index >self.n - 1: raise IndexError return Fibonacci.fib(index) else: indices = index.indices(self.n) return [Fibonacci.fib(k) for k in range(*indices)] @staticmethod @lru_cache def fib(n): if n < 2: return 1 return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)

Теперь можно сделать срез последовательности следующим образом:

from fibonacci import Fibonacci fibonacci = Fibonacci(10) print(fibonacci[1:5])

Что нужно запомнить

• Для создания кастомной последовательно нужно реализовать методы __len__ и __getitem__ .
• Метод __getitem__ должен возвращать элемент по заданному индексу или вызывать ошибку IndexError, если индекс выходит за границы последовательности.

СodeСhick.io - простой и эффективный способ изучения программирования.

2023 © ООО "Алгоритмы и практика"

Источник

Числа фибоначчи python поиск

Как находить числа Фибоначчи в Python: простые способы и оптимизации

В этой статье мы рассмотрим несколько простых способов нахождения чисел Фибоначчи в Python и оптимизации для более быстрого выполнения кода.

Числа Фибоначчи - это последовательность чисел, начинающаяся с 0 и 1, где каждое последующее число равно сумме двух предыдущих.

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

Рекурсивный подход нахождения чисел Фибоначчи

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

Вот как это может выглядеть в Python:

def fibonacci_recursive(n):  if n  1:  return n else:  return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)  print(fibonacci_recursive(20)) #6765 

Этот код будет работать правильно, но может быть очень медленным при больших значениях n , так как он будет вызывать себя множество раз для каждого числа Фибоначчи. Это связано с тем, что мы вычисляем каждое число Фибоначчи несколько раз.

Итерационный подход нахождения чисел Фибоначчи

Более эффективный подход - это использование итераций для нахождения чисел Фибоначчи. В этом случае мы будем использовать цикл for для последовательного вычисления каждого числа Фибоначчи от 0 до n .

Вот как это может выглядеть в Python:

def fibonacci_iterative(n):  if n  1:  return n else:  fib_prev, fib_current = 0, 1  for i in range(2, n+1):  fib_next = fib_prev + fib_current fib_prev, fib_current = fib_current, fib_next return fib_current print(fibonacci_iterative(20)) #6765 

Использование формулы Бине для нахождения чисел Фибоначчи

Еще более эффективный способ нахождения чисел Фибоначчи - это использование формулы Бине. Формула Бине позволяет вычислить любое число Фибоначчи за O(1) времени.

Для использования формулы Бине, нам нужно знать золотое сечение и его сопряженное число, которые можно выразить следующим образом:

φ = (1 + sqrt(5)) / 2 ψ = (1 - sqrt(5)) / 2

Затем, мы можем использовать формулу Бине, чтобы вычислить n-ое число Фибоначчи следующим образом:

Вот как это может выглядеть в Python:

from math import sqrt def fibonacci_binet(n):  phi = (1 + sqrt(5)) / 2  psi = (1 - sqrt(5)) / 2  return int((phi**n - psi**n) / sqrt(5))  print(fibonacci_binet(20)) #6765 

Обратите внимание, что мы используем функцию sqrt() из модуля math для вычисления квадратного корня.

Оптимизации для итерационного подхода

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

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

Мы можем использовать формулу Бине для нахождения только одного числа Фибоначчи, если нам не нужно вычислять последовательность чисел.

Вот как это может выглядеть в Python:

from math import sqrt fib_dict = 0: 0, 1: 1>  def fibonacci_dp(n):  if n not in fib_dict:  fib_dict[n] = fibonacci_dp(n-1) + fibonacci_dp(n-2)  return fib_dict[n]  def fibonacci_binet_single(n):  phi = (1 + sqrt(5)) / 2  psi = (1 - sqrt(5)) / 2  return int((phi**n - psi**n) / sqrt(5))  print(fibonacci_binet_single(20)) #6765 print(fibonacci_dp(20)) #6765 

Эти оптимизации помогут ускорить выполнение кода, особенно при больших значениях n .

Заключение по нахождению чисел Фибоначчи в Python

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

Выбор подхода зависит от конкретных требований задачи и необходимой производительности. Оптимизации могут помочь ускорить выполнение кода, особенно при больших значениях n.

Источник