EJemplo de las Torres de Hanoi:
Hay tres postes: A, B y C. En el poste A se ponen cinco discos de diámetro diferente de tal manera
que un disco de diámetro mayor siempre queda debajo de uno de diámetro menor. El objetivo es
mover los discos al poste C usando B como auxiliar. Sólo puede moverse el disco superior de
cualquier poste a otro poste, y un disco mayor jamás puede quedar sobre uno menor. Considérese la
posibilidad de encontrar una solución. En efecto, ni siquiera es claro que exista una.
Ahora se verá si se puede desarrollar una solución. En lugar de concentrar la atenciń en una
solución para cinco discos, considérese el caso general de n discos. Supóngase que se tiene una
solución para n – 1 discos y que en términos de ésta, se pueda plantear la solución para n – 1 discos.
El problema se resolvería entonces. Esto sucede porque en el caso trivial de un disco (al restar 1 de
n de manera sucesiva se producirá, al final, 1) la solución es simple: sólo hay que mover el único
disco del poste A a C. Así se habrá desarrollado una solución recursiva si se plantea una solución
para n discos en términos de n – 1. Considérese la posibilidad de encontrar tal relación. Para el caso
de cinco discos en particular, supóngase que se conoce la forma de mover cuatro de ellos del poste
A al otro, de acuerdo con las reglas. ¿Cómo puede completarse entonces el trabajo de mover el
quinto disco? Cabe recordar que hay 3 postes disponibles.
Supóngase que se supo cómo mover cuatro discos del poste A al C. Entonces, se pondrá mover
éstos exactamente igual hacia B usando el C como auxiliar. Esto da como resultado la situación los
cuatro primeros discos en el poste B, el mayor en A y en C ninguno. Entonces podrá moverse el
disco mayor de A a C y por último aplicarse de nuevo la solución recursiva para cuatro discos para
moverlo de B a C, usando el poste A como auxilia. Por lo tanto, se puede establecer una solución
recursiva de las torres de Hanoi como sigue:
Para mover n discos de A a C usando B como auxiliar:
1. Si n = = 1, mover el disco único de A a C y parar.
2. Mover el disco superior de A a B n – 1 veces, usando C como auxiliar.
3. Mover el disco restante de A a C.
4. Mover los disco n – 1 de B a C usando A como auxiliar
Con toda seguridad este algoritmo producirá una solución completa por cualquier valor de n. Si n =
= 1, el paso 1 será la solución correcta. Si n = = 2, se sabe entonces que hay una solución para n –
1 = = 1, de manera tal que los pasos 2 y 4 se ejecutaran en forma correcta. De manera análoga,
cuando n = = 3 ya se habrá producido una solución para n – 1 = = 2, por lo que los pasos 2 y 4
pueden ser ejecutados. De esta forma se puede mostrar que la solución funciona para n = = 1, 2, 3,
4, 5,... hasta el valor para el que se desee encontrar una solución. Adviértase que la solución se
desarrolló mediante la identificación de un caso trivial (n = = 1) y una solución para el caso general
y complejo (n) en términos de un caso mas simple (n – 1).
Ya se demostró que las transformaciones sucesivas de una simulación no recursiva de una rutina
recursiva pueden conducir a un programa mas simple para resolver un problema. Ahora se simulará
la recursión del problema y se intentará simplificar la simulación no recursiva.
#include <iostream>
#include <cstdlib>
using namespace std;
int hanoi(int n, char origen, char destino, char auxiliar);
int main(){
int valor;
system("clear");
cout << "Introduzca numero a calcular: ";
cin >> valor;
hanoi(valor,'A','B','C');
return 0;
}
int hanoi(int n, char origen, char destino, char auxiliar){
if (n <= 1){
cout << "\nmover disco 1 del poste "<< origen << " al poste " << destino << endl;
}else {
hanoi(n-1, origen, auxiliar, destino);
cout << "\nmover disco " << n << " del poste " << origen << " al poste "<< destino;
hanoi (n-1, auxiliar, destino, origen);
}
}