-- | -- Module : DivideVenceras -- Description : El patrón "divide y vencerás". -- License : Creative Commons -- Maintainer : José A. Alonso -- -- = El patrón "divide y vencerás" -- -- La técnica "divide y vencerás" consta de los siguientes pasos: -- -- 1. Dividir el problema en subproblemas menores. -- 2. Resolver por separado cada uno de los subproblemas; si los -- subproblemas son complejos, usar la misma técnica recursivamente; -- si son simples, resolverlos directamente. -- 3. 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 <http://bit.ly/1IstbhD tema 15> del curso. Además, en -- el tema se incluye dos casos de aplicación del patrón: -- -- * <http://bit.ly/1Istd99 la ordenación por mezcla> y -- * <http://bit.ly/1Istid7 la ordenación rápida>. module I1M.DivideVenceras (divideVenceras) where -- --------------------------------------------------------------------- -- El patrón de diseño "divide y vencerás" -- -- --------------------------------------------------------------------- -- La técnica "divide y vencerás" consta de los siguientes pasos: -- 1. Dividir el problema en subproblemas menores. -- 2. Resolver por separado cada uno de los subproblemas; si los -- subproblemas son complejos, usar la misma técnica recursivamente; -- si son simples, resolverlos directamente. -- 3. Combinar todas las soluciones de los subproblemas en una solución -- simple. -- | (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 divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s divideVenceras ind resuelve divide combina = dv' where dv' pb | ind pb = resuelve pb | otherwise = combina pb [dv' sp | sp <- divide pb]