Sequência de Fibonacci

É uma sequência numérica

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.
Teste Sequência Fibonacci
Sequência de Fibonacci mostrando o crescimento populacional de coelhos. (Foto: Wikipédia)

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

← 0

para K de 1 até n faça

ti + j

ij

jt

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

in – 1

a ← 1

b ← 0

c ← 0

d ← 1

aux10

aux20

enquanto i > 0 faça

se i é impar então

aux1db + ca

aux2d(b+a) + cb

aaux1

baux2

aux1c² + d²

aux2d(2c+d)

caux1

daux2

ii dividido por 2

retorne a + b

Faça a referência deste conteúdo seguindo as normas da ABNT:

Oliveira, Filipe. Sequência de Fibonacci; Guia Estudo. Disponível em

< https://www.guiaestudo.com.br/sequencia-de-fibonacci >. Acesso em 29 de janeiro de 2020 às 17:53.

Copiar referência

Outros Artigos de Matemática

O sistema da Blockchain possibilita o uso de Bitcoins no mundo todo.

Bitcoin

Bitcoin é uma criptomoeda utilizada em transações financeiras virtuais sem […]

Engenho de açúcar

Sistema Plantation

Sistema plantation é um sistema descendente do período colonial europeu […]

Colheita de plantação

Sistemas agrícolas

Os sistemas agrícolas formam o conjunto de atividades técnicas, econômicas […]

Setores da economia

Os setores da economia existem para medir o desenvolvimento econômico […]