I1M2014: Ejercicios de definiciones por comprensión
En la segunda parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los 12 primeros ejercicios de la 3ª relación sobre definiciones por comprensión.
Los ejercicios y su solución se muestran a continuación
|
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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- En esta relación se presentan ejercicios con definiciones por -- comprensión correspondientes al tema 5 cuyas transparencias se -- encuentran en -- http://www.cs.us.es/~jalonso/cursos/i1m-14/temas/tema-5.pdf -- -- Consta de dos partes: la primera con ejercicios resueltos del libro -- "Piensa en Haskell" http://bit.ly/1r2qcZk y la segunda con una -- colección de ejercicios propuestos. -- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- § Ejercicios resueltos -- -- --------------------------------------------------------------------- -- En el capítulo 2 del libro "Piensa en Haskell" http://bit.ly/1r2qcZk -- se encuentra una colección de ejercicios resueltos por comprensión. -- Concretamente, -- 1. Suma de los cuadrados de los n primeros números (p. 40) -- 2. Listas con un elemento replicado (p. 40) -- 3. Triángulos aritméticos (p. 40) -- 4. Números perfectos (p. 41) -- 5. Números abundantes (p. 42) -- 6. Problema 1 del proyecto Euler (p. 43) -- 7. Número de pares de naturales en un círculo (p. 44) -- 8. Aproximación del número e (p. 44) -- 9. Aproximación del límite (p. 46) -- 10. Cálculo del número π (p. 46) -- 11. Ternas pitagóricas (p. 47) -- 12. Problema 9 del Proyecto Euler (p. 48) -- 13. Producto escalar (p. 49) -- 14. Suma de pares de elementos consecutivos (p. 50) -- 15. Posiciones de un elemento en una lista (p. 50) -- 16. Representación densa de un polinomio representado dispersamente (p. 51) -- 17. Producto cartesiano (p. 51) -- 18. Consulta de bases de datos (p. 52) -- --------------------------------------------------------------------- -- § Ejercicios propuestos -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- subconjunto :: Eq a => [a] -> [a] -> Bool -- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de -- ys. por ejemplo, -- subconjunto [3,2,3] [2,5,3,5] == True -- subconjunto [3,2,3] [2,5,6,5] == False -- --------------------------------------------------------------------- subconjunto :: Eq a => [a] -> [a] -> Bool subconjunto xs ys = [x | x <- xs, x `elem` ys] == xs -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- iguales :: Eq a => [a] -> [a] -> Bool -- tal que (iguales xs ys) se verifica si xs e ys son iguales. Por -- ejemplo, -- iguales [3,2,3] [2,3] == True -- iguales [3,2,3] [2,3,2] == True -- iguales [3,2,3] [2,3,4] == False -- iguales [2,3] [4,5] == False -- --------------------------------------------------------------------- iguales :: Eq a => [a] -> [a] -> Bool iguales xs ys = subconjunto xs ys && subconjunto ys xs -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- union :: Eq a => [a] -> [a] -> [a] -- tal que (union xs ys) es la unión de los conjuntos xs e ys. Por -- ejemplo, -- union [3,2,5] [5,7,3,4] == [3,2,5,7,4] -- --------------------------------------------------------------------- union :: Eq a => [a] -> [a] -> [a] union xs ys = xs ++ [y | y <- ys, y `notElem` xs] -- --------------------------------------------------------------------- -- Nota. En los ejercicios de comprobación de propiedades, cuando se -- trata con igualdades es la igualdad conjuntista (definida por la -- función iguales) en lugar de la igualdad de lista (definida por ==) -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 4. Comprobar con QuickCheck que la unión es conmutativa. -- --------------------------------------------------------------------- -- La propiedad es prop_union_conmutativa :: [Int] -> [Int] -> Bool prop_union_conmutativa xs ys = iguales (union xs ys) (union ys xs) -- La comprobación es -- λ> quickCheck prop_union_conmutativa -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- interseccion :: Eq a => [a] -> [a] -> [a] -- tal que (interseccion xs ys) es la intersección de xs e ys. Por -- ejemplo, -- interseccion [3,2,5] [5,7,3,4] == [3,5] -- interseccion [3,2,5] [9,7,6,4] == [] -- --------------------------------------------------------------------- interseccion :: Eq a => [a] -> [a] -> [a] interseccion xs ys = [x | x <- xs, x `elem` ys] -- --------------------------------------------------------------------- -- Ejercicio 6. Comprobar con QuickCheck si se cumple la siguiente -- propiedad -- A ∪ (B ∩ C) = (A ∪ B) ∩ C -- donde se considera la igualdad como conjuntos. En el caso de que no -- se cumpla verificar el contraejemplo calculado por QuickCheck. -- --------------------------------------------------------------------- prop_union_interseccion :: [Int] -> [Int] -> [Int] -> Bool prop_union_interseccion xs ys zs = iguales (union xs (interseccion ys zs)) (interseccion (union xs ys) zs) -- La comprobación es -- λ> quickCheck prop_union_interseccion -- *** Failed! Falsifiable (after 3 tests and 2 shrinks): -- [0] -- [] -- [] -- -- Por tanto, la propiedad no se cumple y un contraejemplo es -- A = [0], B = [] y C = [] -- ya que entonces, -- A ∪ (B ∩ C) = [0] ∪ ([] ∩ []) = [0] ∪ [] = [0] -- (A ∪ B) ∩ C = ([0] ∪ []) ∩ [] = [0] ∩ [] = [] -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- diferencia :: Eq a => [a] -> [a] -> [a] -- tal que (diferencia xs ys) es la diferencia entre los conjuntos xs e -- ys. Por ejemplo, -- diferencia [3,2,5,6] [5,7,3,4] == [2,6] -- diferencia [3,2,5] [5,7,3,2] == [] -- --------------------------------------------------------------------- diferencia :: Eq a => [a] -> [a] -> [a] diferencia xs ys = [x | x <- xs, x `notElem` ys] -- --------------------------------------------------------------------- -- Ejercicio 8. Comprobar con QuickCheck si la diferencia es -- conmutativa. -- --------------------------------------------------------------------- prop_diferencia_conmutativa :: [Int] -> [Int] -> Bool prop_diferencia_conmutativa xs ys = iguales (diferencia xs ys) (diferencia ys xs) -- La comprobación es -- λ> quickCheck prop_diferencia_conmutativa -- *** Failed! Falsifiable (after 2 tests and 2 shrinks): -- [0] -- [] -- que es un contraejemplo, ya que -- [0] - [] = [0] -- [] - [0] = [] -- --------------------------------------------------------------------- -- Ejercicio 9. Comprobar con QuickCheck si se cumple la siguiente -- propiedad: A \ B ⊂ A -- --------------------------------------------------------------------- -- La propiedad es prop_diferencia_subconjunto :: [Int] -> [Int] -> Bool prop_diferencia_subconjunto xs ys = subconjunto (diferencia xs ys) xs -- La comprobación es -- λ> quickCheck prop_diferencia_subconjunto -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 10. Comprobar con QuickCheck si se cumple la siguiente -- propiedad: (A \ B) ∩ B = ∅. -- --------------------------------------------------------------------- -- La propiedad es prop_diferencia_interseccion :: [Int] -> [Int] -> Bool prop_diferencia_interseccion xs ys = interseccion (diferencia xs ys) ys == [] -- La comprobación es -- λ> quickCheck prop_diferencia_interseccion -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 11. Definir la función -- divisoresPrimos :: Int -> [Int] -- tal que (divisoresPrimos x) es la lista de los divisores primos de x. -- Por ejemplo, -- divisoresPrimos 40 == [2,5] -- divisoresPrimos 70 == [2,5,7] -- ------------------------------------------------------------------------ divisoresPrimos :: Int -> [Int] divisoresPrimos x = [n | n <- divisores x, primo n] -- (divisores n) es la lista de los divisores del número n. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] divisores :: Int -> [Int] divisores n = [x | x <- [1..n], n `mod` x == 0] -- (primo n) se verifica si n es primo. Por ejemplo, -- primo 30 == False -- primo 31 == True primo :: Int -> Bool primo n = divisores n == [1, n] -- --------------------------------------------------------------------- -- Ejercicio 12. Un número es libre de cuadrados si no es divisible el -- cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de -- cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 -- no es libre de cuadrados porque es divisible por 2^2. -- -- Definir la función -- libreDeCuadrados :: Int -> Bool -- tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. -- Por ejemplo, -- libreDeCuadrados 70 == True -- libreDeCuadrados 40 == False -- --------------------------------------------------------------------- -- 1ª definición: libreDeCuadrados :: Int -> Bool libreDeCuadrados x = x == product (divisoresPrimos x) -- 2ª definición libreDeCuadrados2 :: Int -> Bool libreDeCuadrados2 n = null [x | x <- [2..n], rem n (x^2) == 0] |