lunes, diciembre 24, 2007

Asombrosa solución del problema

Pues si, no se si alguien lo ha intentado pero la resolución es asombrosa. Parece mentira que la cosa pueda funcionar y seguramente la mayoría dude de que funcione:

Creamos un fichero de texto llamado hanoi.lsp por ejemplo.

(defun hanoi (num-discos torre-origen torre-auxiliar torre-destino)
(when (> num-discos 0)
(hanoi (1- num-discos) torre-origen torre-destino torre-auxiliar)
(format t "~%Mover disco superior de la torre ~D a la torre ~D."
torre-origen torre-destino)
(hanoi (1- num-discos) torre-auxiliar torre-origen torre-destino)
)
T
)

Cargamos la función en el interprete lisp:
> (load 'hanoi)

y ya podemos verlo en funcionamiento:

Para 5 discos, torre 1 de origen, torre 2 auxiliar y torre 3 destino...

> (hanoi 5 1 2 3)



El resultado para (hanoi 4 1 2 3) es el siguiente:

> (hanoi 4 1 2 3)

Mover disco superior de la torre 1 a la torre 2.
Mover disco superior de la torre 1 a la torre 3.
Mover disco superior de la torre 2 a la torre 3.
Mover disco superior de la torre 1 a la torre 2.
Mover disco superior de la torre 3 a la torre 1.
Mover disco superior de la torre 3 a la torre 2.
Mover disco superior de la torre 1 a la torre 2.
Mover disco superior de la torre 1 a la torre 3.
Mover disco superior de la torre 2 a la torre 3.
Mover disco superior de la torre 2 a la torre 1.
Mover disco superior de la torre 3 a la torre 1.
Mover disco superior de la torre 2 a la torre 3.
Mover disco superior de la torre 1 a la torre 2.
Mover disco superior de la torre 1 a la torre 3.
Mover disco superior de la torre 2 a la torre 3.
T



Lo más importante es que para estas soluciones mágicas hay que asegurarse bien de que se pueda solucionar recursivamente. En el caso de HANOI era fácil, ya que es el problema recursivo más clásico de todos.

Saludos.

4 comentarios:

PS3Mania dijo...

Hola, me ha servido de mucho el codigo, pero quiero mejorarlo de manera que tenga el algoritmo esta entrada (hanoi (1 2 3) () ()) y que en cada iteracion me vaya dando la posicion de los discos...

Por ejemplo, la siguiente iteracion seria... (2 3) () (1)

No encuentro la manera de especificarlo...

Aitor Iriarte dijo...

Hola,
Siento el enorme retraso pero de verdad ando liadísimo. Ya le he dedicado tiempo al problema y estoy en condiciones de contestar:

Los algoritmos recursivos de hanoi se basan en un intercambio de columnas en cada llamada a la función recursiva.

Para lo que quieres hacer tú, no te sirve ese algoritmo, ya que te desbarata las listas que representan las columnas.

Vas a tener que utilizar uno de los infinitos algoritmos iterativos que existen. Cuidado porque no todos son igual de eficientes.

En este enlace tienes una buena explicación y dos algoritmos iterativos.

Aquí otro algoritmo iterativo.

Saludos.

Anónimo dijo...

La puta que los parioooooo !!!!!!!!
página de mierda

Anónimo dijo...

Al Anónimo anterior: ¡Que imbecil eres tio! Lamentablemente, nunca llegarás a entender el mal que haces por tu propia imbecilidad.