I1M2011: La sucesión de Hamming en Haskell
En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los 4 primeros ejercicios de la 24ª relación, cuyo objetivo es dar una definición alternativa de la sucesión de Hamming estudiada en el tema 11.
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 |
-- --------------------------------------------------------------------- -- Importación de librerías -- -- --------------------------------------------------------------------- import Test.QuickCheck import Data.List -- --------------------------------------------------------------------- -- Ejercicio 1.1. Definir la función -- divisoresEn :: Integer -> [Integer] -> Bool -- tal que (divisoresEn x ys) se verifica si x puede expresarse como un -- producto de potencias de elementos de ys. Por ejemplo, -- divisoresEn 12 [2,3,5] == True -- divisoresEn 14 [2,3,5] == False -- --------------------------------------------------------------------- divisoresEn :: Integer -> [Integer] -> Bool divisoresEn 1 _ = True divisoresEn x [] = False divisoresEn x (y:ys) | mod x y == 0 = divisoresEn (div x y) (y:ys) | otherwise = divisoresEn x ys -- --------------------------------------------------------------------- -- Ejercicio 1.2. Los números de Hamming forman una sucesión -- estrictamente creciente de números que cumplen las siguientes -- condiciones: -- 1. El número 1 está en la sucesión. -- 2. Si x está en la sucesión, entonces 2x, 3x y 5x también están. -- 3. Ningún otro número está en la sucesión. -- Definir, usando divisoresEn, la constante -- hamming :: [Integer] -- tal que hamming es la sucesión de Hamming. Por ejemplo, -- take 12 hamming == [1,2,3,4,5,6,8,9,10,12,15,16] -- --------------------------------------------------------------------- hamming :: [Integer] hamming = [x | x <- [1..], divisoresEn x [2,3,5]] -- --------------------------------------------------------------------- -- Ejercicio 1.3. Definir la función -- cantidadHammingMenores :: Integer -> Int -- tal que (cantidadHammingMenores x) es la cantidad de números de -- Hamming menores que x. Por ejemplo, -- cantidadHammingMenores 6 == 5 -- cantidadHammingMenores 7 == 6 -- cantidadHammingMenores 8 == 6 -- --------------------------------------------------------------------- cantidadHammingMenores :: Integer -> Int cantidadHammingMenores x = length (takeWhile (<x) hamming) -- --------------------------------------------------------------------- -- Ejercicio 1.4. Definir la función -- siguienteHamming :: Integer -> Integer -- tal que (siguienteHamming x) es el menor número de la sucesión de -- Hamming mayor que x. Por ejemplo, -- siguienteHamming 6 == 8 -- siguienteHamming 21 == 24 -- --------------------------------------------------------------------- siguienteHamming :: Integer -> Integer siguienteHamming x = head (dropWhile (<=x) hamming) |