curso
Sequência de Fibonacci em Python: Aprenda e explore técnicas de codificação
A sequência de Fibonacci é uma maneira divertida de continuar praticando Python. Neste artigo, você aprenderá a implementar a sequência de Fibonacci no Python usando diferentes técnicas do Python, desde escrever funções eficientes e lidar com recursão até usar princípios orientados a objetos para obter soluções mais otimizadas.
Quando você terminar o curso, faça o curso Writing Functions in Python para reforçar conceitos como escopo e tratamento de erros, ou experimente o curso Intermediate Object-Oriented Programming in Python para aprender sobre herança e classes de base. Agora, vamos experimentar a sequência de Fibonacci.
O que é a sequência de Fibonacci?
A sequência de Fibonacci é um conceito matemático que aparece em muitas áreas da ciência e da natureza. É uma série de números em que cada número é a soma dos dois anteriores, começando com 0 e 1. Esse padrão forma a base para aplicações em áreas como ciência da computação e finanças.
Dois aspectos principais definem a sequência de Fibonacci: a estrutura recursiva da sequência e sua relação com a proporção áurea.
Natureza recursiva da sequência de Fibonacci
A sequência de Fibonacci começa com 0 e 1. Cada novo número é a soma dos dois números anteriores a ele. Por exemplo:
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
E assim por diante.
Matematicamente, escrevemos isso como F(n) = F(n-1) + F(n-2)
. A sequência se constrói adicionando repetidamente os dois últimos números. Os dois primeiros números, 0 e 1, são o ponto de partida ou casos de base. Sem isso, a sequência não funcionaria.
Esse padrão recursivo serve como base para alguns algoritmos da ciência da computação. Por exemplo, a recursão na programação trabalha com essa sequência ao resolver problemas como a geração de números de Fibonacci ou a divisão de tarefas em partes menores e gerenciáveis.
Conexão de proporção áurea
A sequência de Fibonacci está intimamente ligada à proporção áurea, que é um número irracional representado por φ
(seu valor é aproximadamente 1,618). Se você dividir um número de Fibonacci pelo número anterior, a proporção se aproximará cada vez mais de φ
. Por exemplo:
5 ÷ 3 ≈ 1.666
8 ÷ 5 ≈ 1.6
13 ÷ 8 ≈ 1.625
Quanto mais você avança, mais se aproxima de 1,618. Isso não é uma coincidência - a proporção aparece naturalmente na sequência de Fibonacci devido à forma como os números crescem.
Euclides o descreveu pela primeira vez na Grécia antiga como a razão extrema e média. Desde então, ela tem sido associada a padrões na natureza, como as espirais em conchas e flores, bem como na arte e na arquitetura.
Proporção áurea na arte. Fonte
Aplicações práticas da sequência de Fibonacci
A sequência de Fibonacci aparece de forma surpreendente em muitos campos. Vamos nos concentrar em duas de suas aplicações mais notáveis: seus padrões na natureza e seu uso na ciência da computação.
Fibonacci na natureza
Você pode ver a sequência de Fibonacci em toda a natureza. Observe as flores - o número de pétalas geralmente corresponde aos números de Fibonacci. Por exemplo, as margaridas podem ter 34, 55 ou 89 pétalas, e os lírios geralmente têm 3, 5 ou 8. Esses padrões ajudam as plantas a crescer de forma a maximizar a luz solar e a chuva.
As espirais nas pinhas e nos girassóis também seguem os números de Fibonacci. A disposição das sementes em um girassol, por exemplo, corresponde à sequência. É fascinante como algo tão simples como somar dois números pode descrever grande parte do mundo natural.
Fibonacci na ciência da computação
A sequência de Fibonacci também desempenha um papel fundamental em algoritmos e estruturas de dados. Por exemplo, os números de Fibonacci são usados em algoritmos de pesquisa para dividir os problemas em partes menores de forma eficiente. A sequência está até mesmo por trás das pilhas de Fibonacci, um tipo de estrutura de dados usada para acelerar determinadas operações, como encontrar o caminho mais curto em uma rede.
Aqui está um exemplo simples de como você pode gerar uma sequência de Fibonacci em Python:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# Example usage
for i in range(10):
print(fibonacci(i), end=" ")
0 1 1 2 3 5 8 13 21 34
Essa função recursiva mostra como a sequência de Fibonacci é construída. Embora a recursão seja fácil de entender, há também versões otimizadas, como a programação dinâmica, para calcular os números de Fibonacci com muito mais rapidez.
Na criptografia, os números de Fibonacci podem ajudar a gerar chaves seguras. E na inteligência artificial, eles otimizam as redes neurais para melhorar a forma como os algoritmos aprendem e se adaptam.
Outros exemplos comuns
Aqui estão mais alguns exemplos de como essa sequência aparece na vida cotidiana e em campos especializados:
- Em Art: A sequência de Fibonacci tem sido usada por artistas e arquitetos há séculos. Estruturas famosas, como o Parthenon, apresentam essas proporções porque são naturalmente agradáveis aos olhos.
- Na música: Os compositores usam os números de Fibonacci para criar ritmos e melodias. Por exemplo, eles atribuem notas inteiras a 1, meias notas a 2 e quartos de notas a 3 para criar padrões harmoniosos.
- Na negociação: Os operadores de ações aplicam os números de Fibonacci para analisar as tendências do mercado. Eles os utilizam para prever os possíveis níveis de preços em que as ações podem reverter, ajudando-os a decidir quando comprar ou vender.
- Em Física: Na física quântica, os padrões de Fibonacci foram observados nas interações e no comportamento das partículas, revelando como essas sequências aparecem mesmo nas menores escalas da natureza.
Implementando a sequência de Fibonacci em Python
Como o Python oferece várias maneiras de gerar a sequência de Fibonacci, discuti as mais comumente usadas passo a passo com exemplos.
Usando um método iterativo
O método iterativo é uma das maneiras mais simples de gerar a sequência de Fibonacci. Ele usa um loop para calcular cada termo da sequência, o que o torna mais eficiente em termos de memória do que os métodos recursivos. Veja como isso funciona:
Defino duas variáveis, a
e b
, como 0
e 1
. Eles representam os dois primeiros números da sequência. Em seguida, uso um loop for
para calcular os próximos números. Atualizo a
para manter o valor de b
, e b
se torna a soma dos anteriores a
e b
.
Aqui está um código Python para isso:
n = 10
a, b = 0, 1
for i in range(n):
print(a)
a, b = b, a + b
0
1
1
2
3
5
8
13
21
34
Se você quiser usar um loop while
em vez de um loop for
, veja como escrever o código:
# Number of terms to print in the Fibonacci series
n = 10
# Initialize the first two terms
a, b = 0, 1
i = 0
while i < n:
print(a, end=' ')
# Update the terms
a, b = b, a + b
i += 1
0 1 1 2 3 5 8 13 21 34
Ambos os métodos são muito fáceis de entender, o que os torna perfeitos para iniciantes.
Usando um método recursivo
O método recursivo é outra maneira de gerar números de Fibonacci. Não é tão rápido quanto o método iterativo para sequências maiores, mas é uma ótima maneira de entender a lógica por trás da construção da sequência.
Por exemplo, eu crio uma função chamada fibonacci_recursive
. Essa função recebe um número n
como entrada. Se n
for 0
ou 1
, a função retornará n
. Esses são os casos básicos que informam à recursão quando você deve parar. Para qualquer outro número, a função chama a si mesma para calcular os dois números anteriores e os soma.
Aqui está o código para isso:
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)
num_terms = 10
for i in range(num_terms):
print(fibonacci_recursive(i), end=" ")
0 1 1 2 3 5 8 13 21 34
Esse método funciona bem para sequências pequenas, mas pode ficar lento à medida que a sequência cresce, pois recalcula os mesmos valores várias vezes.
Usando um método recursivo otimizado com armazenamento em cache
Para corrigir a ineficiência da recursão simples, costumo usar o cache. O site lru_cache
do Python armazena valores calculados anteriormente para que a função não precise refazer o trabalho.
Veja como eu faço isso:
from functools import lru_cache
@lru_cache(maxsize = None)
def fib_cache(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib_cache(n-1) + fib_cache(n-2)
print(f"The Fibonacci Number is {fib_cache(10)}")
The Fibonacci Number is 55.
Essa abordagem combina a clareza da recursão com a eficiência do armazenamento em cache.
Maneiras mais avançadas de fazer a sequência de Fibonacci em Python
Se você estiver procurando outras maneiras de calcular os números de Fibonacci, aqui estão algumas técnicas mais avançadas:
Exponenciação de matriz
A exponenciação da matriz é uma das maneiras mais eficientes de calcular os números de Fibonacci para valores grandes de n
. Em vez de recalcular os termos repetidamente, esse método usa a multiplicação de matrizes para obter resultados em tempo logarítmico.
Veja como implementei isso no Python:
import numpy as np
def fibonacci_matrix(n):
def matrix_power(matrix, power):
return np.linalg.matrix_power(matrix, power)
if n == 0:
return 0
matrix = np.array([[1, 1], [1, 0]])
result = matrix_power(matrix, n-1)
return result[0][0]
for i in range(10):
print(fibonacci_matrix(i) , end=" ")
0 1 1 2 3 5 8 13 21 34
Nesse código, se n
for 0
, você retornará 0
como o caso base. Para outros valores, a matriz é elevada à potência (n-1)
usando a função matrix_power
do numpy. O número de Fibonacci na posição n
é encontrado no elemento superior esquerdo da matriz resultante.
Fórmula de Binet
A fórmula de Binet calcula diretamente o número nth
de Fibonacci sem iteração ou recursão. Ele se baseia na proporção áurea, φ
, e usa uma expressão matemática para calcular o resultado instantaneamente.
A fórmula é:
Onde:
- φ = (1 + √5) / 2, a proporção áurea.
- 1 - φ é o conjugado de φ.
Aqui está o código Python para a fórmula de Binet:
import math
def fibonacci_binet(n):
phi = (1 + math.sqrt(5)) / 2
return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))
# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f" The Fibonacci Number of {n}th term is {result}" )
The Fibonacci number of 10th term is 55
Nesse código, a função fibonacci_binet(n)
calcula o número nth
de Fibonacci usando a fórmula de Binet. Dentro da função, eu calculo phi (a proporção áurea) como (1 + math.sqrt(5)) / 2
, usando math.sqrt()
para a raiz quadrada de 5. A fórmula (phi ** n - (1 - phi) ** n) / math.sqrt(5)
é então aplicada para que você encontre diretamente o número nth
de Fibonacci. Em seguida, uso a função round()
para lidar com pequenas imprecisões de ponto flutuante.
Matrizes
Você pode até mesmo usar matrizes para gerar e armazenar toda a sequência de Fibonacci. Isso é útil quando você precisa de vários termos simultaneamente.
Aqui está o código para isso:
def fibonacci(n):
if n <= 0:
return "Incorrect Output"
data = [0, 1] # Initialize list with first two Fibonacci terms: 0 and 1
if n > 2:
for i in range(2, n): # Start loop from the third term
data.append(data[i-1] + data[i-2]) # Calculate next term as sum of previous two
return data[n-1] # Return the nth term
print(f"Fibonacci Number: {fibonacci(10)}")
Fibonacci number: 34
Retrocesso
Backtracking é outra opção que eu poderia usar, especialmente quando quero combinar recursão com memoização para melhorar o desempenho.
Aqui está o código para isso:
def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
if n in computed:
return computed[n]
computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
return computed[n]
n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")
The 10th Fibonacci term is 55
Complexidade dos algoritmos de Fibonacci em Python
Já passamos por vários exemplos! Vejamos agora suas diferenças em termos de complexidade de tempo e espaço. Como mencionamos, alguns métodos do são rápidos, mas usam mais memória, enquanto outros são mais lentos, mas precisam de menos espaço. Preparei esta tabela para comparar a eficiência de cada abordagem.
Método | Complexidade de tempo | Complexidade espacial |
---|---|---|
Iterativo (For Loop) | O(n) | O(1) |
Iterativo (While Loop) | O(n) | O(1) |
Recursão simples | O(2ⁿ) | O(n) |
Memoização/Cache | O(n) | O(n) |
Baseado em matriz | O(n) | O(n) |
Método de retrocesso | O(2ⁿ) | O(2ⁿ) |
Exponenciação de matrizes | O(log n) | O(log n) |
Na tabela acima, você verá o que significa cada complexidade de tempo e espaço:
-
O(n): O algoritmo itera pela sequência uma vez, executando um número fixo de operações para cada elemento. O tempo necessário cresce linearmente com o tamanho da entrada
n
. -
O(1): O número de Fibonacci é calculado usando um número fixo de operações sem iteração ou recursão.
-
O(2n): O algoritmo faz duas chamadas recursivas para cada entrada, o que leva a um crescimento exponencial no número de chamadas de função à medida que
n
aumenta. -
O(log n): O tempo de execução aumenta proporcionalmente ao logaritmo do tamanho da entrada
n
.
-
O(n): O algoritmo usa memória que cresce diretamente com o número de entradas
n
. Aqui, cada elemento requer uma quantidade fixa de espaço. -
O(1): O uso da memória permanece constante, independentemente do tamanho da entrada.
-
O(2n): Ele usa espaço exponencial devido à criação de novos estados para cada ramo.
-
O(log n): As multiplicações de matrizes intermediárias usam memória logarítmica.
Considerações finais
Como você viu, no Python, é possível calcular os números de Fibonacci usando muitos métodos diferentes, desde loops simples até técnicas avançadas, como exponenciação de matriz e fórmula de Binet. Cada método tem seus pontos fortes e desvantagens.
Espero que você tenha aprendido algo sobre a sequência de Fibonacci e também sobre programação em Python. Se você quiser saber mais sobre Python e tópicos relacionados, confira nosso curso Introduction to Python. Você também pode experimentar nossa carreira completa de desenvolvedor Python e aprender técnicas de programação e até mesmo começar a desenvolver seus próprios pacotes!
Sou um estrategista de conteúdo que adora simplificar tópicos complexos. Ajudei empresas como Splunk, Hackernoon e Tiiny Host a criar conteúdo envolvente e informativo para seus públicos.
Perguntas frequentes sobre a sequência de Fibonacci em Python
Para que é usada a sequência de Fibonacci?
A sequência de Fibonacci é usada em vários campos, como matemática, ciência da computação e estudos da natureza, para modelar padrões de crescimento e otimizar algoritmos.
Como a sequência de Fibonacci é calculada?
A sequência de Fibonacci é calculada pela adição dos dois números anteriores para obter o próximo número, começando com 0 e 1.
Quais são os exemplos da sequência de Fibonacci na natureza?
Os exemplos incluem a disposição das folhas em um caule, a ramificação das árvores e o padrão de várias frutas e flores.
Como você implementa a sequência de Fibonacci em Python?
Você pode implementá-lo usando uma abordagem iterativa ou recursiva, com exemplos de código Python disponíveis em muitos tutoriais de programação.
Qual é a fórmula para o n-ésimo termo da sequência de Fibonacci?
O n-ésimo termo pode ser calculado usando a fórmula de Binet, que envolve a proporção áurea e fornece um método de cálculo direto.
Aprenda Python com o DataCamp
curso
Intermediate Object-Oriented Programming in Python
curso
Python Toolbox

blog
5 desafios Python para desenvolver suas habilidades

DataCamp Team
5 min
tutorial
Tutorial de funções Python
tutorial
Tutorial de strings em Python
tutorial
Tutorial do For Loops em Python
tutorial
Tutorial de iteradores e geradores Python
tutorial