Exemple 1 : Hanoi

Contenu du fichier

/**
    \file hanoi.cpp

    \brief Programme de resolution du probleme des tours de Hanoi

    Ce programme resoud le probleme des tours de Hanoi pour un nombre
    de tours quelconque, par un algorithme simple recursif.
    Le programme, a partir du nombre de disque initiaux, indique
    comment les deplacer de la tour d'origine (A) a la tour cible (C)
    en passant par la tour auxiliaire (B).
    La solution est indiquee par la liste des mouvements a effectuer.

    \author Gabriel Girard
    \version 1.1
    \date 16 novembre 2006

    Entree:
        \li (clavier) nombre de disques dans la tour d'origine initiale (entier positif)

    Sortie:
        \li (ecran) liste des mouvements qui permet la resolution du probleme (chaine de caractere)
        \li (ecran) nombre de deplacements necessaires pour la solution (entier positif)

    Date de creation: 1994 \n
    Modification:
        \li 25 aout 2003, mise a jour, Benoit Fraikin
        \li 15 novembre 2006, mise a jour des normes, Benoit Fraikin
        \li 16 novembre 2006, ajout du calcul du nombre de deplacement, Benoit Fraikin
 */
#include <iostream>

using namespace std;
/**
   \brief Programme de resolution du probleme des tours de Hanoi
 */
int main()
{
    int hanoi(char, char, char, int);

    int nbre_disques;
    int nombre_deplacements;

    cout << "Probleme de la tour de Hanoi. " << endl ;
    cout << "Entrez le nombre de disques : ";
    cin >> nbre_disques;
    
    nombre_deplacements = hanoi('A', 'C', 'B', nbre_disques);

    cout << "Deplacement pour la solution : " << nombre_deplacements << endl;

    return 0;
}

/**
   \brief Resoud le probleme des tours de Hanoi pour un nombre qcq de disques.

   Resoud le probleme des tours de Hanoi en deplacant \c nb_disques disques
   de la tour \c tour_origine vers la tour \c tour_cible en utilisant la tour
   \c tour_auxiliaire.\n

   L'algorithme est recursif :
   \li si \c nb_disques, le nombre de disques, est egale a 1, on deplace un anneau
   \li sinon on en deplace \c nb_disques-1 sur la tour auxiliaire
   \li puis on deplace 1 disque de la tour d'origine a la tour cible
   \li puis on replace les \c nb_disques-1 disques sur la tour cible.

   \param[in] tour_origine tour d'origine ou sont places les \c nb_disques disques
   \param[in] tour_cible tour cible ou doivent etre places \c nb_disques disques
   \param[in] tour_auxiliaire tour auxiliaire servant de position temporaire
   \param[in] nb_disques le nombre de disques a deplacer de \c tour_origine vers \c tour_cible
   
   \return le nombre de deplacement effectue
 */
int hanoi(char tour_origine, char tour_cible,
           char tour_auxiliaire, int nb_disques)
{
    void deplacer_un_disque(char, char, int);

    int nombre_deplacements;
    
    if (nb_disques == 1)
    {
        deplacer_un_disque(tour_origine, tour_cible, nb_disques);
        nombre_deplacements = 1;
    }
    else
    {
        nombre_deplacements = hanoi(tour_origine, tour_auxiliaire, tour_cible, nb_disques-1);
        deplacer_un_disque(tour_origine, tour_cible, nb_disques);
        nombre_deplacements += 1; // deplacement du disque precedent
        nombre_deplacements += hanoi(tour_auxiliaire, tour_cible, tour_origine, nb_disques-1);
    }

    return nombre_deplacements;
}

/**
   \brief Deplace un disque entre deux tours.

   Deplace un disque de la tour \c tour_origine vers la tour \c tour_cible.

   \param[in] tour_origine tour d'origine ou sont places les \c nb_disques disques
   \param[in] tour_cible tour cible ou doivent etre places \c nb_disques disques
   \param[in] numero numero du disque a deplacer
 */
void deplacer_un_disque(char tour_origine, char tour_cible, int numero)
{
    cout << " - Deplacement de l'anneau " << numero ;
    cout << " de la tour " << tour_origine << " vers la tour ";
    cout << tour_cible << "." << endl;

    return ;
}