| License | Creative Commons |
|---|---|
| Maintainer | José A. Alonso |
| Safe Haskell | Safe |
| Language | Haskell2010 |
I1M.DivideVenceras
Description
El patrón "divide y vencerás"
La técnica "divide y vencerás" consta de los siguientes pasos:
- Dividir el problema en subproblemas menores.
- Resolver por separado cada uno de los subproblemas; si los subproblemas son complejos, usar la misma técnica recursivamente; si son simples, resolverlos directamente.
- Combinar todas las soluciones de los subproblemas en una solución simple.
Este módulo contiene la definición del patrón "divide y vencerás" estudiado en el tema 15 del curso. Además, en el tema se incluye dos casos de aplicación del patrón:
- divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s
Documentation
divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s Source
(divideVenceras ind resuelve divide combina pbInicial) resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde
- (ind pb) se verifica si el problema pb es indivisible
- (resuelve pb) es la solución del problema indivisible pb
- (divide pb) es la lista de subproblemas de pb
- (combina pb ss) es la combinación de las soluciones ss de los subproblemas del problema pb.
- pbInicial es el problema inicial