I1M-0.0.1: Code for the Haskell course taught at the University od Seville.

LicenseCreative Commons
MaintainerJosé A. Alonso
Safe HaskellSafe
LanguageHaskell2010

I1M.DivideVenceras

Description

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 tema 15 del curso. Además, en el tema se incluye dos casos de aplicación del patrón:

Synopsis

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