Correction
Tableaux et chaînes de caractères

Exercice 1 : générateur automatique de lettres

Première version du code :

#include <iostream>
using namespace std;

void genereLettre()
{
  cout 
    << "Il faudrait que nous nous voyons le 18/12 pour en discuter." << endl
    << "Donnez-moi vite de vos nouvelles !"                          << endl
    << "Amicalement, John."                                          << endl;
}

int main()
{
  genereLettre();
  return 0;
}

Seconde version du code :

#include <iostream>
#include <string>
using namespace std;

void genereLettre(bool masculin, string destinataire, string sujet,
                  unsigned int jour, unsigned int mois,
                  string politesse, string auteur)
{
  cout << "Bonjour ";
  if (masculin) cout << "cher";
  cout << " " << destinataire << "," << endl;

  cout 
    << "Il faudrait que nous nous voyons le " << jour << "/" << mois 
    << " pour en discuter." << endl
    << "Donnez-moi vite de vos nouvelles !" << endl
    << politesse << ", " << auteur << endl;
}

int main()
{
  genereLettre(false, "Mireille", "votre cours" , 18, 12,
               "Amicalement", "John");
  cout << endl;
  genereLettre(true, "John", "votre demande de rendez-vous", 16, 12,
  return 0;
}

On peut bien sûr optimiser le code précédent en évitant les copies de chaînes de caractères dans le passage d'arguments en remplaçant les arguments de type string par des passages par références constantes (string const&) ou, encore mieux, depuis C++17 par des string_view.

Exercice 2 : segmentation en mots

Note : en version C++17, on préfèrera remplacer les const string& de la solution ci-dessous par des string_view.

#include <iostream>
#include <string>
using namespace std;

bool nextToken(const string& str, size_t& from, size_t& len);

int main()
{
  string phrase;

  getline(cin,  phrase);

  cout << "Les mots de \"" << phrase << "\" sont :" << endl;
  size_t debut(0);
  size_t longueur(0);
  while (nextToken(phrase, debut, longueur)) {
    cout << "'" << phrase.substr(debut, longueur) << "'" << endl;
    debut += longueur;
  }
  return 0;
}

 *
 */
bool issep (char c)
{
  return (c == ' ');
}

 */
bool nextToken(const string& str, size_t& from, size_t& len)
{
  const size_t taille(str.size());

  while ((from < taille) and issep(str[from])) ++from;

  len = 0;
  for (size_t i(from); ((i < taille) and not issep(str[i])); ++len, ++i);

  return (len != 0);
}

Commentaires

Le corrigé proposé pour nextToken est assez compact (cf commentaire donné avant) et nécessite d'avoir bien compris les structures de contrôle (while, for), ce qui le rend un peu plus difficile à comprendre que d'autres solutions.

Comme indiqué, vous pouvez le faire de plein de façons différentes ; mais examinons justement celle proposée :

bool nextToken (string const& str, int& from, int& len)
{
   int const taille(str.size());

Bon, jusque là je pense que ça va... ; juste peut être préciser les arguments :

• string const& str : la chaîne à traiter. Le passage par « const ref » est, bien sûr, une optimisation ; et l'on pourra dans un premier temps se contenter d'un simple passage par valeur : string str ;
• int& from : contient au départ la première position à partir de laquelle il faut chercher un nouveau « token », et devra contenir à la sortie de nextToken la position du début du token suivant ; il va donc être modifié par nextToken, et c'est pour cela qu'il est passé par référence ;
• int& len : va également être modifié par nextToken pour contenir la longueur du nouveau « token » (éventuellement) trouvé.

Continuons avec :

while ((from < taille) && issep(str[from])) ++from;

from est ici incrémenté(/augmenté) du nombre de séparateurs rencontrés. En effet, on ne peut pas commencer le nouveau « token » par un séparateur.

Comment fait-on pour sauter tous ces séparateurs ?
-> tant que le caractère courant est un séparateur, on avance. Ça, c'est le « while (issep(str[from])) ».

Mais il faut penser aussi à ne pas déborder de la chaîne (imaginez le cas où la chaîne ne contient que des séparateurs). Ça, c'est le « (from < taille) » dans le test du while.

Passons au bloc suivant. Son but est de trouver la fin du « token » (puisqu'on vient de trouver le début avec la boucle while précédente).

Cette fin de « token » est en fait indiquée par la longueur, len, du « token ». Au départ le « token » est vide (on a très bien pu sortir du while précédent par la condition « from ≥ taille ». Repensez encore une fois au cas d'une chaîne ne contenant aucun « token », mais uniquement des séparateurs). On a donc :

len = 0;

Puis on cherche la fin du « token » ; c'est-à-dire le prochain séparateur. C'est-à-dire que tant que l'on n'a pas de séparateur (« !issep(str[i]) »), on avance.

Ca veut dire quoi « on avance » ?
-> on passe au caractère suivant, ça c'est le « ++i », et on met à jour la taille du « token » en la faisant augmenter de 1, ça c'est le « ++len ».

D'où part-on ?
-> du caractère « from » précédemment trouvé.

Il ne reste plus qu'à ne pas oublier de ne pas déborder de la chaîne (« i < taille »), et le tour est joué :

for (int i(from); ((i < taille) && !issep(str[i])); ++len, ++i);

Pour essayer d'être encore plus clair, ceci peut aussi s'écrire de la façon moins compacte suivante (rappel : « from » représente le début de « token ») :

 bool continuer(true);
 int position_courante(from);

 do {
	if (position_courante >= taille) {
		continuer = false ;
	}

        // (c'est la fin du token)
	else if (issep(str[position_courante])) {
		continuer = false ;
	}
	
	// sinon, tout va bien, ...
	else {
		// ...on augmente la longueur du token de 1...
		len = len + 1;

		++position_courante;
	}

 } while (continuer);

Voilà pour cette partie.

Et pour finir, on renvoit (« true » si on a trouvé un « token », c.-à-d. si len n'est pas nulle, et « false » sinon. Soit :

return (len != 0);

if (len != 0) {
	return true;
} else {
	return false;
}

Exercice 3 : placements sans recouvrements

Le code fourni ici est en C++11. Pour une version compilant avec l'ancien standard (C++98) voir ci-dessous.

#include <iostream>
#include <array>
using namespace std;

constexpr size_t DIM(10);

// --------------------------------------------------------------------
bool remplitGrille(array<array<bool, DIM>, DIM>& grille,
                   unsigned int ligne, unsigned int colonne,
                   char direction, unsigned int longueur)
{
  int dx, dy;

  switch (direction) {
  case 'N': dx = -1; dy =  0; break;
  case 'S': dx =  1; dy =  0; break;
  case 'E': dx =  0; dy =  1; break;
  case 'O': dx =  0; dy = -1; break;
  }



  // mettre tout l'objet.
  for (// Initialisation 
       l = 0;

       /* Condition de continuation. Vu que i et j sont des "unsigned" *
        * pas besoin de tester ici les condition (i >= 0) et (j >= 0), *
       (possible) and (i < grille.size()) and (j < grille[0].size()) 
         and (l < longueur);

       ++l, i += dx, j += dy) {
    {
      possible = false;  // on ne peut donc pas mettre tout l'objet voulu
    }
  }

  /* Si l == longueur c'est qu'on a pu tout placer.
   * Il se pourrait en effet qu'on soit sorti de la boucle ci-dessus
   * "possible" jusqu'ici.
   */
  possible = possible and (l == longueur); 

  if (possible) {
    // on met effectivement l'objet, plus besoin de test ici
    for (l = 0, i = ligne, j = colonne; l < longueur; 
         ++l, i += dx, j += dy) {
      grille[i][j] = true;
    }
  }

  return possible;
}

// --------------------------------------------------------------------
void initGrille(array<array<bool, DIM>, DIM>& grille) 
{
  for (auto& ligne : grille) 
    for (auto& cell : ligne) 
      cell = false;
}

// --------------------------------------------------------------------
void ajouterElements(array<array<bool, DIM>, DIM>& grille)
{
  int x, y;
  do {
    cout << "Entrez coord. x : ";
    cin >> x;

    if (x >= 0) {
      cout << "Entrez coord. y : ";
      cin >> y;

      if (y >= 0) {

        char dir;
        do {
          cout << "Entrez direction (N,S,E,O) : ";
          cin >> dir;
        } while ((dir != 'N') and (dir != 'S') and
                 (dir != 'E') and (dir != 'O'));

        cout << "Entrez taille : ";
        unsigned int l;
        cin >> l;

        cout << "Placement en (" << x << "," << y << ") direction "
             << dir << " longueur " << l << " -> ";

        if (remplitGrille(grille, x, y, dir, l))
        else
          cout << "ECHEC";
        cout << endl;

      }
    }
  } while ((x >= 0) and (y >= 0));
}

// --------------------------------------------------------------------
void afficheGrille(const array<array<bool, DIM>, DIM>& grille)
{
  for (auto ligne : grille) {
    for (auto cell : ligne) {
      if (cell) cout << '#';
      else      cout << '.';
    }
    cout << endl;
  }
}

// --------------------------------------------------------------------
int main()
{
  array<array<bool, DIM>, DIM> grille;
  initGrille(grille);
  ajouterElements(grille);
  afficheGrille(grille);
  return 0;
}

Voici la version en «ancien» code (C++98) avec des tableaux à la C :

#include <iostream>
using namespace std;

const unsigned int DIM(10);

// --------------------------------------------------------------------
bool remplitGrille(bool grille[DIM][DIM],
                   unsigned int ligne, unsigned int colonne,
                   char direction, unsigned int longueur)
{
  int dx, dy;

  switch (direction) {
  case 'N': dx = -1; dy =  0; break;
  case 'S': dx =  1; dy =  0; break;
  case 'E': dx =  0; dy =  1; break;
  case 'O': dx =  0; dy = -1; break;
  }



  // mettre tout l'objet.
  for (// Initialisation 
       l = 0;

       /* Condition de continuation. Vu que i et j sont des "unsigned" *
        * pas besoin de tester ici les condition (i >= 0) et (j >= 0), *
       (possible) and (i < DIM) and (j < DIM) and (l < longueur);

       ++l, i += dx, j += dy) {
    {
      possible = false;  // on ne peut donc pas mettre tout l'objet voulu
    }
  }

  /* Si l == longueur c'est qu'on a pu tout placer.
   * Il se pourrait en effet qu'on soit sorti de la boucle ci-dessus
   * "possible" jusqu'ici.
   */
  possible = possible and (l == longueur); 

  if (possible) {
    // on met effectivement l'objet, plus besoin de test ici
    for (l = 0, i = ligne, j = colonne; l < longueur; 
         ++l, i += dx, j += dy) {
      grille[i][j] = true;
    }
  }

  return possible;
}

// --------------------------------------------------------------------
void initGrille(bool grille[DIM][DIM]) 
{
  for (unsigned int i(0); i < DIM; ++i) 
    for (unsigned int j(0); j < DIM; ++j) 
      grille[i][j] = false;
}

// --------------------------------------------------------------------
void ajouterElements(bool grille[DIM][DIM])
{
  int x, y;
  do {
    cout << "Entrez coord. x : ";
    cin >> x;

    if (x >= 0) {
      cout << "Entrez coord. y : ";
      cin >> y;

      if (y >= 0) {

        char dir;
        do {
          cout << "Entrez direction (N,S,E,O) : ";
          cin >> dir;
        } while ((dir != 'N') and (dir != 'S') and
                 (dir != 'E') and (dir != 'O'));

        cout << "Entrez taille : ";
        unsigned int l;
        cin >> l;

        cout << "Placement en (" << x << "," << y << ") direction "
             << dir << " longueur " << l << " -> ";

        if (remplitGrille(grille, x, y, dir, l))
        else
          cout << "ECHEC";
        cout << endl;

      }
    }
  } while ((x >= 0) and (y >= 0));
}

// --------------------------------------------------------------------
void afficheGrille(bool grille[DIM][DIM])
{
  for (unsigned int i(0); i < DIM; ++i) {
    for (unsigned int j(0); j < DIM; ++j) {
      if (grille[i][j]) 
        cout << "#";
      else
        cout << ".";
    }
    cout << endl;
  }
}

// --------------------------------------------------------------------
int main()
{
  bool grille[DIM][DIM];
  initGrille(grille);
  ajouterElements(grille);
  afficheGrille(grille);

  return 0;
}

Exercice 4 : Décimal en binaire

/* ======================================================================
 *
 * Decimal to binary and reverse conversions.
 *
 * Version: 1.0 (170901)
 * Author: J.-C. Chappelier (EPFL, 2017)
 *
 * ======================================================================
 */
#include <iostream>
#include <string>
using namespace std;

/* ======================================================================
 * This is the first algorithm of interest:
 * convertion from positive decimal to binary.
 */
string binary_nonnegative(int n)
{
  if (n <= 0) {
    return "0"s;
  }

  // here n >= 1
  string output;
  while (n > 0) {
    output = char('0' + n%2) + output;
    /* We could also make use of a less compact form, like:
       if (n%2 == 1) {
           output = '1' + output;
       } else {
           output = '0' + output;
       }
    */
    
    n /= 2;
  }
  
  return output;
}

/* ======================================================================
 * This is the second algorithm of interest:
 * convertion from positive binary (no sign bit) to decimal.
 */
unsigned int decimal_nonnegative(string const& binary)
// Note: from C++-17, make use of string_view rather than "string const&"
{
  unsigned int output(0);
  unsigned int power(1);

  /* There are more advanced way to iterate over a const string in C++ (crbegin(),
   * crend()). This is the very basic way for beginners in C++ programming.
   */
  if (not binary.empty()) {
    for (size_t i(binary.size() - 1); i < binary.size(); --i) {
      if (binary[i] == '1') {
        output += power;
      }
      power *= 2;
    }
  }

  return output;
}

/* ======================================================================
 * This is the third algorithm of interest:
 * two's complement of binary string
 */
string twos_complement(string const& binary)
// Note: from C++-17, make use of string_view rather than "string const&"
{
  string output(binary); // starts from a copy

  if (not binary.empty()) {
    
    // invert all bits left to the least-signicant 1 (LS1)

    // first search for LS1
    /* There are more advanced way to iterate over a string in C++ (cbegin(),
     * cend()). This is the very basic way for beginners in C++ programming.
     */
    size_t i(output.size() - 1);
    while ((i < output.size()) and (output[i] != '1')) --i;

    // skip that LS1
    --i;

    // then invert all "higher" bits
    while (i < output.size()) {
      if (output[i] == '1') {
        output[i] = '0';
      } else {
        output[i] = '1';
      }
      --i;
    }
  }
  
  return output;
}

/* ======================================================================
 * This is the forth algorithm of interest:
 * convertion from (signed) decimal to binary, making use of former algorithms.
 */
string binary(int n)
{
  // Add the bit sign to the corresponding "unsigned" representation
  if (n < 0) {
    return "1"s + twos_complement(binary_nonnegative(-n));
    /* could also be written as:
     * return twos_complement("0"s + binary_nonnegative(-n));
     */
  }
  return "0"s + binary_nonnegative(n);
}

/* ======================================================================
 * This is the fifth algorithm of interest:
 * convertion from binary (with sign bit) to decimal.
 */
int decimal(string const& binary)
// Note: from C++-17, make use of string_view rather than "string const&"
{
  // test sign bit
  if (not binary.empty() and (binary[0] == '1')) {
    return -decimal_nonnegative(twos_complement(binary));
  }

  return decimal_nonnegative(binary);
}

/* ======================================================================
 * All the rest below is not the core of the exercise but is just for
 * convenience.
 */

/* ======================================================================
 * Tool function: test an int value and its binary writing
 */
void test(int n)
{
  const string result(binary(n));
  cout << n << " is " << result << endl;
  cout << "and " << result << " is indeed " << decimal(result) << '.' << endl;
}

/* ======================================================================
 * Tool function: ask for some integer.
 */
int require_int()
{
  int value(0);
  cout << "Enter some integer: ";
  cin >> value;
  return value;
}

/* ======================================================================
 * Tool function: ask to continue or not.
 */
bool go_ahead() {
  char read('x');
  do {
    cout << "Shall we continue (y/n)? ";
    cin >> read;
  } while ((read != 'y') and (read != 'Y') and
           (read != 'n') and (read != 'N'));
  return (read == 'y') or (read == 'Y');
}

// ======================================================================
int main()
{
  const int t(42);
  cout << binary_nonnegative(t) << endl;
  test(t);
  test(-t);
  
  do {
    test(require_int());
  } while (go_ahead());

  return 0;
}

Exercice 5 : Entropie

#include <iostream>
#include <cmath> // pour log()
#include <cctype> // pour isalpha() et toupper()
#include <vector>
#include <array>
using namespace std;

// ======================================================================
typedef vector<double> Distribution;

// ======================================================================
Distribution calcule_probas(string const& s, bool compter_espace = false)
{
  for (auto& f : frequences) f = 0.0;

  for (const char c : s) {
    if (isalpha(c)) {
      ++frequences[toupper(c) - 'A'];
      ++somme;
    } else if ((c == ' ') and (compter_espace)) {
      ++frequences.back();
      ++somme;
    }
  }

  Distribution probas;
  
  for (auto& f : frequences) {
    if (f > 0.0) { // on ne retient que les non nuls ici
      probas.push_back(f / somme);
    }
  }

   return probas;
}

// ======================================================================
double log2(double x)
{
  return log(x) / log(2.0);
}

// ======================================================================
double entropie(Distribution const& probas)
{
  double entropy(0.0);
  for (auto p : probas) {
    entropy -= p * log2(p);
  }
  return entropy;
}

// ======================================================================
double entropie(string const& s)
{
  return entropie(calcule_probas(s));
}

// ======================================================================
// Tests
// --------------------------------------------------
void test2(Distribution const& probas) {
  cout << "p=(";
  for (auto p : probas) cout << p << ", ";
  cout << ") --> H = " << entropie(probas) << " bit" << endl;
}
// --------------------------------------------------
void test1(double p0) {
  test2({ p0, 1.0 - p0 });
}
// --------------------------------------------------
void test3(string const& s) {
  test2(calcule_probas(s));
  cout << "et directement : H = " << entropie(s) << " bit" << endl;
}

// ======================================================================
int main()
{
  // ---- 1) tests entropie binaire
  test1(0.0);
  test1(0.3);
  test1(0.5);
  test1(0.7);
  test1(1.0);

  test2({ 0.1, 0.2, 0.3, 0.4 }); 

  test3("IL FAIT BEAU A IBIZA");
  test3("AAAAA");
  test3("A");

  string s;
  cin >> s;
  test3(s);
  
  return 0;
}

Exercice 6 : tours de Hanoï

Cet exercice est de niveau 3 en raison de sa longueur et de l'appel récursif double (hanoi s'appelle deux fois) qui peut, peut être, troubler une première fois.

Cependant l'énoncé est assez bien détaillé et guide relativement bien.
Voici donc directement le code solution en C++11. Pour une version compilant avec l'ancien standard (C++98), voir ci-dessous.

#include <iostream>
#include <vector>
#include <array>
using namespace std;


typedef unsigned int Disque; 
// 0 signifiant pas de disque
constexpr Disque PAS_DE_DISQUE(0);

typedef vector<Disque> Pilier; // un pilier est une pile de disques

// les fonctions
void affiche(char c, unsigned int n = 1);
void affiche(const Disque& d);
void affiche(const Jeu& jeu);
void init(Jeu& jeu, unsigned int taille = N);
size_t sommet(const Pilier& p);
void deplace(Pilier& origine, Pilier& destination);
unsigned int autre(unsigned int p1, unsigned int p2);
void hanoi(unsigned int taille, unsigned int origine,
           unsigned int destination, Jeu& jeu);

// ----------------------------------------------------------------------
int main()
{
  Jeu monjeu;

  init(monjeu);
  affiche(monjeu);
  hanoi(N, 0, 2, monjeu);

  return 0;
}

/* ----------------------------------------------------------------------
 * Initialise le jeu
 * ---------------------------------------------------------------------- */
void init(Jeu& jeu, unsigned int taille)
{
  for (auto& pilier : jeu) {
    pilier = Pilier(taille, PAS_DE_DISQUE);
  }

  // remplit le 1er pilier :
  for (size_t i(0); (i < jeu[0].size()) and (i < taille); ++i) {
    jeu[0][i] = Disque(i+1);
  }
}

/* ----------------------------------------------------------------------
 * ---------------------------------------------------------------------- */
void affiche(char c, unsigned int n)
{
  for (unsigned int i(0); i < n; ++i) cout << c;
}

/* ----------------------------------------------------------------------
 * Affiche un dique
 * ---------------------------------------------------------------------- */
void affiche(const Disque& d)
{
  if (d == PAS_DE_DISQUE) {
    affiche(' ', N-1);
    affiche('|');
  }
  else {
    affiche(' ', N-d);
    affiche('-', 2*d-1);
  }
}

/* ----------------------------------------------------------------------
 * Affiche un jeu
 * ---------------------------------------------------------------------- */
void affiche(const Jeu& jeu)
{
  for (size_t i(0); i < jeu[0].size(); i++) {
    affiche(jeu[0][i]);
    affiche(jeu[1][i]);
    affiche(jeu[2][i]);
    cout << endl;
  }
  // le socle
  affiche('#', 6*N-1); // 3*(2*N-1)+2 = 6*N-1, ou autre choix...
  cout << endl << endl;
}

/* ----------------------------------------------------------------------
 * Retourne l'indice du sommet d'une tour sur un pilier. Retourne N si pas
 * de tour sur ce pilier
 * ---------------------------------------------------------------------- */
size_t sommet(const Pilier& p)
{
  size_t top;
  for (top = 0; (top < p.size()) and (p[top] == PAS_DE_DISQUE); ++top);
  return top;
}

/* ----------------------------------------------------------------------
 * ---------------------------------------------------------------------- */
void deplace(Pilier& origine, Pilier& destination)
{
  size_t top1(sommet(origine));
  if (top1 < origine.size()) { // si la tour d'origine existe bien

    size_t top2(sommet(destination));
    if ((top2 < destination.size()) and (destination[top2] < origine[top1])) {
      /* on essaye de mettre un disque plus gros (origine[top1])
       * sur un disque plus petit (destination[top2]) : ce n'est pas 
       */
	   << origine[top1] << " sur un disque de taille "
	   << destination[top2] << " !" << endl;
      return;
    }

    // effectue le mouvement
    destination[top2-1] = origine[top1];
    origine[top1] = PAS_DE_DISQUE;
  }
}

/* ----------------------------------------------------------------------
 * pilier
 * ---------------------------------------------------------------------- */
unsigned int autre(unsigned int p1, unsigned int p2)
{
  return 3 - p1 -p2;
}

/* ----------------------------------------------------------------------
 * ---------------------------------------------------------------------- */
void hanoi(unsigned int n, unsigned int origine, unsigned int destination,
	   Jeu& jeu)
{
  if (n != 0) {
    const unsigned int auxiliaire(autre(origine, destination));
    hanoi(n-1, origine, auxiliaire, jeu);
    deplace(jeu[origine], jeu[destination]);
    affiche(jeu);
    hanoi(n-1, auxiliaire, destination, jeu);
  }
}

Version C++98, les différences avec la version C++11 sont mises en évidence :

#include <iostream>
using namespace std;



typedef unsigned int Disque; 
// 0 signifiant pas de disque
const Disque PAS_DE_DISQUE(0);

typedef Disque Pilier[N]; // un pilier est une pile d'au plus N disques



// les fonctions
void affiche(char c, unsigned int n = 1);
void affiche(Disque d);
void affiche(Jeu jeu);




		      * cette fonction */

unsigned int sommet(Pilier p);
unsigned int autre(unsigned int p1, unsigned int p2);
void hanoi(unsigned int n, unsigned int origine, unsigned int destination,

// ----------------------------------------------------------------------
int main()
{
  Jeu monjeu;

  init(monjeu);
  affiche(monjeu);
  hanoi(N, 0, 2, monjeu);

  return 0;
}

/* ----------------------------------------------------------------------
 * Initialise le jeu
 * ---------------------------------------------------------------------- */
void init(Jeu& jeu)
{
  for (unsigned int i(0); i < N; ++i) {
    jeu[0][i] = Disque(i+1);
    jeu[1][i] = PAS_DE_DISQUE;
    jeu[2][i] = PAS_DE_DISQUE;
  }
}

/* ----------------------------------------------------------------------
 * ---------------------------------------------------------------------- */
void affiche(char c, unsigned int n)
{
  for (unsigned int i(0); i < n; ++i) cout << c;
}

/* ----------------------------------------------------------------------
 * Affiche un dique
 * ---------------------------------------------------------------------- */
void affiche(Disque d)
{
  if (d == PAS_DE_DISQUE) {
    affiche(' ', N-1);
    affiche('|');
  }
  else {
    affiche(' ', N-d);
    affiche('-', 2*d-1);
  }
}

/* ----------------------------------------------------------------------
 * Affiche un jeu
 * ---------------------------------------------------------------------- */
void affiche(Jeu jeu)
{
  for (unsigned int i(0); i < N; ++i) {
    affiche(jeu[0][i]);
    affiche(jeu[1][i]);
    affiche(jeu[2][i]);
    cout << endl;
  }
  // le socle
  affiche('#', 6*N-1); // 3*(2*N-1)+2 = 6*N-1, ou autre choix...
  cout << endl << endl;
}

/* ----------------------------------------------------------------------
 * Retourne l'indice du sommet d'une tour sur un pilier. Retourne N si pas
 * de tour sur ce pilier
 * ---------------------------------------------------------------------- */
unsigned int sommet(Pilier p)
{
  unsigned int top;
  for (top = 0; (top < N) and (p[top] == PAS_DE_DISQUE); ++top);
  return top;
}

/* ----------------------------------------------------------------------
 * ---------------------------------------------------------------------- */
void deplace(Pilier& origine, Pilier& destination)
{
  unsigned int top1(sommet(origine));
  if (top1 < N) { // si la tour d'origine existe bien

    unsigned int top2(sommet(destination));
    if ((top2 < N) and (destination[top2] < origine[top1])) {
      /* on essaye de mettre un disque plus gros (origine[top1])
       * sur un disque plus petit (destination[top2]) : ce n'est pas 
       */
	   << origine[top1] << " sur un disque de taille "
	   << destination[top2] << " !" << endl;
      return;
    }

    // effectue le mouvement
    destination[top2-1] = origine[top1];
    origine[top1] = PAS_DE_DISQUE;
  }
}

/* ----------------------------------------------------------------------
 * pilier
 * ---------------------------------------------------------------------- */
unsigned int autre(unsigned int p1, unsigned int p2)
{
  return 3 - p1 -p2;
}

/* ----------------------------------------------------------------------
 * ---------------------------------------------------------------------- */
void hanoi(unsigned int n, unsigned int origine, unsigned int destination,
	   Jeu& jeu)
{
  if (n != 0) {
    const unsigned int auxiliaire(autre(origine, destination));
    hanoi(n-1, origine, auxiliaire, jeu);
    deplace(jeu[origine], jeu[destination]);
    affiche(jeu);
    hanoi(n-1, auxiliaire, destination, jeu);
  }
}