Recursividad aplicada: Torres de Hanoi

Este juego matemático es clásico de los problemas de programación. Hoy vamos a ver cómo calcular el número de movimientos necesarios para resolver el juego según el número de discos, de forma recursiva en C++.

#include
int hanoi(int n)
{
    if(n==1)
        return 1;
    else
        return 2 * hanoi(n-1) + 1;
}
int main()
{
    int disc, mov;
    printf("::TORRES DE HANOI::n");
    printf("Numero de discos: ");scanf("%i",&disc);
    printf("tMovimientos necesarios: %in", hanoi(disc));
    return 0;
}

Otro algoritmo raro. Lo que sabemos es que si tenemos 1 disco el número de movimientos es 1 y que ese es nuestro caso base (si n==1 retorna 1), a partir de ahí el número de movimientos se puede calcular si multiplicamos por dos el número de movimientos para n-1 y le sumamos 1, o sea: 2 + hanoi(n-1) + 1

  • Si son 2 discos, entonces 2 * hanoi(1) + 1 = 2 * 1 + 1 = 3
  • Si son 3 discos, entonces 2 * hanoi(2) + 1 = 2 * 3 + 1 = 7
  • etc

11 thoughts on “Recursividad aplicada: Torres de Hanoi

  1. mmm la verdad no entiendo la cuenta que hace la subrutina al poner valores mayores a tres o sk acaso return 2 toma esos valores porq de otra forma los resultados no me dan😦

  2. Hola, yo les puedo explicar porque se multiplica por 2 y porque se le suma 1. Bueno resulta que el 2 corresponde a la complejidad logaritmica base 2, es decir un disco puede o no estar en un determinado poste (digamos tomar el valor 0 o 1, como en el cálculo binario), por ello (2^n)-1 movimientos, luego se le suma 1 porque existe un poste auxiliar que si bien ayudará a los movimientos, aumentará la complejidad (matemáticamente hablando) de la cantidad de posibles combinaciones. Recuerden que aqui lo que el autor menciona solo es el cálculo del número de movivmientos, si quisieran ver los movivmientos, entonces es necesario hacer unos cambios a la función recursiva que aquí se plantea.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s