Dans le jeu des tours de Hanoï, on dispose de trois piquets : le piquet de départ, le piquet objectif et un piquet intermédiaire.
Au départ, n disques de rayons différents sont empilés sur le piquet de départ. Le disque de plus grand rayon est le disque le plus bas, le disque de plus petit rayon est le disque le plus haut.
Tout disque est posé sur un disque de plus grand rayon que lui. Et ceci devra être conservé lors des déplacements de disque : interdiction absolue de poser à un moment donné un disque sur un disque de rayon plus petit.
L'objectif est de déplacer les disques du piquet de départ vers le piquet objectif. On ne peut déplacer qu'un seul disque à la fois, la règle énoncée ci-dessus sur les rayons est à respecter et on peut bien entendu utiliser le piquet intermédiaire.
Donner une programmation récursive.
| Entrée | Un entier naturel n (nombre de disques sur la tour initiale). Les disques seront numérotés de 1 à n, le numéro d'un disque pourra être considéré comme son rayon. |
|---|---|
| Sortie | Messages indiquant les déplacements à faire. |
- principe
- un code
- petite amélioration
Il est facile de traiter le cas n=1 correspondant à la présence d'un seul disque.
Si l'on dispose de 2 disques, on déplace le disque 1 du piquet 'départ' vers le piquet 'intermédiaire', puis le disque 2 du piquet 'départ' vers le piquet 'final' et enfin le disque 1 de 'intermédiaire' vers 'final.
Avec 3 piquets, on déplace 1 et 2 vers le piquet intermédiaire (par une suite de mouvements analogues au cas précédent) puis on déplace le 3 vers le piquet final et enfin 1 et 2 vers le piquet final.
On voit que le plus grand disque joue le même rôle que le sol vis-à-vis des autres disques : on peut déplacer les autres disques sans se préoccuper du plus grand disque, ce plus grand disque restera toujours au sol sauf dans son unique déplacement du piquet initial vers le final.
Le cas récursif est donc (avec n>1 disques) :
- déplacer les n-1 disques du dessus vers le piquet intermédiaire.
- déplacer le grand disque du piquet 'départ' vers le piquet 'final'.
- déplacer les n-1 disques du piquet intermédiaire vers le piquet 'final'.
Une erreur : - déplacer le disque du dessus et se dire qu'on n' a plus qu'à en déplacer n-1 (par récursivité). Ce raisonnement ne fonctionne pas du fait que le petit disque ne joue pas, contrairement au grand disque, un rôle 'neutre' comme le grand disque. Il empêche les mouvements vers son piquet et le problème à n-1 disques obtenu n'est donc pas de même nature que celui de départ.
def hanoi(n, a='départ', b='intermédiaire', c='objectif', z=1):
""" a piquet de départ.
b piquet intermédiaire.
c piquet d'arrivée.
n nombre d'anneaux à déplacer.
z anneau déplacé."""
if n == 1 :
print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
else:
hanoi(n-1, a, c, b)
hanoi( 1, a, b, c, n)
hanoi(n-1, b, a, c)
hanoi(4)
on obtient :
Déplacer l'anneau 1 du piquet départ vers le piquet intermédiaire. Déplacer l'anneau 2 du piquet départ vers le piquet objectif. Déplacer l'anneau 1 du piquet intermédiaire vers le piquet objectif. Déplacer l'anneau 3 du piquet départ vers le piquet intermédiaire. Déplacer l'anneau 1 du piquet objectif vers le piquet départ. Déplacer l'anneau 2 du piquet objectif vers le piquet intermédiaire. Déplacer l'anneau 1 du piquet départ vers le piquet intermédiaire. Déplacer l'anneau 4 du piquet départ vers le piquet objectif. Déplacer l'anneau 1 du piquet intermédiaire vers le piquet objectif. Déplacer l'anneau 2 du piquet intermédiaire vers le piquet départ. Déplacer l'anneau 1 du piquet objectif vers le piquet départ. Déplacer l'anneau 3 du piquet intermédiaire vers le piquet objectif. Déplacer l'anneau 1 du piquet départ vers le piquet intermédiaire. Déplacer l'anneau 2 du piquet départ vers le piquet objectif. Déplacer l'anneau 1 du piquet intermédiaire vers le piquet objectif.
Petite amélioration pour l'affichage :
def tourHanoi(n):
tours = dict()
tours['départ'] = [ j for j in range(n,0,-1) ]
tours['intermédiaire'] = []
tours['objectif'] = []
def affichage(lesTours) :
d = len(tours['départ'])
i = len(tours['intermédiaire'])
o = len(tours['objectif'])
hauteur = max(d, i, o)
for h in range(hauteur, 0, -1) :
if d >= h : print( tours['départ'][h-1], end=' ')
else : print(' ', end=' ')
if i >= h : print( tours['intermédiaire'][h-1], end=' ')
else : print(' ', end=' ')
if o >= h : print( tours['objectif'][h-1])
else : print(' ')
print('\u2AE0 \u2AE0 \u2AE0')
print()
def hanoi(n,a='départ',b='intermédiaire',c='objectif',z=1):
""" a piquet de départ.
b piquet intermédiaire.
c piquet d'arrivée.
n nombre d'anneaux à déplacer.
z anneau déplacé."""
if n==1:
print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
anneau_deplace = tours[a].pop()
tours[c].append(anneau_deplace)
affichage(tours)
else:
hanoi(n-1, a,c,b )
hanoi(1,a,b,c, n)
hanoi(n-1,b,a,c)
hanoi(n)
tourHanoi(4)
on obtient :
Déplacer l'anneau 1 du piquet départ vers le piquet intermédiaire.
2
3
4 1
⫠ ⫠ ⫠
Déplacer l'anneau 2 du piquet départ vers le piquet objectif.
3
4 1 2
⫠ ⫠ ⫠
Déplacer l'anneau 1 du piquet intermédiaire vers le piquet objectif.
3 1
4 2
⫠ ⫠ ⫠
Déplacer l'anneau 3 du piquet départ vers le piquet intermédiaire.
1
4 3 2
⫠ ⫠ ⫠
Déplacer l'anneau 1 du piquet objectif vers le piquet départ.
1
4 3 2
⫠ ⫠ ⫠
Déplacer l'anneau 2 du piquet objectif vers le piquet intermédiaire.
1 2
4 3
⫠ ⫠ ⫠
Déplacer l'anneau 1 du piquet départ vers le piquet intermédiaire.
1
2
4 3
⫠ ⫠ ⫠
Déplacer l'anneau 4 du piquet départ vers le piquet objectif.
1
2
3 4
⫠ ⫠ ⫠
Déplacer l'anneau 1 du piquet intermédiaire vers le piquet objectif.
2 1
3 4
⫠ ⫠ ⫠
Déplacer l'anneau 2 du piquet intermédiaire vers le piquet départ.
1
2 3 4
⫠ ⫠ ⫠
Déplacer l'anneau 1 du piquet objectif vers le piquet départ.
1
2 3 4
⫠ ⫠ ⫠
Déplacer l'anneau 3 du piquet intermédiaire vers le piquet objectif.
1 3
2 4
⫠ ⫠ ⫠
Déplacer l'anneau 1 du piquet départ vers le piquet intermédiaire.
3
2 1 4
⫠ ⫠ ⫠
Déplacer l'anneau 2 du piquet départ vers le piquet objectif.
2
3
1 4
⫠ ⫠ ⫠
Déplacer l'anneau 1 du piquet intermédiaire vers le piquet objectif.
1
2
3
4
⫠ ⫠ ⫠