Cómo determinar el número de pasos en el problema de Towers of Hanoi

Answer 1

El problema de la Torre de Hanoi tiene la siguiente relación de recurrencia:
T (n) = 2 * T (n-1) +1

Explicación de la relación de recurrencia anterior:

Como en el problema de la torre estándar de Hanoi, tenemos tres clavijas. Deja que sea A, B, C.
La configuración inicial es que todos los discos de orden creciente de radios se apilan en el orden de radio pequeño a mayor en el Disco A. Necesitamos movernos a todos estos discos a la clavija B usando la clavija intermedia C. Solo se permite un movimiento a la vez.

inicialmente hay n discos en la clavija A.

Entonces, primero movemos n-1 discos a la clavija C (T (n-1)) + movemos el disco más grande a la clavija B + movemos todo el disco restante (n-1) de la clavija c a la clavija A. (T (n-1 )).

Por lo tanto, [matemáticas] T (n) = T (n-1) + 1 + T (n-1). [/ Matemáticas]

La solución a la relación de recurrencia anterior se rige por su:
1. Ecuación característica c (p):
[matemáticas] x ^ {n} -2 * x ^ {n-1} = 0 [/ matemáticas]
=> raíces es x = 2
por lo tanto, [matemática] C (n) = k_ {1} * 2 ^ {n} [/ matemática], donde [matemática] k_ {1} [/ matemática] es constante.
2. Ecuación particular P (n):
P (n) = [matemáticas] k_ {2} [/ matemáticas], [ya que, [matemáticas] a_ {n} + c_ {1} * a _ {(n-1)} +…. = f (n) [/ math], y si f (n) es constante, la solución particular es algo constante].

Entonces, la solución total [matemática] T (n) = C (n) + P (n) = k_ {1} * 2 ^ {n} + k_ {2} [/ matemática]

=> [matemáticas] T (n) = k_ {1} * 2 ^ {n} + k_ {2} [/ matemáticas] —————— eq’n (1)

caso base son:
[matemáticas] T (0) = 0 [/ matemáticas]
[matemáticas] T (1) = 1 [/ matemáticas]

Considerando estos casos base y la ecuación (1), tenemos
[matemáticas] k_ {1} + k_ {2} = 0 [/ matemáticas] ———————- (i)
[matemáticas] 2 * k_ {1} + k_ {2} = 1 [/ matemáticas] ———————- (ii)

resolviendo (i) y (ii), tenemos

[matemáticas] k_ {2} = – k_ {1} = – 1. [/matemáticas]

Por lo tanto, [matemáticas] T (n) = 2 ^ {n} -1 [/ matemáticas], es la solución final.
¿Cuál es el número de movimientos necesarios con 3 clavijas?

Answer 2

La torre de hanoi

Este es un programa C ++ que toma el número de discos en la Torre de Hanoi como entrada y escupe el número mínimo de pasos necesarios como salida …

  #include 
 usando el espacio de nombres estándar;
 int power (int a, int k)
 {
     int x = 1;
     para (int i = 0; i > n;
     dec = potencia (n, 2) -1;
     cout << "El número mínimo de pasos necesarios es:" << dec;
     devuelve 0;
 }

Lo que me gusta de The Tower Of Hanoi es el hecho de que uno puede calcular fácilmente la cantidad mínima de pasos necesarios usando Números binarios (100100011001111001 ...)

Esto es lo que haces en este método rudo ...

Lo que básicamente he hecho en este programa es almacenar la entrada del usuario (número de discos) en una variable n. Luego construí un número binario (bin) usando solo 1 pero n veces. Entonces, si tiene digamos 3 discos, entonces bin = 111. O digamos n = 5, entonces bin = 11111 (cinco veces 1).

Ahora todo lo que queda por hacer es simplemente convertir este número binario recién construido en su equivalente decimal.

Veamos algunas salidas ...

¿Ves lo increíblemente grande que se pone

Gracias por leer 🙂

Answer 3

El número de pasos para resolver un problema de torre de Hanoi de discos [matemáticos] N [/ matemáticos] es [matemático] 2 ^ {N-1} [/ matemático].

En otro ángulo, el número de pasos también es igual al número total de nodos en un árbol binario completo de altura N.