Diagrama descreve recursão que recalcula subproblemas sem memoização para obter f(n). Avalie por que essa…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Aplicar a estratégia de decomposição para resolver problemas complexos, dividindo esse problema em partes menores, resolvendo-as e combinando suas soluções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Diagrama descreve recursão que recalcula subproblemas sem memoização para obter f(n). Avalie por que essa recursão pode ser ineficiente e proponha em até duas frases uma melhoria usando listas.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Sem memoização a função recalcula subproblemas várias vezes, causando explosão exponencial do tempo. Melhoria: usar uma lista 'memo' para armazenar resultados já calculados; antes de calcular f(k) verificar memo[k] e, se ausente, calcular e salvar na lista para reutilizar.
Explicação
A resposta identifica a ineficiência da recursão sem memoização, que leva a múltiplos cálculos dos mesmos subproblemas, resultando em um aumento exponencial no tempo de execução. A proposta de usar uma lista para armazenar resultados já calculados é uma técnica de otimização que evita cálculos redundantes, melhorando a eficiência do algoritmo. Essa abordagem, conhecida como memoização, permite que a função acesse rapidamente resultados anteriores, reduzindo significativamente o tempo de execução.
Raio-X da questão
recursão e eficiência
avaliacao
recursão em programação · memoização
Revisar conceitos de recursão e memoização.
O aluno pode não perceber que a recursão sem memoização recalcula os mesmos subproblemas repetidamente, levando a um aumento exponencial no tempo de execução.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Projete, em passos claros, um algoritmo para transferir um arquivo grande pela rede garantindo confidencialidade e…
- Elabore um algoritmo em pseudocódigo que: receba um arquivo (fluxo de bytes) e um valor MTU; divida o arquivo em pacotes…
- Descreva um algoritmo generalizado que receba uma matriz de dados (grid) e um parâmetro função 'valido(p)' que indica se…
- Você recebeu um algoritmo que processa fluxo de dados de sensores em rede; leitura, validação, transformação e…
- Projete um plano para transformar um algoritmo de cálculo de rotas que usa variáveis globais ('vel_max'…
- Explique como a decomposição de um problema pode ajudar na resolução de um desafio cotidiano, como organizar uma viagem…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog