{"id":1936,"date":"2012-03-09T18:44:27","date_gmt":"2012-03-09T18:44:27","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1936"},"modified":"2012-03-13T08:46:10","modified_gmt":"2012-03-13T08:46:10","slug":"i1m2011-los-problemas-de-las-n-reinas-y-de-hamming-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-los-problemas-de-las-n-reinas-y-de-hamming-en-haskell\/","title":{"rendered":"I1M2011: Los problemas de las N reinas y de Hamming en Haskell"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos vistos dos aplicaciones de la programaci\u00f3n funcional en Haskell: el problema de las reinas (consistente en colocar N reinas en un tablero de dimensiones N por N de forma que no se encuentren m\u00e1s de una en la misma l\u00ednea: horizontal, vertical o diagonal) y 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 las N reinas es
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Enunciado                                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Colocar N reinas en un tablero rectangular de dimensiones N por N de\r\n-- forma que no se encuentren m\u00e1s de una en la misma l\u00ednea: horizontal,\r\n-- vertical o diagonal. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librerias auxiliares                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List ((\\\\))\r\n\r\n-- El tablero se representa por una lista de n\u00fameros que indican las\r\n-- filas donde se han colocado las reinas. Por ejemplo, [3,5]\r\n-- indica que se han colocado las reinas (1,3) y (2,5). \r\ntype Tablero = [Int]  \r\n\r\n-- (reinas n) es la lista de soluciones del problema de las N\r\n-- reinas. Por ejemplo, \r\n--    reinas 4  == [[3,1,4,2],[2,4,1,3]].  \r\n-- La primera soluci\u00f3n [3,1,4,2] se interpreta como \r\n--    +---------------+\r\n--    |   | R |   |   |\r\n--    +---------------+\r\n--    |   |   |   | R |\r\n--    +---------------+\r\n--    | R |   |   |   |\r\n--    +---------------+\r\n--    |   |   | R |   |\r\n--    +---------------+\r\nreinas :: Int -> [Tablero]\r\nreinas n = aux n\r\n    where aux 0 = [[]]\r\n          aux m = [r:rs | rs <- aux (m-1),\r\n                          r <- ([1..n] \\\\ rs),\r\n                          noAtaca r rs 1]\r\n\r\n-- (noAtaca r rs d) se verifica si la reina r no ataca a niguna de las\r\n-- de la lista rs donde la primera de la lista est\u00e1 a una distancia\r\n-- horizontal d. \r\nnoAtaca :: Int -> Tablero -> Int -> Bool\r\nnoAtaca _ [] _ = True\r\nnoAtaca r (a:rs) distH = abs(r-a) \/= distH &&\r\n                         noAtaca r rs (distH+1)\r\n<\/pre>\n
El c\u00f3digo del problema de Hamming es<\/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 37 a la 45 del tema 11<\/a>:
\n