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