Las torres de Hanói

Las torres de Hanoi es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.

Los postes se pueden representar mediante el siguiente tipo de datos

   data Poste = A | B | C
     deriving Show

1 2	data Poste = A \| B \| C deriving Show

Definir las funciones

   movimientos :: Integer -> [(Integer,Poste,Poste)]
   hanoi       :: Integer -> IO ()

1 2	movimientos :: Integer -> [(Integer,Poste,Poste)] hanoi :: Integer -> IO ()

tales que

(movimientos n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,

     λ> movimientos 1
     [(1,A,C)]
     λ> movimientos 2
     [(1,A,B),(2,A,C),(1,B,C)]
     λ> movimientos 3
     [(1,A,C),(2,A,B),(1,C,B),(3,A,C),(1,B,A),(2,B,C),(1,A,C)]

λ> movimientos 1

[(1,A,C)]

λ> movimientos 2

[(1,A,B),(2,A,C),(1,B,C)]

λ> movimientos 3

[(1,A,C),(2,A,B),(1,C,B),(3,A,C),(1,B,A),(2,B,C),(1,A,C)]

(hanoi n) escribe los mensajes de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,

     λ> hanoi 3
     Mueve el disco 1 de A a C
     Mueve el disco 2 de A a B
     Mueve el disco 1 de C a B
     Mueve el disco 3 de A a C
     Mueve el disco 1 de B a A
     Mueve el disco 2 de B a C
     Mueve el disco 1 de A a C

λ> hanoi 3

Mueve el disco 1 de A a C

Mueve el disco 2 de A a B

Mueve el disco 1 de C a B

Mueve el disco 3 de A a C

Mueve el disco 1 de B a A

Mueve el disco 2 de B a C

Mueve el disco 1 de A a C

Soluciones

data Poste = A | B | C
  deriving (Eq, Show)

movimientos :: Integer -> [(Integer,Poste,Poste)]
movimientos n = aux n A B C
  where  
    aux n a b c
      | n == 1    = [(1,a,c)]
      | otherwise = aux (n-1) a c b ++ (n,a,c) : aux (n-1) b a c

hanoi :: Integer -> IO ()
hanoi n = 
  putStrLn (unlines (map mensaje (movimientos n)))

-- (mensaje (n.x.y)) es la cadena indicando que el disco n se ha movido
-- desde el poste x al poste y. Por ejemplo, 
--    λ> mensaje (1,A,B)
--    "Mueve el disco 1 de A a B"
mensaje :: (Integer,Poste,Poste) -> String
mensaje (n,x,y) =
  "Mueve el disco " ++ show n ++ " de " ++ show x ++ " a " ++ show y

data Poste = A | B | C

deriving (Eq, Show)

movimientos :: Integer -> [(Integer,Poste,Poste)]

movimientos n = aux n A B C

where

aux n a b c

| n == 1 = [(1,a,c)]

| otherwise = aux (n-1) a c b ++ (n,a,c) : aux (n-1) b a c

hanoi :: Integer -> IO ()

hanoi n =

putStrLn (unlines (map mensaje (movimientos n)))

-- (mensaje (n.x.y)) es la cadena indicando que el disco n se ha movido

-- desde el poste x al poste y. Por ejemplo,

-- λ> mensaje (1,A,B)

-- "Mueve el disco 1 de A a B"

mensaje :: (Integer,Poste,Poste) -> String

mensaje (n,x,y) =

"Mueve el disco " ++ show n ++ " de " ++ show x ++ " a " ++ show y

Pensamiento

En preguntar lo que sabes
el tiempo no has de perder …
Y a preguntas sin respuesta
¿quién te podrá responder?

Antonio Machado

2 Comentarios

data Poste = A | B | C  deriving Show
 
movimientos :: Integer -> [(Integer,Poste,Poste)]
movimientos n = aux n A B C
  where aux 1 a b c = [(1,a,c)]
        aux n a b c = (aux (n-1) a c b) ++ [(n,a,c)] ++ (aux (n-1) b a c)
 
hanoi :: Integer -> IO ()
hanoi n =
  sequence_ [putStrLn ("Mueve el disco " ++
                       show a ++
                       " de " ++
                       show b ++
                       " a " ++
                       show c)
            | (a,b,c) <- movimientos n]

data Poste = A | B | C deriving Show

movimientos :: Integer -> [(Integer,Poste,Poste)]

movimientos n = aux n A B C

where aux 1 a b c = [(1,a,c)]

aux n a b c = (aux (n-1) a c b) ++ [(n,a,c)] ++ (aux (n-1) b a c)

hanoi :: Integer -> IO ()

hanoi n =

sequence_ [putStrLn ("Mueve el disco " ++

show a ++

" de " ++

show b ++

" a " ++

show c)

| (a,b,c) <- movimientos n]

Responder

movimientos :: Integer -> [(Integer,Poste,Poste)]
movimientos n = aux n  A B C
  where aux 1 a b c = [(1,a,c)]
        aux n a b c =  aux (n-1) a c b ++ (n,a,c):aux (n-1) b a c

hanoi :: Integer -> IO ()
hanoi x = do
  let xs = movimientos x
  aux xs
  where aux []           = return ()
        aux ((x,y,z):xs) = do
             putStrLn ("Mueve el disco " ++
                       show x ++
                       " de " ++
                       show y ++
                       " a " ++
                       show z)
             aux xs

movimientos :: Integer -> [(Integer,Poste,Poste)]

movimientos n = aux n A B C

where aux 1 a b c = [(1,a,c)]

aux n a b c = aux (n-1) a c b ++ (n,a,c):aux (n-1) b a c

hanoi :: Integer -> IO ()

hanoi x = do

let xs = movimientos x

aux xs

where aux [] = return ()

aux ((x,y,z):xs) = do

putStrLn ("Mueve el disco " ++

show x ++

" de " ++

show y ++

" a " ++

show z)

aux xs

Responder

Las torres de Hanói

Soluciones

Pensamiento

2 Comentarios

Leave a Reply to frahidzamCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

2 Comentarios

Leave a Reply to frahidzamCancel reply

Entradas recientes

Buscar

Correo electrónico