1029 - Fibonacci, Quantas Chamadas?

Programação dinâmica clássica aplicada ao problema de Fibonacci.

Descrição

beecrowd Talent Cloudbeecrowd

Solução

Uma coisa interessante desse problema é como ele explica com detalhes como as chamadas recursivas do algoritmo comumente usado para calcular o k-ésimo número de Fibonacci. Nós vamos usar exatamente essa mesma ideia para calcular não só o número de Fibonacci como normalmente calculamos, mas também para calcular o número de chamadas que o nosso algoritmo vai fazer.

Primeiramente, a recorrência de Fibonacci que todos nós conhecemos

$$F(0) = 0 \\ F(1) = 1 \\ F(i) = F(i - 1) + F(i - 2)$$

que é inclusive a que está no enunciado. Vamos usar essa recorrência para calcular no número de Fibonacci e em conjunto a isso, faremos também a recorrência para o número de chamadas

$$CF(0) = 1 \\ CF(1) = 1 \\ CF(i) = CF(i - 1) + CF(i - 2) + 1$$

com o mais um porque contamos a própria chamada representada por CF(i).

Perceba que o número de chamadas recursivas envolve todas as chamadas exceto a chamada inicial, o que significa que, para nossa recorrência, é importante manter essa fórmula, mas para a resposta final, é necessário remover 1 para não contar a chamada inicial.

Com isso, no nosso código, podemos fazer o cálculo de ambos os valores ao mesmo tempo, pois precisamos tanto do Fibonacci quanto do número de chamadas.

Perceba que como temos apenas 39 valores diferentes, podemos inclusive pré-processar todos os casos antes de começarmos a receber as requisições ou podemos ir atendendo pela demanda, fica a seu critério. No meu código eu decidi fazer por demanda; para pré-processar todos os casos, basta acrescentar uma chamada calcula(39) na frente da leitura do input.

Por algum motivo, o problem setter achou legal trocar o Fibonacci e o número de chamadas de lugar, então fique ciente disso quando você for apresentar o output do seu problema.

C99

#include <stdio.h>

int F[40], CF[40];

void calcula(int n){
    if(F[n] == -1){
        calcula(n - 1);
        calcula(n - 2);

        F[n] = F[n - 1] + F[n - 2];
        CF[n] = CF[n - 1] + CF[n - 2] + 1;
    }
}

int main(){
    int N, X;

    F[0] = 0;
    F[1] = 1;

    CF[0] = 1;
    CF[1] = 1;

    for(int i = 2; i < 40; ++i){
        F[i] = -1;
        CF[i] = -1;
    }

    scanf("%d", &N);
    for(int i = 0; i < N; ++i){
        scanf("%d", &X);
        calcula(X);
        printf("fib(%d) = %d calls = %d\n", X, CF[X] - 1, F[X]);
    }

    return 0;
}

C++17

Python 3.9