Tour de Hanoi

[Morpheus]

Salut,

j'aurais aimé savoir comment se passe l'algo pour les tours de Hanoi.

Merci

[Quidam]

Bonjour,

Code: Tout sélectionner

routine hanoi(n,A,B,C)
{
   // Transporte n disques de A à B en utilisant par C comme place intermédiaire
   // A, B et C sont les trois numéros 0,1,2 pas nécessairement
   // dans cet ordre

   si n=1 alors prendre le disque situé en haut de A et le placer sur B
   sinon
       hanoi(n-1,A,C,B)  // Transporter n-1 disques de A à C pour liberer le n-ième
       transporter le disque situé en haut de la pile A sur la pile B
       hanoi(n-1,C,B,A)  // Transporter n-1 disques de C à B
}

Voilà !

[olivthill]

C'est un cas typique où il faut utiliser la récursivité.

[Quidam]

C'est un cas typique où il faut utiliser la récursivité.

La récursivité dans l'esprit : sans aucun doute. Mais il ne faut jamais oublier que le récursivité au sens informatique du terme (celle que j'ai exhibée ci-dessus) est très consommatrice de ressources calcul... C'est très élégant, très sobre comme programmation, mais le CPU pédale comme un fou si on programme comme ça...

[eusebius]

La récursivité dans l'esprit : sans aucun doute. Mais il ne faut jamais oublier que le récursivité au sens informatique du terme (celle que j'ai exhibée ci-dessus) est très consommatrice de ressources calcul... C'est très élégant, très sobre comme programmation, mais le CPU pédale comme un fou si on programme comme ça...

Le CPU ça va, c'est surtout la mémoire (pile d'appel) qui y est sensible. Mais pour un problème de dimension raisonnable, sur une machine qui n'est pas une antiquité, ça me pose pas de problèmes existentiels. A mon avis le plus gros risque de la récursivité, c'est de foirer l'implémentation :langue:

[Patastronch]

Et puis pas mal de compilateurs bien foutu (dans certains langages seulement et cetaines formes de récursivité seulement), traduisent maintenant la récursivité en itératif a la compilation. Donc ca commence a ne plus etre vrai les overflows fréquent de la récursion.