MO417 - QUESTÃO PARA A PROVA ORAL
Número: 2013-037Enunciado: Considere o problema de encontrar a rota máxima do topo até a base de um triangulo usando apenas elementos adjacentes, sendo um de cada linha. Por exemplo, x+y+d+c, marcada em vermelho na figura, seria uma rota possível no triangulo a seguir:
x
y z
a d e
b c f g
Para um triângulo com n elementos,
NÃO seria correto afirmar que:
A) 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.
B) a = a + max(b, c) seria parte de uma estratégia de programação dinâmica bottom-up para resolver o problema.
C) f = f + max(d, e) seria parte de uma estratégia de programação dinâmica top down para resolver o problema.
D) Existe um algoritimo O(2^h) que usa forca 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
A) 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.
B) a = a + max(b, c) seria parte de uma estratégia de programação dinâmica bottom-up para resolver o problema.
C) f = f + max(d, e) seria parte de uma estratégia de programação dinâmica top down para resolver o problema.
D) Existe um algoritimo O(2^h) que usa forca 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