Entre dos conjuntos
Se dice que un x número 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}.
Definir la función
|
1 |
entreDosConjuntos :: [Int] -> [Int] -> [Int] |
tal que (entreDosConjuntos xs ys) es la lista de elementos entre xs e ys (se supone que xs e ys son listas no vacías de números enteros positivos). Por ejemplo,
|
1 2 |
entreDosConjuntos [2,6] [24,36] == [6,12] entreDosConjuntos [2,4] [32,16,96] == [4,8,16] |
Otros ejemplos
|
1 2 3 4 5 6 |
λ> (xs,a) = ([1..15],product xs) λ> length (entreDosConjuntos5 xs [a,2*a..10*a]) 270 λ> (xs,a) = ([1..16],product xs) λ> length (entreDosConjuntos5 xs [a,2*a..10*a]) 360 |
Soluciones
|
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
import Test.QuickCheck -- 1ª solución -- =========== entreDosConjuntos :: [Int] -> [Int] -> [Int] entreDosConjuntos xs ys = [z | z <- [a..b] , and [z `mod` x == 0 | x <- xs] , and [y `mod` z == 0 | y <- ys]] where a = maximum xs b = minimum ys -- 2ª solución -- =========== entreDosConjuntos2 :: [Int] -> [Int] -> [Int] entreDosConjuntos2 xs ys = [z | z <- [a..b] , all (`divideA` z) xs , all (z `divideA`) ys] where a = mcmL xs b = mcdL ys -- mcmL [2,3,18] == 18 -- mcmL [2,3,15] == 30 mcdL :: [Int] -> Int mcdL [x] = x mcdL (x:xs) = gcd x (mcdL xs) -- mcmL [12,30,18] == 6 -- mcmL [12,30,14] == 2 mcmL :: [Int] -> Int mcmL [x] = x mcmL (x:xs) = lcm x (mcmL xs) divideA :: Int -> Int -> Bool divideA x y = y `mod` x == 0 -- 3ª solución -- =========== entreDosConjuntos3 :: [Int] -> [Int] -> [Int] entreDosConjuntos3 xs ys = [z | z <- [a..b] , all (`divideA` z) xs , all (z `divideA`) ys] where a = mcmL2 xs b = mcdL2 ys -- Definición equivalente mcdL2 :: [Int] -> Int mcdL2 = foldl1 gcd -- Definición equivalente mcmL2 :: [Int] -> Int mcmL2 = foldl1 lcm -- 4ª solución -- =========== entreDosConjuntos4 :: [Int] -> [Int] -> [Int] entreDosConjuntos4 xs ys = [z | z <- [a,a+a..b] , z `divideA` b] where a = mcmL2 xs b = mcdL2 ys -- 5ª solución -- =========== entreDosConjuntos5 :: [Int] -> [Int] -> [Int] entreDosConjuntos5 xs ys = filter (`divideA` b) [a,a+a..b] where a = mcmL2 xs b = mcdL2 ys -- Equivalencia -- ============ -- Para comprobar la equivalencia se define el tipo de listas no vacías -- de números enteros positivos: newtype ListaNoVaciaDePositivos = L [Int] deriving Show -- genListaNoVaciaDePositivos es un generador de listas no vacióas de -- enteros positivos. Por ejemplo, -- λ> sample genListaNoVaciaDePositivos -- L [1] -- L [1,2,2] -- L [4,3,4] -- L [1,6,5,2,4] -- L [2,8] -- L [11] -- L [13,2,3] -- L [7,3,9,15,11,12,13,3,9,6,13,3] -- L [16,2,11,10,6,5,16,4,1,15,9,11,8,15,2,15,7] -- L [5,4,9,13,5,6,7] -- L [7,4,6,12,2,11,6,14,14,13,14,11,6,2,18,8,16,2,13,9] genListaNoVaciaDePositivos :: Gen ListaNoVaciaDePositivos genListaNoVaciaDePositivos = do x <- arbitrary xs <- arbitrary return (L (map ((+1) . abs) (x:xs))) -- Generación arbitraria de listas no vacías de enteros positivos. instance Arbitrary ListaNoVaciaDePositivos where arbitrary = genListaNoVaciaDePositivos -- La propiedad es prop_entreDosConjuntos_equiv :: ListaNoVaciaDePositivos -> ListaNoVaciaDePositivos -> Bool prop_entreDosConjuntos_equiv (L xs) (L ys) = entreDosConjuntos xs ys == entreDosConjuntos2 xs ys && entreDosConjuntos xs ys == entreDosConjuntos3 xs ys && entreDosConjuntos xs ys == entreDosConjuntos4 xs ys && entreDosConjuntos xs ys == entreDosConjuntos5 xs ys -- La comprobación es -- λ> quickCheck prop_entreDosConjuntos_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> (xs,a) = ([1..10],product xs) -- λ> length (entreDosConjuntos xs [a,2*a..10*a]) -- 36 -- (5.08 secs, 4,035,689,200 bytes) -- λ> length (entreDosConjuntos2 xs [a,2*a..10*a]) -- 36 -- (3.75 secs, 2,471,534,072 bytes) -- λ> length (entreDosConjuntos3 xs [a,2*a..10*a]) -- 36 -- (3.73 secs, 2,471,528,664 bytes) -- λ> length (entreDosConjuntos4 xs [a,2*a..10*a]) -- 36 -- (0.01 secs, 442,152 bytes) -- λ> length (entreDosConjuntos5 xs [a,2*a..10*a]) -- 36 -- (0.00 secs, 374,824 bytes) |
Referencia
Este ejercicio está basado en el problema Between two sets de HackerRank.
Pensamiento
Las razones no se transmiten, se engendran, por cooperación, en el diálogo.
Antonio Machado
6 Comentarios