Défi programmation java: Récursoires des tours de Hanoi - mannequins

Ce défi vous aide à utiliser vos talents de programmeur pour écrire un programme Java qui imprimera les étapes nécessaires pour résoudre un puzzle de Tours de Hanoi étant donné le nombre de disques.

Les Tours de Hanoi est un puzzle de logique classique composé de trois piquets verticaux et d'un certain nombre de disques de différents diamètres. Chaque disque a un trou au centre, permettant aux disques d'être glissés sur les piquets.

Le puzzle commence avec tous les disques empilés sur l'un des pions, avec le plus gros disque en bas et le plus petit en haut. L'objet du puzzle est de déplacer la pile de disques vers l'un des autres pions, en obéissant à deux règles simples: (1) vous ne pouvez déplacer qu'un seul disque à la fois, et (2) vous ne pouvez jamais placer un disque plus grand sommet d'un plus petit.

La figure suivante montre la solution pour une pile de trois disques. Comme vous pouvez le voir, la solution nécessite sept déplacements:

Déplacer le disque 1 de Peg 1 à Peg 3.
Déplacer le disque 2 de Peg 1 vers Peg 2.
Déplacer le disque 1 de Peg 3 vers Peg 2.
Déplacer le disque 3 de Peg 1 à Peg 3.
Déplacer le disque 1 de Peg 2 vers Peg 1.
Déplacer le disque 2 de Peg 2 vers Peg 3.
Déplacer le disque 1 de Peg 1 à Peg 3.

Après ces sept étapes, la pile de disques sera sur Peg 3.

La solution pour le puzzle des Tours de Hanoi avec trois disques.

Le puzzle devient intéressant lorsque vous commencez à ajouter des disques à la position de départ. Avec trois disques, le puzzle nécessite seulement 7 mouvements à résoudre. Avec quatre disques, 15 coups sont nécessaires. Avec cinq disques, vous aurez besoin de 31 coups. Six disques nécessitent 64 mouvements.

Si vous avez suivi les maths, le nombre de mouvements requis pour résoudre le puzzle augmente exponentiellement à mesure que le nombre de disques augmente. Plus précisément, le nombre de déplacements requis pour déplacer les disques n est 2 ⁿ - 1. Par exemple, une pile de 20 disques nécessitera 2 ²⁰ - 1 coups; c'est plus d'un million de coups!

Une légende intéressante est associée à l'énigme: Dans un temple de Hanoi, des moines ont travaillé sur un puzzle de tours de Hanoi avec 64 disques depuis la création de la terre. Quand ils auront fini, le monde prendra fin. Heureusement, nous avons beaucoup de temps à attendre: si les moines peuvent déplacer un disque par seconde, il faudra encore 580 milliards d'années avant de finir le puzzle.

Votre défi est simple: Écrivez un programme Java qui imprimera les étapes nécessaires pour résoudre un puzzle de Tours de Hanoi étant donné le nombre de disques. Le programme devrait d'abord demander à l'utilisateur le nombre de disques. Ensuite, il devrait afficher les étapes, une par ligne.Chaque étape doit indiquer le point d'ancrage à partir duquel un disque doit être déplacé et le point d'ancrage dans lequel le disque doit être déplacé. Les étapes doivent également être numérotées séquentiellement.

Une fois terminé, le programme devrait répéter, en demandant de nouveau à l'utilisateur le nombre de disques. Le programme devrait se terminer lorsque l'utilisateur entre 0.

Voici un exemple de sortie de console que votre programme devrait générer:

Combien de disques? (0 à la fin) 3 1: 1 à 3 2: 1 à 2 3: 3 à 2 4: 1 à 3 5: 2 à 1 6: 2 à 3 7: 1 à 3 Combien de disques ? (0 à la fin) 0

La seule autre exigence pour résoudre ce problème est que votre solution utilise une programmation récursive. En d'autres termes, votre solution doit inclure une méthode qui s'appelle pour résoudre le puzzle.

La programmation récursive peut être difficile, alors voici quelques astuces pour résoudre ce puzzle:

Le puzzle se compose de trois chevilles. L'un d'eux contient la pile de disques de départ; appelez cette pince la source peg . L'une des deux autres chevilles est la cheville à laquelle vous voulez déplacer la pile de disques; Appelez cette cheville cheville cible . Le troisième ancrage est disponible pour que vous puissiez l'utiliser en tant que piquet intermédiaire pour stocker des disques temporairement lorsque vous les déplacez. Appelez cette cheville pièce de rechange .
Votre méthode récursive doit accepter trois paramètres: le nombre de disques à déplacer, le point d'ancrage source et le point d'ancrage cible. Utilisez les valeurs entières 1, 2 et 3 pour représenter les chevilles.
L'idée de base de la résolution récursive du puzzle est la suivante: Pour déplacer une pile de disques d'une cheville source vers une cheville cible, trois étapes sont nécessaires:
1. Déplacez tous les disques de la pile à l'exception du disque inférieur pince de rechange.
2. Déplacez le plus gros disque de la pile d'origine vers le repère cible.
3. Déplacez la pile que vous avez déplacée à l'étape 1 de la cheville libre vers la cheville cible.
Bien sûr, les règles de puzzle vous permettent de déplacer un seul disque à la fois, donc vous ne pouvez pas accomplir les étapes 1 et 3 de la procédure donnée en récupérant simplement la pile et en la déplaçant. C'est là qu'intervient la récurrence. Pour les étapes 1 et 3, vous appelez la méthode de manière récursive, en spécifiant à chaque fois un disque de moins à déplacer, et en utilisant à chaque fois la cible précédente comme pièce de rechange.
Vous vous demandez pourquoi la méthode récursive n'a pas besoin d'accepter le rattachement de rechange comme argument? Parce que vous pouvez facilement le calculer, étant donné les piquets source et cible. Comme il n'y a que trois pions, numérotés 1, 2 et 3, la somme des trois pions est 6 (1 + 2 + 3). Étant donné les points d'ancrage source et cible, vous pouvez calculer l'ancrage de réserve en soustrayant les points source et cible de 6. Par exemple, si le point d'origine est 1 et le point d'ancrage cible est 3, la point d'ancrage doit être 2 car

6 - 3 - 1 = 2.