Table des Matières
Publicité
Problème des Tours de Hanoi
Algorithme utilisé
Texte du
programme
1
2
3
35–4
Exemples de programmes
On dispose de trois piquets. On veut déplacer une pile de n
disques situés sur un premier piquet vers le troisième.
Ces disques sont de tailles croissantes. On s'interdit de placer
un disque sur un disque plus petit. On peut en revanche
utiliser le deuxième piquet pour y placer les disques de façon
temporaire.
Quels sont les déplacements à effectuer ?
Pour déplacer n disques d'un piquet a vers un piquet b, on procède
de la façon suivante :
S'il n'y a qu'un disque à déplacer, il suffit de noter le numéro du
piquet de départ et le numéro du piquet d'arrivée.
Sinon,
1. On déplace les n-1 premiers disques du piquet a vers le piquet
intermédiaire c.
2. On déplace le dernier disque (le plus gros) de a vers b
3. On termine en déplaçant les n − 1 disques de c vers b.
Il suffit ensuite de remarquer que si a et b représentent les numéros
de deux piquets, alors le troisième porte toujours le numéro
= − −
. (Par exemple, si a = 1 et b = 3 , c = − − =
c
6
a b
: deplace(n,a,b)
: Prgm
: If n=1 then
Pause string(a)&" ú "&string(b)
:
: Else
deplace(n-1,a,6-a-b)
:
deplace(1,a,b)
:
deplace(n-1,6-a-b,b)
:
: EndIf
: EndPrgm
Voici par exemple la liste des déplacements à effectuer pour
déplacer 3 anneaux du piquet 1 vers le piquet 3 :
ClrIO:deplace(3,1,3) ¸
6 1 3 2 .)
Publicité
Chapitres
Table des Matières
