¿Qué es la Torre de Hanói?
La Torre de Hanói es un juego matemático y lógico que consiste en mover una serie de discos de diferentes tamaños entre tres postes (torres), siguiendo reglas específicas. Fue propuesto en 1883 por el matemático francés Édouard Lucas.
Reglas del juego
- Objetivo
- Transferir toda la pila de discos desde la torre inicial hasta la torre final usando la torre auxiliar.
- Hay tres torres: origen, auxiliar y destino.
- Todos los discos comienzan en la torre de origen, ordenados de mayor (abajo) a menor (arriba).
- Solo se puede mover un disco a la vez.
- Un disco nunca puede colocarse sobre uno más pequeño.
- El objetivo es mover todos los discos a la torre destino respetando las reglas anteriores.
¿Por qué se relaciona con la informática?
La Torre de Hanói es un problema clásico en informática porque ejemplifica conceptos fundamentales:
- Recursividad
- Complejidad computacional: el número mínimo de movimientos necesarios está dado por:
$$ 2^n - 1 $$
| Discos (n) | Movimientos mínimos |
|---|---|
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 9 | 511 |
Esto muestra un crecimiento exponencial, lo cual es importante para entender:
- Eficiencia de algoritmos
- Límites de escalabilidad
- Pensamiento algorítmico
- Estructuras de datos: el comportamiento de las torres es similar a una pila (stack); último en entrar, primero en salir (LIFO)