Последовательность Фибоначчи в Python
В этой статье вы узнаете, как определить пользовательский тип последовательности в Python и как реализовать последовательность Фибоначчи с помощью кастомного типа Sequence.
Иногда полезно реализовать собственный тип последовательности, у которого есть функции, аналогичные встроенным функциям для кортежей или списков.
Как вы уже знаете, последовательность может быть изменяемой или неизменяемой. В этой статье мы сосредоточимся на создании пользовательского неизменяемого типа последовательности.
У неизменяемой последовательность должно быть две основные возможности:
- Возвращать количество элементов последовательности.
- Возвращать элемент по заданному индексу или вызывать ошибку 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, как сейчас. То есть вот так:
0, 1, 1, 2, 3, 5, 8 , 13, 21, ...
Но мы будем придерживаться исходной последовательности Фибоначчи, которая начинается с единицы.
Чтобы вычислить число Фибоначчи в Python, нужно создать такую рекурсивную функцию:
def fib(n):
if n < 2:
return 1
return fib(n-2) + fib(n-1)
В этой рекурсивной функции fib(1)
и fib(2)
всегда возвращают 1. А когда n
больше 2, fib(n)
= fib(n-2)
- fib(n-1)
.
Добавим print()
в начало функции, чтобы посмотреть, как она работает, и вызовем функцию fib()
с аргументом 6.
def fib(n):
print(f'Считаю {n} число Фибоначчи')
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'Считаю {n} число Фибоначчи')
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
Как это работает
- Создаем новый экземпляр последовательности Фибоначчи, в котором содержится 10 элементов.
- Получаем доступ к элементам последовательности Фибначчи с помощью квадратных скобок [].
- Используем последовательность Фибоначии в цикле for.
Добавляем поддержку срезов
Чтобы можно было делать срезы нашей последовательности, как показано ниже,
fibonacci[1:5]
... нужно добавить соответсвующую логику, которая будет обрабатывать объект среза.
В 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])
Вывод
[1, 2, 3, 5]
Что нужно запомнить
- Для создания кастомной последовательно нужно реализовать методы
__len__
и__getitem__
. - Метод
__getitem__
должен возвращать элемент по заданному индексу или вызывать ошибку IndexError, если индекс выходит за границы последовательности.