Durante uma brincadeira, cada amigo deve escolher um caminho em um labirinto. Qual a melhor maneira de…
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
Durante uma brincadeira, cada amigo deve escolher um caminho em um labirinto. Qual a melhor maneira de encontrar o menor caminho até a saída?
- A) Usar o algoritmo de Dijkstra.
- B) Escolher qualquer caminho.
- C) Contar passos até a saída.
- D) Seguir sempre à direita.
- E) Usar a força bruta.
✅ Resposta correta: alternativa A
Resolução passo a passo
- A questão pede a melhor forma de encontrar o menor caminho até a saída de um labirinto, ou seja, um método que compare caminhos possíveis e escolha o de menor custo (número de passos ou distância). Passo 2: Modelamos o labirinto como um grafo, em que cada cruzamento é um vértice e cada trecho entre cruzamentos é uma aresta com um custo. Passo 3: O algoritmo de Dijkstra foi criado justamente para encontrar o caminho de menor custo entre um ponto de partida e um destino. Ele explora sempre o vértice mais próximo ainda não visitado e atualiza as distâncias, garantindo o menor caminho quando os custos não são negativos. Passo 4: Por que as outras estão erradas: B) escolher qualquer caminho não garante que ele seja o menor. C) contar passos serve para medir um caminho já percorrido, mas não diz qual dos caminhos possíveis é o menor. D) seguir sempre à direita (regra da mão direita) leva à saída em labirintos simples, mas pode gerar caminhos longos com muitas voltas. E) a força bruta testa todos os caminhos e até encontra o menor, mas é lenta e impraticável em labirintos grandes, então não é a melhor maneira. Passo 5: Conclusão: a alternativa A é a correta e coincide com o gabarito oficial. Observação: em labirintos sem custos diferentes, a busca em largura também resolve o problema, mas, entre as opções, o Dijkstra é a resposta mais adequada e geral.
💡 Dica: Considere as estratégias de busca em labirintos.
Alternativa por alternativa
Esse algoritmo é eficaz para encontrar o menor caminho em grafos.
O aluno acredita que qualquer caminho até a saída serve, sem perceber que a questão exige o menor caminho.
Por que engana: Escolher qualquer caminho, acreditando que a primeira opção é sempre a melhor, sem considerar a eficiência do percurso.
O aluno confunde medir um caminho com otimizar a escolha, achando que contar passos já resolve o problema de encontrar o menor trajeto entre várias opções.
O aluno acredita que a regra da mão direita garante o menor caminho, quando ela apenas garante chegar à saída em certos labirintos, podendo passar por trechos desnecessários.
O aluno pensa que, por testar todas as possibilidades, a força bruta é a melhor estratégia, ignorando que ela é lenta e impraticável em labirintos grandes.
Raio-X da questão
menor caminho labirinto
fixacao
algoritmos de busca · estruturas de dados
Revisar algoritmos de busca em grafos.
Escolher qualquer caminho, acreditando que a primeira opção é sempre a melhor, sem considerar a eficiência do percurso.
ciencia_tecnologia
tomada_decisao
cotidiano
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