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;
}

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:
Esse exercício usa a ideia de programação dinâmica. Primeiro, tem que entender que a cada nível de fibonacci, o número de calls é a soma dos dois níveis anteriores mais dois. E em fibonacci, a cada nível é a soma de dois níveis anteriores.
Assim, foi feito dois vetores que computam esses valores. Esses vetores são preenchidos conforme a necessidade. Supondo que x = 5, então só será preenchido até 5. Quando um x maior for necessário, o vetor é preenchido a partir do último ponto que já estava preenchido.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include <iostream> using namespace std; int main(){ int n,x; int calls[40], fib[40]; calls[0] = 0; calls[1] = 0; fib[0] = 0; fib[1] = 1; int done = 1; cin >> n; while(n--){ cin >> x; while(done < x){ done++; fib[done] = fib[done-1] + fib[done-2]; calls[done] = calls[done-1]+ calls[done-2] + 2; } cout << "fib(" << x << ") = " << calls[x] << " calls = " << fib[x] << endl; } return 0; }