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.

[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

[Trap D]

J'insiste sur la version itérative

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.

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

[Trap D]

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 :

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

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 !

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

[Trap D]

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

[zais_ethael]

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.

[koala01]

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 )

Je plussote donc tout à fait zais lorsqu'il dit

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.

[droggo]

Gio,

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 :

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

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;
    }

[Trap D]

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 :

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

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.

[yan]

y as quand même plus simple

Code :

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

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)

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