I1M2012: 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 hemos estudiado el problema de Hamming (consistente definir una sucesión estrictamente creciente de números tales que el número 1 está en la sucesión y que, si x está en la sucesión, entonces 2*x, 3*x y 5*x también están).
El código del problema de Hamming es
|
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 |
-- Los números de Hamming forman una sucesión estrictamente creciente de -- números que cumplen las siguientes condiciones: -- * El número 1 está en la sucesión. -- * Si x está en la sucesión, entonces 2x, 3x y 5x también están. -- * Ningún otro número está en la sucesión. -- 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 :: [Int] hamming = 1 : mezcla3 [2*i | i <- hamming] [3*i | i <- hamming] [5*i | i <- hamming] -- (mezcla3 xs ys zs) es la lista obtenida mezclando las listas -- ordenadas xs, ys y zs y eliminando los elementos duplicados. Por -- ejemplo, -- ghci> mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10] -- [2,3,4,5,6,8,9,10,12] mezcla3 :: [Int] -> [Int] -> [Int] -> [Int] mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs) -- (mezcla2 xs ys zs) es la lista obtenida mezclando las listas -- ordenadas xs e ys y eliminando los elementos duplicados. Por ejemplo, -- ghci> mezcla2 [2,4,6,8,10,12] [3,6,9,12] -- [2,3,4,6,8,9,10,12] mezcla2 :: [Int] -> [Int] -> [Int] mezcla2 p@(x:xs) q@(y:ys) | x < y = x:mezcla2 xs q | x > y = y:mezcla2 p ys | otherwise = x:mezcla2 xs ys mezcla2 [] ys = ys mezcla2 xs [] = xs |
Las transparencias usadas en la clase son desde la página 39 a la 42 del tema 11: