Ya explique el problema de las torres de Hanoi y publique una solucion recursiva a dicho problema. En este post pondre la solucion No recursiva iterativa en modo de pseudocodigo.
Pseudocodigo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
solucionIterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (n>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (n>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
Explicacion breve del pseudocodigo.
La recursion sacrifica mucho espacio en memoria para guardar el estado del flujo del programa en el momento en que la recursion es iniciada, por ello resulta costoso en cuanto a espacio en memoria y debemos buscar otro tipo de soluciones. En este caso simularemos la recursion utilizando pilas para guardar el estado de las variables.
En el algoritmo de recursion, utilizamos las variables n, origen, destino y auxiliar que pusimos como argumentos en el metodo HANOI. Bueno pues en este metodo tambien utilizaremos esas variables y para guardar el estado de cada una utilizaremos estructuras de tipo pila, crearemos una pila por variable y en estas pilas iremos guardando los valores que va tomando cada variable.
pilaN para guardar los valores de n
pilaO para guardar los valores de origen
pilaD para guardar los valores de destino
pilaA para guardar los valores de auxiliar
La variable tope la usaremos para indicar el ultimo valor de las pilas, es decir el que se encuentra hasta arriba por eso es de tipo entero, para indicar la posicion del elemento.
La variable varaux es una variable que sirve para rotar las pilas origen y destino, segun el movimiento que se desee hacer.
y la variable bandera, sirve como indicador, para saber si hay mas iteraciones que hacer o no, ya no habra mas movimientos que hacer si las pilas estan vacias.
En la siguiente tabla se muestran los valores que toman todas las variables en cada paso para un mejor entendimiento:
Comportamiento de variables en el metodo
Donde A, B y C representan el valor existente en la variable origen, destino y auxiliar respectivamente y podemos ver como estos valores van cambiando de posicion conforme aumentan los pasos.
y donde
[A:C] quiere decir que se mueve el valor A al valor C (sin confundir que en realidad el movimiento es de la variable origen a la variable destino, como lo indica el algoritmo)
Bitacoras.com
octubre 5, 2009 at 10:26 pmInformación Bitacoras.com…
Valora en Bitacoras.com: No hay resumen disponible para esta anotación…
Pseudocodigo de las torres de Hanoi | Godieboy
octubre 6, 2009 at 12:49 am[…] Para ver la solucion sin recursividad clic aqui […]
Pila de enteros en Java | Godieboy
octubre 11, 2009 at 9:26 pm[…] Hize una clase Pila como se explico uno posts antes para que hagan el ejercicio de las torres de hanoi sin recursividad. […]
Denisse
septiembre 25, 2010 at 2:40 pmSabes que tu algoritmo deja un renglon vacio??? por que??
Yared • Post Author •
septiembre 25, 2010 at 4:19 pmComo que un renglón vacÃo?
Ese algoritmo fue sacado de un libro, probablemente omità poner algo. Déjame checarlo paso por paso de nuevo =).
Pseudocodigo PILAS push() y pop() estructura de datos | Godieboy
octubre 13, 2010 at 8:49 pm[…] post anteriores dimos solucion al problema de las torres de Hanoi, de manera recursiva y no recursiva. Para la segunda opcion utilizamos estructuras de tipo pila, pero algunos lectores me regañaron […]
3dfx
octubre 2, 2011 at 3:02 pmOye una pregunta tenes un «repetir mientras (N>1)» la variable «N» es la misma «n» que entra como paramentro?
yared_usuario • Post Author •
octubre 3, 2011 at 2:52 pmAsà es, buena observación. He hecho las correcciones correspondientes. Muchas gracias por comentar =)
Carmen
abril 10, 2015 at 1:31 amAmi me corrio de esta forma, bueno hay un detalle cuando corre me corre bien los pasos pero al final corre uno extra con ceros
public void hanoi_Solucion(int Numero_discos, string Torre_Origen, string Torre_Auxiliar, string Torre_Destino)
{
int tope = 0;//Señala el tope de la pila
string aux;//Sirve como variable temporal para el intercambio de las pilas
int [] PilaN=new int [Numero_discos];
string[] PilaO = new string [Numero_discos];
string[] PilaD = new string[Numero_discos];
string[] PilaA = new string[Numero_discos];
Boolean bandera = false;//indicador si existe o no mas repeticiones
while (Numero_discos > 0 && bandera==false)
{
while (Numero_discos > 1)
{
tope = tope + 1;
PilaN[tope] = Numero_discos;
PilaO[tope] = Torre_Origen;
PilaD[tope] = Torre_Destino;
PilaA[tope] = Torre_Auxiliar;
Numero_discos = Numero_discos – 1;
aux = PilaD[tope];
PilaD[tope] = PilaA[tope];
PilaA[tope] = aux;
}
Console.WriteLine(«Movemos {0} a {1}», Torre_Origen, Torre_Destino);
bandera = true;
if (Numero_discos > 0)
{
Numero_discos = PilaN[tope];
Torre_Origen = PilaO[tope];
Torre_Destino = PilaD[tope];
Torre_Auxiliar = PilaA[tope];
tope = tope – 1;
Console.WriteLine(«Movemos {0} a {1}», Torre_Origen, Torre_Destino);
Numero_discos = Numero_discos – 1;
aux = Torre_Origen;
Torre_Origen = Torre_Auxiliar;
Torre_Auxiliar = aux;
bandera = false;
}
}