J'ai trouvé sur Internet l'algorithme de la résolution des tours de Hanoï, sauf que c'est en récursif :
d ← 0
fonction Hanoï (a,b,c)
│ si nombre > 1
│ │ alors fonction Hanoï (a-1,b,6-b-c)
│ │ │ fonction Hanoï (1,b,c)
│ │ │ fonction Hanoï (a-1,6-b-c,c)
│ │ sinon d ← d+1
│ │ │ écrire d," : déplacer ",b," vers ",c
│ fin si
fin fonction Hanoï
alors que je le voudrais sans utiliser de fonction récursive, c'est-à-dire uniquement avec des boucles, des conditions, des listes. Je pense que c'est possible mais je ne vois pas du tout comment faire, même si je pense avoir compris à peu près ce qu'est une fonction récursive.
J'attends la réponse en langage algorithmique, sinon la réponse ne me sert à rien.
J'espère que quelqu'un trouvera/m'aidera à trouver la solution ! (parce que la je nage ). Je ne sais pas trop comment partir.
Il y a une méthode très simple en itératif.
Fais des essais "à la main", observe bien le déplacement de la petite couronne ensuite de l'autre couronne et tu auras la solution : une simple boucle while. T'en dire plus c'est donner la solution.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Quand a est pair, la petite couronne se déplace vers la gauche, celle d'après vers la droite, celle d'après vers la gauche... Quand a est impair, la petite couronne se déplace vers la droite, celle d'après vers la gauche, celle d'après vers la droite... :
La petite couronne est déplacé une fois sur deux :
Oui je l'ai remarqué, mais comment en déduire la boucle ?
Parce que avant de faire ce topic, j'avais fais ça :
v ← c-b
si v = 2
│ alors v ← -1
fin si
si v=-2
│ alors v ← 1
fin si
si a/2-E(a/2) ≠ 0
│ alors v ← -v
fin si
d ← b
e ← b
f ← b
g ← b
h ..
..
pour w de 1 à 2^a-1
│ si (w-1)/2-E((w-1)/2) = 0
│ │ alors x ← d
│ │ │ y ← v
│ fin si
│ si (w-2)/4-E((w-2)/4) = 0
│ │ alors x ← e
│ │ │ y ← -v
│ fin si
│ si (w-4)/8-E((w-4)/8) = 0
│ │ alors x ← f
│ │ │ y ← v
│ fin si
│ si (w-8)/16-E((w-8)/16) = 0
│ │ alors x ← g
│ │ │ y ← -v
│ fin si
│ si ...
│ ...
│ z ← x+y
│ si z = 0
│ │ alors z ← 3
│ fin si
│ si z = 4
│ │ alors z ← 0
│ fin si
│ écrire w," déplacer : ",x," vers ",z
│ si (w-1)/2-E((w-1)/2) = 0
│ │ alors d ← z
│ fin si
│ si (w-2)/4-E((w-2)/4) = 0
│ │ alors e ← z
│ fin si
│ si (w-4)/8-E((w-4)/8) = 0
│ │ alors f ← z
│ fin si
│ si (w-8)/16-E((w-8)/16) = 0
│ │ alors g ← z
│ fin si
│ si ...
│ ...
fin pour w
On voit bien qu'il y a comme un petit problème, non ? J'ai stocké les positions à chaque instant de chaque couronne dans les variables d,e,f,...,t,u puisque je n'ai pas d'autres variables et je veux garder les valeurs de b et c. Je suis donc limité à 18 couronnes.
Et je suis loin d'une boucle tant que ! Que pourrais-je mettre comme condition dans une telle boucle, je me le demande bien. J'ai fait une boucle pour qui correspond au nombre de déplacements à effectuer.
Si tu es limité par le nombre de variables, tu devrais probablement utiliser une liste pour stocker les états intermédiaires (ce qui revient à émuler une pile d'appels, mais chut )
déplacer-petit-plateau : ça c'est bon je sais quoi faire (et c'est un passage de l'algorithme que j'ai mis plus haut).
autre déplacement : là je ne vois vraiment pas quoi faire ! il faut regrouper tous les autres plateaux alors que moi je les avais séparés. Mais le problème c'est que le plateau à déplacer n'est pas forcément sur le même pilier qu'où étais le petit plateau...
Il y a un pilier qui est occupé par le plus petit plateau, donc le déplacement est entre les deux autres mais reste à savoir où est le plus petit des plateaux supérieurs de ces deux piliers. J'ai trouvé une solution mais elle me paraît un peu compliquée pour la chose :
En reprenant les mêmes variables qu'hier (sauf pour les variables "t" et "u" qui servent maintenant au fonctionnement de la boucle et non plus à connaître la position du 17 et 18 ème plateau),
t ← 1
u ← d
tant que u = d
│ t ← t+1
│ si t = 2
│ │ alors u ← e
│ fin si
│ si t = 3
│ │ alors u ← f
│ fin si
│ si..
│ ..
fin tant que u = d
écrire "déplacer : ",u," vers ",6-d-u
Ton code devra à peu près correspondre à ça :
Variables
Les piles PA, PB, PC tableau d'entiers
Les hauteurs HA, HB, HC entiers (avec la signification évidente)
Initialisation
PA <- [6, 5, 4, 3, 2, 1] NA <- 6
PB <- [] NB <- 0
PC <- [] NC <- 0
Pour un Hanoi de A vers C en utilisant B la condition de fin est NC = 6
par exemple
tant que NC <> 6 faire
deplacer-petit-plateau(PA, NA, PB, NB, PC, NC, PA', NA', PB', NB', PC', NC')
autre-deplacement(PA', NA', PB', NB', PC', NC', PA, NA, PB, NB, PC, NC)
fin tant que
On peut évidemment améliorer suivant le langage utilisé.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
En fait je vais garder le premier algorithme que j'ai écris, même s'il est un peu lent, je n'irai que juste à 15 plateaux, parce que ça commence déjà à être long pour ma calculatrice
Donc : sujet résolu .
[Algorithmique] Hanoï en itératif
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !