Instinto Lógico

Recuerda que nadie debe pensar por tí.

Torres de Hanoi.

El juego matemático de las Torres de Hanoi consiste en un dispositivo que consta de tres varillas verticales A, B y C y un número variable de discos. Los n discos son todos de diferente tamaño y, en la posición de partida del juego, todos los discos están colocados en la varilla A ordenados de mayor a menor tamaño, esto es, el mayor en el lugar más bajo y el menor arriba. En el mundo de la informática se emplea como el ejemplo de recursividad por excelencia.

hanoiDel número de discos depende la complejidad de la solución. El juego consiste en lo siguiente: Comenzando en la posición de partida. Trasladar todos los discos a la varilla B, pero colocados también de mayor a menor, en el mismo orden en el que estaban colocados en la varilla A. Para el traslado de discos podemos utilizar la varilla C, pero se debe cumplir siempre la condición de que sólo se puede mover un disco cada vez y que en ningún caso y en ningún paso se podrá colocar un disco mayor sobre otro de menor radio que él.

El origen de juego de las Torres de Hanoi dejó de caminar por el terreno de la historia y se elevó por las nubes de la leyenda. Dice la leyenda que cuando Dios creó el mundo, creó tres varillas de diamante con 64 discos de tamaños diferentes y los colocó en orden descendente en la primera de las varillas. Alrededor de las varillas creó un monasterio con monjes, a los que encomendó la tarea de trasladar todos los discos a la tercera varilla con las condiciones que hemos detallado anteriormente.

El día que los monjes acaben de trasladar los discos el mundo acabará. Cuando resolvamos el problema veremos que, por ahora no hay motivos de preocupación, ya que el mínimo número de movimientos necesarios para cumplir el cometido que Dios encargó a los monjes es de , que es un número enormemente grade. Para hacernos una idea del tiempo que se necesita para hacer esos movimientos supongamos que los monjes hicieran un movimiento por segundo; los segundos son, aproximadamente 585 mil millones de años, que son muchísimos años. Basta con pensar que el Universo sólo tiene 15 mil millones de años de antigüedad, que es la cuarentaava parte.

¿Cuántos movimientos son necesarios para trasladar los discos de A a C con las condiciones exigidas?

Resolución: recordemos las condiciones:

1.- Sólo se puede mover un disco cada vez.

2.- Nunca debe apilarse un disco sobre otro más pequeño

Pasaremos a analizar el problema según el número de discos:

Caso 1: Para un disco en la varilla A:

  • Pasar el disco de A a B.

Solución: Un movimiento.

Caso 2: Para dos discos en la varilla A:

  • Pasar disco de A a C.
  • Pasar un disco de A a B.
  • Pasar disco de C a B.

Solución: Tres movimientos.

Caso 3: Para tres discos en la varilla A. (Utilizaremos el movimiento de cuando en A hay dos discos)

  • Pasar dos discos de A a C, usando B como almacenamiento temporal. (3)
  • Pasar disco de A a B. (1)
  • Pasar dos discos de C a B, usando A como almacenamiento temporal (3)

Solución: Siete movimientos.

Caso 4: Para cuatro discos en la varilla A. (Utilizaremos el movimiento de cuando en A hay tres discos)

  • Pasar tres discos de A a C, usando B como almacenamiento temporal. (7)
  • Pasar un disco de A a B. (1)
  • Pasar tres discos de C a B, usando A como almacenamiento temporal (3)

Solución: quince movimientos.

Caso general: Para n discos en la varilla A. (Utilizaremos el movimiento de cuando en A hay discos)

  • Pasar n-1 discos de A a C, usando B como almacenamiento temporal.
  • Pasar un disco de A a B. (1)
  • Pasar n-1 discos de C a B, usando A como almacenamiento temporal

Solución:   número de movimientos movimientos.

Resumiendo:

 

Nº de discos

Movimientos

1

 

1= 21-1

2

3= 22-1

3

7= 23-1

4

15= 24-1

 

n

2n-1

 

 

En consecuencia, la función recursiva que nos da la expresión del número de movimientos del problema de las Torres de Hanoi es :

problema-hanoi

Podemos comprobar sin dificultad que el número de movimientos para unas torres de Hanoi con n discos será:

2n-1

TORRES DE HANOI EN C

A continuación se expone un programa en C para resolver el juego de las torres de Hanoi en C.

 

#include <stdio.h>
#include <conio.h>

void hanoi(int n,int com, int aux, int fin);

void main(void){

clrscr();
char com=’A’;
char aux=’B’;
char fin=’C’;
int n;

printf(“\nN£mero de discos: “);
scanf(“%d”,&n);
fflush(stdin);

printf(“\n\nLos movimientos a realizar son: \n”);
hanoi(n,com,aux,fin);
}

void hanoi(int n,int com, int aux, int fin){

if(n==1){
printf(“%c->%c”,com,fin);
}
else{
hanoi(n-1,com,fin,aux);
printf(“\n%c->%c\n”,com,fin);
hanoi(n-1,aux,com,fin);
}
}

JUEGO DE LAS TORRES DE HANOI EN FLASH

(Juego obtenido de DisfrutalasMatematicas.com )

Be Sociable, Share!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Instinto Lógico © 2014 Frontier Theme