Proceso de ejecución de la Torre Pascal de Hanoi
Esta es una recursividad clásica.
Análisis: Este es un muy buen ejemplo de programación recursiva. A diferencia del programa recursivo anterior, primero tuvo un programa no recursivo y luego lo reescribió en forma recursiva. Si este problema no utiliza un procedimiento recursivo, es posible que no se inicie. Pongamos el ejemplo de tres piezas de oro:
Para pasar de la barra a a la barra b, hay que hacer la transición con la ayuda de la barra c. El plan de mudanza es:
A-B
Paso 2 A-C
Paso 3 B-C
A-B
Quinto Paso C-A
Paso 6 C-B
A-B
* * * Muévete siete veces para completar las tres pepitas de oro en el poste A, y muévelas según las reglas. requerido por la pregunta.
La pregunta requiere mover N monedas de oro del polo A al polo B de la misma manera:
1 Primero (recursivamente) mueva los n-1 bloques sobre el polo A a la barra On. C (use la barra B);
2. Luego mueva la única pieza en la barra A a la barra B
3. recursivamente) en la tira B (usando la tira A).
Este es un proceso de llamada recursivo. El proceso es el siguiente:
Programa P6-14;
Definir variables
n: entero;
Movimiento del proceso (n: integer; a, b, c: char); {definir proceso recursivo}
Inicio
Si n=1, entonces
writeln('move ', n, 'de', a, 'a', b)
Else {Múltiples sectores, recursivo}
Iniciar
move(n-1, a , c, b); {mover recursivamente n-1 bloques de A a C y usar la varilla B para transformar}
writeln('move ', n, ' from ', a, ' to ' , b). ); {La última película se mueve de A a b}
Mover (n-1, c, a, b) {Mueva recursivamente n-1 de la varilla C a la varilla B y use la palanca; A para transición}
Fin;
Fin;
Iniciar {programa principal}
write('Entrada n:');
Leer como (n);
move(n, 'A', 'B', 'C');
Fin .
Ejecutar:
Ingrese n: 3 (Enter)
Mover 1 de A a B
Mover 2 de A a C
Mover 1 de B a C
Mover 3 de A a B
Mover 1 de C a A
Mover 2 de C a B
Mueva 1 de A a B
Cuando el programa se esté ejecutando, ingrese el valor de n. Además de 3, puede elegir 4, 5 o 6, pero nunca. Introduzca 64. Porque por deducción, si mueves 64 monedas de oro según las reglas, tienes que mover 2 64-1 = 1,8 * 10 19 veces. Si se moviera una vez por segundo, tardaría un billón de años. Según cálculos científicos, la "vida útil" de la Tierra es de aproximadamente varios miles de millones a decenas de miles de millones de años. Puedes ver la destrucción de la Tierra y no puedes completar el juego. Incluso si la computadora se "moviera" 100 millones de veces por segundo, tardaría 5.800 años, por lo que sería imposible completar el juego.
¿Es esto lo suficientemente detallado? Extraído de "Pascal Language Middle School Edition, segunda edición, libro de texto de capacitación de la Olimpiada de Informática Juvenil" Beijing Institute of Technology Press, esto no está mal.