Expresión recursiva de las Torres de Hanoi para el algoritmo EVERY

Question

Cuál es el algoritmo recursivo para mover $n$ discos dice, es:

1. Si $n > 1$ , moverte $n-1$ discos de A a B.
2. Mueve el $n$ el disco de A a C.
3. Si $n > 1$ , moverte $n-1$ discos de B a C.

Dejemos que $T_n$ sea el número de movimientos para mover n discos.

Tenemos $ T_n=2T_{n-1}+1 , T_1=1 $ Así que $T_n=2^n-1, n \geq 1 $

¿Es correcto decir que para cada algoritmo resolver el problema de las Torres de Hanoi, es cierto que $$ T_n=2T_{n-1}+c $$ Por lo tanto, necesitaríamos saber $c$ (número de movimientos para mover el último disco de A a C) y algunos otros $T_i$ con el fin de calcular $T_ n$ por cada $n$ .

Gracias de antemano

Answer 1

"Cada algoritmo" es un conjunto bastante amplio de algoritmos. Si se dibuja, incluso para tres discos, el gráfico de los posibles estados y los movimientos entre ellos, se obtiene un cuadro muy complicado:

Aquí, estoy representando un estado como una cadena de la ubicación del primer, segundo y tercer disco, por lo que estamos tratando de obtener de aaa a ccc .

Un algoritmo sería simplemente cualquier método para hacerlo. Si quieres que el algoritmo no tenga memoria, en el sentido de que siempre haga lo mismo desde cualquier estado, entonces podrías obtener el número de movimientos a $T_n = 3^n-1$ Tomando la ruta más indirecta posible, y visitando cada uno de los otros estados antes de llegar desde aa...a a cc...c . Si no es así, se puede hacer que el algoritmo tarde un tiempo arbitrario, por ejemplo, siguiendo la regla "Mover el primer disco por $2^{2^n}$ veces, entonces utiliza el algoritmo ordinario".

En particular, no es cierto que todo algoritmo obedezca a una recurrencia de la forma $T_n = 2T_{n-1} + c$ . Un algoritmo general:

• No necesita mover el último disco de A a C directamente, pero podría mover el último disco de A a B a C (recorriendo el diagrama de arriba el camino largo).
• No necesita dar un número constante de pasos, $c$ para mover el último disco de A a C, pero podría tomar un número de pasos dependiendo de $n$ .
• No necesita seguir reglas similares antes de mover el último disco y después de moverlo. (El hecho de que el algoritmo estándar hace seguir la misma regla en ambos casos es lo que nos da la $2T_{n-1}$ plazo).