I1M2012: Ejercicios de definiciones por recursión y comprensión en Haskell (6)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los ejercicios 9 a 12 de la 11ª 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:
|
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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 9.1. [Problema 357 del Project Euler] Un número natural n -- es especial si para todo divisor d de n, d+n/d es primo. Definir la -- función -- especial :: Integer -> Bool -- tal que (especial x) se verifica si x es especial. Por ejemplo, -- especial 30 == True -- especial 20 == False -- --------------------------------------------------------------------- especial :: Integer -> Bool especial x = and [primo (d + x `div` d) | d <- factores x] -- --------------------------------------------------------------------- -- Ejercicio 9.2. Definir la función -- sumaEspeciales :: Integer -> Integer -- tal que (sumaEspeciales n) es la suma de los números especiales -- menores o iguales que n. Por ejemplo, -- sumaEspeciales 100 == 401 -- --------------------------------------------------------------------- -- Por comprensión sumaEspeciales :: Integer -> Integer sumaEspeciales n = sum [x | x <- [1..n], especial x] -- Por recursión sumaEspecialesR :: Integer -> Integer sumaEspecialesR 0 = 0 sumaEspecialesR n | especial n = n + sumaEspecialesR (n-1) | otherwise = sumaEspecialesR (n-1) -- --------------------------------------------------------------------- -- Ejercicio 10.1. La distancia de Hamming entre dos listas es el número -- de posiciones en que los correspondientes elementos son -- distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba" -- es 2 (porque hay 2 posiciones en las que los elementos -- correspondientes son distintos: la 1ª y la 3ª). -- -- Definir por comprensión la función -- distancia :: Eq a => [a] -> [a] -> Int -- tal que (distanciaC xs ys) es la distancia de Hamming entre xs e -- ys. Por ejemplo, -- distanciaC "romano" "comino" == 2 -- distanciaC "romano" "camino" == 3 -- distanciaC "roma" "comino" == 2 -- distanciaC "roma" "camino" == 3 -- distanciaC "romano" "ron" == 1 -- distanciaC "romano" "cama" == 2 -- distanciaC "romano" "rama" == 1 -- --------------------------------------------------------------------- distanciaC :: Eq a => [a] -> [a] -> Int distanciaC xs ys = sum [1 | (x,y) <- zip xs ys, x /= y] -- --------------------------------------------------------------------- -- Ejercicio 10.2. Definir por recursión la función -- distanciaR :: Eq a => [a] -> [a] -> Int -- tal que (distanciaR xs ys) es la distancia de Hamming entre xs e -- ys. Por ejemplo, -- distanciaR "romano" "comino" == 2 -- distanciaR "romano" "camino" == 3 -- distanciaR "roma" "comino" == 2 -- distanciaR "roma" "camino" == 3 -- distanciaR "romano" "ron" == 1 -- distanciaR "romano" "cama" == 2 -- distanciaR "romano" "rama" == 1 -- --------------------------------------------------------------------- distanciaR :: Eq a => [a] -> [a] -> Int distanciaR [] ys = 0 distanciaR xs [] = 0 distanciaR (x:xs) (y:ys) | x /= y = 1 + distanciaR xs ys | otherwise = distanciaR xs ys -- --------------------------------------------------------------------- -- Ejercicio 11. Definir la función -- traspuesta :: [[a]] -> [[a]] -- tal que (traspuesta m) es la traspuesta de la matriz m. Por ejemplo, -- traspuesta [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]] -- traspuesta [[1,4],[2,5],[3,6]] == [[1,2,3],[4,5,6]] -- --------------------------------------------------------------------- traspuesta :: [[a]] -> [[a]] traspuesta ([]:_) = [] traspuesta xss = primeros xss : traspuesta (restos xss) -- (primeros xss) es la lista de los primeros elementos de xss. Por -- ejemplo, -- primeros [[1,2,3],[4,5,6]] == [1,4] -- primeros [[1,4],[2,5],[3,6]] == [1,2,3] primeros xss = [head xs | xs <- xss] -- (restos xss) es la lista de los restos de xss. Por ejemplo, -- restos [[1,2,3],[4,5,6]] == [[2,3],[5,6]] -- restos [[1,4],[2,5],[3,6]] == [[4],[5],[6]] restos xss = [tail xs | xs <- xss] -- --------------------------------------------------------------------- -- Ejercicio 12. [2.5 puntos] Definir la función -- sumas :: Int -> [Int] -> [Int] -- tal que (sumas n xs) es la lista de los números que se pueden obtener -- como suma de n, o menos, elementos de xs. Por ejemplo, -- sumas 0 [2,5] == [0] -- sumas 1 [2,5] == [2,5,0] -- sumas 2 [2,5] == [4,7,2,10,5,0] -- sumas 3 [2,5] == [6,9,4,12,7,2,15,10,5,0] -- sumas 2 [2,3,5] == [4,5,7,2,6,8,3,10,5,0] -- --------------------------------------------------------------------- sumas :: Int -> [Int] -> [Int] sumas 0 _ = [0] sumas _ [] = [0] sumas n (x:xs) = [x+y | y <- sumas (n-1) (x:xs)] ++ sumas n xs |