I1M2013: Ejercicios de definiciones por comprensión (4)
En la clase de hoy del curso Informática (de 1º de Grado en Matemáticas) se han comentado las soluciones de los dos últimos ejercicios de la 4ª relación y de los 7 primeros de la 5ª relación. Ambas son sobre definiciones por comprensión.
Los ejercicios de la 4ª relación 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 |
-- --------------------------------------------------------------------- -- Ejercicio 20.1. Definir la función numDiv tal que (numDiv x) es el -- número de divisores del número natural x. Por ejemplo, -- numDiv 11 == 2 -- numDiv 12 == 6 -- --------------------------------------------------------------------- numDiv x = length [n | n <- [1..x], rem x n == 0] -- --------------------------------------------------------------------- -- Ejercicio 20.2. Definir la función entre tal que (entre a b c) es la -- lista de los naturales entre a y b con, al menos, c divisores. Por -- ejemplo, -- entre 11 16 5 == [12, 16] -- --------------------------------------------------------------------- entre a b c = [x | x <- [a..b], numDiv x >= c] -- --------------------------------------------------------------------- -- Ejercicio 21.1. Definir la función conPos tal que (conPos xs) es la -- lista obtenida a partir de xs especificando las posiciones de sus -- elementos. Por ejemplo, -- conPos [1,5,0,7] == [(1,0),(5,1),(0,2),(7,3)] -- --------------------------------------------------------------------- conPos xs = zip xs [0..] -- --------------------------------------------------------------------- -- Ejercicio 21.2. Definir la función tal que (pares cs) es la cadena -- formada por los caracteres en posición par de cs. Por ejemplo, -- pares "el cielo sobre berlin" == "e il or eln" -- --------------------------------------------------------------------- pares cs = [c | (c,n) <- conPos cs, even n] |
Los ejercicios de la 5ª relación 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 |
-- --------------------------------------------------------------------- -- Ejercicio 1.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 1.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) = length [1 | n <- [x,y,z], even n] -- --------------------------------------------------------------------- -- Ejercicio 1.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 1.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 2.1. (Problema 9 del Proyecto Euler). Una terna pitagórica -- es una terna de números naturales (a,b,c) tal que a<b<c y -- a^2+b^2=c^2. Por ejemplo (3,4,5) es una terna pitagórica. -- -- Definir la función -- ternasPitagoricas :: Integer -> [[Integer]] -- tal que (ternasPitagoricas x) es la lista de las ternas pitagóricas -- cuya suma es x. Por ejemplo, -- ternasPitagoricas 12 == [(3,4,5)] -- ternasPitagoricas 60 == [(10,24,26),(15,20,25)] -- --------------------------------------------------------------------- ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)] ternasPitagoricas x = [(a,b,c) | a <- [1..x], b <- [a+1..x], c <- [x-a-b], a^2 + b^2 == c^2] -- --------------------------------------------------------------------- -- Ejercicio 2.2. Definir la constante euler9 tal que euler9 es producto -- abc donde (a,b,c) es la única terna pitagórica tal que a+b+c=1000. -- Calcular el valor de euler9. -- --------------------------------------------------------------------- euler9 = a*b*c where (a,b,c) = head (ternasPitagoricas 1000) -- El cálculo del valor de euler9 es -- ghci> euler9 -- 31875000 -- --------------------------------------------------------------------- -- Ejercicio 3. 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 4. Definir, por comprensión, la función -- sumaConsecutivos :: [Int] -> [Int] -- tal que (sumaConsecutivos xs) es la suma de los pares de elementos -- consecutivos de la lista xs. Por ejemplo, -- sumaConsecutivos [3,1,5,2] == [4,6,7] -- sumaConsecutivos [3] == [] -- --------------------------------------------------------------------- sumaConsecutivos :: [Int] -> [Int] sumaConsecutivos xs = [x+y | (x,y) <- zip xs (tail xs)] -- --------------------------------------------------------------------- -- Ejercicio 5. 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 6. Los polinomios pueden representarse de forma dispersa o -- densa. Por ejemplo, el polinomio 6x^4-5x^2+4x-7 se puede representar -- de forma dispersa por [6,0,-5,4,-7] y de forma densa por -- [(4,6),(2,-5),(1,4),(0,-7)]. -- -- Definir la función -- densa :: [Int] -> [(Int,Int)] -- tal que (densa xs) es la representación densa del polinomio cuya -- representación dispersa es xs. Por ejemplo, -- densa [6,0,-5,4,-7] == [(4,6),(2,-5),(1,4),(0,-7)] -- densa [6,0,0,3,0,4] == [(5,6),(2,3),(0,4)] -- --------------------------------------------------------------------- densa :: [Int] -> [(Int,Int)] densa xs = [(x,y) | (x,y) <- zip [n-1,n-2..0] xs, y /= 0] where n = length xs -- --------------------------------------------------------------------- -- Ejercicio 7. 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] |