É uma sucessão de números que seguem um padrão
A sequência de Fibonacci nada mais é que a ordem de números inteiros, que parte, normalmente, de zero e um no qual cada número seguinte corresponde a soma dos dois algarismos anteriores. Essa continuidade pode ser vista em vários fenômenos da natureza.
A sequência de Fibonacci foi nomeada pelo matemático italiano Leonardo de Pisa, também conhecido como Fibonacci. Em 1202, a partir dessa sequência numérica, o matemático relatou o avanço de uma população de coelhos.
Fórmula de Fibonacci
A sucessão de Fibonacci é uma sequência de números inteiros iniciados por zero e um, no qual cada termo subsequente corresponde a soma dos dois números anteriores:
0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584...
Modelos naturais
A sequência de Fibonacci também pode ser observada em fenômenos naturais. Confira abaixo alguns deles:
Girassol: o miolo do girassol possui sementes que são dispostas em um conjunto de espiral duplo. Na maioria das vezes são 21 no sentido horário e outras 34 em anti-horário.
Pinha: depois do crescimento da fruta, as sementes formam um duplo espiral com oito no sentido horário e outras 13 em anti-horário.
Concha do caramujo: cada parte da concha possui o tamanho da soma dos dois antecessores. Sabe-se que um conha apresenta três lados principais, então, supondo que um lado mede 2 (1 + 1), e outro 5 (3 + 2) o terceiro será 8 (5 + 3).
Algoritmo Fibonacci
Existem vários métodos para calcular o n-ésimo elemento da sequência de Fibonacci, entretanto os mais comuns utilizam uma dos seguintes critérios:
Abordagem recursiva
A definição da sequência de Fibonacci pode ser usada 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 devem ser calculados uma grande quantidade de vezes. Em razão disso, normalmente determina-se os números de Fibonacci de baixo para cima, iniciando com os números zero e um, e depois repetidamente ir trocando o primeiro número pelo segundo, e o segundo número pela soma dos dois algarismo anteriores.
Abordagem Iterativa
Usando um algoritmo iterativo, como foi feito a seguir, é possível obter a sequência de forma mais eficaz:
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 competente e toma como base a representação matricial da sequência de Fibonacci. A dificuldade 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
aux 1 <-- 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
Quem foi Leonardo Fibonacci?
Nascido em 1170, Leonardo Pisano ficou conhecido como Leonardo Fibonacci. Ele foi o primeiro grande matemático da Europa no período da história medieval, atuando na redescoberta de fórmulas matemáticas e realizando colaborações significantes até a morte, em 1240.
Leonardo Fibonacci. (Foto: Wikimedia Commons)
O matemático italiano escreveu o livro "Liber Abacci", conteúdo responsável pela introdução do sistema de números hindu-árabe utilizando dez variáveis.