I1M2012: Ejercicios de definiciones por recursión y comprensión en Haskell (5)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los ejercicios 6 a 8 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 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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 6.1. Una persona es tan agarrada que sólo compra cuando le -- hacen un descuento del 10% y el precio (con el descuento) es menor o -- igual que 199. -- -- Definir, usando comprensión, la función -- agarradoC :: [Float] -> Float -- tal que (agarradoC ps) es el precio que tiene que pagar por una compra -- cuya lista de precios es ps. Por ejemplo, -- agarradoC [45.00, 199.00, 220.00, 399.00] == 417.59998 -- --------------------------------------------------------------------- agarradoC :: [Float] -> Float agarradoC ps = sum [p * 0.9 | p <- ps, p * 0.9 <= 199] -- --------------------------------------------------------------------- -- Ejercicio 6.2. Definir, por recursión, la función -- agarradoR :: [Float] -> Float -- tal que (agarradoR ps) es el precio que tiene que pagar por una compra -- cuya lista de precios es ps. Por ejemplo, -- agarradoR [45.00, 199.00, 220.00, 399.00] == 417.59998 -- --------------------------------------------------------------------- agarradoR :: [Float] -> Float agarradoR [] = 0 agarradoR (p:ps) | precioConDescuento <= 199 = precioConDescuento + agarradoR ps | otherwise = agarradoR ps where precioConDescuento = p * 0.9 -- --------------------------------------------------------------------- -- Ejercicio 6.3. Comprobar con QuickCheck que ambas definiciones son -- similares; es decir, el valor absoluto de su diferencia es menor que -- una décima. -- --------------------------------------------------------------------- -- La propiedad es prop_agarrado :: [Float] -> Bool prop_agarrado xs = abs (agarradoR xs - agarradoC xs) <= 0.1 -- La comprobación es -- *Main> quickCheck prop_agarrado -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 7.1. Definir la función -- factores :: Integer -> Integer -- tal que (factores n) es la lista de los factores de n. Por ejemplo, -- factores 60 == [1,2,3,4,5,6,10,12,15,20,30,60] -- --------------------------------------------------------------------- factores :: Integer -> [Integer] factores n = [x | x <- [1..n], rem n x == 0] -- --------------------------------------------------------------------- -- Ejercicio 7.2. Definir la función -- primo :: Integer -> Bool -- tal que (primo n) se verifica si n es primo. Por ejemplo, -- primo 7 == True -- primo 9 == False -- --------------------------------------------------------------------- primo :: Integer -> Bool primo x = factores x == [1,x] -- --------------------------------------------------------------------- -- Ejercicio 7.3. Definir la función -- factoresPrimos :: Integer -> [Integer] -- tal que (factoresPrimos n) es la lista de los factores primos de -- n. Por ejemplo, -- factoresPrimos 60 == [2,3,5] -- --------------------------------------------------------------------- factoresPrimos :: Integer -> [Integer] factoresPrimos n = [x | x <- factores n, primo x] -- --------------------------------------------------------------------- -- Ejercicio 8.1. Definir, por recursión, la función -- mayorExponenteR :: Integer -> Integer -> Integer -- tal que (mayorExponenteR a b) es el exponente de la mayor potencia de -- a que divide b. Por ejemplo, -- mayorExponenteR 2 8 == 3 -- mayorExponenteR 2 9 == 0 -- mayorExponenteR 5 100 == 2 -- mayorExponenteR 2 60 == 2 -- --------------------------------------------------------------------- mayorExponenteR :: Integer -> Integer -> Integer mayorExponenteR a b | rem b a /= 0 = 0 | otherwise = 1 + mayorExponenteR a (b `div` a) -- --------------------------------------------------------------------- -- Ejercicio 8.2. Definir, por recursión, la función -- mayorExponenteC :: Integer -> Integer -> Integer -- tal que (mayorExponenteC a b) es el exponente de la mayor potencia de -- a que divide a b. Por ejemplo, -- mayorExponenteC 2 8 == 3 -- mayorExponenteC 5 100 == 2 -- mayorExponenteC 5 101 == 0 -- --------------------------------------------------------------------- mayorExponenteC :: Integer -> Integer -> Integer mayorExponenteC a b = head [x-1 | x <- [0..], mod b (a^x) /= 0] -- --------------------------------------------------------------------- -- Ejercicio 8.3. Definir la función -- factorizacion :: Integer -> [(Integer,Integer)] -- tal que (factorizacion n) es la factorización de n. Por ejemplo, -- factorizacion 60 == [(2,2),(3,1),(5,1)] -- --------------------------------------------------------------------- factorizacion :: Integer -> [(Integer,Integer)] factorizacion n = [(x,mayorExponenteR x n) | x <- factoresPrimos n] -- --------------------------------------------------------------------- -- Ejercicio 8.4. Definir, por recursión, la función -- expansionR :: [(Integer,Integer)] -> Integer -- tal que (expansionR xs) es la expansión de la factorización de -- xs. Por ejemplo, -- expansionR [(2,2),(3,1),(5,1)] == 60 -- --------------------------------------------------------------------- expansionR :: [(Integer,Integer)] -> Integer expansionR [] = 1 expansionR ((x,y):zs) = x^y * expansionR zs -- --------------------------------------------------------------------- -- Ejercicio 8.5. Definir, por comprensión, la función -- expansionC :: [(Integer,Integer)] -> Integer -- tal que (expansionC xs) es la expansión de la factorización de -- xs. Por ejemplo, -- expansionC [(2,2),(3,1),(5,1)] == 60 -- --------------------------------------------------------------------- expansionC :: [(Integer,Integer)] -> Integer expansionC xs = product [x^y | (x,y) <- xs] -- --------------------------------------------------------------------- -- Ejercicio 8.6. Definir la función -- prop_factorizacion :: Integer -> Bool -- tal que (prop_factorizacion n) se verifica si para todo número -- natural x, menor o igual que n, se tiene que -- (expansionC (factorizacion x)) es igual a x. Por ejemplo, -- prop_factorizacion 100 == True -- --------------------------------------------------------------------- prop_factorizacion n = and [expansionC (factorizacion x) == x | x <- [1..n]] |