Pseudocodigo torres Hanoi Sin recursividad

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

tabla de valores que van adquiriendo las variables en cada paso
tabla de valores que van adquiriendo las variables en cada paso

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)

9 comments
  1. Bitacoras.com
    octubre 5, 2009 at 10:26 pm

    Información Bitacoras.com…

    Valora en Bitacoras.com: No hay resumen disponible para esta anotación…

    Reply
  2. 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. […]

    Reply
  3. Denisse
    Denisse
    septiembre 25, 2010 at 2:40 pm

    Sabes que tu algoritmo deja un renglon vacio??? por que??

    Reply
    • Yared
      Yared • Post Author •
      septiembre 25, 2010 at 4:19 pm

      Como 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 =).

      Reply
  4. 3dfx
    3dfx
    octubre 2, 2011 at 3:02 pm

    Oye una pregunta tenes un “repetir mientras (N>1)” la variable “N” es la misma “n” que entra como paramentro?

    Reply
    • yared_usuario
      yared_usuario • Post Author •
      octubre 3, 2011 at 2:52 pm

      Así es, buena observación. He hecho las correcciones correspondientes. Muchas gracias por comentar =)

      Reply
  5. Carmen
    Carmen
    abril 10, 2015 at 1:31 am

    Ami 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;
    }
    }

    Reply
Leave a Reply

Your email address will not be published. Required fields are marked *

Do NOT follow this link or you will be banned from the site!