Escreva um pseudocódigo recursivo para calcular C(n,k) = n choose k usando memoização; descreva qual estrutura…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Escreva um pseudocódigo recursivo para calcular C(n,k) = n choose k usando memoização; descreva qual estrutura de dados usar como memo (e a chave) e estime a complexidade temporal com memoização.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Pseudocódigo: memo = {} // dicionário/hash com chave (n,k) function C(n,k): if k == 0 or k == n: return 1 if (n,k) in memo: return memo[(n,k)] val = C(n-1,k-1) + C(n-1,k) memo[(n,k)] = val return val Descrição: usar um dicionário (hash map) como estrutura de memoização, indexando por tupla (n,k) para armazenar resultados já calculados. Isso evita recomputações das subproblemas sobrepostos. Complexidade: com memoização o número de pares (n,k) visitados é O(n·k), portanto tempo aproximado O(n·k) e espaço O(n·k) para o memo.
Explicação
O pseudocódigo apresentado utiliza a técnica de memoização para armazenar resultados de subproblemas, evitando cálculos repetidos, o que é essencial em problemas recursivos como o cálculo de combinações. A escolha de um dicionário com tuplas como chave permite acessar rapidamente os resultados armazenados, otimizando o desempenho. A complexidade temporal e espacial é determinada pelo número de combinações únicas de (n, k) que podem ser calculadas, resultando em O(n·k).
Raio-X da questão
pseudocódigo recursivo
avaliacao
funções recursivas · estrutura de dados
Revisar conceitos de recursão e memoização em algoritmos.
O aluno pode confundir a implementação de memoização com a simples chamada recursiva, não armazenando os resultados intermediários.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Enquanto visitantes aguardavam a abertura de um museu, técnicos programaram um painel luminoso e um robô-guia para…
- Para resolver uma atividade de Matemática, um estudante anota os passos nesta ordem: ler o enunciado, identificar os…
- Em um aplicativo, o total de maçãs é calculado a partir de duas informações informadas pelo usuário: as maçãs que estão…
- No fim da tarde, a responsável por uma sala de leitura separa dois tablets para um grupo de crianças. Antes de entregar…
- Descreva, em algoritmo de alto nível (passos), como um receptor deve processar pacotes de um arquivo recebido: verificar…
- Proponha um algoritmo de alto nível para que um sistema destino reconstitu´a um arquivo recebido em pacotes que podem…
🔎 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