Torres de Hanoi

Las Torres de Hanoi es un juego matemático que consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en una varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento. El juego consiste en pasar todos los discos a otra varilla colocados de mayor a menor ascendentemente.

Leyenda: Dios al crear el mundo, colocó tres varillas de diamante con 64 discos en la primera. También creó un monasterio con monjes, los cuales tienen la tarea de resolver esta Torre de Hanoi divina. El día que estos monjes consigan terminar el juego, el mundo acabará. El mínimo número de movimientos que se necesita para resolver este problema es de 264-1. Si los monjes hicieran un movimiento por segundo, los 64 discos estarían en la tercera varilla en poco menos de 585 mil millones de años. Como comparación para ver la magnitud de esta cifra, la Tierra tiene como 5 mil millones de años, y el Universo entre 15 y 20 mil millones de años de antigüedad, sólo una pequeña fracción de esa cifra.

Algoritmo de Recursividad

El número de pasos para resolverlo crece exponencialmente conforme aumenta el número de disco es decir m=(2^n)-1

Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos. El algoritmo de la función sería el siguiente:

1. Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
2. Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
3. mover disco n a destino //mover la ficha grande hasta la varilla final
4. hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
5. terminar

Java

/*
{Pre: discos > 1 ^ discos = número de discos ^ ori,dest,aux = carácteres que identifiquen las torres}
{Post: Se escriben los movimientos a realizar, índicados a partir de
los carácteres que identifican las torres, para llevar todos los discos desde la torre origen
a la de destino}
*/
void hanoi(int discos, char ini, char dest, char aux) {
if (discos == 1) cout << class="st0">" --> " << class="kw1">else {
    hanoi(discos - 1, ori, aux, dest);
    cout << class="st0">" --> " << class="br0">(discos - 1, aux, dest, ori);
}
}

/*
Ejemplo de función que llama automáticamente a hanoi(int, char, char, char) solo dándole el número de discos
{Pre: discos > 1}
{Post: Se escriben los movimientos a realizar para llevar todos los discos
desde la torre de origen hasta la de destino. Las torres serán identificadascomo A B C siendo el origen A
y la de destino C}
*/
void hanoi(int discos) {
hanoi(discos, 'A', 'C', 'B');
}