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
- Imagem descrita: fluxograma mostra função rec_calc(n): se n==0 retorna 1; senão retorna n * rec_calc(n+1). Observando a…
- Qual é um exemplo de problema que pode ser resolvido com recursão usando listas?
- Ao projetar um algoritmo recursivo que recalcula repetidamente os mesmos subproblemas, qual técnica baseada em armazenar…
- Utilizando a técnica de recursão, como você solucionaria um problema que requer o cálculo de um fatorial? Descreva o…
- Em um projeto de programação, uma equipe precisa calcular o termo de número n da sequência de Fibonacci usando recursão…
- Projete em pseudocódigo um algoritmo recursivo map_recursive(L,f) que recebe uma lista L e uma função f e retorna uma…
🔎 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