Deitel_C++_3.42 (Torres de Hanoi en C++, Version Recursiva)

_____________________________________________________________________________________
3.42 (Las Torres de Hanoi) Cada científico de la computación en ciernes debe batallar con ciertos problemas clásicos. Las Torres de Hanoi representan uno de los más famosos. La leyenda cuenta que en un templo del lejano oriente, unos sacerdotes intentan mover una pila de discos de una pila a otra. La pila inicial tiene 64 discos y están acomodados de abajo hacia arriba en orden de tamaño decreciente. Los sacerdotes intentan mover la pila de esta pila hacia una segunda, con las restricciones de mover sólo un disco a la vez, y que ningún disco más grande debe colocarse en encima de uno más pequeño. Una tercera pila está disponible para alojar temporalmente los discos. Se supone que el mundo terminará cuando los sacerdotes completen su tarea, por lo cual no hay ningún incentivo para facilitarles la tarea.
_____________________________________________________________________________________

Antes de intentar resolver este problema es bueno conseguirse un juego de torres de hanoi por ahi, los he visto en puestos callejeros de ajedrez, cartas, etc.; o improvisar uno, como hacen en las ferias de ciencias; tal vez la primera impresion sea que es complicado, sin embargo no tardaran en darse cuenta de que una vez que logran agarrar la idea, la solucion es bastante aburrida, solo hay que repetir una y otra vez el mismo procedimiento. Es por eso que este problema es tan susceptible de ser resuelto mediante la recursion. Se daran cuenta de que hay que solucionarlo de abajo para arriba. Tienen que mover el disco que esta en el fondo hacia la espiga de destino, para hacer esto tienen que mover una torre un poco menor (de solo N-1 discos) hacia la espiga destino. Este ultimo paso es crucial. Es muydiscos) hacia la espiga intermedia y entonces si mover el disco mas grande a su destino. Ahora lo que falta es mover la torre de N - 1 discos que esta en la importante darse cuenta de que la torre con N - 1 discos se mueve DOS VECES, la primera hacia la espiga intermedia y la segunda hacia la espiga de destino despues de haber movido el disco de abajo. Si logran comprender esto entonces ya resolvieron el problema, solo hagan lo mismo con todas las torres hasta que lleguen a tener una torre con un solo disco. En ese caso limite ya no necesitan usar una espiga intermedia, pueden pasar directamente el disco del origen al destino.

# include <iostream>

using namespace::std;

////////////////////////////////////////////////////////////////////

// FUNCION MOVER_TORRES

////////////////////////////////////////////////////////////////////

void Mover_Torres(int N, int Origen, int Intermedio, int Destino)

{ // Abre funcion Mover_Torres

if ( N > 1 )

{ // Abre if
Mover_Torres( N - 1, Origen, Destino, Intermedio);

/* Se mueve una torre de N - 1 discos desde la espiga origen
pero hacia la espiga intermedia ( para dejar la destino libre)
usando la espiga destino como intermedia cout << "\nMueve disco "
<< N << " de " << Origen << " a " << Destino <<endl;
con esta instruccion mueven el disco de la base hacia su destino
Como comento arriba, ahora hay que mover nuevamente la torre de
N - 1 discos hacia el destino original ( en donde se ha puesto el
disco mayor ) Esto implica una segunda llamada recursiva. Ahora
el origen es la espiga intermedia a la que se movio la torre y
el destino es el destino primitivo,lo que originalmente era el
origen se usa ahora como espiga intermedia */

cout <<"\nMueve el disco " <<  N  << " de " << Origen << " a " <<  Destino << endl;
Mover_Torres( N - 1, Intermedio, Origen, Destino);
} // Cierra if

// El caso limite mas sencillo se resuelve directamente

if ( 1 == N )
cout << "\nMueve el disco 1 de " << Origen << " a " << Destino << endl;

} // Cierra funcion Mover_Torres

int main()

{ // Abre funcion main
int Discos;
cout << "\nEste programa resuelve el problema clasico de las Torres de Hanoi";
cout <<" mediante la recursion." << endl;
cout << "\nPor favor introduzca el numero de discos que quiere mover ";
cout << " de la pila 1 a la pila 3" << endl;
cin >> Discos;

Mover_Torres( Discos, 1, 2, 3);

cout << endl << endl;

return 0;

} // Cierra funcion main

Como nota final se daran cuenta de que para pasar N discos de una torre a otra se requieren (2^N) - 1 movimientos. Asi que si los monjes de marras inician con una torre de 64 discos necesitaran hacer (2 ^ 64) - 1 ( = 18446744073709551616) movimientos para terminar. Suponiendo que hacen un movimiento por segundo entonces necesitarian 584942417355 años para terminar el trabajo. Pero como esto supera, y con mucho, la edad del universo, entonces no hay por que preocuparse de los avances de los monjes ni del fin del mundo.