A sequência de Fibonacci é uma sequência numérica, composta por números inteiros, que começam normalmente por zero ou um. Nesta sequência de números, cada termo subsequente corresponde à soma dos dois números anteriores.
Em 1202, Leonardo Pisa, também conhecido como Fibonacci, utilizou essa sequência para descrever o crescimento de uma população de coelhos, porém essa mesma sucessão já era conhecida na antiguidade.
Leonardo Fibonacci
O italiano Leonardo Fibonacci foi apontado como o primeiro grande matemático proveniente da Europa na Idade Média. Ficou conhecido por causa da descoberta da sequência de Fibonacci e pela sua atuação na introdução dos números arábicos na Europa.
Assim como outros matemáticos do seu tempo, Leonardo Fibonacci contribuiu para o ressurgimento das ciências exatas, após o período de decadência vivido na antiguidade clássica e do início da Idade Média.
O estudioso também se destacou ao grafar o Liber Abaci, em 1202 – atualizado 52 anos depois -, o primeiro livro importante sobre matemática desde a época de Eratóstenes. Através do Liber Abaci os números hindu-arábicos foram introduzidos na Europa, além de debater vários problemas da matemática.
Formula de Fibonacci
Sequência de Fibonacci é um seguimento de numerais que atendem a um padrão, em que cada elemento subsequente é a soma dos dois algarismos anteriores.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584…
A sequência é definida pela fórmula a seguir:
Fn = Fn−1 + Fn − 2
Dessa forma, temos:
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
e assim sucessivamente.
Origem
Como falado anteriormente, no ocidente, a sequência de Fibonacci apareceu pela primeira vez no livro Liber Abaci, grafado em 1202, por Leonardo Fibonacci, apesar de já ter sido descrita por gregos e indianos.
O matemático levou em consideração o crescimento de uma população de coelhos. Os números mostram a quantidade de casais na população de coelhos após um determinado período, supondo que:
- No primeiro mês nasce somente um casal;
- Casais amadurecem sexualmente e reproduzem depois do segundo mês de vida;
- Não existem problemas genéticos no cruzamento consanguíneo;
- Todos os meses, cada casal fértil gera um novo casal;
- Os coelhos nunca morrem.
Genericamente chama-se se sequência de Fibonacci qualquer função g tal que g(n + 2) = g(n) + g(n + 1). Essas funções possuem o formato g(n) = aF(n) + bF(n + 1) para alguns números a e b, então as sequências de Fibonacci formam um espaço vetorial com as funções F(n) e F(n + 1) como base. Em particular, a sequência de Fibonacci com F(1) = 1 e F(2) = 3 é conhecida como a sequência de Lucas.
Fibonacci algoritmo
Existem várias formas para calcular o n-ésimo elemento da sequência de Fibonacci, porém os mais comuns utilizam um dos seguintes métodos:
- Abordagem Recursiva
- Abordagem Iterativa
- Dividir para conquistar
Abordagem recursiva
A definição da sequência de Fibonacci pode ser utilizada para executar um algoritmo recursivo que forma os termos da sequência, veja a seguir:
Função fib(n)
Se n < 2 então
retorne n
pelo contrário
retorne fib(n – 1) + fib(n – 2)
Mesmo sendo simples, esse método não é recomendável, pois os valores são calculados uma grande quantidade de vezes. Por conta disso, normalmente calcula-se os números de Fibonacci de baixo para cima, começando com os dois valores 0 e 1, e depois repetidamente vai substituindo o primeiro número pelo segundo, e o segundo número pela soma dos dois anteriores.
Abordagem Iterativa
Através de um algoritmo iterativo como o que será mostrado a seguir, é possível obter a sequência de forma mais eficientemente.
função fib(n)
j ← 1
i ← 0
para K de 1 até n faça
t ← i + j
i ← j
j ← t
retorne j
Nesse caso a complexidade computacional do algoritmo será O(n).
Dividir para conquistar
Esse algoritmo é mais eficiente e toma como base a representação matricial da sequência de Fibonacci. A computacional é O(log(n)).
Função fib(n)
Se n for menor ou igual a zero então
retorne 0
i ← n – 1
a ← 1
b ← 0
c ← 0
d ← 1
aux1 ← 0
aux2 ← 0
enquanto i > 0 faça
se i é impar então
aux1 ← db + ca
aux2 ← d(b+a) + cb
a ← aux1
b ← aux2
aux1 ← c² + d²
aux2 ← d(2c+d)
c ← aux1
d ←aux2
i ← i dividido por 2
retorne a + b