¿Cómo se puede resolver el problema de la torre de Hanói si hay discos de anchura similar en ella?

Question

Por ejemplo, una línea con "1111" representa un disco con un diámetro de longitud 4. Del mismo modo, una línea con "111" representa un disco con un diámetro de longitud 3.

A continuación se muestra la representación de una torre que tiene 5 discos. el disco de tierra tiene un diámetro 9, el disco '2' d=5, los discos '3 y 4' d=3 y el disco '4' tiene d = 1.

$1$

$111$

$111$

$ 11111$

$111111111$

¿Cuántos movimientos serán necesarios para trasladar este tipo de torres?

Answer 1

Si tienes dos discos iguales, entonces mientras estén en diferentes clavijas, no puedes mover ningún disco más grande. Así que no tiene sentido permanecer en esta situación más tiempo del necesario. Por lo tanto, la solución óptima debe ser mantener todos los discos del mismo tamaño juntos, y sólo dividirlos temporalmente cuando necesites moverlos todos de una clavija a otra, lo que debe ocurrir de uno en uno.

Esto reduce el problema al habitual de las Torres de Hanoi con un disco por clase de tamaño. Sólo hay que multiplicar el número de movimientos que hace cada disco en el estándar problema (a saber $2^n$ donde $n$ es el número de tamaños mayores) por el número de discos de un tamaño determinado, y luego se suma todo.

Answer 2

Es posible mover una torre de este tipo más rápido: Primero se "fusionan" discos de igual tamaño en uno solo, luego se resuelve el problema para el número reducido de discos, y después se sustituye cada movimiento de un disco obtenido por la fusión $k$ discos con el movimiento de la $k$ discos fusionados. En su ejemplo, primero tenemos que mover $4$ discos, que lleva $2^2-1=15$ se mueve. Entre ellos, $4$ se mueve en relación con el disco "III", y se sustituye por $8$ movimientos individuales, lo que resulta en un total de $15-4+8=19$ se mueve (en lugar de $31$ movimientos).

Answer 3

Después de considerar todos los métodos sugeridos y algunos cálculos llegué a esta llamada recursiva:

Todos sabemos que cuando no hay bloques de anchura similar se utiliza la llamada : $T_{n+1} = 2T_{n}+1$ Así que un poco de conocimiento te dirá claramente que en caso de que el bloque sea de la misma anchura que el anterior su llamada sería $T_{n+1} = T_{n}+1$