I1M2012: Ejercicios de evaluación perezosa y listas infinitas (3)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentando soluciones de los sguientes ejercicios de la relación 17 (sobre evaluación perezosa y listas infinitas):
- 8. Menor número triangular con más de n divisores.
- 9. Números primos consecutivos con dígitos con igual media.
- 10. Decisión de pertenencia al rango de una función creciente
- 11. Pares ordenados por posición.
- 12. Aplicación iterada de una función.
- 13. La bicicleta de Turing.
- 14. La sucesión de Golomb.
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 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 |
-- --------------------------------------------------------------------- -- Ejercicio 8. (Problema 12 del Proyecto Euler) La sucesión de los -- números triangulares se obtiene sumando los números naturales. Así, -- el 7º número triangular es -- 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. -- Los primeros 10 números triangulares son -- 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... -- Los divisores de los primeros 7 números triangulares son: -- 1: 1 -- 3: 1,3 -- 6: 1,2,3,6 -- 10: 1,2,5,10 -- 15: 1,3,5,15 -- 21: 1,3,7,21 -- 28: 1,2,4,7,14,28 -- Como se puede observar, 28 es el menor número triangular con más de 5 -- divisores. -- -- Definir la función -- euler12 :: Int -> Integer -- tal que (euler12 n) es el menor número triangular con más de n -- divisores. Por ejemplo, -- euler12 5 == 28 -- --------------------------------------------------------------------- euler12 :: Int -> Integer euler12 n = head [x | x <- triangulares, nDivisores x > n] -- triangulares es la lista de los números triangulares -- take 10 triangulares == [1,3,6,10,15,21,28,36,45,55] triangulares :: [Integer] triangulares = 1:[x+y | (x,y) <- zip [2..] triangulares] -- Otra definición de triangulares es triangulares' :: [Integer] triangulares' = scanl (+) 1 [2..] -- (divisores n) es la lista de los divisores de n. Por ejemplo, -- divisores 28 == [1,2,4,7,14,28] divisores :: Integer -> [Integer] divisores x = [y | y <- [1..x], mod x y == 0] -- (nDivisores n) es el número de los divisores de n. Por ejemplo, -- nDivisores 28 == 6 nDivisores :: Integer -> Int nDivisores x = length (divisores x) -- --------------------------------------------------------------------- -- Ejercicio 9.1. Dos números son equivalentes si la media de sus cifras -- son iguales. Por ejemplo, 3205 y 41 son equvalentes ya que -- (3+2+0+5)/4 = (4+1)/2. Definir la función -- equivalentes :: Int -> Int -> 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 :: Int -> Int -> Bool equivalentes x y = media (cifras x) == media (cifras y) -- (cifras n) es la lista de las cifras de n. Por ejemplo, -- cifras 3205 == [3,2,0,5] cifras :: Int -> [Int] cifras n = [read [y] | y <- show n] -- (media xs) es la media de la lista xs. Por ejemplo, -- media [3,2,0,5] == 2.5 media :: [Int] -> Float media xs = (fromIntegral (sum xs)) / (fromIntegral (length xs)) -- --------------------------------------------------------------------- -- Ejercicio 9.2. Definir la función -- relacionados :: (a -> a -> Bool) -> [a] -> Bool -- tal que (relacionados r xs) se verifica si para todo par (x,y) de -- elementos consecutivos de xs se cumple la relación r. Por ejemplo, -- relacionados (<) [2,3,7,9] == True -- relacionados (<) [2,3,1,9] == False -- relacionados equivalentes [3205,50,5014] == True -- --------------------------------------------------------------------- relacionados :: (a -> a -> Bool) -> [a] -> Bool relacionados r (x:y:zs) = (r x y) && relacionados r (y:zs) relacionados _ _ = True -- Una definición alternativa es relacionados' :: (a -> a -> Bool) -> [a] -> Bool relacionados' r xs = and [r x y | (x,y) <- zip xs (tail xs)] -- --------------------------------------------------------------------- -- Ejercicio 9.3. Definir la función -- primosEquivalentes :: Int -> [[Int]] -- tal que (primosEquivalentes n) es la lista de las sucesiones de n -- números primos consecutivos equivalentes. Por ejemplo, -- take 2 (primosEquivalentes 2) == [[523,541],[1069,1087]] -- head (primosEquivalentes 3) == [22193,22229,22247] -- --------------------------------------------------------------------- primosEquivalentes :: Int -> [[Int]] primosEquivalentes n = aux primos where aux (x:xs) | relacionados equivalentes ys = ys : aux xs | otherwise = aux xs where ys = take n (x:xs) primos :: Integral a => [a] primos = criba [2..] where criba [] = [] criba (n:ns) = n : criba (elimina n ns) elimina n xs = [x | x <- xs, x `mod` n /= 0] -- --------------------------------------------------------------------- -- Ejercicio 10. Definir la función -- perteneceRango:: Int -> (Int -> Int) -> Bool -- tal que (perteneceRango x f) se verifica si x pertenece al rango de -- la función f, suponiendo que f es una función creciente cuyo dominio -- es el conjunto de los números naturales. Por ejemplo, -- perteneceRango 5 (\x -> 2*x+1) == True -- perteneceRango 1234 (\x -> 2*x+1) == False -- --------------------------------------------------------------------- perteneceRango:: Int -> (Int -> Int) -> Bool perteneceRango y f = elem y (takeWhile (<=y) (imagenes f)) where imagenes f = [f x | x <- [0..]] -- --------------------------------------------------------------------- -- Ejercicio 11.1. Definir, por recursión, la función -- paresOrdenados :: [a] -> [(a,a)] -- tal que (paresOrdenados xs) es la lista de todos los pares de -- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por -- ejemplo, -- paresOrdenados [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)] -- paresOrdenados [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)] -- --------------------------------------------------------------------- paresOrdenados :: [a] -> [(a,a)] paresOrdenados [] = [] paresOrdenados (x:xs) = [(x,y) | y <- xs] ++ paresOrdenados xs -- --------------------------------------------------------------------- -- Ejercicio 11.2. Definir, por plegado, la función -- paresOrdenados2 :: [a] -> [(a,a)] -- tal que (paresOrdenados2 xs) es la lista de todos los pares de -- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por -- ejemplo, -- paresOrdenados2 [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)] -- paresOrdenados2 [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)] -- --------------------------------------------------------------------- paresOrdenados2 :: [a] -> [(a,a)] paresOrdenados2 [] = [] paresOrdenados2 (x:xs) = foldr (\y ac -> (x,y):ac) (paresOrdenados2 xs) xs -- --------------------------------------------------------------------- -- Ejercicio 11.3. Definir, usando repeat, la función -- paresOrdenados3 :: [a] -> [(a,a)] -- tal que (paresOrdenados3 xs) es la lista de todos los pares de -- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por -- ejemplo, -- paresOrdenados3 [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)] -- paresOrdenados3 [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)] -- --------------------------------------------------------------------- paresOrdenados3 :: [a] -> [(a,a)] paresOrdenados3 [] = [] paresOrdenados3 (x:xs) = zip (repeat x) xs ++ paresOrdenados3 xs -- --------------------------------------------------------------------- -- Ejercicio 12.1. Definir, por recursión, la función -- potenciaFunc :: Int -> (a -> a) -> a -> a -- tal que (potenciaFunc n f x) es el resultado de aplicar n veces la -- función f a x. Por ejemplo, -- potenciaFunc 3 (*10) 5 == 5000 -- potenciaFunc 4 (+10) 5 == 45 -- --------------------------------------------------------------------- potenciaFunc :: Int -> (a -> a) -> a -> a potenciaFunc 0 _ x = x potenciaFunc n f x = potenciaFunc (n-1) f (f x) -- --------------------------------------------------------------------- -- Ejercicio 12.2. Definir, sin recursión, la función -- potenciaFunc2 :: Int -> (a -> a) -> a -> a -- tal que (potenciaFunc2 n f x) es el resultado de aplicar n veces la -- función f a x. Por ejemplo, -- potenciaFunc2 3 (*10) 5 == 5000 -- potenciaFunc2 4 (+10) 5 == 45 -- --------------------------------------------------------------------- potenciaFunc2 :: Int -> (a -> a) -> a -> a potenciaFunc2 n f x = last (take (n+1) (iterate f x)) -- --------------------------------------------------------------------- -- Ejercicio 13.1. Cuentan que Alan Turing tenía una bicicleta vieja, -- que tenía una cadena con un eslabón débil y además uno de los radios -- de la rueda estaba doblado. Cuando el radio doblado coincidía con el -- eslabón débil, entonces la cadena se rompía. -- -- La bicicleta se identifica por los parámetros (i,d,n) donde -- * i es el número del eslabón que coincide con el radio doblado al -- empezar a andar, -- * d es el número de eslabones que se desplaza la cadena en cada -- vuelta de la rueda y -- * n es el número de eslabones de la cadena (el número n es el débil). -- Si i=2 y d=7 y n=25, entonces la lista con el número de eslabón que -- toca el radio doblado en cada vuelta es -- [2,9,16,23,5,12,19,1,8,15,22,4,11,18,0,7,14,21,3,10,17,24,6,... -- Con lo que la cadena se rompe en la vuelta número 14. -- -- Definir la función -- eslabones :: Int -> Int -> Int -> [Int] -- tal que (eslabones i d n) es la lista con los números de eslabones -- que tocan el radio doblado en cada vuelta en una bicicleta de tipo -- (i,d,n). Por ejemplo, -- take 10 (eslabones 2 7 25) == [2,9,16,23,5,12,19,1,8,15] -- --------------------------------------------------------------------- eslabones :: Int -> Int -> Int -> [Int] eslabones i d n = [(i+d*j) `mod` n | j <- [0..]] -- 2ª definición (con iterate): eslabones2 :: Int -> Int -> Int -> [Int] eslabones2 i d n = map (\x-> mod x n) (iterate (+d) i) -- --------------------------------------------------------------------- -- Ejercicio 13.2. Definir la función -- numeroVueltas :: Int -> Int -> Int -> Int -- tal que (numeroVueltas i d n) es el número de vueltas que pasarán -- hasta que la cadena se rompa en una bicicleta de tipo (i,d,n). Por -- ejemplo, -- numeroVueltas 2 7 25 == 14 -- --------------------------------------------------------------------- numeroVueltas :: Int -> Int -> Int -> Int numeroVueltas i d n = length (takeWhile (/=0) (eslabones i d n)) -- --------------------------------------------------------------------- -- Ejercicio 14.1. [Basado en el problema 341 del proyecto Euler]. La -- sucesión de Golomb {G(n)} es una sucesión auto descriptiva: es la -- única sucesión no decreciente de números naturales tal que el número -- n aparece G(n) veces en la sucesión. Los valores de G(n) para los -- primeros números son los siguientes: -- n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... -- G(n) 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 ... -- En los apartados de este ejercicio se definirá una función para -- calcular los términos de la sucesión de Golomb. -- -- Definir la función -- golomb :: Int -> Int -- tal que (golomb n) es el n-ésimo término de la sucesión de Golomb. -- Por ejemplo, -- golomb 5 == 3 -- golomb 9 == 5 -- Indicación: Se puede usar la función sucGolomb del apartado 2. -- --------------------------------------------------------------------- golomb :: Int -> Int golomb n = sucGolomb !! (n-1) -- --------------------------------------------------------------------- -- Ejercicio 14.2. Definir la función -- sucGolomb :: [Int] -- tal que sucGolomb es la lista de los términos de la sucesión de -- Golomb. Por ejemplo, -- take 15 sucGolomb == [1,2,2,3,3,4,4,4,5,5,5,6,6,6,6] -- Indicación: Se puede usar la función subSucGolomb del apartado 3. -- --------------------------------------------------------------------- sucGolomb :: [Int] sucGolomb = subSucGolomb 1 -- --------------------------------------------------------------------- -- Ejercicio 14.3. Definir la función -- subSucGolomb :: Int -> [Int] -- tal que (subSucGolomb x) es la lista de los términos de la sucesión -- de Golomb a partir de la primera ocurrencia de x. Por ejemplo, -- take 10 (subSucGolomb 4) == [4,4,4,5,5,5,6,6,6,6] -- Indicación: Se puede usar la función golomb del apartado 1. -- --------------------------------------------------------------------- subSucGolomb :: Int -> [Int] subSucGolomb 1 = [1] ++ subSucGolomb 2 subSucGolomb 2 = [2,2] ++ subSucGolomb 3 subSucGolomb x = (replicate (golomb x) x) ++ subSucGolomb (x+1) -- Nota: La sucesión de Golomb puede definirse de forma más compacta -- como se muestra a continuación. sucGolomb' :: [Int] sucGolomb' = 1 : 2 : 2 : g 3 where g x = replicate (golomb x) x ++ g (x+1) golomb n = sucGolomb !! (n-1) |