vous avez des disques empilés sur une tour de départ. Le but va être de les déplacer sur une tour d'arrivée en vous aidant d'une tour intermédiaire. Jusque là, ça va... le seul petit problème c'est qu'on :
- ne pas déplacer plus d'un disque à la fois
- on ne peut déplacer un disque que sur un emplacement vide ou alors sur un disque plus grand
voila, c'est le type même de beau problème. Enoncé simple, réalisation pas forcément aussi aisée.
Maintenant, prenons un exemple de résolution de ce problème avec 3 disques . Au départ, j'ai 3 disques empilés sur la 1ére tour. 1ère itération, je déplace le 1er disque sur la tour 3. Ensuite je déplace le 2nd disque sur la tour intermédiaire 2 et je peux alors dans la 3éme itération remettre mon 1er disque sur le second, tour intermédiaire.
Dans la 4éme itération, j'ai enfin mon plus grand disque disponible pour être déplacer sur la tour d'arrivée. Après, je m'aide de ma tour de départ comme tour intermédiaire pour enfin reconstituer ma pile.
Au final, 7 itérations pour arriver au but ! sur la page wikipedia on vous donne la formule du nombre d'itération, c'est 2 puissance votre nombre de disque - 1. Dans notre cas : 23-1 = 7 bingo
Nous allons maintenant voir comment résoudre ce problème grace a un algorithme récursif !
Si on regarde bien les déplacements, on peut dire que tout le problème consiste à :
- déplacer les 2 premiers disques vers la tour intermédiaire
- déplacer le 3éme disque vers la tour d'arrivée
- déplacer les 2 disques de la tour intermédiaire vers la tour d'arrivée
Au final, cela nous donne la fonction suivante :
Procedure Deplacer(nbdisques,depart,arrivee,intermediaire)
Si (nbdisques = 1) Alors
Ecrire (depart, " -> ", arrivee)
Sinon
Deplacer(nbdisques-1,depart,intermediaire,arrivee)
Deplacer(1,depart,arrivee,intermediaire)Deplacer(nbdisques-1,intermediaire,arrivee,depart)
FinSi
Fin
pas compliqué, hein ?
Aucun commentaire:
Enregistrer un commentaire