El problema de la Torre de Hanoi

Cuando programes, no pienses en el proceso recursivo en tu mente (darle la vuelta te dará dolor de cabeza y te mareará después de un tiempo).

Creo que tiene clara la secuencia. La llamada recursividad consiste en convertir an en a(n-1) para tratar el problema. El mismo método se utiliza para tratar un término general. Simplemente proporcione a1 (o también hay a2), que es la condición para el final de la recursividad.

Supongamos que hay tres agujas A B C en la Torre de Hanoi, y solo considere mover la placa inferior.

Si solo hay una placa, es directamente A-gt;

Si solo hay dos placas, es A-gt; B luego A-gt;

Si solo hay tres placas, es A-gt; gt; B C-gt; B then Agt; Puede encontrar que

(1) Si desea mover el disco inferior, primero debe mover el top n-1 al disco B.

(2) Al mover la placa inferior entre n-1 en el disco B, simplemente cambie la aguja de origen y la aguja del medio, es decir: considere B como A y A como B

p>

(3) A continuación, al mover la placa inferior entre n-2 en el disco A, simplemente restaure la aguja de origen y la aguja del medio, es decir: A sigue siendo A, B sigue siendo B. Este paso es el mismo que el primer paso, es decir, los dos pasos 1 y 2 están en el ciclo de ngt;

(4) Cuando solo hay una placa (n=1), simplemente vaya de la "aguja de origen" a la "aguja de destino" y finalice esta recursión.

Por lo tanto, el programa recursivo sólo necesita los tres pasos anteriores para realizar el movimiento de la Torre de Hanoi.