Se dice que un x n\u00famero se encuentra entre dos conjuntos xs e ys si x es divisible por todos los elementos de xs y todos los elementos de zs son divisibles por x. Por ejemplo, 12 se encuentra entre los conjuntos {2, 6} y {24, 36}.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n entreDosConjuntos :: [Int] -> [Int] -> [Int]\n<\/pre>\ntal que (entreDosConjuntos xs ys) es la lista de elementos entre xs e ys (se supone que xs e ys son listas no vac\u00edas de n\u00fameros enteros positivos). Por ejemplo,<\/p>\n
\n entreDosConjuntos [2,6] [24,36] == [6,12]\n entreDosConjuntos [2,4] [32,16,96] == [4,8,16]\n<\/pre>\nOtros ejemplos<\/p>\n
\n \u03bb> (xs,a) = ([1..15],product xs) \n \u03bb> length (entreDosConjuntos5 xs [a,2*a..10*a])\n 270\n \u03bb> (xs,a) = ([1..16],product xs) \n \u03bb> length (entreDosConjuntos5 xs [a,2*a..10*a])\n 360\n<\/pre>\nSoluciones<\/h4>\n\nimport Test.QuickCheck \n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nentreDosConjuntos :: [Int] -> [Int] -> [Int]\nentreDosConjuntos xs ys =\n [z | z <- [a..b]\n , and [z `mod` x == 0 | x <- xs]\n , and [y `mod` z == 0 | y <- ys]]\n where a = maximum xs\n b = minimum ys\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nentreDosConjuntos2 :: [Int] -> [Int] -> [Int]\nentreDosConjuntos2 xs ys =\n [z | z <- [a..b]\n , all (`divideA` z) xs\n , all (z `divideA`) ys]\n where a = mcmL xs\n b = mcdL ys\n\n-- mcmL [2,3,18] == 18\n-- mcmL [2,3,15] == 30\nmcdL :: [Int] -> Int\nmcdL [x] = x\nmcdL (x:xs) = gcd x (mcdL xs)\n\n-- mcmL [12,30,18] == 6\n-- mcmL [12,30,14] == 2\nmcmL :: [Int] -> Int\nmcmL [x] = x\nmcmL (x:xs) = lcm x (mcmL xs)\n\ndivideA :: Int -> Int -> Bool\ndivideA x y = y `mod` x == 0\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nentreDosConjuntos3 :: [Int] -> [Int] -> [Int]\nentreDosConjuntos3 xs ys =\n [z | z <- [a..b]\n , all (`divideA` z) xs\n , all (z `divideA`) ys]\n where a = mcmL2 xs\n b = mcdL2 ys\n\n-- Definici\u00f3n equivalente\nmcdL2 :: [Int] -> Int\nmcdL2 = foldl1 gcd\n\n-- Definici\u00f3n equivalente\nmcmL2 :: [Int] -> Int\nmcmL2 = foldl1 lcm\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nentreDosConjuntos4 :: [Int] -> [Int] -> [Int]\nentreDosConjuntos4 xs ys =\n [z | z <- [a,a+a..b]\n , z `divideA` b] \n where a = mcmL2 xs\n b = mcdL2 ys\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nentreDosConjuntos5 :: [Int] -> [Int] -> [Int]\nentreDosConjuntos5 xs ys =\n filter (`divideA` b) [a,a+a..b]\n where a = mcmL2 xs\n b = mcdL2 ys\n\n-- Equivalencia\n-- ============\n\n-- Para comprobar la equivalencia se define el tipo de listas no vac\u00edas\n-- de n\u00fameros enteros positivos:\nnewtype ListaNoVaciaDePositivos = L [Int]\n deriving Show\n\n-- genListaNoVaciaDePositivos es un generador de listas no vaci\u00f3as de\n-- enteros positivos. Por ejemplo,\n-- \u03bb> sample genListaNoVaciaDePositivos\n-- L [1]\n-- L [1,2,2]\n-- L [4,3,4]\n-- L [1,6,5,2,4]\n-- L [2,8]\n-- L [11]\n-- L [13,2,3]\n-- L [7,3,9,15,11,12,13,3,9,6,13,3]\n-- L [16,2,11,10,6,5,16,4,1,15,9,11,8,15,2,15,7]\n-- L [5,4,9,13,5,6,7]\n-- L [7,4,6,12,2,11,6,14,14,13,14,11,6,2,18,8,16,2,13,9]\ngenListaNoVaciaDePositivos :: Gen ListaNoVaciaDePositivos\ngenListaNoVaciaDePositivos = do\n x <- arbitrary\n xs <- arbitrary\n return (L (map ((+1) . abs) (x:xs)))\n\n-- Generaci\u00f3n arbitraria de listas no vac\u00edas de enteros positivos.\ninstance Arbitrary ListaNoVaciaDePositivos where\n arbitrary = genListaNoVaciaDePositivos\n\n-- La propiedad es\nprop_entreDosConjuntos_equiv ::\n ListaNoVaciaDePositivos\n -> ListaNoVaciaDePositivos\n -> Bool\nprop_entreDosConjuntos_equiv (L xs) (L ys) =\n entreDosConjuntos xs ys == entreDosConjuntos2 xs ys &&\n entreDosConjuntos xs ys == entreDosConjuntos3 xs ys &&\n entreDosConjuntos xs ys == entreDosConjuntos4 xs ys &&\n entreDosConjuntos xs ys == entreDosConjuntos5 xs ys \n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_entreDosConjuntos_equiv\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> (xs,a) = ([1..10],product xs) \n-- \u03bb> length (entreDosConjuntos xs [a,2*a..10*a])\n-- 36\n-- (5.08 secs, 4,035,689,200 bytes)\n-- \u03bb> length (entreDosConjuntos2 xs [a,2*a..10*a])\n-- 36\n-- (3.75 secs, 2,471,534,072 bytes)\n-- \u03bb> length (entreDosConjuntos3 xs [a,2*a..10*a])\n-- 36\n-- (3.73 secs, 2,471,528,664 bytes)\n-- \u03bb> length (entreDosConjuntos4 xs [a,2*a..10*a])\n-- 36\n-- (0.01 secs, 442,152 bytes)\n-- \u03bb> length (entreDosConjuntos5 xs [a,2*a..10*a])\n-- 36\n-- (0.00 secs, 374,824 bytes)\n<\/pre>\nReferencia<\/h4>\n