I1M2011: Ejercicios de definiciones por comprensión en Haskell (1)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios de la 3ª relación que trata sobre definiciones por comprensión.
Los ejercicios, y sus soluciones, 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 |
-- I1M 2011-12: Rel_3_sol.hs (21 de Octubre de 2011) -- Definiciones por comprensión (1) -- Departamento de Ciencias de la Computación e I.A. -- Universidad de Sevilla -- ===================================================================== -- --------------------------------------------------------------------- -- 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-11/temas/tema-5.pdf -- En concreto, se estudian funciones para calcular -- * la suma de los cuadrados de los n primeros números, -- * listas con un elemento replicado, -- * ternas pitagóricas, -- * números perfectos, -- * producto cartesiano, -- * posiciones de un elemento en una lista, -- * producto escalar y -- * la solución del problema 1 del proyecto Euler. -- --------------------------------------------------------------------- -- Ejercicio 1. Definir, por comprensión, la función -- sumaDeCuadrados :: Integer -> Integer -- tal que (sumaDeCuadrados n) es la suma de los cuadrados de los -- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo, -- sumaDeCuadrados 3 == 14 -- sumaDeCuadrados 100 == 338350 -- --------------------------------------------------------------------- sumaDeCuadrados :: Integer -> Integer sumaDeCuadrados n = sum [x^2 | x <- [1..n]] -- --------------------------------------------------------------------- -- Ejercicio 2. Definir por comprensión la función -- replica :: Int -> a -> [a] -- tal que (replica n x) es la lista formada por n copias del elemento -- x. Por ejemplo, -- replica 3 True == [True, True, True] -- Nota: La función replica es equivalente a la predefinida replicate. -- --------------------------------------------------------------------- replica :: Int -> a -> [a] replica n x = [x | _ <- [1..n]] -- --------------------------------------------------------------------- -- Ejercicio 3.1. Una terna (x,y,z) de enteros positivos es pitagórica -- si x^2 + y^2 = z^2. Usando una lista por comprensión, definir la -- función -- pitagoricas :: Int -> [(Int,Int,Int)] -- tal que (pitagoricas n) es la lista de todas las ternas pitagóricas -- cuyas componentes están entre 1 y n. Por ejemplo, -- pitagoricas 10 == [(3,4,5),(4,3,5),(6,8,10),(8,6,10)] -- --------------------------------------------------------------------- pitagoricas :: Int -> [(Int,Int,Int)] pitagoricas n = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], x^2 + y^2 == z^2] -- --------------------------------------------------------------------- -- Ejercicio 3.2. Definir la función -- numeroDePares :: (Int,Int,Int) -> Int -- tal que (numeroDePares t) es el número de elementos pares de la terna -- t. Por ejemplo, -- numeroDePares (3,5,7) == 0 -- numeroDePares (3,6,7) == 1 -- numeroDePares (3,6,4) == 2 -- numeroDePares (4,6,4) == 3 -- --------------------------------------------------------------------- numeroDePares :: (Int,Int,Int) -> Int numeroDePares (x,y,z) = sum [1 | n <- [x,y,z], even n] -- --------------------------------------------------------------------- -- Ejercicio 3.3. Definir la función -- conjetura :: Int -> Bool -- tal que (conjetura n) se verifica si todas las ternas pitagóricas -- cuyas componentes están entre 1 y n tiene un número impar de números -- pares. Por ejemplo, -- conjetura 10 == True -- --------------------------------------------------------------------- conjetura :: Int -> Bool conjetura n = and [odd (numeroDePares t) | t <- pitagoricas n] -- --------------------------------------------------------------------- -- Ejercicio 3.4. Demostrar la conjetura para todas las ternas -- pitagóricas. -- --------------------------------------------------------------------- -- Sea (x,y,z) una terna pitagórica. Entonces x^2+y^2=z^2. Pueden darse -- 4 casos: -- -- Caso 1: x e y son pares. Entonces, x^2, y^2 y z^2 también lo -- son. Luego el número de componentes pares es 3 que es impar. -- -- Caso 2: x es par e y es impar. Entonces, x^2 es par, y^2 es impar y -- z^2 es impar. Luego el número de componentes pares es 1 que es impar. -- -- Caso 3: x es impar e y es par. Análogo al caso 2. -- -- Caso 4: x e y son impares. Entonces, x^2 e y^2 también son impares y -- z^2 es par. Luego el número de componentes pares es 1 que es impar. -- --------------------------------------------------------------------- -- Ejercicio 4. Un entero positivo es perfecto si es igual a la suma de -- sus factores, excluyendo el propio número. -- -- Definir por comprensión la función -- perfectos :: Int -> [Int] -- tal que (perfectos n) es la lista de todos los números perfectos -- menores que n. Por ejemplo, -- perfectos 500 == [6,28,496] -- Indicación: Usar la función factores del tema 5. -- --------------------------------------------------------------------- -- La función factores del tema es factores :: Int -> [Int] factores n = [x | x <- [1..n], n `mod` x == 0] -- La definición es perfectos :: Int -> [Int] perfectos n = [x | x <- [1..n], sum (init (factores x)) == x] -- --------------------------------------------------------------------- -- Ejercicio 5. La función -- pares :: [a] -> [b] -> [(a,b)] -- definida por -- pares xs ys = [(x,y) | x <- xs, y <- ys] -- toma como argumento dos listas y devuelve la listas de los pares con -- el primer elemento de la primera lista y el segundo de la -- segunda. Por ejemplo, -- ghci> pares [1..3] [4..6] -- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)] -- -- Definir, usando dos listas por comprensión con un generador cada una, -- la función -- pares' :: [a] -> [b] -> [(a,b)] -- tal que pares' sea equivalente a pares. -- -- Indicación: Utilizar la función predefinida concat y encajar una -- lista por comprensión dentro de la otra. -- --------------------------------------------------------------------- -- La definición de pares es pares :: [a] -> [b] -> [(a,b)] pares xs ys = [(x,y) | x <- xs, y <- ys] -- La redefinición de pares es pares' :: [a] -> [b] -> [(a,b)] pares' xs ys = concat [[(x,y) | y <- ys] | x <- xs] -- --------------------------------------------------------------------- -- Ejercicio 6. En el tema se ha definido la función -- posiciones :: Eq a => a -> [a] -> [Int] -- tal que (posiciones x xs) es la lista de las posiciones ocupadas por -- el elemento x en la lista xs. Por ejemplo, -- posiciones 5 [1,5,3,5,5,7] == [1,3,4] -- -- Definir, usando la función busca (definida en el tema 5), la función -- posiciones' :: Eq a => a -> [a] -> [Int] -- tl que posiciones' sea equivalente a posiciones. -- --------------------------------------------------------------------- -- La definición de posiciones es posiciones :: Eq a => a -> [a] -> [Int] posiciones x xs = [i | (x',i) <- zip xs [0..n], x == x'] where n = length xs - 1 -- La definición de busca es busca :: Eq a => a -> [(a, b)] -> [b] busca c t = [v | (c', v) <- t, c' == c] -- La redefinición de posiciones es posiciones' :: Eq a => a -> [a] -> [Int] posiciones' x xs = busca x (zip xs [0..]) -- --------------------------------------------------------------------- -- Ejercicio 7. El producto escalar de dos listas de enteros xs y ys de -- longitud n viene dado por la suma de los productos de los elementos -- correspondientes. -- -- Definir por comprensión la función -- productoEscalar :: [Int] -> [Int] -> Int -- tal que (productoEscalar xs ys) es el producto escalar de las listas -- xs e ys. Por ejemplo, -- productoEscalar [1,2,3] [4,5,6] == 32 -- --------------------------------------------------------------------- productoEscalar :: [Int] -> [Int] -> Int productoEscalar xs ys = sum [x*y | (x,y) <- zip xs ys] -- --------------------------------------------------------------------- -- Ejercicio 8 (Problema 1 del proyecto Euler) Definir la función -- euler1 :: Integer -> Integer -- (euler1 n) es la suma de todos los múltiplos de 3 ó 5 menores que -- n. Por ejemplo, -- euler1 10 == 23 -- -- Calcular la suma de todos los múltiplos de 3 ó 5 menores que 1000. -- --------------------------------------------------------------------- euler1 :: Integer -> Integer euler1 n = sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5] where multiplo x y = mod x y == 0 -- Cálculo: -- ghci> euler1 1000 -- 233168 |