Implementar um algoritmo que solicita um número inteiro positivo N e mostre o enésimo termo da sequência de Fibonacci. Essa sequência começa no termo de ordem zero e, a partir do segundo termo, seu valor é dado pela soma dos dois termos anteriores. Exemplo: para
, o enésimo termo é 13 , uma vez que a sequência de Fibonacci até o oitavo termo é: 0,1,1,2,3,5,8,13.
Passo 1
Beleza, o enunciado pede pra gente criar um algoritmo que lê um inteiro positivo N e devolve o N-ésimo termo da sequência de Fibonacci. A sequência começa em F₀=0, F₁=1 e, a partir daí, cada termo é a soma dos dois anteriores.
Matéria envolvida: estrutura de repetição (loop), variáveis e atribuição. Vamos precisar entender a definição
Matéria envolvida: estrutura de repetição (loop), variáveis e atribuição. Vamos precisar entender a definição
e usar um loop para calcular até F_N de forma eficiente.
Passo 2
Entendendo a teoria:
- Fibonnaci é uma sequência recursiva, mas implementar recursão pura dá muita repetição de cálculo.
- A ideia é usar iteração: ir construindo F₂, F₃, … até F_N, sempre guardando só os dois últimos valores.
- Isso economiza tempo e memória.
Passo 3
Escolhendo o método iterativo:
- Se N for 0 ou 1, já sabemos a resposta: F₀=0 ou F₁=1.
- Se N≥2, inicializamos duas variáveis:
a = F₀ = 0
b = F₁ = 1 - Em cada passo do loop, de i=2 até i=N, calculamos
e “deslocamos” os valores: - No final, b contém F_N.
Passo 4
Pseudocódigo comentado (linguagem neutra):
Algoritmo Fibonacci
Leia N // N é inteiro e N ≥ 0
Se N = 0 então
resultado ← 0
Senão se N = 1 então
resultado ← 1
Senão
a ← 0 // F₀
b ← 1 // F₁
Para i de 2 até N faça
c ← a + b // calcula F_i = F_{i-1} + F_{i-2}
a ← b // atualiza F_{i-2} para o próximo loop
b ← c // atualiza F_{i-1} para o próximo loop
FimPara
resultado ← b // aqui b = F_N
FimSe
Escreva resultado
FimAlgoritmo
Resposta
O algoritmo acima, quando você digitar um N qualquer, vai imprimir o N-ésimo termo da sequência de Fibonacci de forma eficiente (complexidade O(N)). Por exemplo, N=8 retorna 13, pois a sequência é 0,1,1,2,3,5,8,13.