Estrutura de Dados UPT 2022_1

Algumas vezes, quando você é um estudante de computação, irá ver exercícios o problemas envolvendo a sequencia de Fibonacci.  Esta sequencia tem os 2 primeiros valores com 0 e 1 e cada valor seguinte é a soma dos dois números anteriores. Por definição, a fórmula para encontrar o n-ésimo número da sequencia de Fibonacci é: 
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2);

Uma forma de encontrar esse número n é usando recursão, na qual uma função chama a si mesma repetidas vezes. O esquema abaixo representa a árvore de derivação quando se calcula fib(4) ou seja, o 5 valor dessa sequencia:

• fib(4) = 1+0+1+1+0 = 3
• 8 chamadas recursivas foram feitas

A primeira linha entrada contém um único inteiro N, indicando o número de casos de teste. Cada caso de teste contem um inteiro  X (1 ≤ X ≤ 39) .

Para cada caso de teste há uma linha de saída com '\n' no final, no formato "fib(n) = F, fazendo C chamadas", onde F é o n-ésimo número da sequencia e C é o número de chamadas recursivas realizadas.