Reto 3 Torres de Hanoi

La Torre de Hanoi es un juego que consiste en tres estacas montadas en una tabla y n dis­cos de varios tamaños con agujeros en sus centros. Se supone que si un disco está en una estaca, sólo un disco de diámetro más pequeño se puede colocar enci­ma de él. Si se tienen todos los discos apilados en una estaca específica inicial, el problema consiste transferir los discos a otra estaca moviendo un disco a la vez.

Movimientos:

1 disco: 1 movimiento

2 discos: 3 movimientos

3 discos: 4 movimientos

Fórmula recursiva:

A₁= 1

A₂=2*(A₁)+1=3

A₃=2*(A₂)+1=7

A₄=2*(A₃)+1=15

Fórmula explícita hacía adelante:

A₁=2*A₀+1=2*0+1=2^1-1

A₂=2*A₁+1=2*1+1=2^2-1

A₃=2*A₂+1=2*3+1=2^3-1

A₄=2*A₃+1=2*7+1=2^4-1

.

.

.

A_n=2*A_n-1+1=2^n-1+2^n-2+…+2^1+1=2^n-1

Para saber la cantidad mínima de movimientos requeridos, basta con elevar el 2 a la cantidad de discos y el resultado le restamos 1.


Aquí un video de cada solución dependiendo de la cantidad de discos.