Algoritmo 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.
Definir la función
|
1 2 3 4 5 6 |
divideVenceras :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s |
tal que divideVenceras ind resuelve divide combina pbInicial resuelve el problema pbInicial mediante la técnica de divide y vencerás, donde
ind pbse verifica si el problemapbes indivisibleresuelve pbes la solución del problema indivisiblepbdivide pbes la lista de subproblemas depbcombina pb sses la combinación de las solucionesssde los subproblemas del problemapb.pbIniciales el problema inicial
Usando la función DivideVenceras, definir las funciones
|
1 2 |
ordenaPorMezcla :: Ord a => [a] -> [a] ordenaRapida :: Ord a => [a] -> [a] |
tales que
ordenaPorMezcla xses la lista obtenida ordenandoxspor el procedimiento de ordenación por mezcla. Por ejemplo,
|
1 2 |
λ> ordenaPorMezcla [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9] |
ordenaRapida xses la lista obtenida ordenandoxspor el procedimiento de ordenación rápida. Por ejemplo,
|
1 2 |
λ> ordenaRapida [3,1,4,1,5,9,2,8] [1,1,2,3,4,5,8,9] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
module DivideVenceras (divideVenceras) where import Test.Hspec (Spec, hspec, it, shouldBe) 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] ordenaPorMezcla :: Ord a => [a] -> [a] ordenaPorMezcla = divideVenceras ind id divide combina where ind xs = length xs <= 1 divide xs = [take n xs, drop n xs] where n = length xs `div` 2 combina _ [l1,l2] = mezcla l1 l2 -- (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo, -- mezcla [1,3] [2,4,6] == [1,2,3,4,6] mezcla :: Ord a => [a] -> [a] -> [a] mezcla [] b = b mezcla a [] = a mezcla a@(x:xs) b@(y:ys) | x <= y = x : mezcla xs b | otherwise = y : mezcla a ys ordenaRapida :: Ord a => [a] -> [a] ordenaRapida = divideVenceras ind id divide combina where ind xs = length xs <= 1 divide (x:xs) = [[ y | y <- xs, y <= x], [ y | y <- xs, y > x]] combina (x:_) [l1,l2] = l1 ++ [x] ++ l2 -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ ordenaPorMezcla [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9] it "e2" $ ordenaRapida [3,1,4,1,5,9,2,8] `shouldBe` [1,1,2,3,4,5,8,9] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- -- Finished in 0.0004 seconds -- 2 examples, 0 failures |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
from typing import Callable, TypeVar P = TypeVar('P') S = TypeVar('S') def divideVenceras(ind: Callable[[P], bool], resuelve: Callable[[P], S], divide: Callable[[P], list[P]], combina: Callable[[P, list[S]], S], p: P) -> S: def dv(pb: P) -> S: if ind(pb): return resuelve(pb) return combina(pb, [dv(sp) for sp in divide(pb)]) return dv(p) def ordenaPorMezcla(xs: list[int]) -> list[int]: def ind(xs: list[int]) -> bool: return len(xs) <= 1 def divide(xs: list[int]) -> list[list[int]]: n = len(xs) // 2 return [xs[:n], xs[n:]] def combina(_: list[int], xs: list[list[int]]) -> list[int]: return mezcla(xs[0], xs[1]) return divideVenceras(ind, lambda x: x, divide, combina, xs) # (mezcla xs ys) es la lista obtenida mezclando xs e ys. Por ejemplo, # mezcla([1,3], [2,4,6]) == [1,2,3,4,6] def mezcla(a: list[int], b: list[int]) -> list[int]: if not a: return b if not b: return a if a[0] <= b[0]: return [a[0]] + mezcla(a[1:], b) return [b[0]] + mezcla(a, b[1:]) def ordenaRapida(xs: list[int]) -> list[int]: def ind(xs: list[int]) -> bool: return len(xs) <= 1 def divide(xs: list[int]) -> list[list[int]]: x, *xs = xs return [[y for y in xs if y <= x], [y for y in xs if y > x]] def combina(xs: list[int], ys: list[list[int]]) -> list[int]: x = xs[0] return ys[0] + [x] + ys[1] return divideVenceras(ind, lambda x: x, divide, combina, xs) # Verificación # ============ def test_divideVenceras() -> None: assert ordenaPorMezcla([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9] assert ordenaRapida([3,1,4,1,5,9,2,8]) == [1,1,2,3,4,5,8,9] print("Verificado") # La verificación es # >>> test_divideVenceras() # Verificado |