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

Télécharger le projet
Commenter

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...
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (Space_e_man)