Tours de Hanoï
On dispose de 3 tiges (gauche – 1, milieu – 2 et droite – 3). Il y a
n disques ronds de tailles différentes sur la première tige. Les disques sont disposés dans un ordre croissant de taille, du haut vers le bas. Vous êtes autorisé à déplacer le disque du dessus d’une tige vers une autre et à le placer sur un disque plus grand. En d’autres termes, il est interdit de placer un disque plus grand sur un disque plus petit.Vous devez imprimer toutes les opérations qui permettent de déplacer l’ensemble des disques de la première tige vers la troisième. Le nombre de coups doit être minimal.
Entrée
L’entrée contient un unique entier
n (1 ≤ n ≤ 16) qui représente le nombre de disques sur la première tige.Sortie
Le programme doit imprimer toutes les opérations nécessaires pour déplacer les disques de la première tige vers la troisième, tout en respectant la condition selon laquelle aucun disque plus grand ne peut être placé sur un disque plus petit. Le nombre total d’opérations ne doit pas dépasser .
Exemples
Entrée | Sortie |
2 | 1 -> 2
1 -> 3
2 -> 3 |
3 | 1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB