recursion - test - Torre de Hanoi: Algoritmo Recursivo

torres de hanoi algoritmo recursivo

Question

Aunque no tengo ningún problema en la recursión de la comprensión, no puedo entender la solución recursiva al problema de la Torre de Hanoi. Aquí está el código de Wikipedia :

procedure Hanoi(n: integer; source, dest, by: char);
Begin
if (n=1) then
writeln(''Move the plate from '', source, '' to '', dest)
else begin
Hanoi(n-1, source, by, dest);
writeln(''Move the plate from '', source, '' to '', dest);
Hanoi(n-1, by, dest, source);
end;
End;

Comprendo el caso base y el concepto de dividir el problema en piezas más pequeñas hasta que pueda mover un solo disco. Sin embargo, no puedo entender cómo funcionan juntas las dos llamadas recursivas en el caso no base. Tal vez alguien me puede ayudar? Gracias.

Answer 1

¡Siento el dolor!

Aunque esta es una publicación anterior, creo que lo que uno realmente necesita comprender, no es el enfoque de "mover esto a eso" sino que la respuesta implica usar el efecto secundario de la recursión.

Una ayuda invaluable para mí fue "The Little Schemer", que enseña a pensar y escribir funciones recursivas.

Sin embargo, esto le enseña al lector a usar los resultados del resultado devuelto en la próxima llamada recursiva.

En la Torre de Hanoi, la respuesta no está en el resultado devuelto per se, sino en la observación del resultado devuelto.

La magia ocurre en la reorganización sucesiva de los parámetros de la función.

Sí, el problema es realmente en tres partes:

• mover una torre más pequeña a la clavija de repuesto
• mover el último disco a la clavija de destino
• mover la torre restante en la clavija de repuesto a la clavija de destino.

En Scheme:

(define (th n a b c)
(if (zero? n) ''done
(begin
(th (- n 1) a c b)
(display (list a c))
(newline)
(th (- n 1) b a c))))
(th 5 ''source ''spare ''destination)

Sin embargo, es la visualización de los parámetros de la función la solución al problema y la comprensión crucial de la estructura de árbol doble de las llamadas.

La solución también transmite el poder de la proof by induction y un brillo cálido a todos los programadores que han luchado con las estructuras de control convencionales.

Incidentemente, resolver el problema a mano es bastante satisfactorio.

• contar la cantidad de discos
• si es así, mueva el primer disco a la clavija de repuesto, realice el siguiente movimiento legal (sin involucrar el disco superior). A continuación, mueva el disco superior a la clavija de destino, realice el siguiente movimiento legal (nittd). A continuación, mueva el disco superior a la clavija de origen, haga la siguiente jugada legal (nittd) ...
• si es impar, mueva el primer disco a la clavija de destino, realice el siguiente movimiento legal (sin involucrar el disco superior). A continuación, mueva el disco superior a la clavija de repuesto, realice el siguiente movimiento legal (nittd). A continuación, mueva el disco superior a la clavija de origen, haga la siguiente jugada legal (nittd) ...

Lo mejor es mantener siempre el disco superior con la misma mano y mover siempre la mano en la misma dirección.

El número final de movimientos para n discos es 2^n - 1 el move n disc to destination está a la mitad del proceso.

Por último, es curioso cómo explicar un problema a un colega, a su esposa / esposo o incluso al perro (incluso si no lo escuchan) puede cimentar la iluminación.

Answer 2

/ ** * * / paquete com.test.recursion;

/ ** * @author kamals1986 El algoritmo recursivo para Tower of Hanoi Problema El algoritmo * crece por potencia (2, n). * / public class TowerOfHanoi {

private static String SOURCE_PEG = "B";
private static String SPARE_PEG = "C";
private static String TARGET_PEG = "A";
public void listSteps(int n, String source, String target, String spare) {
if (n == 1) {
System.out.println("Please move from Peg " + source + "/tTo Peg/t"
+ target);
} else {
listSteps(n - 1, source, spare, target);
listSteps(1, source, target, spare);
listSteps(n - 1, spare, target, source);
}
}
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);
long endTime = System.currentTimeMillis();
System.out.println("Done in " + (endTime - startTime) / 1000
+ "/t seconds");
}

}

Answer 3

Aquí está mi código de solución al problema de Towers of Hanoi usando recursion con golang. `paquete principal

import "fmt"
func main() {
toi(4, "src", "dest", "swap")
}
func toi(n int, from, to, swap string) {
if n == 0 {
return
}
if n == 1 {
fmt.Printf("mov %v %v -> %v/n", n, from, to)
return
}
toi(n-1, from, swap, to)
fmt.Printf("mov %v %v -> %v/n", n, from, to)
toi(n-1, swap, to, from)
}`

Answer 4

Aquí va la explicación. Mira la imagen ->

Al llamar a Movetower(3,a,b,c) , tiene la intención de mover los 3 discos de la torre A a la torre B Entonces las llamadas secuenciales son ->

1. Movetower(3,a,b,c) // No Move needed
2. Movetower(2,a,c,b) // No move needed
3. Movetower(1,a,b,c) // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b) // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a) // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c) // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a) // Not the time to move
8. Movetower(1,c,a,b) // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a) // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b) // Here is the time to move, move disc1 from a to b

Espero eso ayude :)

Para la animación: https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

Answer 5

Como estudiante de CS, es posible que haya oído hablar de la inducción matemática. La solución recursiva de la Torre de Hanoi funciona de manera análoga: solo una parte diferente es no perderse realmente con B y C, como lo fue la torre completa.

Answer 6

Como sugirieron algunos de nuestros amigos, eliminé las dos respuestas anteriores y las consolidé aquí.

Esto te da una comprensión clara.

Lo que el algoritmo general es ...

Algoritmo:

solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination
{
if(n==0)return;
solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move
move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d
solve(n-1,i,s,d); // we have left n-1 disc in ''i'', so bringing it to from i to d (recursive call)
}

aquí está el ejemplo de trabajo Haga clic aquí

Answer 7

Después de leer todas estas explicaciones, pensé que opinaría con el método que mi profesor utilizó para explicar la solución recursiva de Towers of Hanoi. Aquí está el algoritmo de nuevo con n que representa el número de anillos, y A, B, C que representa las clavijas. El primer parámetro de la función es el número de timbres, el segundo parámetro representa la clavija de origen, el tercero es la clavija de destino y el cuarto es la clavija de repuesto.

procedure Hanoi(n, A, B, C);
if n == 1
move ring n from peg A to peg B
else
Hanoi(n-1, A, C, B);
move ring n-1 from A to C
Hanoi(n-1, C, B, A);
end;

Me enseñaron en la escuela de posgrado para nunca avergonzarse de pensar en pequeño. Entonces, veamos este algoritmo para n = 5. La pregunta que debe hacerse primero es si quiero mover el quinto anillo de A a B, ¿dónde están los otros 4 anillos? Si el quinto anillo ocupa la clavija A y queremos moverlo a la clavija B, los otros 4 aros solo pueden estar en la clavija C. En el algoritmo anterior, la función Hanoi (n-1, A, C, B) está intentando mueva todos esos otros 4 anillos a la clavija C, para que el anillo 5 pueda moverse de A a B. Siguiendo este algoritmo vemos n = 4. Si el anillo 4 se moverá de A a C, donde están los anillos 3 y ¿menor? Solo pueden estar en la clavija B. A continuación, para n = 3, si el anillo 3 se moverá de A a B, ¿dónde están los anillos 2 y 1? En la clavija C, por supuesto. Si continúa siguiendo este patrón, puede visualizar lo que está haciendo el algoritmo recursivo. Este enfoque difiere del enfoque del principiante en que mira el último disco primero y el último al último.

Answer 8

En realidad, la Wikipedia ofrece una explicación:

Para mover n discos de la clavija A a la clavija C:

1. mueva n-1 discos de A a B. Esto deja el disco #n solo en la clavija A
2. mover el disco #n de A a C
3. mueva n-1 discos de B a C para que se sientan en el disco #n

Está bastante claro que primero tienes que eliminar n - 1 discos para acceder al n º uno. Y que tiene que moverlos primero a otra clavija de donde desea que aparezca la torre completa.

El código en su publicación tiene tres argumentos, además del número de discos: una clavija de origen , una clavija de destino y una clavija temporal en la que los discos se pueden almacenar (donde encajan todos los discos con tamaño n - 1).

La recursión ocurre en realidad dos veces, allí, una vez antes de la writeln , una vez después. El que está antes de la writeln moverá n - 1 discos en la clavija temporal, usando la clavija de destino como almacenamiento temporal (los argumentos en la llamada recursiva están en orden diferente). Después de eso, el disco restante se moverá a la clavija de destino y luego la segunda recursión compele el movimiento de la torre completa, moviendo la n - 1 torre desde la clavija de temperatura a la clavija de destino, encima del disco n.

Answer 9

En sentido simple, la idea es llenar otra torre entre las tres torres definidas en el mismo orden de discos que el presente sin un disco más grande superpuesto a un disco pequeño en cualquier momento durante el procedimiento.

Deje que ''A'', ''B'' y ''C'' sean tres torres. ''A'' será la torre que contiene ''n'' discos inicialmente. ''B'' se puede usar como torre intermedia y ''C'' es la torre objetivo.

El algo es el siguiente:

1. Mueva n-1 discos de la torre ''A'' a ''B'' con ''C''
2. Mueva un disco de ''A'' a ''C''
3. Mueva n-1 discos de la torre ''B'' a ''C'' usando ''A''

El código es el siguiente en java:

clase pública TowerOfHanoi {

public void TOH(int n, int A , int B , int C){
if (n>0){
TOH(n-1,A,C,B);
System.out.println("Move a disk from tower "+A +" to tower " + C);
TOH(n-1,B,A,C);
}
}
public static void main(String[] args) {
new TowerOfHanoi().TOH(3, 1, 2, 3);
}

}

Answer 10

Es sencillo. Supongamos que quiere pasar de A a C

si solo hay un disco, solo muévelo.

Si hay más de un disco, haz

• mover todos los discos (n-1 discos), excepto el de abajo de A a B
• mueve el disco inferior de A a C
• mover los discos n-1 del primer paso de A a C

Tenga en cuenta que, al mover los discos n-1, la enésima no será un problema en absoluto (una vez que sea más grande que todos los demás)

Tenga en cuenta que mover los discos n-1 se repite en el mismo problema nuevamente, hasta que n-1 = 1, en cuyo caso estará en el primero si (donde debería moverlo).

Answer 11

Estoy de acuerdo que este no es inmediato cuando lo miras por primera vez, pero es bastante simple cuando llegas a él.

Caso base: su torre es de tamaño 1. Así que puede hacerlo en un solo movimiento, desde la fuente directamente a dest.

Caso recursivo: su torre tiene un tamaño n> 1. Así que mueve la torre superior de tamaño n-1 a una clavija adicional (por), mueve la "torre" inferior del tamaño 1 a la clavija de destino y mueve la torre superior de a to dest.

Entonces, con un caso simple, tienes una torre de altura 2:

 _|_ | |
__|__ | |
===== ===== =====

Primer paso: mueva la torre superior de 2-1 (= 1) a la clavija extra (la del medio, digamos).

 | | |
__|__ _|_ |
===== ===== =====

Siguiente: mueva el disco inferior al destino:

 | | |
| _|_ __|__
===== ===== =====

Y finalmente, mueva la torre superior de (2-1) = 1 al destino.

 | | _|_
| | __|__
===== ===== =====

Si lo piensas bien, incluso si la torre tiene 3 o más, siempre habrá una clavija adicional vacía, o una clavija con todos los discos más grandes, para que la recursión se use al intercambiar torres.

Answer 12

Estoy tratando de obtener recursión también.

Encontré una manera de pensar,

lo veo como una cadena de pasos (el paso no es constante, puede cambiar dependiendo del nodo anterior)

Tengo que descubrir 2 cosas:

1. nodo anterior
2. paso tipo
3. después del paso qué más antes de llamar (este es el argumento para la próxima llamada)

ejemplo

factorial

1,2,6,24,120 ......... o

1,2 * (1), 3 * (2 * 1), 4 * (3 * 2 * 1,5 * (4 * 3 * 2 * 1)

paso = múltiple por último nodo

después del paso lo que necesito para llegar al siguiente nodo, resumen 1

De acuerdo

function =
n*f(n-1)
its 2 steps process
from a-->to step--->b

Espero esta ayuda, solo piense en 2 thniks, no en cómo pasar de un nodo a otro, sino en un nodo -> paso -> nodo

nodo -> paso es el cuerpo de la función paso -> nodo es los argumentos de la otra función

adiós :) espero haber ayudado

Answer 13

Hace un año tuve un curso de programación funcional y dibujé esta ilustración para el algoritmo. ¡Espero eso ayude!

(0) _|_ | |
__|__ | |
___|___ | |
____|____ ____|____ ____|____
(1.1) | | |
__|__ | |
___|___ _|_ |
____|____ ____|____ ____|____ (A -> B)
(1.2) | | |
| | |
___|___ _|_ __|__
____|____ ____|____ ____|____ (A -> C)
(1.3) | | |
| | _|_
___|___ | __|__
____|____ ____|____ ____|____ (B -> C)
(2.1) | | |
| | _|_
| ___|___ __|__
____|____ ____|____ ____|____ (A -> B)
(3.1) | | |
| | |
_|_ ___|___ __|__
____|____ ____|____ ____|____ (C -> A)
(3.2) | | |
| __|__ |
_|_ ___|___ |
____|____ ____|____ ____|____ (C -> B)
(3.3) | _|_ |
| __|__ |
| ___|___ |
____|____ ____|____ ____|____ (A -> B)

El problema de los 3 anillos se ha dividido en 2 problemas de 2 anillos (1.x y 3.x)

Answer 14

Hay tres torres a saber, torre de origen, torre de destino y torre de ayuda. La torre fuente tiene todos los discos y su objetivo es mover todos los discos a la torre de destino y asegurarse de que al hacerlo, nunca coloque un disco más grande encima de un disco más pequeño. Podemos resolver este problema usando la recursión en los pasos a continuación:

Tenemos n números de discos en la torre fuente

Caso base: n = 1 Si solo hay un disco en la torre fuente, muévalo a la torre de destino.

Caso recursivo: n> 1

• Mueva los discos superiores n-1 desde la torre fuente a la torre auxiliar
• Mueva el único disco restante, el enésimo (después del paso 1) a la torre de destino
• Mueva los discos n-1 que están en la torre auxiliar ahora, a su destino
  torre, utilizando la torre fuente como ayudante.

Código fuente en Java:

private void towersOfHanoi(int n, char source, char destination, char helper) {
//Base case, If there is only one disk move it direct from source to destination
if(n==1){
System.out.println("Move from "+source+" to "+destination);
}
else{
//Step1: Move the top n-1 disks from source to helper
towersOfHanoi(n-1, source, helper, destination);
//Step2: Move the nth disk from source to destination
System.out.println("Move from "+source+" to "+destination);
/*Step3: Move the n-1 disks(those you moved from source to helper in step1)
* from helper to destination, using source(empty after step2) as helper
*/
towersOfHanoi(n-1, helper, destination, source);
}
}

Answer 15

Hay una buena explicación de la implementación recursiva de Hanoi en http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html .

El resumen es, si desea mover la placa inferior desde la varilla A a la vara B, primero tiene que mover todas las placas más pequeñas encima de la A a C. La segunda llamada recursiva es mover las placas que movió a C vuelve a B después de que tu maletín base movió el único plato grande de A a B.

Answer 16

La primera llamada recursiva mueve todas las piezas excepto la más grande desde la fuente hasta el uso de dest como pila auxiliar. Cuando terminen todas las piezas, excepto la más grande, quedarán y la más grande estará libre. Ahora puede mover el más grande a dest y usar otra llamada recursiva para mover todas las piezas de a dest.

Las llamadas recursivas no sabrán nada sobre la pieza más grande (es decir, la ignorarán), pero está bien porque las llamadas recursivas solo tratarán con las piezas que son más pequeñas y, por lo tanto, se pueden mover hacia y desde la pieza más grande libremente.

Answer 17

La respuesta a la pregunta, ¿cómo sabe el programa, que incluso es "src" a "aux", y es "src" a "dst" para el movimiento de apertura se encuentra en el programa. Si desglosas el primer movimiento con 4 discos, entonces esto se ve así:

hanoi(4, "src", "aux", "dst");
if (disc > 0) {
hanoi(3, ''src'', ''dst'', ''aux'');
if (disc > 0) {
hanoi(2, ''src'', ''aux'', ''dst'');
if (disc > 0) {
hanoi(1, ''src'', ''dst'', ''aux'');
if (disc > 0) {
hanoi(0, ''src'', ''aux'', ''dst'');
END
document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
hanoi(0, ''aux'', ''src'', ''dst'');
END
}

también el primer movimiento con 4 discos (par) va de Src a Aux.

Answer 18

Piense en ello como una pila con el diámetro de los discos representados por números enteros (4, 3, 2, 1) La primera llamada de recursión se llamará 3 veces y, por lo tanto, completará la pila de tiempo de ejecución de la siguiente manera

1. primera llamada: 1. Segunda llamada: 2,1. y tercera llamada: 3,2,1.

Una vez que finaliza la primera recursividad, el contenido de la pila de tiempo de ejecución se coloca en el polo central desde el mayor diámetro hasta el más pequeño (el primero en salir por última vez). A continuación, el disco con diámetro 4 se mueve al destino.

La segunda llamada de recursión es la misma que la primera, con la excepción de mover los elementos del polo central a destino.

Answer 19

Supongamos que queremos mover un disco de A a C a B y luego:

1. mueve un disco más pequeño a B.
2. mueva otro disco a C.
3. mover B a C.
4. pasar de A a B.
5. mover todo de C a A.

Si repite todos los pasos anteriores, el disco se transferirá.

Answer 20

Tower (N,source,aux.dest):

1. if N =1 Then
   Write : Source -> dest
   return
   end of if

2. mover el disco N-1 de la fuente de clavija a la clavija auxiliar

   call Tower (N-1, source, dest, aux)

3. escribir fuente -> dest

4. mover los discos N-1 de la clavija aux al clavijero dest

   call Tower (N-1, source, dest, aux)

5. regreso

Answer 21

def Hanoi(n, A, B, C):
if(n==1): print "move plates to empty peg"
else:
Hanoi(n-1, A, B, C)
print "move"+str(n)+" to peg "+C
Hanoi(n-1, B, C, A)

Answer 22

public static void hanoi(int number, String source, String aux, String dest)
{
if (number == 1)
{
System.out.println(source + " - > "+dest);
}
else{
hanoi(number -1, source, dest, aux);
hanoi(1, source, aux, dest);
hanoi(number -1, aux, source, dest);
}
}

Answer 23

void TOH(int n, int a, int b){
/*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
*/
int c = 6-a-b;
if(n==1){
cout<<"Move from "<<a<<" to "<<b<<"/n";
}
else{
// Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
TOH(n-1, a, c);
// Move the last alone disk from 1st to 3rd stack.
TOH(1, a, b);
// Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
TOH(n-1, c, b);
}
}
int main() {
TOH(2, 1, 3);
cout<<"FINISHED /n";
TOH(3, 1, 3);
cout<<"FINISHED /n";
TOH(4, 1, 3);
return 0;
}