La pregunta es : ha dado una clavija 3 (clavija de inicio, clavija auxiliar / auxiliar y clavija de finalización) La clavija de inicio contiene 3 discos de diferentes tamaños como se muestra. Tiene que mover todo el disco de la clavija de inicio a la clavija de finalización mediante la clavija auxiliar.
Hay pocas reglas que deben tener en cuenta,
1. Solo se puede mover un disco a la vez.
- Cómo obtener el índice de clasificación de matriz
- ¿Cómo podemos encontrar la aparición de una cadena dada (la secuencia no importa) en una secuencia dada en Java?
- ¿Cómo se vinculan los nodos al mismo nivel en un árbol binario?
- ¿Es el amor solo un algoritmo informático?
- ¿Qué debe saber todo programador sobre Lisp?
2. El disco de gran tamaño no se puede colocar encima del disco de pequeño tamaño.
Algoritmo
Di si hay,
Solo 1 disco presente (n = 1)
Podemos mover directamente 1 disco de la clavija A (fuente) a la clavija B (destino) .
Nota: No hay uso de clavija auxiliar cuando solo hay 1 disco, por lo que lo trasladamos directamente desde el origen al destino.
Entonces, para un total de 1 disco, independientemente de la Clavija que esté presente, moverlo a cualquier otra Clavija requiere solo 1 paso.
(1 disco se puede mover de la clavija A a la clavija B, la clavija B a la clavija C, la clavija C a la clavija A, etc. en 1 paso).
En nuestra recursividad, este será nuestro caso base.
Cuando el disco restante sea solo 1, muévalo directamente de principio a fin.
2 discos presentes (n = 2)
Para 2 discos, debemos realizar los siguientes 3 pasos,
1. Mueva el disco 1 de la clavija A a la clavija Ayuda,
2. Mueva el disco 2 de la clavija A a la clavija B,
3. Mueva el disco 1 de la Ayuda de clavija a la Clavija B.
Esto dice, para mover 2 discos de la clavija A a la clavija B, requiere 3 pasos.
Nota: En general, podemos decir que, para 2 discos, se requieren un mínimo de 3 pasos para mover discos desde cualquier clavija de origen a cualquier clavija de destino.
3 discos presentes (n = 3)
Si tenemos 3 discos, primero lo dividiremos en 2 discos (y lo reduciremos a 1 disco) usando recursividad.
Ya sabemos cómo resolver un problema con 2 discos.
En nuestro problema Towers of Hanoi, si hay más de 2 discos, haga una llamada recursiva en el disco hasta que solo quede un disco.
Tenga en cuenta el rastro de la pila de recursión de la Torre de Hanoi y será muy fácil de codificar.
Programa de seguimiento de pila
Explicación detallada paso a paso con el programa: Torre de Hanoi