Sequência de Fibonacci em Python

Resumo : neste tutorial, você aprenderá como definir um tipo de sequência personalizado em Python e como implementar a sequência de Fibonacci usando um tipo de sequência personalizado.

Introdução ao tipo de sequência personalizado em Python

Às vezes, é útil implementar um tipo de sequência personalizado que tenha funções semelhantes ao tipo de sequência integrado, como tuples e lists .

Como você aprendeu até agora, uma sequência pode ser mutável ou imutável . Neste tutorial, você se concentrará na definição de um tipo de sequência imutável personalizado.

Basicamente, um tipo de sequência imutável deve suportar duas funções principais:

• Retorne o número de elementos da sequência. Tecnicamente, este requisito não é necessário.
• Retorne um elemento em um determinado índice ou aumente IndexErrorse o índice estiver fora dos limites.

Se um objeto puder atender aos requisitos acima, você poderá:

• Use a sintaxe de colchetes []para recuperar um elemento por um índice.
• Itere sobre os elementos da sequência usando o loop for, compreensão, etc.

Tecnicamente, um tipo de sequência personalizada precisa implementar os seguintes métodos:

• __getitem__– retorna um elemento em um determinado índice.
• __len__– retorna o comprimento da sequência.

1) O __getitem__método

O __getitem__método possui o indexargumento que é um número inteiro. O ___getitem__deve retornar um elemento da sequência com base no arquivo index.

O intervalo do indexdeve ser de zeroa length - 1. Se indexestiver fora dos limites, o __getitem__método deverá gerar uma IndexErrorexceção.

Além disso, o __getitem__método pode aceitar um objeto de fatia para suportar o fatiamento.

2) O __len__método

Se uma sequência personalizada tiver o __len__método, você poderá usar a função integrada lenpara obter o número de elementos da sequência.

Introdução à sequência de Fibonacci

A sequência de Fibonacci foi descoberta pela primeira vez por Leonardo Fibonacci, um matemático italiano, por volta de 1170 DC.

Na sequência de Fibonacci, cada número é a soma de dois números que o precedem. Por exemplo:

1, 1, 2, 3, 5, 8 , 13, 21, ...

A fórmula a seguir descreve a sequência de Fibonacci:

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) if n > 2

Algumas fontes afirmam que a sequência de Fibonacci começa em zero, e não em 1 assim:

0, 1, 1, 2, 3, 5, 8 , 13, 21, ...

Mas ficaremos com a sequência original de Fibonacci que começa em um.

Para calcular um número de Fibonacci em Python, você define uma função recursiva da seguinte forma:

def fib(n):
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1) Linguagem de código:  Python  ( python )

Nesta função recursiva, o fib(1)e fib(2)sempre retorna 1. E quando n é maior que 2, o fib(n) = fib(n-2) – fib(n-1)

O seguinte adiciona uma instrução no início da fibfunção para fins de depuração de registro:

def fib(n):
    print(f'Calculate Fibonacci of {n}')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)Linguagem de código:  Python  ( python )

E isso mostra a saída da fibfunção ao calcular o Fibonacci de 6:

Calculate the Fibonacci of 6
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 5
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1

Conforme mostrado claramente na saída, a fibfunção tem muitas repetições.

Por exemplo, tem que calcular o Fibonacci de 3 três vezes. Isso não é eficiente.

Para resolver isso, Python fornece um decorador chamado lru_cachea partir do functoolsmódulo.

O lru_cachepermite armazenar em cache o resultado de uma função. Quando você passa o mesmo argumento para a função, a função apenas obtém o resultado do cache em vez de recalculá-lo.

A seguir mostramos como usar o lru_cachedecorador para acelerar a fibfunção:

from functools import lru_cache


@lru_cache
def fib(n):
    print(f'Calculate the Fibonacci of {n}')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)


fib(6)Linguagem de código:  Python  ( python )

Saída:

Calculate the Fibonacci of 6
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 5    

Conforme mostrado claramente na saída, o número de cálculos é reduzido significativamente.

Exemplo de sequência Python Fibonacci

Primeiro, defina uma classe que implemente a sequência de Fibonacci:

class Fibonacci:
    def __init__(self, n):
        self.n = nLinguagem de código:  Python  ( python )

O __init__método aceita um número inteiro nque especifica o comprimento da sequência.

Segundo, defina um método estático que calcule um número de Fibonacci de um inteiro:

@staticmethod
@lru_cache(2**16)
def fib(n):
    if n < 2:
        return 1
    return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)Linguagem de código:  Python  ( python )

Terceiro, implemente o __len__método para que você possa usar a função integrada lenpara obter o número de elementos da sequência de Fibonacci:

def __len__(self):
    return self.n Linguagem de código:  Python  ( python )

Por fim, implemente o __getitem__método para suportar a indexação por meio da sintaxe de colchetes:

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

        return Fibonacci.fib(index)Linguagem de código:  Python  ( python )

O __getitem__método aceita um indexque é um número inteiro. O __getitem__verifica se indexé um número inteiro usando a isinstancefunção.

O __getitem__método gera a IndexErrorexceção se indexestiver fora dos limites. Caso contrário, ele retorna o número de Fibonacci do arquivo index.

Juntando tudo.

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)Linguagem de código:  Python  ( python )

Não, você pode salvar a classe Fibonacci no fibonacci.pymódulo e usá-la em um novo script.

Usando a sequência de Fibonacci

O seguinte mostra como usar a sequência de Fibonacci do fibonaccimódulo:

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)

# access elements via indices
print('Accessing Fibonacci sequence using []:')
print(fibonacci[0])
print(fibonacci[1])
print(fibonacci[2])

print('Accessing Fibonacci sequence using for loop:')
# using for loop
for f in fibonacci:
    print(f)Linguagem de código:  Python  ( python )

Saída:

Accessing Fibonacci sequence using []:
1
1
2
Accessing Fibonacci sequence using for loop:
1
1
2
3
5
8
13
21
34
55Linguagem de código:  CSS  ( css )

Como funciona.

• Primeiro, crie uma nova instância da Fibonaccisequência que contém 10 elementos.
• Segundo, acesse os elementos da sequência de Fibonacci usando colchetes [].
• Terceiro, use a sequência de Fibonacci em um loop for .

Adicionando suporte para fatiamento

Para apoiar o fatiamento assim:

fibonacci[1:5]Linguagem de código:  CSS  ( css )

…você precisa adicionar uma lógica para lidar com o sliceobjeto.

No fibonacci[1:5], o indexargumento do __getitem__método é um sliceobjeto cujo startvalor é 1 e stopé 5.

E você pode usar o indicesmétodo do sliceobjeto para obter os índices dos elementos que retornarão da sequência:

indices = index.indices(self.n)Linguagem de código:  Python  ( python )

O self.né o comprimento da sequência que será fatiada. Neste caso, é o número de elementos da sequência de Fibonacci.

Para retornar uma lista de Fibonacci da fatia, você pode passar os índices para rangefuncionar e usar a compreensão da lista da seguinte forma:

[Fibonacci.fib(k) for k in range(*indices)]Linguagem de código:  Python  ( python )

A seguir mostramos a nova versão da sequência de Fibonacci que suporta fatiamento:

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)Linguagem de código:  Python  ( python )

Agora, você pode dividir a sequência de Fibonacci da seguinte forma:

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)
print(fibonacci[1:5])Linguagem de código:  Python  ( python )

Saída:

[1, 2, 3, 5]Linguagem de código:  JSON/JSON com comentários  ( json )

Resumo

• Implemente o método __len__and __getitem__para definir uma sequência personalizada.
• O __getitem__método precisa retornar um elemento baseado em um determinado índice ou gerar um IndexError se o índice estiver fora dos limites.