Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUNDATEC 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq893852
Banca
FUNDATEC
Órgão
IF-RS
Ano
2023
Nível
Superior
Cargo
Professor - Informática: Programação, Estrutura de Dados e Análise de Algoritimos
Muitos algoritmos úteis são recursivos em sua estrutura, ou seja, para resolver um dado problema, eles chamam a si mesmos recursivamente uma ou mais vezes para lidar com subproblemas relacionados. Em geral, esses algoritmos seguem uma abordagem chamada:
ACombinar e dividir.
BConquistar para dividir.
CDividir para conquistar.
DCombinar para dividir.
EDividir para combinar.
Revelar gabarito e comentário▾
GabaritoC — Dividir para conquistar.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos recursivos: abordagem "Dividir para Conquistar"
Gabarito: letra C. A abordagem clássica para algoritmos recursivos que resolvem problemas dividindo-os em subproblemas menores, resolvendo-os recursivamente e combinando as soluções é denominada "Dividir para Conquistar" (do inglês divide and conquer). As demais alternativas invertem ou embaralham os termos, não correspondendo ao conceito consagrado na computação.
A estratégia dividir para conquistar é amplamente utilizada em algoritmos como Merge Sort, Quick Sort, busca binária, torre de Hanói, entre outros. Seus três passos fundamentais são:
Dividir: o problema original é quebrado em subproblemas menores e semelhantes ao original.
Conquistar: os subproblemas são resolvidos recursivamente. Quando são suficientemente pequenos, resolvem-se de forma direta (caso base).
Combinar: as soluções dos subproblemas são combinadas para formar a solução do problema original.
PEGA ESSA DICA!
A banca pode tentar confundir invertendo a ordem ou trocando os verbos. Lembre-se do nome consagrado: Dividir para Conquistar. A ordem importa: primeiro se divide, depois se conquista. Memorize os três passos: dividir, conquistar, combinar.
1DividirQuebrar em subproblemas
2ConquistarResolver recursivamente
3CombinarUnir as soluções
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
"Combinar e dividir" inverte a ordem do processo: a combinação é a última etapa, não a primeira. O termo correto começa com "dividir".
Alternativa B — ❌ Incorreta
"Conquistar para dividir" também inverte a ordem e o sentido: conquistar (resolver) antes de dividir não faz sentido na estratégia. Primeiro divide-se, depois conquista-se.
Alternativa C — ✅ Correta ⟵ GABARITO
"Dividir para conquistar" reflete exatamente a abordagem: divide-se o problema em partes menores e, após resolver cada parte (conquistar), combina-se o resultado. É a nomenclatura clássica e amplamente aceita em Ciência da Computação.
Alternativa D — ❌ Incorreta
"Combinar para dividir" é o oposto do que ocorre: combinar é a última fase, não um pré-requisito para dividir. A ordem é dividir → conquistar → combinar.
Alternativa E — ❌ Incorreta
"Dividir para combinar" omite a etapa de conquistar (resolver os subproblemas). A combinação só faz sentido após os subproblemas terem sido resolvidos, o que caracteriza a "conquista". Portanto, o nome completo é "dividir para conquistar".
Conclusão: A única alternativa que nomeia corretamente a abordagem de algoritmos recursivos que quebram o problema em subproblemas é a letra C.