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
|
1 2 |
data Poste = A | B | C deriving Show |
Definir las funciones
|
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,
|
1 2 3 4 5 6 |
λ> 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,
|
1 2 3 4 5 6 7 8 |
λ> 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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