Explique o que é a sequência de Fibonacci, como calcular seus termos e a relação com a proposição da razão de ouro, além de apresentar os principais métodos de implementação de algoritmos.
A sequência de Fibonacci é uma sequência infinita de números inteiros típica em que cada termo é a soma dos dois termos anteriores.
Forma comum da sequência (iniciando com 0 e 1): 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
A definição recursiva clássica é Fn = Fn−1 + Fn−2, com F0 = 0 e F1 = 1. O início dos termos depende da convenção escolhida, porém a relação de soma permanece constante.
A razão entre termos consecutivos tende ao valor φ (phi) ≈ 1,618... quando n aumenta, ou seja, Fn / Fn−1 → φ. Esse fenómeno está ligado à chamada proporção áurea, que é considerada visualmente agradável e aparece, por exemplo, na arquitetura e em configurações naturais.
Na prática, basta dividir um termo da sequência pelo antecessor para observar a aproximação de φ. Também é comum expressar φ como 1,61803398875... e associar com várias proporções visuais, incluindo porcentagens como 61,8% e 38,2% entre segmentos.
Há várias abordagens para calcular Fn. As mais comuns são:
Definida pela função fib(n): se n < 2 então retorne n, senão retorne fib(n − 1) + fib(n − 2).
Observação: esse método é ineficiente, calculando repetidamente os mesmos valores. Em prática, utiliza-se computação de baixo para cima, substituindo valores anteriores para construir a sequência.
Exemplo de implementação iterativa com complexidade O(n):
\nfunção fib(n)
j ← 1
i ← 0
para K de 1 até n faça
t ← i + j
i ← j
j ← t
retorne j\n
Essa abordagem obtém os termos da sequência de forma eficiente, sem recomputar valores anteriores.
Utiliza a representação matricial da sequência, com complexidade 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
Para consolidar, a seção de questões abaixo aborda compreensão sobre conceituações e métodos de cálculo.
Escolha a opção correta:
Resposta correta: B) 0
Obs.: Ao iniciar com F0 = 0 e F1 = 1, o primeiro termo da sequência é 0.
Escolha a opção correta:
Resposta correta: C) 1
Explicação: após 0, 1, o próximo termo é 0 + 1 = 1.
Escolha a opção correta:
Resposta correta: A) Fn = Fn−1 + Fn−2
Explicação: por definição Fn depende da soma dos dois termos anteriores.
Escolha a opção correta:
Resposta correta: C) 1.618
Explicação: φ ≈ 1,618 é a razão entre termos consecutivos da sequência de Fibonacci em limitante.