Fibonacci, Quantas Chamadas?
Quase todo estudante de Ciência da Computação recebe em algum momento no início de seu curso de graduação algum problema envolvendo a sequência de Fibonacci. Tal sequência tem como os dois primeiros valores 0 (zero) e 1 (um) e cada próximo valor será sempre a soma dos dois valores imediatamente anteriores. Por definição, podemos apresentar a seguinte fórmula para encontrar qualquer número da sequência de Fibonacci:
fib(0) 0
fib(1) 1
fib(n) fib(n-1) fib(n-2);
Uma das formas de encontrar o número de Fibonacci é através de chamadas recursivas. Isto é ilustrado a seguir, apresentando a árvore de derivação ao calcularmos o valor fib(4), ou seja o 5º valor desta sequência:
Desta forma,
- fib(4) 1 0 1 1 0 3
- Foram feitas 8 calls, ou seja, 8 chamadas recursivas.
Entrada
A primeira linha da entrada contém um único inteiro , indicando o número de casos de teste. Cada caso de teste contém um inteiro .
Saída
Para cada caso de teste de entrada deverá ser apresentada uma linha de saída, no seguinte formato: _ , aonde _ é o número de chamadas recursivas, tendo sempre um espaço antes e depois do sinal de igualdade, conforme o exemplo abaixo.