URI - 1029 - Fibonacci, Quantas Chamadas? - Paradigmas - C

Plataforma: URI
Problema: 1029

Enunciado:
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.

Linguagem: C

Solução:

#include<stdio.h>

int main() {
    int n, i;
    long long int a;
    long long int acum[61];
    long long int calls[60];
    
    scanf("%i",&n);
    
    for (i = 0; i < n; i++) {
        scanf("%lld", &a);

        int i;

        acum[0] = 0;
        acum[1] = 1;

        calls[0] = 0;
        calls[1] = 0;
        
        for(i = 2; i <= a; i++) {
            acum[i] = acum[i-1] + acum[i-2];
            calls[i] = calls[i-1] + calls[i-2] + 2;
        }
    
        printf("fib(%lld) = %lld calls = %lld\n", a, calls[a], acum[a]);
    }
    return 0;
}