| Exercice 1 | Exercice 2 | Exercice 3 | Exercice 4 | Exercice 5 | Exercice 6 |
Première version du code :
#include <iostream> using namespace std; void genereLettre() { cout << "Bonjour chère Mireille," << endl << "Je vous écris à propos de votre cours." << endl << "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"; else cout << "chère"; cout << " " << destinataire << "," << endl; cout << "Je vous écris à propos de " << sujet << endl << "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, "Sincèrement", "Mireille"); 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.
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); bool issep (char c); // teste si le caractère est un separateur int main() { string phrase; cout << "Entrez une chaîne : "; 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; } /* La fonction suivante teste si le caractère est un séparateur. * * Ecrire une fonction présente l'avantage de pouvoir redéfinir facilement * la notion de séparateur (et éventuellement d'en définir plusieurs). */ bool issep (char c) { return (c == ' '); } /* Il y a de multiples façons d'écrire cette fonction. * Nous trouvons celle-ci est assez élégante. */ bool nextToken(const string& str, size_t& from, size_t& len) { const size_t taille(str.size()); // saute tous les separateurs à partir de from while ((from < taille) and issep(str[from])) ++from; // avance jusqu'au prochain séparateur ou la fin de str len = 0; for (size_t i(from); ((i < taille) and not issep(str[i])); ++len, ++i); return (len != 0); }
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 { // si on déborde de la chaine il faut s'arrêter if (position_courante >= taille) { continuer = false ; } // si on rencontre un séparateur, il faut s'arrêter // (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; // ...et on passe au caractère suivant. ++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);qui revient exactement à
if (len != 0) {
return true;
} else {
return false;
}
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; } unsigned int i(ligne); // les coordonnées de la case... unsigned int j(colonne); // ...à modifier unsigned int l; // la longueur modifiée bool possible(true); // est-ce possible de mettre tout l'élément ? // avant de modifier la grille, il faut vérifier si c'est possible de // 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), * * lesquelles sont forcément vraies */ (possible) and (i < grille.size()) and (j < grille[0].size()) and (l < longueur); // Incréments ++l, i += dx, j += dy) { if (grille[i][j]) // c'est-à-dire la grille est déjà occupée { 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 * parce que i >= DIM ou j >= DIM... ...ce qui n'a pas modifié * "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)) cout << "succès"; 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; } unsigned int i(ligne); // les coordonnées de la case... unsigned int j(colonne); // ...à modifier unsigned int l; // la longueur modifiée bool possible(true); // est-ce possible de mettre tout l'élément ? // avant de modifier la grille, il faut vérifier si c'est possible de // 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), * * lesquelles sont forcément vraies */ (possible) and (i < DIM) and (j < DIM) and (l < longueur); // Incréments ++l, i += dx, j += dy) { if (grille[i][j]) // c'est-à-dire la grille est déjà occupée { 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 * parce que i >= DIM ou j >= DIM... ...ce qui n'a pas modifié * "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)) cout << "succès"; 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; }
/* ====================================================================== * * 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; }
#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) { array<double, 27> frequences; // 28 = 26 caractères alphabétiques + 1 espace for (auto& f : frequences) f = 0.0; double somme(0.0); /* Nombre de caractères pris en compte. * N'est pas forcément égal à s.size() si il y a des caractères parasites. * Mis en double pour la division ultérieure. */ for (const char c : s) { if (isalpha(c)) { ++frequences[toupper(c) - 'A']; ++somme; } else if ((c == ' ') and (compter_espace)) { ++frequences.back(); ++somme; } } // Crée la distribution 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) { if (x == 0.0) return 0.0; // pour éviter le NaN 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) { cout << "Chaîne « " << s << " » :" << endl; 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 }); test2(Distribution(8, 1.0/8.0)); // équirépartie test3("IL FAIT BEAU A IBIZA"); test3("AAAAA"); test3("A"); cout << "Entrez une chaîne : "; string s; cin >> s; test3(s); return 0; }
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; constexpr unsigned int N(4); // la taille de la tour de départ // un disque sera représenté simplement par sa taille (rayon) 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 typedef array<Pilier, 3> Jeu; // le jeu est constitué de 3 piliers // 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) { // crée un jeu vide : 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); } } /* ---------------------------------------------------------------------- * Affiche n fois un caractère * Entrée : le caractère à afficher et le nombre de fois * ---------------------------------------------------------------------- */ void affiche(char c, unsigned int n) { for (unsigned int i(0); i < n; ++i) cout << c; } /* ---------------------------------------------------------------------- * Affiche un dique * Entrée : le dique à afficher * ---------------------------------------------------------------------- */ void affiche(const Disque& d) { if (d == PAS_DE_DISQUE) { affiche(' ', N-1); affiche('|'); affiche(' ', N); // N = N-1 de tour vide + 1 espace intermédiaire } else { affiche(' ', N-d); affiche('-', 2*d-1); affiche(' ', N-d+1); // +1 pour l'espace intermédiaire } } /* ---------------------------------------------------------------------- * Affiche un jeu * Entrée : le jeu à afficher * ---------------------------------------------------------------------- */ 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; } /* ---------------------------------------------------------------------- * Déplace le disque du top d'une tour à un autre pilier. * Vérifie que le mouvement est valide. * Entrée : le pilier d'où enlever le disque, et le pilier destination * ---------------------------------------------------------------------- */ 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 * un déplacement autorisé ! */ cerr << "ERREUR : on ne peut pas déplacer un disque de taille " << origine[top1] << " sur un disque de taille " << destination[top2] << " !" << endl; return; } // effectue le mouvement destination[top2-1] = origine[top1]; origine[top1] = PAS_DE_DISQUE; } } /* ---------------------------------------------------------------------- * Étant donnés deux numéros de pilier p1 et p2, retourne l'indice du 3e * pilier * ---------------------------------------------------------------------- */ unsigned int autre(unsigned int p1, unsigned int p2) { return 3 - p1 -p2; } /* ---------------------------------------------------------------------- * Déplace une tour d'un pilier à un autre. * Vérifie que le mouvement est valide. * Entrée : la taille de la tour, le pilier de départ, le pilier de destination * ---------------------------------------------------------------------- */ 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; const unsigned int N(4); // la taille de la tour de départ // un disque sera représenté simplement par sa taille (rayon) 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 typedef Pilier Jeu[3]; // le jeu est constitué de 3 piliers // les fonctions void affiche(char c, unsigned int n = 1); void affiche(Disque d); void affiche(Jeu jeu); void init(Jeu& jeu); /* Note: le passage par référence est ici facultatif * vu que Jeu est un tableau "à la C". * Mais je préfère marquer clairement par ce passage * par référence que l'argument jeu est modifié par * cette fonction */ unsigned int sommet(Pilier p); void deplace(Pilier& origine, Pilier& destination); // même remarque (bis) unsigned int autre(unsigned int p1, unsigned int p2); void hanoi(unsigned int n, unsigned int origine, unsigned int destination, Jeu& jeu); // même remarque (ter) // ---------------------------------------------------------------------- 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; } } /* ---------------------------------------------------------------------- * Affiche n fois un caractère * Entrée : le caractère à afficher et le nombre de fois * ---------------------------------------------------------------------- */ void affiche(char c, unsigned int n) { for (unsigned int i(0); i < n; ++i) cout << c; } /* ---------------------------------------------------------------------- * Affiche un dique * Entrée : le dique à afficher * ---------------------------------------------------------------------- */ void affiche(Disque d) { if (d == PAS_DE_DISQUE) { affiche(' ', N-1); affiche('|'); affiche(' ', N); // N = N-1 de tour vide + 1 espace intermédiaire } else { affiche(' ', N-d); affiche('-', 2*d-1); affiche(' ', N-d+1); // +1 pour l'espace intermédiaire } } /* ---------------------------------------------------------------------- * Affiche un jeu * Entrée : le jeu à afficher * ---------------------------------------------------------------------- */ 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; } /* ---------------------------------------------------------------------- * Déplace le disque du top d'une tour à un autre pilier. * Vérifie que le mouvement est valide. * Entrée : le pilier d'où enlever le disque, et le pilier destination * ---------------------------------------------------------------------- */ 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 * un déplacement autorisé ! */ cerr << "ERREUR : on ne peut pas déplacer un disque de taille " << origine[top1] << " sur un disque de taille " << destination[top2] << " !" << endl; return; } // effectue le mouvement destination[top2-1] = origine[top1]; origine[top1] = PAS_DE_DISQUE; } } /* ---------------------------------------------------------------------- * Étant donnés deux numéros de pilier p1 et p2, retourne l'indice du 3e * pilier * ---------------------------------------------------------------------- */ unsigned int autre(unsigned int p1, unsigned int p2) { return 3 - p1 -p2; } /* ---------------------------------------------------------------------- * Déplace une tour d'un pilier à un autre. * Vérifie que le mouvement est valide. * Entrée : la taille de la tour, le pilier de départ, le pilier de destination * ---------------------------------------------------------------------- */ 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); } }