I1M2012: Ejercicios de definiciones por recursión y comprensión en Haskell (3)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los ejercicios 14 a 17 de la 9ª relación y 1 a 3 de la 10ª relación en las que se presentan ejercicios con dos definiciones (una por recursión y otra por comprensión) y la comprobación de la equivalencia de las dos definiciones con QuickCheck.
Los ejercicios, y sus soluciones, se muestran a continuación: Las de la relación 9 son
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 |
-- --------------------------------------------------------------------- -- Ejercicio 14. (Problema 16 del proyecto Euler) El problema se -- encuentra en http://goo.gl/4uWh y consiste en calcular la suma de los -- dígitos de 2^1000. Lo resolveremos mediante los distintos apartados de -- este ejercicio. -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 14.1. Definir la función -- euler16 :: Integer -> Integer -- tal que (euler16 n) es la suma de los dígitos de 2^n. Por ejemplo, -- euler16 4 == 7 -- --------------------------------------------------------------------- euler16 :: Integer -> Integer euler16 n = sumaDigitosNR (2^n) -- --------------------------------------------------------------------- -- Ejercicio 14.2. Calcular la suma de los dígitos de 2^1000. -- --------------------------------------------------------------------- -- El cálculo es -- *Main> euler16 1000 -- 1366 -- --------------------------------------------------------------------- -- Ejercicio 15. En el enunciado de uno de los problemas de las -- Olimpiadas matemáticas de Brasil se define el primitivo de un número -- como sigue: -- Dado un número natural N, multiplicamos todos sus dígitos, -- repetimos este procedimiento hasta que quede un solo dígito al -- cual llamamos primitivo de N. Por ejemplo para 327: 3x2x7 = 42 y -- 4x2 = 8. Por lo tanto, el primitivo de 327 es 8. -- -- Definir la función -- primitivo :: Integer -> Integer -- tal que (primitivo n) es el primitivo de n. Por ejemplo. -- primitivo 327 == 8 -- --------------------------------------------------------------------- primitivo :: Integer -> Integer primitivo n | n < 10 = n | otherwise = primitivo (producto n) -- (producto n) es el producto de las cifras de n. Por ejemplo, -- producto 327 == 42 producto :: Integer -> Integer producto n = product (digitosC n) -- --------------------------------------------------------------------- -- Ejercicio 16. Dos números son equivalentes si la media de sus dígitos -- son iguales. Por ejemplo, 3205 y 41 son equivalentes ya que -- (3+2+0+5)/4 = (4+1)/2. Definir la función -- equivalentes :: Integer -> Integer -> Bool -- tal que (equivalentes x y) se verifica si los números x e y son -- equivalentes. Por ejemplo, -- equivalentes 3205 41 == True -- equivalentes 3205 25 == False -- --------------------------------------------------------------------- equivalentes :: Integer -> Integer -> Bool equivalentes x y = media (digitosC x) == media (digitosC y) -- (media xs) es la media de la lista xs. Por ejemplo, -- media [3,2,0,5] == 2.5 media :: [Integer] -> Float media xs = (fromIntegral (sum xs)) / (fromIntegral (length xs)) -- --------------------------------------------------------------------- -- Ejercicio 17. Un número x es especial si el número de ocurrencia de -- cada dígito d de x en x^2 es el doble del número de ocurrencia de d -- en x. Por ejemplo, 72576 es especial porque tiene un 2, un 5, un 6 y -- dos 7 y su cuadrado es 5267275776 que tiene exactamente dos 2, dos 5, -- dos 6 y cuatro 7. -- -- Definir la función -- especial :: Integer -> Bool -- tal que (especial x) se verifica si x es un número especial. Por -- ejemplo, -- especial 72576 == True -- especial 12 == False -- Calcular el menor número especial mayor que 72576. -- --------------------------------------------------------------------- especial :: Integer -> Bool especial x = sort (ys ++ ys) == sort (show (x^2)) where ys = show x -- El cálculo es -- ghci> head [x | x <- [72577..], especial x] -- 406512 |
y los de la relación 10 son
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 |
-- --------------------------------------------------------------------- -- Ejercicio 1.1. Definir, por comprensión, la función -- cuadradosC :: [Integer] -> [Integer] -- tal que (cuadradosC xs) es la lista de los cuadrados de xs. Por -- ejemplo, -- cuadradosC [1,2,3] == [1,4,9] -- --------------------------------------------------------------------- cuadradosC :: [Integer] -> [Integer] cuadradosC xs = [x^2 | x <- xs] -- --------------------------------------------------------------------- -- Ejercicio 1.2. Definir, por recursión, la función -- cuadradosR :: [Integer] -> [Integer] -- tal que (cuadradosR xs) es la lista de los cuadrados de xs. Por -- ejemplo, -- cuadradosR [1,2,3] == [1,4,9] -- --------------------------------------------------------------------- cuadradosR :: [Integer] -> [Integer] cuadradosR [] = [] cuadradosR (x:xs) = x^2 : cuadradosR xs -- --------------------------------------------------------------------- -- Ejercicio 2.1. Definir, por comprensión, la función -- imparesC :: [Integer] -> [Integer] -- tal que (imparesC xs) es la lista de los números impares de xs. Por -- ejemplo, -- imparesC [1,2,3] == [1,3] -- --------------------------------------------------------------------- imparesC :: [Integer] -> [Integer] imparesC xs = [x | x <- xs, odd x] -- --------------------------------------------------------------------- -- Ejercicio 2.2. Definir, por recursión, la función -- imparesR :: [Integer] -> [Integer] -- tal que (imparesR xs) es la lista de los números impares de xs. Por -- ejemplo, -- imparesR [1,2,3] == [1,3] -- --------------------------------------------------------------------- imparesR :: [Integer] -> [Integer] imparesR [] = [] imparesR (x:xs) | odd x = x : imparesR xs | otherwise = imparesR xs -- --------------------------------------------------------------------- -- Ejercicio 3.1. Definir, por comprensión, la función -- imparesCuadradosC :: [Integer] -> [Integer] -- tal que (imparesCuadradosC xs) es la lista de los cuadrados de los -- números impares de xs. Por ejemplo, -- imparesCuadradosC [1,2,3] == [1,9] -- --------------------------------------------------------------------- imparesCuadradosC :: [Integer] -> [Integer] imparesCuadradosC xs = [x^2 | x <- xs, odd x] -- --------------------------------------------------------------------- -- Ejercicio 3.2. Definir, por recursión, la función -- imparesCuadradosR :: [Integer] -> [Integer] -- tal que (imparesCuadradosR xs) es la lista de los cuadrados de los -- números impares de xs. Por ejemplo, -- imparesCuadradosR [1,2,3] == [1,9] -- --------------------------------------------------------------------- imparesCuadradosR :: [Integer] -> [Integer] imparesCuadradosR [] = [] imparesCuadradosR (x:xs) | odd x = x^2 : imparesCuadradosR xs | otherwise = imparesCuadradosR xs |