I1M2018: 2º examen de programación funcional con Haskell
Hoy se ha realizado el 2º examen del curso de Informática (de 1º de Grado en Matemáticas). 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 |
-- Informática (1º del Grado en Matemáticas, Grupo 4) -- 2º examen de evaluación continua (19 de diciembre de 2018) -- --------------------------------------------------------------------- -- Nota: La puntuación de cada ejercicio es 2.5 puntos. import Data.Char import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. Se dice que un número natural n es una colina si su -- primer dígito es igual a su último dígito, los primeros dígitos son -- estrictamente creciente hasta llegar al máximo, el máximo se puede -- repetir y los dígitos desde el máximo al final son estrictamente -- decrecientes. -- -- Definir la función -- esColina :: Integer -> Bool -- tal que (esColina n) se verifica si n es un número colina. Por -- ejemplo, -- esColina 12377731 == True -- esColina 1237731 == True -- esColina 123731 == True -- esColina 122731 == False -- esColina 12377730 == False -- esColina 12374731 == False -- esColina 12377730 == False -- esColina 10377731 == False -- esColina 12377701 == False -- esColina 33333333 == True -- --------------------------------------------------------------------- -- 1ª definición -- ============= esColina :: Integer -> Bool esColina n = head ds == last ds && esCreciente xs && esDecreciente ys where ds = digitos n m = maximum ds xs = takeWhile (<m) ds ys = dropWhile (==m) (dropWhile (<m) ds) -- (digitos n) es la lista de los dígitos de n. Por ejemplo, -- digitos 425 == [4,2,5] digitos :: Integer -> [Int] digitos n = map digitToInt (show n) -- (esCreciente xs) se verifica si la lista xs es estrictamente -- creciente. Por ejemplo, -- esCreciente [2,4,7] == True -- esCreciente [2,2,7] == False -- esCreciente [2,1,7] == False esCreciente :: [Int] -> Bool esCreciente xs = and [x < y | (x,y) <- zip xs (tail xs)] -- (esDecreciente xs) se verifica si la lista xs es estrictamente -- decreciente. Por ejemplo, -- esDecreciente [7,4,2] == True -- esDecreciente [7,2,2] == False -- esDecreciente [7,1,2] == False esDecreciente :: [Int] -> Bool esDecreciente xs = and [x > y | (x,y) <- zip xs (tail xs)] -- 2ª definición -- ============= esColina2 :: Integer -> Bool esColina2 n = head ds == last ds && null (dropWhile (==(-1)) (dropWhile (==0) (dropWhile (==1) xs))) where ds = digitos n xs = [signum (y-x) | (x,y) <- zip ds (tail ds)] -- Equivalencia -- ============ -- La propiedad de equivalencia es prop_esColina :: Integer -> Property prop_esColina n = n >= 0 ==> esColina n == esColina2 n -- La comprobación es -- λ> quickCheck prop_esColina -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 2. La persistencia multiplicativa de un número es la -- cantidad de pasos requeridos para reducirlo a un dígito multiplicando -- sus dígitos. Por ejemplo, la persistencia de 39 es 3 porque 3*9 = 27, -- 2*7 = 14 y 1*4 = 4. -- -- Definir la función -- persistencia :: Integer -> Integer -- tal que (persistencia x) es la persistencia de x. Por ejemplo, -- persistencia 39 == 3 -- persistencia 2677889 == 8 -- persistencia 26888999 == 9 -- persistencia 3778888999 == 10 -- persistencia 277777788888899 == 11 -- persistencia 77777733332222222222222222222 == 11 -- --------------------------------------------------------------------- persistencia :: Integer -> Integer persistencia x | x < 10 = 0 | otherwise = 1 + persistencia (productoDigitos x) productoDigitos :: Integer -> Integer productoDigitos x | x < 10 = x | otherwise = r * productoDigitos y where (y,r) = quotRem x 10 -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- producto :: [[a]] -> [[a]] -- tal que (producto xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- ghci> producto [[1,3],[2,5]] -- [[1,2],[1,5],[3,2],[3,5]] -- ghci> producto [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] -- ghci> producto [[1,3,5],[2,4]] -- [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]] -- ghci> producto [] -- [[]] -- --------------------------------------------------------------------- -- 1ª solución producto :: [[a]] -> [[a]] producto [] = [[]] producto (xs:xss) = [x:ys | x <- xs, ys <- producto xss] -- 2ª solución producto2 :: [[a]] -> [[a]] producto2 = foldr f [[]] where f xs xss = [x:ys | x <- xs, ys <- xss] -- 3ª solución producto3 :: [[a]] -> [[a]] producto3 = foldr aux [[]] where aux [] _ = [] aux (x:xs) ys = map (x:) ys ++ aux xs ys -- --------------------------------------------------------------------- -- Ejercicio 4. Las expresiones aritméticas. generales se contruyen con -- las sumas generales (sumatorios) y productos generales -- (productorios). Su tipo es -- data Expresion = N Int -- | S [Expresion] -- | P [Expresion] -- deriving Show -- Por ejemplo, la expresión (2 * (1 + 2 + 1) * (2 + 3)) + 1 se -- representa por S [P [N 2, S [N 1, N 2, N 1], S [N 2, N 3]], N 1] -- -- Definir la función -- valor :: Expresion -> Int -- tal que (valor e) es el valor de la expresión e. Por ejemplo, -- λ> valor (S [P [N 2, S [N 1, N 2, N 1], S [N 2, N 3]], N 1]) -- 41 -- --------------------------------------------------------------------- data Expresion = N Int | S [Expresion] | P [Expresion] deriving Show valor :: Expresion -> Int valor (N x) = x valor (S es) = sum (map valor es) valor (P es) = product (map valor es) |