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)


Warning: Missing argument 1 for cwppos_show_review(), called in /home/godie/godieboy.com/wp-content/themes/flat/content-single.php on line 29 and defined in /home/godie/godieboy.com/wp-content/plugins/wp-product-review/includes/legacy.php on line 18

Comentarios

  1. Información Bitacoras.com…

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

  2. […] Para ver la solucion sin recursividad clic aqui […]

  3. […] Hize una clase Pila como se explico uno posts antes para que hagan el ejercicio de las torres de hanoi sin recursividad. […]

  4. Denisse dice:

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

    1. Yared dice:

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

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

  6. 3dfx dice:

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

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

  7. Carmen dice:

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