420KEL00 – Bases

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!).

#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.

#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 :

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 {
      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;
}

Vous remarquerez peut-être que la classe Noeud dans ce exemple est placée hors de la classe ListeEntiers, ce qui est un mauvais design (pourquoi un détail d'implémentation comme Noeud serait-il exposé au code client?). Si vous êtes confortable avec le concept, je vous suggère (fortement!) de faire un petti changement à ce code pour faire de Noeud une classe interne à ListeEntiers. Si vous ne comprenez pas ce que je veux dire par là, n'hésitez pas à en discuter avec moi!

Relatif à EX03 et à EX04

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!

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
bool est_lettre(unsigned char c) {
   return 'A' <= c && c <= 'Z' || 'a' <= c && c <= 'z';
}
unsigned char rot13(unsigned char c) {
   if(!est_lettre(c)) return c;
   const int EVENTAIL_LETTRES = ('z' - 'a' + 1);
   const int ROTATION = EVENTAIL_LETTRES / 2; // algo ROT 13
   const unsigned char PLANCHER = (c >= 'a' && c <= 'z')? 'a' : 'A';
   return (c - PLANCHER + ROTATION) % EVENTAIL_LETTRES + PLANCHER;
}
void encodage_full_cool(unsigned char *texte) {
   while(*texte) {
      *texte = rot13(*texte);
      texte++;
   }
}
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;
}

Bases – Support

Relatif à EX00

Relatif à EX01

Relatif à EX02

Relatif à EX03 et à EX04

Relatif à EX05