Pseudocodigo de las torres de Hanoi

Esta vez comparto con ustedes el pseudocodigo para resolver el problema de las torres de hanoi utilizando recursividad, este dilema es tipico de la programacion que suelen dejar en las escuelas como tarea.

Para ver la solucion sin recursividad clic aqui

Descripcion del problema:

Se tienen tres torres y un conjunto N de discos dediferentes tamaños. Cada uno tiene una perforacion en el centro que le permite desplazarse por las torres. Inicialmente, los N discos estan ordenados de mayor a menor en una de las torres. Se debe de pasar los discos a otra torre utilizando la tercera como auxiliar. Este movimiento debe hacerse respetando las siguientes reglas:

1.- En cada movimiento solo puede intervenir un disco, por lo tanto siempre sera el disco superior el que puede moverse.
2.-No puede quedar un disco sobre otro de menor tamaño.

Explicacion grafica:

torres hanoi

Pseudocodigo:

hanoi(n, origen, destino, auxiliar)

si n=1

entonces

mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}


si no

//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino

//{mover n-1 discos de la torre auxiliar a la torre destino}

llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}


fin

fin

Pequeño analisis del procedimiento

Supongamos que tenemos solo dos discos (N=2) en la torre ORIGEN y debemos pasarlos a la torre DESTINO.

Recordemos que un disco no puede estar sobre uno de menor tamaño, entonces no podemos mover ambos discos a la misma columna en los dos primeros movimientos, debido a que quedaria el disco mas pequeño bajo el disco mas grande, por lo tanto se requiere de tres movimientos para lograr el objetivo:

Mover disco de  ORIGEN a AUXILIAR
Mover disco de ORIGEN a DESTINO
Mover disco de AUXILIAR a DESTINO

En caso de tener 3 discos, es decir N=3 se deben hacer los siguientes movimientos:

Mover disco de  ORIGEN a DESTINO
Mover disco de ORIGEN a AUXILIAR
Mover disco de DESTINO a AUXILIAR
Mover disco de  ORIGEN a DESTINO
Mover disco de AUXILIAR a ORIGEN
Mover disco de AUXILIAR a DESTINO
Mover disco de ORIGEN a DESTINO

Formula

Si para N=2 tenemos que realizar 3 movimientos y para N=3, son 7 movimientos, podemos concluir la siguiente ecuacion:

FORMULA

Donde:
NM = numero de movimientos
N= Numero de discos

Solo hace falta elegir el lenguaje para implementar el algoritmo. Si algo les hace falta haganmelo saber en los comentarios. Espero les sirva.

Comentarios

  1. Información Bitacoras.com…

    Valora en Bitacoras.com: Esta vez comparto con ustedes el pseudocodigo para resolver el problema de las torres de hanoi, este dilema es tipico de la programacion que suelen dejar en las escuelas como tarea. El pseudocodigo utiliza la recursividad par…..

  2. ultimate733 dice:

    changos esto me ubiera servido mas hace un añejo cuando me lo dejaron de tarea hahahahaha

  3. […] explique el problema de las torres de Hanoi y publique una solucion recursiva a dicho problema. En este post pondre la solucion No recursiva  […]

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

  5. angel dice:

    disculpa pero como podria hacerlo en visual basic para k sea visible

  6. abel dice:

    Hola quisiera ayuda para entender la recursividad de este codigo!

    Class Hanoi1
    {
    public void Hanoi(int N1, string A1, string B1, string C1)
    {
    int Cont = 0;

    if (N1 == 1)
    {
    Console.WriteLine(“Mover un Discos de ” + A1 + ” a ” + C1);
    Cont++;
    }
    else
    {
    Hanoi(N1 – 1, A1, C1, B1);
    Console.WriteLine(“Mover un Disco de ” + A1 + ” a ” + C1);
    Hanoi(N1 – 1, B1, A1, C1);
    Cont++;
    }
    }

    }