MO417 - QUESTÃO PARA A PROVA ORAL
Número:
Enunciado: Considere o problema de encontrar a rota máxima do topo até a base de um triangulo usando apenas elementos adjacentes, x+y+d+c seria uma rota possível no triangulo:
x
y z
a d e
b c f g
NÃO seria correto afirmar para um triângulo com n elementos:
A) a = a + max(b, c) seria parte da estratégia para resolver o problema usando programação dinâmica bottom-up.
B) f = f + max(d, e) seria parte da estratégia para resolver o problema usando programação dinâmica top-down.
C) Com uma estratégia de programação dinâmica bottom-up podemos conseguir complexidade assintótica menor do que com uma estratégia de programação dinâmica top-down.
D) Existe um algorítimo O(2^h) que usa força bruta para calcular todas as possíveis somas, onde h é a altura do triângulo.
E) NDA
Ideia original de: Fabrício Matheus Gonçalves
Nenhum comentário:
Postar um comentário