Tours de Hanoï

Les tours de hanoï sont un casse-tête très ancien. Trois piquets sont plantés côte à côte sur le sol. Sur le premier piquet sont enfilés des disques de bois de différentes tailles, du plus grand au plus petit.

Voici une illustration d'un jeu de tours de Hanoï composé de 9 disques :

Le but du casse-tête est de déplacer l'ensemble de la pile de disques vers le troisième piquet. Un coup consiste à déplacer un disque du sommet d'un piquet vers le sommet d'un autre piquet, en respectant la règle suivante :

Un disque ne peut jamais être placé sur un disque plus petit que lui.

Illustration de l'état du jeu après quelques coups :

Vous devez écrire un programme qui, étant donné le nombre de disques se trouvant sur le premier piquet, décrit comment atteindre la position finale en effectuant un minimum de coups.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 1 000 ko.

Contraintes

  • 1 <= N <= 12, où N est le nombre de disques.

Entrée

Vous devez lire un entier sur l'entrée standard : le nombre de disques se trouvant sur le piquet 1 au départ.

Sortie

Vous devez écrire une ligne sur la sortie par déplacement permettant d'arriver à la solution finale (dans l'ordre où ils doivent être effectués).

Chaque déplacement est décrit par le numéro du piquet duquel un disque est retiré, le texte " -> ", puis le numéro du piquet sur lequel le disque est placé. Les piquets sont numérotés de 1 à 3.

Exemple

entrée :

3

sortie :

1 -> 3
1 -> 2
3 -> 2
1 -> 3
2 -> 1
2 -> 3
1 -> 3

Commentaires

Une fois que l'on a trouvé le principe, le casse-tête se résout toujours de la même manière, assez simplement. Si vous ne trouvez pas, demandez les conseils automatiques avant d'essayer de programmer une solution compliquée.


Source : https://www.france-ioi.org/ Créé par : Mathias Hiron.