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
- Em um projeto de programação, uma equipe precisa calcular o termo de número n da sequência de Fibonacci usando recursão…
- Diagrama descreve recursão que recalcula subproblemas sem memoização para obter f(n). Avalie por que essa recursão pode…
- Analise a função recursiva que calcula o fatorial de um número. Qual é a estrutura de dados mais adequada para armazenar…
- Utilizando a técnica de recursão, como você solucionaria um problema que requer o cálculo de um fatorial? Descreva o…
- Descreva um algoritmo em pseudocódigo que, dado n variáveis booleanas (dados de entrada), gere todas as 2^n combinações…
- Dada uma matriz m×n de inteiros (representando pontos de um mapa), escreva em pseudocódigo um algoritmo recursivo que…
🔎 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