Ansi/iso c++ : 010 : tours de hanoi

Soyez le premier à donner votre avis sur cette source.

Vue 7 500 fois - Téléchargée 5 689 fois

Description

Voici un petit exemple typique de fonction récursive.
Ici, il s’agit de résoudre le déplacement d’une tour de Hanoi.

Source / Exemple :


#include <vector>
#include <iostream>

std::vector<int> tower[ 3 ];

void init_towers( int nb_discs )
{
   tower[ 0 ].resize( nb_discs );

   for( int disc_i = 0 ; disc_i < nb_discs ; ++disc_i )
      tower[ 0 ][ disc_i ] = nb_discs - disc_i;

   tower[ 1 ].clear();
   tower[ 2 ].clear();
}

void cout_towers()
{
   using namespace std;
   
   for( size_t tower_i = 0 ; tower_i < 3 ; ++tower_i )
   {
      cout << "tower[" << tower_i << "]: ";

      for(
         size_t disc_i = 0;
         disc_i < tower[ tower_i ].size();
         ++disc_i
      )
         cout << tower[ tower_i ][ disc_i ] << ' ';

      cout << endl;
   }

   cin.ignore( 1, '\n' );
}

void cout_move( int src, int dest )
{
   using namespace std;

   cout
      << "move from tower " << src
      << " to tower " << dest << endl
   ;
}

void move( int src, int dest, int size )
{
   int third = 3 - ( src + dest );

   --size;

   if( size ) move( src, third , size );

   if(
      ( ! tower[ src ].empty() )
      &&
      (
         tower[ dest ].empty()
         ||
         tower[ dest ].back() > tower[ src ].back()
      )
   )
   {
      cout_move( src, dest );

      tower[ dest ].push_back( tower[ src ].back() );
      tower[ src ].pop_back();

      cout_towers();
   }
   // else error !

   if( size ) move( third, dest, size );
}

int main()
{
   int nb_discs = 6;
   init_towers( nb_discs );
   move( 0, 2, nb_discs );
}

Conclusion :


Les disques des tours sont représentés par des 'int' signifiants leurs tailles.
Aussi, les tours sont-elles représentées par des 'std::vector<int>', regroupés en un array : 'std::vector<int> tower[ 3 ];'.
La fonction 'init_towers' initialise le tours, 'tower[ i ]' de sorte à rassembler les 'nb_discs' disques sur la première tour('tower[ 0 ]').
La fonction 'cout_tower' affiche l'état des 3 tours.
La fonction 'cout_move' affiche un déplacement de disque, d'une tours vers une autre.
La fonction 'move' déplace 'size' disques, d'une tour vers une autre. Il s'agit de la fameuse fonction récursive. En effet, pour déplacer 'size' ('size <= 2') disques, il faut d'abord en déplacer 'size -1', puis 1, puis encore 'size -1', et ainsi de suite, jusqu'à ce que 'size ==1'.
La fonction 'main' est finalement très simple. Nous initialisons les tours 'init_towers( nb_discs );' et nous déplacons tous les disque de la tour '0' à la tour '2'.
A l'exécution, vous devez appuyer sur la touche [enter] à chaque déplacement. Vous pouvez ainsi suivre l'évolution...

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
C'est un peu longuet tout ça... il y a bcp bcp plus simple. il existe un code pour Hanoi d'une seule et unique ligne.
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
J'oubliais, qui est en C et non en C++
cs_Matt67
Messages postés
549
Date d'inscription
samedi 6 septembre 2003
Statut
Membre
Dernière intervention
6 mars 2010
-
Bonjour,

Je serais interressé par le code qui tient en une seule et unique ligne...

Merci,

Matt...

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.