Ao generalizar um algoritmo recursivo que calcula custo mínimo em uma rede (grafo) para múltiplas instâncias…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio da reutilização de partes de soluções existentes.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Ao generalizar um algoritmo recursivo que calcula custo mínimo em uma rede (grafo) para múltiplas instâncias, qual variável parâmetro permite reaproveitar subresultados (memoização) entre chamadas e evitar recomputação? Especifique tipo.
- A) cache: List<Cost>
- B) cache: Map<NodeKey, string>
- C) cache: Set<NodeKey>
- D) cache: Map<Cost, NodeKey>
- E) cache: Map<NodeKey, Cost> (ou dictionário de pares estado->custo)
✅ Resposta correta: alternativa E
Resolução passo a passo
- A memoização guarda, para cada subproblema já resolvido, o resultado calculado, de modo que uma nova chamada com a mesma entrada apenas consulte o valor armazenado. No problema de custo mínimo em uma rede, o subproblema é identificado por um nó (ou estado) e o resultado é o custo mínimo associado a ele.
- Logo, a estrutura precisa associar uma chave (identificador do nó/estado, NodeKey) a um valor numérico (custo, Cost). Isso é exatamente um mapa de chave para custo: Map<NodeKey, Cost>, também descrito como dicionário de pares estado->custo.
- A alternativa A usa uma lista, que não permite consulta direta pela chave do subproblema, obrigando a percorrê-la e perdendo a eficiência da memoização. A alternativa B guarda strings como valor, mas o resultado de custo mínimo é numérico, não texto. A alternativa C é um conjunto, que só registra presença de chaves e não armazena o custo calculado. A alternativa D inverte chave e valor, tornando o custo a chave e o nó o valor, o que não faz sentido para consulta por subproblema.
- Portanto, a alternativa correta é a E, em concordância com o gabarito oficial.
💡 Dica: Associe cada estado do problema à chave e armazene seu custo como valor.
Alternativa por alternativa
O aluno pensa que qualquer estrutura de armazenamento serve para guardar resultados, sem perceber que uma lista não oferece acesso direto pela chave do subproblema.
O aluno associa a chave ao nó corretamente, mas acredita que o valor guardado pode ser texto, sem considerar que o custo mínimo é um valor numérico.
O aluno entende que basta registrar quais nós já foram visitados, sem perceber que a memoização precisa reter o custo calculado para reutilizá-lo.
O aluno inverte os papéis de chave e valor, usando o custo como chave e o nó como resultado, o que impede consultar o resultado a partir do subproblema.
Por que engana: Escolher um conjunto ou inverter chave e valor, sem perceber que a memoização precisa localizar cada estado e recuperar o custo correspondente.
Um mapa/dicionário armazenando resultados de subproblemas permite reutilizar cálculos entre instâncias e reduzir redundância.
Raio-X da questão
Memoização de estados recursivos
avaliacao
Estruturas de dados associativas · Recursão e estados de problema
Revise como mapas associam chaves a valores e armazenam resultados por estado para evitar recomputações.
Escolher um conjunto ou inverter chave e valor, sem perceber que a memoização precisa localizar cada estado e recuperar o custo correspondente.
ciencia_tecnologia
tomada_decisao
cientifico
Questões parecidas com resolução
- Ao projetar um algoritmo recursivo que recalcula repetidamente os mesmos subproblemas, qual técnica baseada em armazenar…
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
- Considere um algoritmo que encontra rotas em uma rede (grafo). Para generalizá-lo a diferentes métricas de custo (tempo…
- Projete a assinatura de um algoritmo que resolve várias instâncias de caminho mínimo: recebe um grafo e uma lista de…
- Em um projeto de programação, uma equipe precisa calcular o termo de número n da sequência de Fibonacci usando recursão…
- Ao representar um autômato de estados com muitos estados e poucas transições entre eles (grafo esparso) para executar um…
🔎 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