Hanoi

Bonjour

Dans le cadre d'un projet scolaire , on doit réaliser la programmation en C++ d'une version récursive & itérative du problème des tours de HANOI.

Pour la 1ere version , cela n'a pas été trop compliqué , c'est vraiment plus simple quand on voit comment fonctionnes la récursivité :)

Sinon , la 2e version (itérative) est un véritable casse tète ! (avec 4 plaques par exemple)
J'ai déja essayé de trouver des exemples sur le net , en vain...

Quelqu'un aurait par hasard la version d'Hanoi en Iteratif ? :aie:

PS : l'utilisation d'une pile faciliterait le problème ?

Cordialement,

bonjour,
[ame="http://www.google.fr/search?q=hanoi+iterative&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a"]:google:[/ame] <=smilets clickable ;)

http://obelix.ee.duth.gr/~apostolo/T...noi/index.html

http://hanoitower.mkolar.org/algo.html

bon courage

Oui merci , j'avais déja parcouru ces liens.

Personne n'a l'algo ? :(

Citation:

---

Envoyé par Kenshin86

Oui merci , j'avais déja parcouru ces liens.

Personne n'a l'algo ? :(

---

?? ben y en as dans les sites, non?

Ce n'est pas une question d'algo. La technique récursive est la seule pour résoudre ce problème. Il n'est donc pas nécessaire de se casser la tête pour trouver une autre solution.
Ce qu'il faut, c'est se casser la tête pour trouver une solution générique et applicable à n'importe quel algo récursif pour le transformer en algo itératif, et je peux te garantir qu'elle existe.
Je vais te laisser réfléchir un peu, avec juste un indice: il te faudra utiliser un conteneur bien précis de la stl.

Mongaulois ->
Si , mais en fait , concernatn les liens :
-> le 1er est en JAVA. Je le comprends pas trop d'ailleurs
-> le 2e est assez complexe , je penses pas qu'on ns demandes de manipuler 3 piles pour résoudre le problème.
-> il sembles assez complexe aussi , mais j'ai testé et j'ai eu un bug à l'exécution.


zais_ethael ->
Mon programme récussif (C++) est le suivant :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

void Hanoi(int n_ha,char A,char B,char C) { if(n_ha>0) { Hanoi(n_ha-1,A,C,B); printf("Deplacer un disque de la tour %c vers la tour %c",A,B); printf("\n"); Hanoi(n_ha-1,C,B,A);     }

---

Mais il faut également le faire en itératif , à partir du récussif ou pas ? la je ne sais pas 8O.

J'ai déja réfléchis sr le problème et je me retrouves un peu pris par le temps parce que je dois le rendre tout à l'heure.

Tu peux dérécursiver en utilisant une pile, ou tu peux trouver la version itérative en observant bien le déplacement de la plus petite tour.

C'est bien moins compliqué que ça en a l'air.
Pense un peu à la façon dont fonctionne un algo récursif au niveau assembleur:
- on entre dans la fonction (un jump au début de la fonction)
- après quelques opérations, la fonction décide de s'appeler elle même (un jump au début de la fonction)
- après quelques opérations, la fonction décide à nouveau de s'appeler elle même (un jump au début de la fonction)
- ect...
Ca ne te rapelle rien? Tous ces jumps qui reviennent au même endroit? Ca ressemblerait pas à un simple while par hasard? La seule différence de taille avec un while classique c'est, c'est,... les variables locales bien sur! Celles-ci sont stockées sur la pile, une nouvelle instance apparait lorqu'une nouvelle fonction est appelée et l'instance précédente est restituée lors d'un return.
La solution est donc d'utiliser une pile (stack dans la stl, quoique tu peux simplement utiliser vector ou list avec les méthodes push_back, pop_back).

PS: c'est dit et redit dans les règles du forum, on est pas la pour faire tes devoirs. Te donner des pistes d'accord mais si tu ne sais vraiment pas le faire tout seul tant pis pour toi.

Oui j'avais deviné qu'il fallait utiliser une pile.

C'est que je n'ai pas fait d'assembleur donc je ne px pas vraiment voir.

Mais bon , merci quand meme

J'insiste sur la version itérative

Citation:

---

tu peux trouver la version itérative en observant bien le déplacement de la plus petite plaque

---

[edit] J'ai écrit tour au lieu de plaque, il faut noter les déplacements de la petite plaque et on trouve assez vite.

Lio,

Citation:

---

Envoyé par zais_ethael

Ce n'est pas une question d'algo. La technique récursive est la seule pour résoudre ce problème. Il n'est donc pas nécessaire de se casser la tête pour trouver une autre solution.
Ce qu'il faut, c'est se casser la tête pour trouver une solution générique et applicable à n'importe quel algo récursif pour le transformer en algo itératif, et je peux te garantir qu'elle existe.
Je vais te laisser réfléchir un peu, avec juste un indice: il te faudra utiliser un conteneur bien précis de la stl.

---

C'est parfaitement faux.

1) On peut toujours remplacer une méthode récursive par une méthode itérative, c'est seulement parfois compliqué à faire.

2) Pour les Tours de Hanoi, ce n 'est pas vraiment compliqué, et on peut parfaitement écrire une solution générale, c'est à dire qui peut travailler avec un nombre quelconque de disques. :)

Citation:

---

Envoyé par droggo

Lio,

C'est parfaitement faux.

1) On peut toujours remplacer une méthode récursive par une méthode itérative, c'est seulement parfois compliqué à faire.

2) Pour les Tours de Hanoi, ce n 'est pas vraiment compliqué, et on peut parfaitement écrire une solution générale, c'est à dire qui peut travailler avec un nombre quelconque de disques. :)

---

Je crois au contraire que c'est exactement ce qu'il disait : la manière itérative de résoudre Hanoi sera une forme de dérécursification.

Mais il n'est pas trop complexe avec une pile et un peu de réflexion d'obtenir cette dérécursification.

Comme dit plus haut, je me souviens avoir écrit le programme des tours de Hanoi avec un simple tant que sans aucune pile.
la fonction principale du programme se résumait à :

Code:

---

1 2 3 4 5

deplacer la petite plaque tant que pas fini faire autre deplacement possible deplacer la petite plaque fin tant que

---

Ce n'est pas moi qui a trouvé la solution , je l'avais lue dans un "Pour La Science" des années 80 !

Citation:

---

Envoyé par droggo

1) On peut toujours remplacer une méthode récursive par une méthode itérative, c'est seulement parfois compliqué à faire.

---

Si par "itérative", tu veux dire "itérative avec pile", alors la méthode est toujours récursive. C'est juste qu'on a déplaçé la pile (en utilisant une pile sur le tas au lieu de la pile système).

Et je ne connais pas de méthode sans pile pour résoudre le problème des tours de hanoi.
Edit: Je n'avais pas vu le code de Trap D. Mais ça ressemble plus à un Brute Force qu'à autre chose...

Citation:

---

Envoyé par Kenshin86

Oui j'avais deviné qu'il fallait utiliser une pile.
C'est que je n'ai pas fait d'assembleur donc je ne px pas vraiment voir.
Mais bon , merci quand meme

---

Ici, il n'est plus question de piles assembleur. Tu peux utiliser les conteneurs C++, notamment un simple std::vector (ses fonctions push_back() et pop_back() ne sont pas ainsi nommées pour rien...)

Citation:

---

Envoyé par Médinoc

Edit: Je n'avais pas vu le code de Trap D. Mais ça ressemble plus à un Brute Force qu'à autre chose...

---

Non pas du tout, la petite plaque parcourt les piles, 1 vers 2, 2 vers 3, 3 vers 1 etc, entre les deux, tu effectues le seul déplacement de plaque possible, (pas un déplacement de la petite plaque bien sûr) ce n'est pas ça que j'appellerais du "brute force".

Citation:

---

Envoyé par befalimpertinent

Je crois au contraire que c'est exactement ce qu'il disait : la manière itérative de résoudre Hanoi sera une forme de dérécursification.

---

Oui, c'est bien cela. Disons que autant il est idiot de vouloir calculer une factorielle par voie récursive, autant il est idiot de considérer qu'un algo "itératif avec pile" est réellement itératif.
Néanmoins, si il existe une solution purement itérative aux tours de hanoi j'aimerais bien la connaitre, juste pour l'aspect ludique.

Citation:

---

Envoyé par Trap D

Non pas du tout, la petite plaque parcourt les piles, 1 vers 2, 2 vers 3, 3 vers 1 etc, entre les deux, tu effectues le seul déplacement de plaque possible, (pas un déplacement de la petite plaque bien sûr) ce n'est pas ça que j'appellerais du "brute force".

---

Ah, non...

Si tu regarde les déplacements nécessaires à la résolution d'une tour composée ne serait-ce que de 3 disques, tu remarque déjà qu'il existe les déplacements

• 1-->2
• 1-->3
• 2-->1
• 2-->3
• 3-->2

Dés que tu essaye de la résoudre pour 4 disques ou plus, tu vois apparaitre le déplacement 3-->1, ce qui nous donne les six possibilités de déplacement envisageables avec 3 piliers (étant donné que 1-->1, 2-->2 et 3-->3 ne sont pas des déplacements valides ;):P)

Je plussote donc tout à fait zais lorsqu'il dit

Citation:

---

Envoyé par zais_ethael

Oui, c'est bien cela. Disons que autant il est idiot de vouloir calculer une factorielle par voie récursive, autant il est idiot de considérer qu'un algo "itératif avec pile" est réellement itératif.
Néanmoins, si il existe une solution purement itérative aux tours de hanoi j'aimerais bien la connaitre, juste pour l'aspect ludique.

---

Gio,

Citation:

---

Envoyé par zais_ethael

Néanmoins, si il existe une solution purement itérative aux tours de hanoi j'aimerais bien la connaitre, juste pour l'aspect ludique.

---

Celle-ci se contente d'afficher les déplacements en donnant les numéros des tours d'origine et destination du mouvement à faire. Je n'en connais pas de plus simple. :)

Si on veut également afficher le n° du disque en déplacement, il faut ajouter un petit calcul assez simple.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

// les tours sont numérotées de 0 à 2   int nbDisques; cout << "Combien de disques ? "; cin >> nbDisques; cout << endl;   int limiteBoucle = 1 << nbDisques; // pour N disques, on a 2^N -1 déplacements à faire   for (int i=1; i < limiteBoucle; i++) { int tOrigine, tDestination; // on déplace un disque de tOrigine à tDestination tOrigine = (i & i-1) % 3; tDestination = ( ( i | i-1 ) +1 ) % 3; cout << "tour " << i << " de " << tOrigine << " a " << tDestination << endl; }

---

:)

Citation:

---

Envoyé par koala01

Ah, non...

Si tu regarde les déplacements nécessaires à la résolution d'une tour composée ne serait-ce que de 3 disques, tu remarque déjà qu'il existe les déplacements

• 1-->2
• 1-->3
• 2-->1
• 2-->3
• 3-->2

---

Eh bien allons-y

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

1 2 3 4   2 3 4 1 petite plaque va de 1 en 2   3 4 1 2 seul déplacement possible   3 1 4 2 petite plaque va de 2 en 3     1 4 3 2 seul déplacement possible     1 4 3 2 petite plaque va de 3 en 1     1 2 4 3 seul déplacement possible   1 2 4 3 petite plaque va de 1 en 2     1 2 3 4 etc   2 1 3 4   1 2 3 4     1 2 3 4   1 3 2 4   3 2 1 4     2 3 1 4     1 2 3 4

---

J'ai peut-être oublié de préciser que seul déplacement possible exclu évidemment un déplacement de la petite plaque.

y as quand même plus simple

Code:

---

1 2 3 4 5 6

std::vector<int> tour1; std::vector<int> tour2; std::vector<int> tour3; for (int i=nbdisque,i>0;--i) tour1.push_back(i);   std::swap(tour1,tour3)

---

:dehors:

[EDIT]
Ici il donne une solution non récursive
http://www.info.univ-angers.fr/~gh/hilapr/programme.htm

Citation:

---

Selon l'auteur, le problème serait originaire d'Inde où une légende raconte que dans un temple où se trouvent trois poteaux sur lesquels s'empilent 64 disques d'or, les prêtres de Brahmâ déplacent continuellement les disques selon les règles édictées ci-dessus. D'après cette même légende, le dernier déplacement de disque marquera la fin du monde. Cette légende existe sous plusieurs versions et dans différentes religions.

Comme indiqué ci-dessous, un jeu à 64 disques requiert un minimum de 2^64-1 déplacements, soit plus de 40 fois le nombre de secondes écoulées depuis l'origine de l'Univers.

---

Je confirme 64 disques sa fait quelque peu ramer le PC :aie: