{"id":2546,"date":"2013-02-26T17:56:31","date_gmt":"2013-02-26T17:56:31","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2546"},"modified":"2013-03-08T05:47:33","modified_gmt":"2013-03-08T05:47:33","slug":"i1m2012-la-sucesion-de-hamming-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-la-sucesion-de-hamming-en-haskell\/","title":{"rendered":"I1M2012: La sucesi\u00f3n de Hamming en Haskell"},"content":{"rendered":"

En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado el problema de Hamming (consistente definir una sucesi\u00f3n estrictamente creciente de n\u00fameros tales que el n\u00famero 1 est\u00e1 en la sucesi\u00f3n y que, si x est\u00e1 en la sucesi\u00f3n, entonces 2*x, 3*x y 5*x tambi\u00e9n est\u00e1n).<\/p>\n

El c\u00f3digo del problema de Hamming es
\n<\/p>\n

\r\n-- Los n\u00fameros de Hamming forman una sucesi\u00f3n estrictamente creciente de\r\n-- n\u00fameros que cumplen las siguientes condiciones: \r\n-- * El n\u00famero 1 est\u00e1 en la sucesi\u00f3n.\r\n-- * Si x est\u00e1 en la sucesi\u00f3n, entonces 2x, 3x y  5x tambi\u00e9n est\u00e1n.\r\n-- * Ning\u00fan otro n\u00famero est\u00e1 en la sucesi\u00f3n. \r\n\r\n-- hamming es la sucesi\u00f3n de Hamming. Por ejemplo,\r\n--    take 12 hamming == [1,2,3,4,5,6,8,9,10,12,15,16]\r\nhamming :: [Int]\r\nhamming = 1 : mezcla3 [2*i | i <- hamming]  \r\n                      [3*i | i <- hamming]  \r\n                      [5*i | i <- hamming]  \r\n\r\n-- (mezcla3 xs ys zs) es la lista obtenida mezclando las listas\r\n-- ordenadas xs, ys y zs y eliminando los elementos duplicados. Por\r\n-- ejemplo, \r\n--    ghci> mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10]\r\n--    [2,3,4,5,6,8,9,10,12]\r\nmezcla3 :: [Int] -> [Int] -> [Int] -> [Int]\r\nmezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs)  \r\n\r\n-- (mezcla2 xs ys zs) es la lista obtenida mezclando las listas\r\n-- ordenadas xs e ys y eliminando los elementos duplicados. Por ejemplo,\r\n--    ghci> mezcla2 [2,4,6,8,10,12] [3,6,9,12]\r\n--    [2,3,4,6,8,9,10,12]\r\nmezcla2 :: [Int] -> [Int] -> [Int]\r\nmezcla2 p@(x:xs) q@(y:ys) | x < y     = x:mezcla2 xs q\r\n                          | x > y     = y:mezcla2 p  ys  \r\n                          | otherwise = x:mezcla2 xs ys\r\nmezcla2 []       ys                   = ys\r\nmezcla2 xs       []                   = xs\r\n<\/pre>\n
Las transparencias usadas en la clase son desde la p\u00e1gina 39 a la 42 del tema 11<\/a>:
\n