Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Quantas chamadas são realizadas à função fibonacci para computar fibonacci(5)?

+1 voto
46 visitas
perguntada Jun 6 em Informática por matheusbenficaleite (6 pontos)  

A sequência de Fibonacci consiste numa sucessão infinita de números que obedecem um padrão onde os dois primeiros elementos são 0 e 1 e para os elementos subsequentes é a soma dos dois elementos imediatamente anterior na sequência. Como exemplo, a sequência formada pelos 7 primeiros números de Fibonacci é: 0, 1, 1, 2, 3, 5, 8. Os números de Fibonacci podem ser definidos pela seguinte relação de recorrência: (SANTOS, Ângela Rocha; BIANCHINI, Waldecir. Aprendendo Cálculo com Maple. Rio de Janeiro: LTC, 2002.)

Abaixo, apresenta-se uma implementação em linguagem funcional para a função Fibonacci.

def fibonacci(n)

{

 if(n==1) or (n==2)

      return 1

 else

      return (fibonacci(n-1) + fibonacci(n-2))

}

Quantas chamadas são realizadas à função fibonacci para computar fibonacci(5)?

Compartilhe

1 Resposta

+1 voto
respondida Jul 15 por Pablo Castro (286 pontos)  

Olá! Na verdade, o primeiro termo da sequência de fibonacci é 0 e não o 1. Uma pequena alteração na implementação acima resolve isso.

Para saber quantas chamadas são realizadas, você pode criar uma lista vazia. Depois adicione à lista o n que a função está calculando. Segue implementação:

chamadas = [] 


def fibonacci(n):
    if n == 1:
        chamadas.append(n)
        return 0
    elif n == 2:
        chamadas.append(n)
        return 1
    else: 
        chamadas.append(n)
        # print(chamadas) 
        return fibonacci(n-1) + fibonacci(n-2)


n = 5
print(f'O {n}th elemento da sequência de fibonacci é {fibonacci(n)}')
print(f'O número de chamadas que são realizadas à função é {len(chamadas)}')

O output da implementação acima é:

O 5th elemento da sequência de fibonacci é 3
O número de chamadas que são realizadas à função é 9 

O print (que está como comentário) também ajuda na visualização.

...