{"id":5207,"date":"2015-12-09T11:55:27","date_gmt":"2015-12-09T10:55:27","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5207"},"modified":"2015-12-12T11:57:04","modified_gmt":"2015-12-12T10:57:04","slug":"i1m2015-los-problemas-de-las-n-reinas-y-de-hamming-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-los-problemas-de-las-n-reinas-y-de-hamming-en-haskell\/","title":{"rendered":"I1M2015: Los problemas de las N reinas y 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 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 2x, 3x y 5x tambi\u00e9n est\u00e1n).<\/p>\n

El c\u00f3digo del problema de las N reinas es
\n<\/p>\n

\n-- ---------------------------------------------------------------------\n-- \u00a7 Enunciado                                                        --\n-- ---------------------------------------------------------------------\n\n-- Colocar N reinas en un tablero rectangular de dimensiones N por N de\n-- forma que no se encuentren m\u00e1s de una en la misma l\u00ednea: horizontal,\n-- vertical o diagonal. \n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librerias auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List ((\\\\))\n\n-- El tablero se representa por una lista de n\u00fameros que indican las\n-- filas donde se han colocado las reinas. Por ejemplo, [3,5]\n-- indica que se han colocado las reinas (1,3) y (2,5). \ntype Tablero = [Int]  \n\n-- (reinas n) es la lista de soluciones del problema de las N\n-- reinas. Por ejemplo, \n--    reinas 4  == [[3,1,4,2],[2,4,1,3]].  \n-- La primera soluci\u00f3n [3,1,4,2] se interpreta como \n--    +---------------+\n--    |   | R |   |   |\n--    +---------------+\n--    |   |   |   | R |\n--    +---------------+\n--    | R |   |   |   |\n--    +---------------+\n--    |   |   | R |   |\n--    +---------------+\nreinas :: Int -> [Tablero]\nreinas n = aux n\n    where aux 0 = [[]]\n          aux m = [r:rs | rs <- aux (m-1),\n                          r <- ([1..n] \\\\ rs),\n                          noAtaca r rs 1]\n\n-- (noAtaca r rs d) se verifica si la reina r no ataca a niguna de las\n-- de la lista rs donde la primera de la lista est\u00e1 a una distancia\n-- horizontal d. \nnoAtaca :: Int -> Tablero -> Int -> Bool\nnoAtaca _ [] _ = True\nnoAtaca r (a:rs) distH = abs(r-a) \/= distH &&\n                         noAtaca r rs (distH+1)\n<\/pre>\n
El c\u00f3digo del problema de Hamming es<\/p>\n
\n-- Los n\u00fameros de Hamming forman una sucesi\u00f3n estrictamente creciente de\n-- n\u00fameros que cumplen las siguientes condiciones: \n-- * El n\u00famero 1 est\u00e1 en la sucesi\u00f3n.\n-- * Si x est\u00e1 en la sucesi\u00f3n, entonces 2x, 3x y  5x tambi\u00e9n est\u00e1n.\n-- * Ning\u00fan otro n\u00famero est\u00e1 en la sucesi\u00f3n. \n\n-- hamming es la sucesi\u00f3n de Hamming. Por ejemplo,\n--    take 12 hamming == [1,2,3,4,5,6,8,9,10,12,15,16]\nhamming :: [Int]\nhamming = 1 : mezcla3 [2*i | i <- hamming]  \n                      [3*i | i <- hamming]  \n                      [5*i | i <- hamming]  \n\n-- (mezcla3 xs ys zs) es la lista obtenida mezclando las listas\n-- ordenadas xs, ys y zs y eliminando los elementos duplicados. Por\n-- ejemplo, \n--    ghci> mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10]\n--    [2,3,4,5,6,8,9,10,12]\nmezcla3 :: [Int] -> [Int] -> [Int] -> [Int]\nmezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs)  \n\n-- (mezcla2 xs ys zs) es la lista obtenida mezclando las listas\n-- ordenadas xs e ys y eliminando los elementos duplicados. Por ejemplo,\n--    ghci> mezcla2 [2,4,6,8,10,12] [3,6,9,12]\n--    [2,3,4,6,8,9,10,12]\nmezcla2 :: [Int] -> [Int] -> [Int]\nmezcla2 p@(x:xs) q@(y:ys) | x < y     = x:mezcla2 xs q\n                          | x > y     = y:mezcla2 p  ys  \n                          | otherwise = x:mezcla2 xs ys\nmezcla2 []       ys                   = ys\nmezcla2 xs       []                   = xs\n<\/pre>\n
Las transparencias usadas en la clase son desde la p\u00e1gina 37 a la 45 del tema 11<\/a><\/p>\n