Module: Atelier sur la récursivité

Puzzle “Tours de Hanoï” se compose de trois tiges, numérotées 1, 2, 3. Une pyramide de n disques de diamètres différents est posée sur la tige 1 par ordre croissant de diamètre. Les disques peuvent être transférés d'une tige à l'autre un par un, tandis que le disque ne peut pas être placé sur un disque d'un diamètre inférieur. Il est nécessaire de transférer toute la pyramide de la tige 1 à la tige 3 en un minimum de transferts.

 

  

Écrire un programme qui résout un puzzle ; pour un nombre donné de disques n imprime une suite de permutations au format a b c, où a — numéro du disque décalé, b — le numéro de la tige dont on retire ce disque, c — le numéro de la tige sur laquelle ce disque est posé.

 

Par exemple, la ligne 1 2 3 signifie déplacer le disque numéro 1 de la broche 2 à la broche 3. Une commande est imprimée sur une ligne. Les disques sont numérotés de 1 à n par ordre croissant de diamètre.

 

Entrez un nombre naturel n ( 0 < n < 11).

 

Le programme doit afficher la manière minimale (en termes de nombre d'opérations effectuées) de réorganiser la pyramide à partir du nombre de disques donné.

Exemples

1 1 2

2 1 3

1 2 3

#	Entrée	Sortie
1	2