MO417 - Questão para a prova oral

Número: 051

Enunciado:
Considere os números de Fibonacci, que são definidos por:

F(n) = {0, se n = 0;
             1, se n = 1;
             F(n - 1) + F(n-2) outros casos. }

Sobre o cáculo de um número de Fibonacci F(n) podemos afirmar que:

1. Este problema não pode ser resolvido recursivamente;
2. Este problema pode ser resolvido através de programação dinâmica, porém utilizando um algoritmo recursivo o desempenho é melhor;
3. Este problema possui subestrutura ótima, porém não possui subproblemas superpostos, portanto não pode ser resolvido através de programação dinâmica;
4. Este problema possui subproblemas superpostos, porém não possui subestrutura ótima, portanto não pode ser resolvido através de programação dinâmica;
5. NDA

Autor: Gabriel de Souza Fedel