PROFDINFO.COM

Votre enseignant d'informatique en ligne

Chapitre 1 - Révision et structures de base

Exercice 1.1 - Le polymorphisme

Programmez et testez un ensemble de classes qui permet de simuler le comportement de capteurs. Un capteur a comme attributs sa valeur courante, sa valeur minimale et sa valeur maximale. Les minimum et maximum doivent être spécifiés à la création du capteur. Un capteur doit avoir une méthode pour lire l'état du capteur et une autre méthode pour afficher la valeur courante du capteur. Il y a deux types de capteur: un capteur constant qui retourne toujours la valeur milieu entre son minimum et son maximum et un capteur aléatoire qui retourne une valeur aléatoire entre son minimum et son maximum inclusivement. Écrivez un programme principal qui teste le bon fonctionnement des deux types de capteurs.

Pour réaliser cet exercice vous devez obligatoirement utiliser:

Montrez votre code ainsi que le bon fonctionnement de votre programme à votre gentil professeur avant la fin de la période de cours.

Exercice 1.2 - La trinité

Reprennez votre solution de l'exercice 1.1 et dérivez la classe CapteurAleatoireAvecMemoire de votre classe qui représente un capteur aleatoire. Cette nouvelle classe devra contenir un tableau dynamique dont la taille sera spécifiée à la construction d'un objet de la classe CapteurAleatoireAvecMemoire. À chaque lecture du capteur, cette classe enregistre la valeur dans sa mémoire. Une méthode propre à cette classe aura pour effet d'afficher le contenu de sa mémoire à l'écran.

Testez le bon fonctionnement de cette classe en utilisant le programme principal suivant:

 

int main()
{
   srand(static_cast (time(0)));

   CapteurAleatoireAvecMemoire caam1(10,20,10);
   caam1.LireCapteur();
   caam1.LireCapteur();
   caam1.AfficherMemoire();

   CapteurAleatoireAvecMemoire caam2(caam1);
   caam2.LireCapteur();
   caam2.LireCapteur();
   caam2.AfficherMemoire();

   CapteurAleatoireAvecMemoire caam3(20,30,20);
   caam3 = caam2;
   caam3.LireCapteur();
   caam3.LireCapteur();
   caam3.AfficherMemoire();
}

Exercice 1.3 - Expérimentation des arrays

Voici une série d'exercices d'utilisation du conteneur array. Vous pourrez trouver de l'aide sur http://www.cplusplus.com/reference/array/array/

  1. Déclarez un array de 4 valeurs entières que vous initialiserez à 1,2,3 et 4;
  2. Affichez le contenu de votre array en utlisant une boucle for et des index;
  3. À l'aide d'une boucle for et d'un ittérateur, multipliez chaque valeur de l'array par 2;
  4. À l'aide d'une boucle for et d'un ittérateur constant, affichez le contenu de votre array;
  5. À l'aide d'un range-for et du mot-clé auto, multipliez chaque valeur de l'array par 3;
  6. À l'aide d'un range-for et du mot-clé auto, affichez le contenu de votre array;
  7. Est-il possible de copier un array de 5 entiers dans un array de 4 entiers (et vice-versa) à l'aide de l'opérateur d'affectation? Sinon pourquoi? Quel test devez-vous faire pour valider votre réponse?
  8. Est-il possible de copier un array de 4 caractères dans un array de 4 entiers (et vice-versa) à l'aide de l'opérateur d'affectation? Sinon pourquoi? Quel test devez-vous faire pour valider votre réponse?
  9. Si vous declarez un autre array de 4 valeurs entières et que vous le copiez dans votre premier array. Est-ce que (contrairement aux tableaux standards C++) les deux array demeurent indépendans? Que test devez-vous faire pour valider votre réponse?
  10. Quelle méthode devez-vous utiliser pour remplir efficacement un array? Programmez un exemple d'utilisation de cette méthode.
  11. Quelle méthode devez-vous utliser échanger le contenu de deux arrays? Programmez un exemple d'utilisation de cette méthode.
  12. À l'aide du conteneur array, déclarez une matrice de 2 lignes et de deux colonnes. Remplissez la matrice en vous assurant que chaque case contienne le produit du numéro de la ligne par le numéro de la colonne. Affichez le contenu de votre matrice à l'écran en utilisant deux range-for.

Exercice 1.4 - La performance des vecteurs

Écrire un programme qui permet de calculer le temps que prend votre ordinateur pour:

  1. Insérer 100 millions d'entiers dans un vecteur vide. Aucune réservation de mémoire préalable ne devra être effectuée. Toutes les insertions doivent être faites à la fin du vecteur.
  2. Insérer 100 millions d'entiers dans un vecteur vide. Tout l'espace mémoire nécessaire devra être reservé avant les insertions. Toutes les insertions doivent être faites à la fin du vecteur.
  3. Mélanger un vecteur de 100 millions d'entiers.
  4. Classer un vecteur d'entiers en ordre croissant.
  5. Inverser un vecteur de 100 millions d'entiers.
  6. Insérer 100 entiers au début d'un vecteur de 100 millions d'entiers.

N.B.: Afin de mesurer le temps d'exécution d'une série d'instructions, utilisez la high_resolution_clockclock() de la bibliothèque chrono.

Exercice 1.5 - La compression RLE

Utilisez un vecteur afin d'implémenter la compression par plages (RLE) d'une chaîne de caractères. La compression RLE est utilisée dans des formats d'images comme BMP, PCX et TIFF pour en réduire la taille. Le principe de base du RLE consiste à compter le nombre de répétitions de chaque valeur puis de sauvegarder seulement les couples compteur, valeur. Par exemple, la chaine AAAAAAAAAAHHH! deviendra 10A3H1!. On note tout de suite que la chaîne une fois compressée est plus courte que la chaine originale à condition que la chaîne originale contienne beaucoup de répétitions. Si ce n'est pas le cas, la compression RLE devient moins efficace et peut même gonfler la taille! Par exemple la chaîne JOAN deviendra 1J1O1A1N.

Votre programme doit donc demander une chaîne à l'usager, effectuer la compresion RLE à l'aide d'un vecteur où chaque élément du vecteur contiendra un compteur et une valeur, puis afficher la chaine compressée à l'écran.

Exercice 1.6 - La recherche linéaire et dichotomique

Écrivez un programme qui:

  1. Effectue la lecture d'un ensemble de mots à la console et les place dans un vecteur;
  2. trie le vecteur de mots en ordre alphabétique croissant;
  3. affiche à la console le vecteur de mots;
  4. demande un mot à l'usager et utilise la recherche linéaire pour déterminer si le mot est présent ou non et sa position dans le vecteur;
  5. et demande un mot à l'usager et utilise la recherche dichotomique pour déterminer si le mot est présent ou non et sa position dans le vecteur.

Une fois votre programme complété et fonctionnel, trouvez une manière de trier le vecteur de mots en ordre décroissant et assurez-vous que les recherches linéaire et dichotomique fonctionnent toujours...

Exercice 1.7 - La Matrice

Créez la classe Matrice qui permet de conserver et d'afficher une matrice de float et qui implémente la multiplication de matrices. Pour de plus amples informations sur la multiplication matricielle, voir https://fr.wikipedia.org/wiki/Produit_matriciel

Votre classe doit contenir au minimum:

Vous devez aussi programmer l'opérateur << qui permet d'afficher une matrice à la console.

Voici le programme principal qui vous servira de test:

 

int main()
{
	float TabA[4] = { 1.0f, 0.0f, -1.0f, 3.0f };
	float TabB[4] = { 3.0f, 1.0f, 2.0f, 1.0f };

	Matrice MatA(2,2,TabA);
	Matrice MatB(2,2,TabB);

	Matrice Res(2,2);

	Res = MatA*MatB;

	cout << Res;
    
    // La réponse est:
    // 3 1
    // 3 2
    
}

Exercice 1.8 - La file STL et le tableau circulaire

On peut modéliser la file FIFO à l'aide d'une classe abstraite. Quoi de mieux qu'une classe abstraite pour modéliser un type abstrait de données (TAD)? Voici la déclaration de la classe abstraite CFileEntiers:

class CFileEntiers
{
public:
     virtual void Ajouter(const int& i) = 0;
     virtual int Retirer() = 0;
     virtual bool EstVide() = 0;
     virtual bool EstPleine() = 0;
};       

La classe CFileEntiers est complète et ne doit pas être modifiée. Aucun code n'est associée à cette classe. Elle joue le rôle d'interface puisque les classes dérivées de CFileEntiers doivent implémenter les méthodes Ajouter, Retirer, EstVide et EstPleine.

Vous devez dériver de cette classe deux implémentations de la file FIFO:

  1. CTableauCirculaire dérive de CFileEntiers et doit implémenter la technique de tableau circulaire telle que vue en classe.
  2. CFileStl dérive de CFileEntiers et doit encapsuler la classe queue de STL.

Ensuite, mesurez la performance de vos deux classes en effectuant:

  1. 100 000 insertions;
  2. 100 000 retraits;
  3. et répétez 10 000 fois les points 1. et 2.

Utilisez un tableau fixe de 200 000 éléments pour le tableau circulaire.

Laquelle de vos implémentations est la plus rapide?

Exercice 1.9 - La pile de cartes

Cet exercice consiste à trier un jeu de cartes mélangées afin d'obtenir quatre piles de cartes. Chaque pile ne doit contenir que des cartes de la même sorte (pique, trèfle, carreau et coeur) et doit être ordonnée en ordre croissant (2, ..., 9, valet, dame, roi, as).

Vous devez donc écrire une fonction qui prend en paramètre un deque (notez ici le subtile jeu de mot anglophone deck et deque) de 52 cartes bien mélangées et un vecteur de quatre piles de cartes. Votre fonction doit vider le deque pour remplir le vecteur de piles.

Voici le squelette du programme principal que vous devez obligatoirement respecter:

// Déclaration de la structure Carte 
// À compléter

// Implémentation de la fonction Classer
// À compléter

// Programme principal
int main()
{
	// Déclaration des structures de données
	deque<Carte> Jeu; 
	vector<stack<Carte>> Piles;

	// Insérer les cartes dans le jeu 
	// À compléter...

	// Mélanger les cartes
	random_shuffle(begin(Jeu), end(Jeu));

	// Classer les cartes
   Classer(Jeu, Piles);

	// Afficher les quatres piles de cartes
	// À compléter...
}