A sequência de Fibonacci é uma sequência numérica em que cada número é a soma dos dois anteriores, iniciando normalmente com 0 e 1 . Ou seja:
(1.5pts) Versão Iterativa: Desenvolva uma função que utilize uma estrutura de repetição (por exemplo, for ou while) para calcular o valor de
sem utilizar recursão.
Passo 1
O enunciado pede que eu desenvolva uma função que calcule o termo
da sequência de Fibonacci usando uma estrutura de repetição (por exemplo, um
ou
), ou seja, sem usar recursão.
Informações dadas:
Informações dadas:
- A sequência é definida por
e, para , .\n
O que se pede: - Uma versão iterativa (uma função) que, dada uma entrada inteira
, retorne sem usar chamada recursiva.
Passo 2
Decidindo a estratégia (sem formalismos chatos): usar um laço que vá construindo os termos da sequência um a um. A ideia é manter só os dois últimos termos vistos e, a cada passo, atualizar para o próximo termo. Isso evita a explosão exponencial da recursão e usa memória constante.
Condições iniciais (casos base) que precisamos tratar antes do laço:
Condições iniciais (casos base) que precisamos tratar antes do laço:
- Se
a resposta é . - Se
a resposta é .
Parausamos o laço para calcular.
Passo 3
Introduzindo as variáveis que vamos usar e o que elas significam:
- Vou usar duas variáveis, que chamo aqui de
e . - Em qualquer momento do laço, vou manter a invariante:
e para algum índice . - Para avançar um passo (ir de
para ) eu calculo o novo termo como e atualizo as variáveis para manter a invariante no próximo : faço e (atenção: o da direita é o valor antigo de ).
Passo 4
Descrevendo o laço mais explicitamente (pseudopasso a passo):
- Trato os casos
e retornando e respectivamente. - Inicializo
e . Nesse momento a invariante vale para : não é interessante; pense que antes do primeiro passo efetivo temos e . - Para cada
indo de até (inclusive), faço: - calcular
(que é ); - atualizar
e .
- calcular
- Ao final do laço,
contém . Retorno .
Passo 5
Exemplo concreto (vamos “mastigar” os valores para
para você ver que o laço funciona):
- Início:
. - Iteração para
: . Atualiza: . Agora . - Iteração para
: . Atualiza: . Agora . - Iteração para
: . Atualiza: . Agora . - Iteração para
: . Atualiza: . Agora que é .
Isso bate com a sequência conhecida.
Passo 6
Justificativa formal curta (invariante do laço — por que isso sempre dá certo):
- Base: antes do primeiro passo efetivo temos
e . - Passo do laço: suponha que, no início de uma iteração para índice
, tenhamos e . Calculamos . Então pela definição da sequência. Ao fazer e passamos a ter e , que é exatamente a invariante para o próximo índice. Portanto, após terminar em , .
Passo 7
Complexidade e observações práticas:
- Tempo: o laço executa
atualizações no pior caso ( ), ou seja tempo . - Espaço: usamos um número constante de variáveis, espaço
. - Caso de entrada inválida: se alguém chamar a função com
devemos tratar (por exemplo, lançar erro) — normalmente Fibonacci é definido para . - Se precisar de Fibonacci para
muito grande, lembre que os valores crescem rápido; pode ser necessário usar tipos de inteiros que suportem muitos dígitos (em Python int é automático).
Resposta
def fibonacci_iterativa(n):
“”"
Retorna F(n) da sequência de Fibonacci de forma iterativa (sem recursão).
Assume n inteiro >= 0. Levanta ValueError se n < 0.
“”"
if n < 0:
raise ValueError(“n deve ser inteiro não-negativo”)
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
for i in range(2, n + 1):
c = a + b
a = b
b = c
return b
“”"
Retorna F(n) da sequência de Fibonacci de forma iterativa (sem recursão).
Assume n inteiro >= 0. Levanta ValueError se n < 0.
“”"
if n < 0:
raise ValueError(“n deve ser inteiro não-negativo”)
if n == 0:
return 0
if n == 1:
return 1
a = 0
b = 1
for i in range(2, n + 1):
c = a + b
a = b
b = c
return b