Approche récursive pour résoudre les tours de Hanoi puzzle
J'essaie de résoudre le problème des "tours de Hanoi", qui déplace des piles de disques organisées du plus petit au plus grand d'une pile de départ à une pile de destination, au moyen d'une pile auxiliaire sans jamais placer un disque plus grand sur un disque plus petit.
On m'a donné l'algorithm:
If numberDisks == 1:
Display “Move the top disk from S to D”.
Else
Move(numberDisks -1, ‘S’, ‘A’, ‘D’);
Move(1, ‘S’, ‘D’, ‘A’);
Move(numberDisks -1, ‘A’, ‘D’, ‘S’);
Toutefois, cela semble différer de la plupart des autres exemples, qui semblent fonctionner sans l'aide de Déplacement(1, ‘S’, ‘D’, ‘A’); dans la fonction récursive.
Comme mon code est, je semble répéter le cas de base pour chaque mouvement, et je ne sais pas comment structurer mes instructions d'impression pour donner la sortie appropriée qui devrait ressembler à:
Move disk 1 from S to D
Move disk 2 from S to A
Move disk 1 from D to A
Move disk 3 from S to D
Move disk 1 from A to S
Move disk 2 from A to D
Move disk 1 from S to D
Lorsque vous essayez de déplacer 3 disques.
// Recursively solve Towers of Hanoi puzzle
public static void main(String[] args) {
if (handleArguments(args)) {
System.out.println("numDisks is ok");
int numDisks = Integer.parseInt(args[0]);
Move(numDisks,'s', 'a', 'd' );
}
}
// recursive case
public static void Move(int disks, char start, char aux, char destination) {
// base case
if (disks == 1) {
System.out.println("Move disk 1 from S to D");
// if number of disks is 2 or greater
} else if(disks > 1) {
Move(disks - 1, start, aux, destination);
System.out.println("move disk " + disks + " from " + start + " to " + destination);
Move(1, start, destination, aux);
Move(disks - 1, aux, destination, start);
}
}
1 answers
Première chose: Comprendre l'algorithme pour déplacer n disques (de S à D, avec A)
- S'il n'y a qu'un seul disque à déplacer, il suffit de le déplacer puis d'arrêter*.
- Déplacer n-1 disques de S à A, avec D.
- Déplacer le nième disque de S à D
- Déplacer n-1 disques de A à D, avec S.
*Également: S'il y a 0 disques, arrêtez-vous. (Certains diront que c'est la condition de terminaison supérieure car, dans votre code, cela empêchera l'instruction print lorsqu'il y en a une d'être un cas particulier, il sera géré naturellement par la déclaration d'impression avec laquelle vous couvrez l'étape 3. Lorsque, par exemple, vous décidez de changer cette méthode retourne une liste des étapes au lieu de l'impression, cette modification ne sera appliquée en un seul lieu)
Vous mentionnez que " Il semble que je répète le cas de base pour chaque mouvement."Si vous regardez votre code, et comparez à mes déclarations ci-dessus. Vous verrez que vous appelez Move(1, start, destination, aux); entre mes étapes 3 et 4. C'est pourquoi vous répétez votre base cas, parce que vous appelez explicitement, en répétant votre cas de base, mais cela n'a aucun sens.
L'autre problème principal que je peux voir:
System.out.println("Move disk 1 from S to D"); imprimera toujours 'S' et 'D', dans cet ordre, lorsque vous devrez souvent spécifier un déplacement différent, assurez-vous d'utiliser les arguments de cette instruction.
Je ne pense pas qu'il y ait autre chose, mais essayez-le et voyez.
En réponse à l'exemple qui vous a été donné, au début de votre message. Il produit une sortie subtilement différente de celle votre version.
Yours spécifie (ou tente de) quelle taille de disque doit être déplacé à chaque étape, l'exemple spécifie uniquement la pile à partir de laquelle déplacer un disque, quelle que soit sa taille.
L'appel récursif avec 1 comme argument au milieu consiste à imprimer l'instruction move pour déplacer le disque final dans la pile (mon étape 3).