© Sashkin/Shutterstock.com
A sequência de Fibonacci é sem dúvida uma das sequências matemáticas mais famosas de todos os tempos. Matemáticos e cientistas vêm usando essa sequência há séculos na matemática e na ciência, nomeando-a em homenagem ao famoso matemático italiano da Idade Média, Fibonacci.
A sequência de Fibonacci é uma série de números em que cada número subsequente é a soma dos dois anteriores, começando em 0 e 1. A sequência geralmente é denotada por Fn e tem a seguinte aparência: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 e assim por diante.
Mas qual é o problema? Por que devemos nos preocupar com a sequência de Fibonacci? Bem, acontece que essa sequência não é apenas uma série arbitrária de números.
A sequência de Fibonacci é encontrada em toda a natureza e em muitas áreas da ciência, e tem aplicações importantes em ciência da computação e programação. O significado da série na ciência da computação decorre dos vários algoritmos que podem gerar seus números.
Linguagens de programação como Python têm funções incorporadas para gerar a sequência de Fibonacci. Se você estiver interessado em entender os algoritmos por trás dessas funções, fique por aqui, pois este artigo explicará alguns dos 7 principais algoritmos e métodos usados para gerar os números de Fibonacci.
Diferentes métodos de criação de programas para números de Fibonacci
Existem vários métodos/abordagens para gerar números de Fibonacci, cada um com diferentes complexidades de tempo e espaço. A maneira mais direta de encontrar o n-ésimo número de Fibonacci é usar a recursão.
No entanto, esta abordagem não é muito eficiente e pode levar a muitos cálculos redundantes. Iremos, portanto, explorar a recursão juntamente com outros métodos para ver qual(is) pode(m) ser considerado(s) o(s) mais eficiente(s).
Recursão
A recursão é um método de resolver um problema onde o solução depende das soluções para instâncias menores do mesmo problema. No contexto da sequência de Fibonacci, a solução recursiva funciona dividindo o problema de encontrar o n-ésimo número de Fibonacci em dois problemas menores: encontrar o (n-1)º número de Fibonacci e encontrar o (n-2)º número de Fibonacci.
Este processo continua recursivamente até que o caso base seja alcançado, onde n é 0 ou 1. O caso base representa a condição que a função deve satisfazer para parar de chamar a si mesma. Uma vez atendida, a função simplesmente retorna n. Para todos os outros valores de n, a função chama a si mesma recursivamente, passando n-1 e n-2 como argumentos/parâmetros.
O exemplo a seguir mostra um programa Python simples que implementa recursão para gerar números de Fibonacci:
def fibonacci(n):
if n=1: # caso base
retorne n
caso contrário:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # Output: 13
A função primeiro verifica o caso base sobre o qual retorna n. Se n for maior que 1, a função chama a si mesma recursivamente com n-1 e n-2 como argumentos e adiciona seus valores de retorno juntos. Isso ocorre porque o n-ésimo número em uma sequência de Fibonacci é igual à soma dos (n-1)-ésimo e (n-2)-ésimo número na sequência.
As chamadas recursivas continuam até que o caso base seja alcançado e a função retorne o n-ésimo número na sequência. Podemos obter a complexidade de tempo da solução recursiva — é exponencial sendo O(2n), já que a função chama a si mesma duas vezes para cada valor de n.
Isso pode rapidamente se tornar ineficiente à medida que n cresce, tornando esse método impraticável para valores maiores de n. A complexidade do espaço é O(n), que é linear, pois a profundidade máxima da árvore de recursão é n.
Iteração
A iteração é uma abordagem mais eficiente para resolver a sequência de Fibonacci problema. A abordagem iterativa envolve resolver um problema executando repetidamente um conjunto de instruções até que uma condição específica seja atendida.
No contexto da sequência de Fibonacci, a solução iterativa funciona começando com os dois primeiros números de Fibonacci e calculando o próximo número de Fibonacci usando os dois anteriores. Esse processo continua até que o n-ésimo número de Fibonacci seja calculado.
A sequência de Fibonacci apareceu pela primeira vez no manuscrito latino “Liber Abaci” (1202), onde foi usada para calcular o crescimento das populações de coelhos.
©TippaPatt/Shutterstock.com
Podemos implementar um programa simples usando iteração para criar números de Fibonacci da seguinte maneira:
def fibonacci(n):
if n==0:
retorna 0
elif n==1:
retorna 1
else:
fib1, fib2=0, 1
para i no intervalo (2, n+1):
fib=fib1 + fib2
fib1, fib2=fib2, fib
retorno fib2
Aqui, estamos usando um loop para calcular o n-ésimo número de Fibonacci em tempo linear. Conseguimos isso começando com os dois primeiros números da sequência (0 e 1) e computando iterativamente o próximo número como a soma dos dois anteriores.
Nós acompanhamos os dois números anteriores em variáveis e os atualizamos a cada iteração. Após n iterações, retornamos o n-ésimo número.
A complexidade de tempo da solução iterativa é O(n), que é linear. Isso ocorre porque o loop for é executado n-1 vezes para calcular o enésimo número de Fibonacci. Como a função usa apenas um número constante de variáveis para calcular o n-ésimo número de Fibonacci, sua complexidade de espaço é O(1), que é constante.
Memoização
Memoização é um método de resolver um problema armazenando os resultados de chamadas de função caras e retornando o resultado armazenado em cache quando as mesmas entradas ocorrerem novamente.
No contexto da sequência de Fibonacci, a solução de memoização funciona armazenando as soluções para subproblemas e retornando o resultado em cache, se disponível.
Desta forma, o programa calcula a solução para cada subproblema apenas uma vez e o reutiliza quando necessário.
Aqui está um exemplo de implementação de memorização:
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
elif n=1:
return n
else:
memo[n]=fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
Este exemplo usa um top-down para calcular o n-ésimo número de Fibonacci armazenando em cache os valores calculados anteriormente para evitar cálculos redundantes. A função primeiro verifica se já calculou e armazenou em cache o valor do n-ésimo número de Fibonacci em um dicionário Python. Se tiver, ele retorna o valor armazenado em cache.
Caso contrário, ele calcula o valor recursivamente como a soma dos (n-1)-ésimo e (n-2)-ésimo número de Fibonacci, armazena em cache o valor calculado no dicionário e retorna.
A complexidade de tempo da solução de memoização é O(n), que é linear. Isso ocorre porque o programa calcula cada número de Fibonacci apenas uma vez e o armazena no dicionário de memorando para uso futuro. A complexidade do espaço também é O(n), que é linear, pois o dicionário memo armazena soluções para subproblemas até n.
Programação dinâmica
A programação dinâmica é um método de resolver um problema dividindo-o em subproblemas menores e armazenando as soluções para esses subproblemas para evitar cálculos redundantes.
No contexto da sequência de Fibonacci, a solução de programação dinâmica funciona calculando os números de Fibonacci de maneira ascendente e armazenando as soluções em uma matriz. Dessa forma, a solução para cada subproblema é computada apenas uma vez e reutilizada quando necessário.
Considere o seguinte exemplo:
def fibonacci(n):
fib=[0, 1]
para i no intervalo(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
A função usa uma lista Python para armazenar os valores calculados da sequência, começando com os dois primeiros valores. Em seguida, itera de 2 a n, calculando o i-ésimo valor como a soma dos (i-1)-ésimo e (i-2)-ésimo valor e armazenando-o na lista. Por fim, ele retorna o n-ésimo valor da lista.
A complexidade de tempo da solução de programação dinâmica é O(n), que é linear. A complexidade de tempo do algoritmo é O(n) porque o loop for calcula o n-ésimo número de Fibonacci executando n-1 vezes, e cada cálculo leva um tempo constante.
Além disso, a complexidade espacial do algoritmo é O(n) porque ele usa uma lista de tamanho n para armazenar as soluções dos subproblemas.
Exponenciação de matrizes
A exponenciação de matrizes é um método de resolver um problema elevando uma matriz a uma potência. No contexto da sequência de Fibonacci, a solução de exponenciação de matrizes funciona usando uma matriz com números de Fibonacci para aumentá-la à potência de n-1 para obter o n-ésimo número de Fibonacci.
podemos usar a exponenciação de matrizes para crie um programa Python para números de Fibonacci, como mostrado:
import numpy as np
def fibonacci(n):
F=np.array([[ 1, 1], [1, 0]])
return np.linalg.matrix_power(F, n-1)[0, 0]
Neste exemplo, Estamos usando uma técnica de exponenciação de matrizes para calcular o n-ésimo número de Fibonacci em tempo logarítmico. Para conseguir isso, elevamos uma matriz 2 × 2 à potência de n-1 e a multiplicamos pelo vetor de estado inicial [0, 1]. A matriz resultante contém o n-ésimo e (n+1)-ésimo número de Fibonacci, e retornamos o n-ésimo número.
A complexidade de tempo da solução de exponenciação da matriz é O(log n), que é, obviamente, logarítmico. O algoritmo de divisão e conquista usado na multiplicação de matrizes reduz o número de multiplicações necessárias. Portanto, a complexidade do espaço é O(1), que é constante, pois apenas uma quantidade constante de memória é usada.
Fórmula de Binet
A fórmula de Binet é uma fórmula direta para calcular o enésimo número de Fibonacci sem ter que calcular todos os números de Fibonacci anteriores.
A fórmula geralmente é escrita como: Fn=round((Φ^n – (1-Φ)^n)/√5), onde Φ (phi) é a proporção áurea.
A fórmula de Binet sugere que a proporção de dois números de Fibonacci consecutivos tende para a proporção áurea à medida que n aumenta.
©TippaPatt/Shutterstock.com
No contexto da sequência de Fibonacci, a fórmula de Binet funciona usando a proporção áurea, que é (1 + √5)/2, e seu conjugado, que é 1 – √5)/2.
Um exemplo em Python seria:
def fibonacci(n):
golden_ratio=(1 + 5**0,5)/2
return round((golden_ratio**n – (1 – golden_ratio)**n)/5**0,5 )
A função primeiro define a proporção áurea. Em seguida, calculamos o n-ésimo termo usando a fórmula de Binet e retornamos o valor inteiro arredondado do resultado.
Esta implementação da fórmula de Binet é computacionalmente eficiente porque requer apenas algumas operações aritméticas simples para calcular qualquer termo da sequência de Fibonacci, sem a necessidade de calcular todos os termos anteriores.
Isso é comprovado pela complexidade de tempo da fórmula de Binet é O(1), que é constante. Isso ocorre porque a fórmula requer apenas algumas operações aritméticas para calcular o enésimo número de Fibonacci. A complexidade do espaço é O(1), que é constante, porque o programa usa apenas algumas variáveis para calcular o n-ésimo número de Fibonacci.
Algoritmo Guloso
O algoritmo guloso é uma técnica usados para resolver problemas de otimização. Ele funciona tomando a melhor decisão em cada etapa e esperando que as decisões tomadas levem a uma solução ótima. Esse algoritmo segue a estratégia “gananciosa” de sempre escolher o maior número possível em cada etapa.
Pode-se gerar números de Fibonacci usando essa abordagem, começando com os dois casos básicos e, em seguida, iterando pela série para encontrar o próximo número.
Primeiro, salve os dois números anteriores em duas variáveis e, em seguida, adicione-os para obter o próximo número de Fibonacci. Este processo continua até que o n-ésimo número da sequência seja gerado.
Podemos implementar um programa para números de Fibonacci usando o algoritmo Greedy de forma simples, como segue:
def fibonacci(n):
se n=1:
retornar n
anterior, atual=0, 1
para i em range(2, n+1):
prev, curr=curr, prev + curr
return curr
Primeiro verificamos se n satisfaz o caso base , caso em que retornamos o valor apropriado. Caso contrário, criamos uma lista para armazenar os dois últimos números de Fibonacci (0 e 1) e, em seguida, usamos um loop para gerar os próximos números na sequência adicionando os dois últimos números da lista. O loop continua até que o n-ésimo número na sequência seja gerado, ponto em que o retornamos.
A complexidade de tempo do Algoritmo Greedy é O(n), que é linear, como precisamos iterar n vezes para gerar o n-ésimo número na sequência. A complexidade do espaço também é O(n), pois precisamos armazenar os dois números anteriores na sequência para cada iteração do loop.
No entanto, poderíamos otimizar a complexidade do espaço armazenando apenas os dois números anteriores em vez de todos os números gerados até agora.
Arredondando para cima
A sequência de Fibonacci é um conceito matemático importante e atemporal com inúmeras aplicações em ciência da computação e programação. Com o algoritmo certo, você pode gerar rápida e facilmente qualquer número de Fibonacci.
De modo geral, a iteração e a programação dinâmica são os algoritmos mais eficientes em termos de complexidade de tempo e espaço, enquanto a exponenciação de matrizes é a mais eficiente em termos de complexidade de tempo para valores maiores de n. A recursão é a mais intuitiva, mas também a menos eficiente em termos de complexidade de tempo e complexidade de espaço.
No final, o melhor algoritmo a ser usado depende do problema em questão. Portanto, é importante entendê-los para saber quando usar cada método para otimizar o desempenho de seus programas de Fibonacci.
Programa para números de Fibonacci com exemplos Perguntas frequentes (perguntas frequentes)
Espiral de Arquimedes, Razão Áurea, Sequência de Fibonacci: qual é a conexão?
A espiral de Arquimedes e a sequência de Fibonacci podem ser relacionadas por meio da proporção áurea.
A proporção áurea é uma constante matemática que é igual à razão de dois números na sequência de Fibonacci. Essa proporção também pode ser encontrada na forma da Espiral de Arquimedes.
Portanto, os três conceitos estão inter-relacionados e têm importantes aplicações em matemática, ciências e arte.
Qual é a diferença entre recursão e iteração ao gerar números de Fibonacci?
A recursão é uma técnica na qual uma função chama a si mesma para resolver um problema, enquanto a iteração é uma estrutura em loop que repete um conjunto de instruções até que uma determinada condição seja atendida.
A recursão é a abordagem mais direta para gerar números de Fibonacci, mas é ineficiente devido à sua complexidade de tempo exponencial. A iteração é mais eficiente e pode calcular o n-ésimo número em tempo linear.
Como a sequência de Fibonacci é aplicada à ciência da computação e à programação?
A A sequência de Fibonacci tem muitas aplicações, como em algoritmos para geração de números aleatórios, gráficos, árvores, algoritmos de classificação e compactação de dados. Além disso, a sequência de Fibonacci é usada na criptografia e na análise do desempenho de algoritmos.
Qual é o significado da sequência de Fibonacci?
Muitas vezes é usado para modelar padrões de crescimento na natureza, como a ramificação das árvores, o arranjo das folhas em um caule e as espirais em uma concha ou pinha. Também é usado em análise técnica para prever tendências de mercado e em criptografia para gerar números aleatórios.
Quais são alguns exemplos de números de Fibonacci na natureza e na arte?
A proporção áurea é encontrada em muitos fenômenos naturais, como as espirais em certas plantas e animais (por exemplo, abacaxis, girassóis, conchas, etc.).
Também é encontrada em certas estruturas, como o Parthenon em Atenas, Grécia, música como a Quinta Sinfonia de Beethoven, arte como a Mona Lisa de Leonardo da Vinci e astronomia como as órbitas dos planetas em torno das estrelas.