Las torres de Hanoi, divide y venceras

Las torres de Hanoi

• Una antigua leyenda dice que en cierto monasterio de Hanoi
había tres postes y que en uno de ellos había 64 discos de
tamaño decreciente, uno encima de otro y con el mayorhasta
abajo. Los monjes del monasterio han estado trabajando sin
cesar para llevar los discos desde su poste original hasta algún
otro siguiendo una regla sencilla: solamente pueden mover un
disco a lavez de un poste a otro, siempre y cuando queda
arriba de uno mayor. La leyenda indica que el mundo
terminará en el momento en que los monjes hayan logrado su
propósito. Nuestra labor será ayudarle alos monjes en el
proceso.

• Llamemos a los postes A, B y C (siendo A el poste original y C el poste al
que queremos mover todos los discos). Si solamente hubiera un disco, la
tarea hubiera sido muysencilla: movamos el único disco del poste A al
poste C (y el mundo se hubiera terminado en un santiamén). Si
solamente hubieran dos discos, la tarea no hubiera sido mucho más
difícil: basta mover eldisco pequeño al poste B, después el disco grande
al poste C y finalmente el disco pequeño al poste C. Si continuamos de
esta manera, pronto nos daremos cuenta que la labor monumental de
mover los 64discos se reduce a la siguiente: movamos los 63 discos más
pequeños del poste A al B, movamos el disco más grande del poste A al C
y finalmente movamos los 63 discos más pequeños del poste B al C.
¿Cómohacemos para mover los 63 discos? Lo haremos de la misma
forma, excepto que renombrando los postes adecuadamente.

• El problema de mover n discos de A a B se
puede ver como dos subproblemas de n-1discos. Primero movemos n-1 discos de A a C,
quedando el n-éismo disco expuesto en A. Se
mueve este disco de A a B. Después se
mueven los n-1 discos de C a B. Para mover n1 discos aplicamos estemétodo de forma
recursiva.

• Hanoi(n, Original, Auxiliar, Destino)
Comienza
Si n es mayor que 0 entonces
Hanoi(n-1, Original, Destino, Auxiliar)
Mueve un disco de Original a Destino
Hanoi(n-1,...