Projete em pseudocódigo uma função recursiva subsequencias(L) que recebe uma lista L de inteiros e retorna a…
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
Projete em pseudocódigo uma função recursiva subsequencias(L) que recebe uma lista L de inteiros e retorna a lista de todas as subsequências (conjuntos ordenados) de L. Explique o caso base, a relação recursiva e comente a complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Pseudocódigo: funcao subsequencias(L): se L == [] então retorne [[]] // caso base: apenas a subsequência vazia senao primeiro = L[0] resto = subsequencias(L[1:]) com_primeiro = map cada s em resto: concatenar([primeiro], s) retorne concatenar(resto, com_primeiro) Explicação: o caso base retorna lista com a subsequência vazia. Na relação recursiva, para cada subsequência do resto existem duas escolhas quanto ao primeiro elemento: mantê-lo ou não — por isso duplicamos as subsequências de 'resto' e as combinamos. Complexidade: gera 2^n subsequências; tempo O(n * 2^n) (cada subsequência pode custar até O(n) para construir) e espaço O(2^n) para armazenar o resultado.
Explicação
A função começa com o caso base que retorna a subsequência vazia quando a lista está vazia, garantindo que sempre haja uma subsequência a ser retornada. A relação recursiva explora todas as combinações possíveis ao decidir se inclui ou não o primeiro elemento, resultando em todas as subsequências. A complexidade reflete o crescimento exponencial do número de subsequências, além do tempo necessário para construir cada uma delas, justificando os limites de tempo e espaço mencionados.
Raio-X da questão
função recursiva
avaliacao
funções recursivas · listas e conjuntos
Revisar conceitos de recursão e complexidade de algoritmos.
O aluno pode confundir a lógica de recursão, não definindo corretamente o caso base ou a relação recursiva.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Os aplicativos de mapa, como o GPS, ajudam o carro de entregas a chegar à casa do cliente. O aplicativo compara dois…
- Lia organiza carrinhos, bonecas e blocos separando cada tipo, colocando-os em caixas e guardando as caixas na…
- Em um jogo, uma personagem controlada por IA precisa chegar a um tesouro sem bater nas paredes. Qual instrução ajuda a…
- Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
- Em um programa, Substring(codigo, início, quantidade) pega letras do texto a partir da posição indicada, e…
- Projete um algoritmo em pseudocódigo que, dadas as variáveis temperatura (inteiro ºC), ocupacao (inteiro, número de…
🔎 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