dividir-para-conquistar.md

Dividir Para Conquistar

Dividir para conquistar é um paradigma de resolução de problemas que procurar subdivir o dominio para encontrar a solução em dominios menores. Ele funciona da seguinte forma:

1. Subdivide o domínio em subparts, normalmente na metade
2. Encontre a solução para os subproblemas
3. Junte a solução dos subproblemas em apenas uma

Alguns algoritmos e estrutura de dados conhecidos utilizam esta estrátegia em suas implementações, que é o caso da busca binária, do merge sort, da árvore binária de busca, e da heap.

Algums métodos da STL do C++ já implementam a busca binária de algumas forma, os metodos são:

• lower_bound
• upper_bound
• binary_search

Exercícios

1. UVA
   1. 10077 - The Stern-Brocot ...
   2. 10474 - Where is the Marble?
   3. 11876 - N + NOD (N)
2. URI
   1. 1520 - Screws and Nuts

Referências

HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.