Discussion :

[Kenshin86]

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 ?

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

Cordialement,

[yan]

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"][/ame] <=smilets clickable

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

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

bon courage

[Kenshin86]

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

Personne n'a l'algo ?

[yan]

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

Personne n'a l'algo ?

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

[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.

[Kenshin86]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 .

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.

[Trap D]

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.

[zais_ethael]

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.

[droggo]

Lio,

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.

[befalimpertinent]

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.

[Médinoc]

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...

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...)