Respostas

Anotacoes

Respostas das Questões 1 a 4 Questão 1 Descreva as etapas da abordagem Divisão e Conquista. A abordagem Divisão e Conquista segue três etapas principais: 1. Dividir: divide-se o problema em subproblemas menores. 2. Conquistar: resolve-se os subproblemas recursivamente. 3. Combinar: combina-se as soluções dos subproblemas para obter a solução final. Exemplo clássico: Merge Sort (Ordenação por Intercalação). Questão 2 Escreva uma maneira para resolver o problema do cálculo da exponenciação por meio da Divisão e Conquista. A técnica é chamada de exponenciação rápida: - Se n for par: a^n = (a^(n/2))^2 - Se n for ímpar: a^n = a * (a^((n-1)/2))^2 Pseudocódigo: def expRapida(a, n): if n == 0: return 1 temp = expRapida(a, n // 2) if n % 2 == 0: return temp * temp else: return a * temp * temp Questão 3 Quais são as três formas principais de aplicar Transformação & Conquista? 1. Aprimoramento da instância: - Transforma a instância em uma versão equivalente mais fácil de resolver. 2. Aprimoramento da representação: - Muda a forma de representar os dados para facilitar a solução. 3. Pré-processamento: - Executa um passo de preparação (como ordenação) antes da resolução do problema. Questão 4 C...