Descreva um algoritmo em pseudocódigo que, dado n variáveis booleanas (dados de entrada), gere todas as 2^n…
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
Descreva um algoritmo em pseudocódigo que, dado n variáveis booleanas (dados de entrada), gere todas as 2^n combinações possíveis e explique a complexidade temporal e espacial do algoritmo.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Resposta modelo (pseudocódigo e análise): Iterativo por contagem binária: 1. Para i de 0 até 2^n - 1: 2. Para j de 0 até n-1: 3. bit[j] ? (i >> j) & 1 4. Emitir bit[0..n-1] Recursivo (backtracking): função gerar(pos, prefixo): se pos == n: emitir prefixo; retornar prefixo[pos] = 0; gerar(pos+1, prefixo) prefixo[pos] = 1; gerar(pos+1, prefixo) Complexidade: - Tempo: O(n · 2^n) porque geramos 2^n combinações e cada combinação leva T(n) para construir/emitir. - Espaço: O(n) adicional para o vetor corrente; se armazenarmos todas as combinações, espaço total O(n · 2^n). Observações: escolha entre iteração e recursão depende de restrições de pilha; ambas produzem o mesmo crescimento assintótico.
Explicação
O pseudocódigo apresentado gera todas as combinações de variáveis booleanas de forma eficiente, utilizando tanto uma abordagem iterativa quanto uma recursiva. A análise de complexidade temporal e espacial demonstra que, independentemente da abordagem escolhida, o crescimento das combinações é exponencial em relação ao número de variáveis, refletindo a natureza do problema. A escolha entre iteração e recursão permite flexibilidade na implementação, dependendo das limitações do ambiente de execução.
Raio-X da questão
algoritmo e complexidade
avaliacao
variáveis booleanas · pseudocódigo
Revisar conceitos de algoritmos e análise de complexidade.
O aluno pode confundir a quantidade de combinações possíveis, não considerando que cada variável pode ser verdadeira ou falsa, resultando em 2^n combinações.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Lia criou um caminho no tabuleiro. O tablet usa “andar 10 passos”, e o robô usa “andar 1 quadrado”. Por que Lia escreveu…
- Algoritmo: "Ler nota. Se nota >= 60 então imprimir 'Aprovado'. Senão imprimir 'Reprovado'." Qual será a saída para nota…
- Na sala, um algoritmo manda ler a temperatura. Se ela for maior que 30 graus, deve ligar o ventilador; caso contrário…
- Descreva em passos um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne todas as…
- Projete um algoritmo em pseudocódigo que receba uma lista de nomes (strings) como dado de entrada e devolva uma lista de…
- Projete um algoritmo reativo (autômato) que filtra eventos duplicados recebidos de um sensor; cada evento tem campos…
🔎 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