Bases – Support

Ce qui suit se veut une forme de support pour vous faciliter la vie lors de la mise en place des exercices portant sur les techniques de base explorées dans le cours. L'idée est de diminuer le recopiage bête pour vous permettre de travailler sur « les vraies affaires ».

Relatif à EX00

Dans EX00, votre objectif est d'appliquer certaines techniques du cours pour améliorer la performance de la fonction transformer_majuscules() ci-dessous. Référez-vous au texte de l'exercice pour plus de détails quant aux contraintes qui vous sont imposées pour y arriver (ne faites pas n'importe quoi!).

Remarquez comment on se sert de toupper(). Comprenez-vous ce qui se passe ici?

Le code original, à modifier, suit :

Code de base pour EX00
#include <string>
#include <locale>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
string transformer_majuscules(string originale) {
   string resultat;
   for (string::size_type i = 0; i < originale.size(); i++) {
      char c;
      c = toupper(originale[i], locale::classic());
      resultat = resultat + c;
   }
   return resultat;
}
int main() {
   const int TAILLE = 5'000'000;
   string texte(TAILLE, 'a');
   string resultat;
   auto avant = system_clock::now();
   resultat = transformer_majuscules(texte);
   auto apres = system_clock::now();
   cout << "Transformer en majuscules v1 " << TAILLE << " caractères: "
        << duration_cast<milliseconds>(apres- avant).count() << " ms." << endl;
}

Relatif à EX01

Dans EX01, votre objectif est d'appliquer certaines techniques du cours pour améliorer la performance de la fonction trier_texte() ci-dessous. Référez-vous au texte de l'exercice pour plus de détails quant aux contraintes qui vous sont imposées pour y arriver (ne faites pas n'importe quoi!).

Comprenez-vous la stratégie appliquée par trier_texte()? Il s'agit d'une technique de tri fort efficace qu'on nomme le tri fusion (en anglais : merge sort). L'idée est que trier un tableau équivaut à trier la première moitié, puis trier la deuxième, puis les fusionner (ce qui se fait rapidement vu que les deux parties sont déjà triées). Croyez-le ou non, c'est presque la meilleure stratégie possible (l'implantation proposée ici pourrait être améliorée un peu, par contre; si vous désirez en savoir plus, regroupez-vous et venez en discuter avec moi).

Pour qu'on ait de grandes chaînes de caractères un peu bizarre à trier, je vous fournis la fonction generer_texte() qui crée une chaîne de caractères d'une certaine longueur avec des caractères alphabétiques minuscules pris au hasard. Pas besoin de l'optimiser, elle vous est donnée telle quelle.

Le code original, à modifier, suit :

Code de base pour EX01
#include <string>
#include <random>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;
string trier_texte(string originale) {
   string resultat, avant_milieu, apres_milieu;
   string::size_type milieu;
   switch (originale.size()) {
   case 2:
      if (originale[0] < originale[1]) {
         resultat += originale[0];
         resultat += originale[1];
      } else {
         resultat += originale[1];
         resultat += originale[0];
      }
      break;
   case 1:
   case 0:
      resultat = originale;
      break;
   default:
      milieu = originale.size() / 2;
      avant_milieu = trier_texte(originale.substr(0, milieu));
      apres_milieu = trier_texte(originale.substr(milieu));
      string::size_type av = 0, ap = 0;
      while (av < avant_milieu.size() && ap < apres_milieu.size()) {
         if (avant_milieu[av] < apres_milieu[ap]) {
            resultat += avant_milieu[av];
            av++;
         } else {
            resultat += apres_milieu[ap];
            ap++;
         }
      }
      if (av < avant_milieu.size()) {
         resultat += avant_milieu.substr(av);
      } else if (ap < apres_milieu.size()) {
         resultat += apres_milieu.substr(ap);
      }
   }
   return resultat;
}
string generer_texte(int taille) {
   random_device rd;
   mt19937 prng { rd() };
   uniform_int_distribution<int> de{0, static_cast<int>('z'-'a')};
   string temp;
   for (int i = 0; i < taille; i++)
      temp += de(prng) + 'a';
   return temp;
}
int main() {
   const int TAILLE = 100'000;
   auto texte = generer_texte(TAILLE);
   auto avant = system_clock::now();
   auto texteTrie = trier_texte(texte);
   auto apres = system_clock::now();
   cout << "Avant: " << texte << endl
        << "Après: " << texteTrie << endl
        << "Tri de " << TAILLE << " caractères: "
        << duration_cast<milliseconds>(apres- avant).count() << " ms." << endl;
}

Relatif à EX02

Dans EX02, votre objectif est d'écrire les opérateurs, les constructeurs et les destructeurs clés des classes Noeud et ListeEntiers. Si le code existant vous pose des problèmes, n'hésitez pas à venir en discuter avec le prof! En attendant, le code original, à modifier, suit :

Code de base pour EX02
struct Noeud {
   Noeud *succ;
   int val;
   // AJOUTEZ ICI
};
class ListeEntiers {
   Noeud *tete;
public:
   class ListeVide { };
   // AJOUTEZ ICI
   bool est_vide() const noexcept {
      return tete == nullptr;
   }
   void ajouter(int val) {
      if (est_vide())
         tete = new Noeud{val};
      else {
         auto p = tete;
         while (p->succ) p = p->succ;
         p->succ = new Noeud{val};
      }
   }
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      const int val = p->val;
      delete p;
      return val;
   }
   int taille() const noexcept {
      auto p = tete;
      int n = 0;
      for (auto p = tete; p; p = p->succ)
         ++n;
      return n;
   }
   void inverser() {
      Noeud *nouvelle_tete = {};
      while(tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelle_tete;
         nouvelle_tete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelle_tete;
   }
};
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter(i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
}

Relatif à EX03 et à EX04

Les exercices EX03 et EX04 utilisent la même base de code que l'exercice EX02.

Relatif à EX05

Dans EX05, votre objectif est de faire compiler un programme C++ exploitant une fonction C en y insérant des conversions explicites de types ISO. Référez-vous au texte de l'exercice pour plus de détails quant aux contraintes qui vous sont imposées pour y arriver (ne faites pas n'importe quoi!).

Si vous ne comprenez pas un morceau de code ou l'autre, allez voir votre professeur tout de suite!

Le code original, à modifier, suit :

Code de base pour EX05
#include <string>
using std::string;
void encodage_full_cool(unsigned char *texte) {
   while(*texte) {
      const int EVENTAIL_LETTRES = ('z' - 'a' + 1);
      const int ROTATION = EVENTAIL_LETTRES / 2; // algo ROT 13
      const unsigned char PLANCHER =
         (*texte >= 'a' && *texte <= 'z')? 'a' : 'A';
      *texte = (*texte - PLANCHER + ROTATION) % EVENTAIL_LETTRES + PLANCHER;
      texte++;
   }
}
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
   using namespace std;
   const string MESSAGE = "Amusez-vous bien!";
   vector<unsigned char> txt(begin(MESSAGE), end(MESSAGE));
   txt.push_back(0);
   cout << "Taille du texte brut: " << txt.size()<< endl;
   cout << "Avant: " << txt.data() << endl;
   encodage_full_cool(&txt[0]);
   cout << "Après encodage: " << txt.data() << endl;
   encodage_full_cool(&txt[0]);
   cout << "Après décodage: " << txt.data() << endl;
}

Valid XHTML 1.0 Transitional

CSS Valide !