Projeto e Análise de Algoritmos

Exercícios de Dividir e Conquistar

Prof. Rodrigo de Barros Paes

rodrigo@ic.ufal.br

​

https://sites.google.com/site/ldsicufal/disciplinas/projeto-e-analise-de-algoritmos

Instruções

1. Resolva o problema usando sempre dividir e conquistar. Mesmo quando você pensou em alguma outra forma de resolver.
2. Submeta ao Online Judge e verifique se você realmente acertou.
3. Não procure pela solução do problema na Internet.
4. Faça a análise da sua solução
1. Monte a equação de recorrência
2. Descubra o Big O
5. Divirta-se fazendo isso!

Problemas

UVA 10611 - The Playboy Chimp

UVA 11057 - Exact Sum

UVA 12032 - The Monkey and the Oiled Bamboo (Rodrigo, olhe isso: discutir essa questão em sala)

UVA 11935 - Through the Desert

UVA 10341 - Solve IT (mostrar tbm)

​

UVA 11057 - Exact Sum

• 3 Soluções
• Dividir e conquistar
• https://github.com/r0drigopaes/paa/blob/master/uva12032.cpp
• Double Pointer
• https://github.com/r0drigopaes/paa/blob/master/uva_11057_double_pointer.py
• E uma outra em O(n)
• https://github.com/r0drigopaes/paa/blob/master/uva_11057_On.py

Mais exercícios

Instruções

Pense em como você aplicará dividir e conquistar

Projete (implemente)

Analise a sua solução

Exercício 1

http://www.practice.geeksforgeeks.org/problem-page.php?pid=896

Dica: Se somente um elemento está faltando, é possível encontrar a diferença da PA fazendo:

(A_n - A₀)/n

, onde n é o número elementos dados, ou seja, sem contar o elemento faltante.

Exemplo:

2, 4, 6, 10

diff = (10-2)/4

Exercício 2

http://www.practice.geeksforgeeks.org/problem-page.php?pid=897

Como usar dividir e conquistar?

Exercício 3

http://www.practice.geeksforgeeks.org/problem-page.php?pid=819

Fazer usando D&Q

Exercício 4

Fonte: Stanford Univertisy

Exercício 5

http://www.geeksforgeeks.org/divide-and-conquer-set-6-tiling-problem/

Esse aqui o foco será treinar recursão, matrizes e um pouco de implementação. A solução está dada na página.