M1103 Feuille 1

Avant de commencer : activez C++14

Les vecteurs ne sont qu’une des structures de données qui existent en C++. Le choix de la bonne structure de données est fondamental pour la résolution de tout problème algorithmique. Vous allez apprendre les avantages et les inconvénients des structures de données les plus courantes dans d’autres cours. Dans ce cours introductoire on se limite à des vecteurs, qui sont souvent un choix raisonnable.

Les exercices de cette feuille d’exercices ont pour but d’approfondir votre familiarisation avec la classe vector de C++. La bonne utilisation de vecteurs est la clé pour leur solution.

Téléchargez le fichier code.zip et ajoutez son contenu (les fichiers unique.cpp, unique.h, merge.cpp, merge.h, sieve.cpp, sieve.h, median.cpp, median.h, test.cpp, asserts.h) à un nouveau projet Code::Blocks.

Vous pouvez tester vos fonctions en lançant le programme dont la fonction main est définie dans le fichier test.cpp.

Exercice 1 — Détection de doublons

Une approche naïve pour résoudre ce problème est une double boucle qui compare tous les couples d’éléments du vecteur et qui renvoie true dès que l’on trouve deux éléments égaux à des indices différents.
Ici, nous allons plutôt privilégier un algorithme qui sépare les deux boules dans deux fonctions différentes pour avoir une architecture conceptionnelle plus propre de notre algorithme.

Dans ce premier exercice nous nous posons le problème de base suivant : pour un vecteur d’entiers donné, nous voulons savoir si le vecteur contient un doublon, c’est-à-dire un élément qui apparaît au moins deux fois.

Nous allons parcourir le vecteur du début à la fin en mettant à jour une collection d’entiers, initialement vide. Pour chaque élément, nous faisons deux choses :

  1. si l’élément courant se trouve dans la collection, arrêter l’algorithme et retourner false
  2. rajouter l’élément courant à la collection

Nous constatons que la collection d’entiers dans chaque itération contient les éléments des itérations précédentes. Si le vecteur contient un doublon, notre algorithme va donc retourner false à la deuxième occurrence du doublon.

a — Recherche d’un élément dans un vecteur

Compléter la fonction contains dans le fichier unique.cpp. Cette fonction prend en paramètre (une référence constante à) un vecteur d’entiers vec et un entier n. Elle renvoie true si l’entier n se trouve dans le vecteur vec, et false sinon.

Cette fonction nous servira pour la recherche de l’élément courant dans la collection d’entiers (qui sera implémentée par un vecteur) dans l’étape 1 décrite ci-dessus.

b — Fonction unique

Compléter la fonction unique dans le fichier unique.cpp. Cette fonction prend en paramètre (une référence constante à) un vecteur d’entiers et renvoie true si et seulement si tous les éléments du vecteur sont uniques, c’est-à-dire le vecteur ne contient pas de doublons.

Exercice 2 — Fusion de deux vecteurs ordonnés

Dans cet exercice nous voulons fusionner deux vecteur ordonnés d’une manière telle que le vecteur résultant est également ordonné. Par exemple, si les deux vecteurs à fusionner sont

2 4 5 7 8

et

1 3 6 9 10

alors le vecteur fusionné sera :

1 2 3 4 5 6 7 8 9 10

a — Vérification d’ordre

Nous commençons avec une vérification si oui ou non un vecteur d’entiers donné est en ordre strictement croissant. Pour cela, il suffit de traverser le vecteur une fois et de comparer tous les couples d’éléments adjacents.

Compléter la fonction increasing dans le fichier merge.cpp. Cette fonction prend en paramètre (une référence constante à) un vecteur d’entiers et renvoie true si et seulement si les éléments sont en ordre strictement croissant.

b — Fusion

Nous allons maintenant implémenter la fonction qui effectue la fusion. Une possibilité pour créer le vecteur fusionné est de garder un indice i1 dans le premier vecteur et un indice i2 dans le deuxième vecteur. Dans chaque itération de la boucle principale, nous allons comparer les éléments correspondant à ces indices. L’élément le plus petit parmi ces deux éléments sera rajouté au vecteur à retourner et l’indice correspondant sera incrémenté. Si un des deux indices atteint la fin du vecteur, nous allons terminer la boucle principale et rajouter au vecteur à retourner tous les éléments restants de l’autre vecteur.

Compléter la fonction merge dans le fichier merge.cpp. Cette fonction prend en paramètre deux (références constantes à des) vecteur d’entiers et renvoie un vecteur d’entiers. Le vecteur retourné doit contenir tous les éléments des deux vecteurs en entrée en ordre croissant. Vous pouvez supposer que tous les élément des deux vecteurs sont différents.

Exercice 3 — Crible d’Ératosthène

Nous voulons maintenant écrire une fonction qui renvoie les nombres premiers inférieurs à une borne supérieure \(n\) donnée. Pour cela, nous utilisons le crible d’Ératosthène. Il procède comme suit :

  1. générer la liste des entiers entre \(2\) et \(n\)

  2. pour chaque entier de la liste commençant à gauche : supprimer tous les multiples de l’entier à droite de l’entier courant

Voici un exemple avec \(n=10\). Après l’étape 1, la liste est :

2 3 4 5 6 7 8 9 10

La première itération de l’étape 2 élimine tous les multiples de \(2\) qui se trouvent à droite de \(2\) :

2 3 4 5 6 7 8 9 10

La liste restante après la première itération de l’étape 2 est donc :

2 3 5 7 9

La deuxième itération de l’étape 2 regarde maintenant l’élément qui suit \(2\), c’est-à-dire \(3\). On élimine donc tous les multiples de \(3\) qui se trouvent à droite de \(3\) :

2 3 5 7 9

Cela nous donne la liste suivante après la deuxième itération de l’étape 2:

2 3 5 7

L’algorithme fait deux itérations supplémentaires avec \(5\) et \(7\) sans trouver de multiples à éliminer. La dernière liste ci-dessus est donc le résultat final du crible d’Ératosthène avec le paramètre \(n=10\). On vérifie que les nombres premiers inférieurs à 10 sont bien \(2\), \(3\), \(5\) et \(7\). La sortie est donc correcte.

a — Fonction range modifiée

On commence par l’implémentation de l’étape 1 :

Compléter la fonction range dans le fichier sieve.cpp. Cette fonction prend en paramètre deux entiers m et n. Elle renvoie le vecteur des entiers compris entre m (inclus) et n (exclu).

Pour m\(=2\) et n\(=11\), la fonction renvoie donc le vecteur avec les éléments \(2\), \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\), \(10\). Si m\(\geq\)n, alors le vecteur renvoyé sera vide.

Vous pouvez prendre votre implémentation de la fonction range de la mini-feuille 1 et la modifier.

b — Supprimer les multiples d’un entier

Nous allons maintenant implémenter une seule itération de l’étape 2.

Compléter la fonction delete_multiples_from dans le fichier sieve.cpp. Cette fonction prend en paramètre (une référence à) un vecteur d’entiers vec et deux entiers from et k. Elle supprime tous les multiples de k du vecteur vec aux indices supérieurs ou égaux à from.

Un appel à cette fonction avec le vecteur vec égal à

6 3 2 4 3 8

et les entiers from\(=3\) et k\(=2\) supprimera les éléments \(4\) et \(8\) de vec. Bien qu’il soit un multiple de k\(=2\), l’élément \(2\) du vecteur n’est pas supprimé car il se trouve à l’indice \(2\) qui n’est pas supérieur ou égal à from\(=3\). Le vecteur après l’appel sera donc égal à :

6 3 2 3

c — Nombres premiers

Nous avons tous les ingrédients pour pouvoir implémenter le crible d’Ératosthène suivant les deux étapes décrites ci-dessus et utilisant les fonctions range et delete_multiples_from.

Compléter la fonction primes dans le fichier sieve.cpp. Cette fonction prend en paramètre un entier n. Elle renvoie le vecteur des nombres premiers inférieurs ou égaux à n.

Exercice 4 (bonus) — Valeur moyenne et médiane d’un vecteur

Dans cet exercice nous allons calculer la moyenne et la médiane d’un vecteur d’entiers. La moyenne d’un vecteur avec les éléments \(x_0,x_1,\dots,x_{n-1}\) est donnée par la formule \[\bar{x} = \frac{x_0+x_1+\cdots+x_{n-1}}{n}.\] La médiane d’un vecteur ordonné \(x_0 \leq x_1 \leq \cdots \leq x_{n-1}\) est une valeur à laquelle la moitie des éléments du vecteur sont inférieurs et la moitie sont supérieurs. Plus précisément, la médiane est donnée par :

Par exemple, la médiane du vecteur

1 2 3 4 5

est l’élément à l’indice \(\frac{n-1}{2} = \frac{5-1}{2} = \frac{4}{2} = 2\), c’est-à-dire \(x_2 = 3\). La médiane du vecteur

1 2 3 4

est la moyenne des éléments aux indices \(\frac{n-2}{2} = \frac{4-2}{2} = \frac{2}{2} = 1\) et \(\frac{n}{2} = \frac{4}{2} = 2\), c’est-à-dire \(\frac{1}{2} x_1 + \frac{1}{2} x_2 = \frac{1}{2} 2 + \frac{1}{2} 3 = 2,5\).

Plus tard dans ce cours nous allons apprendre comment trier un vecteur pour plus directement réduire le cas d’un vecteur non-ordonné à celui d’un vecteur ordonné.

La définition précédente de la médiane suppose un vecteur ordonné. Pour un vecteur non-ordonné, nous définissons sa médiane comme celle de la version ordonnée du vecteur. Il sera nécessaire de calculer, pour chaque élément d’un vecteur non-ordonné, le nombre d’éléments qui sont inférieurs.

Le type invalid_argument fait partie de la librairie standard de C++. Il décrit la situation générale d’une fonction appelée avec un paramètre non valide. On peut lancer une exception de type invalid_argument via throw invalid_argument("message"). Au lieu du string message on peut mettre une description plus précise de l’exception lancée.

Pour un vecteur vide, ni la moyenne ni la médiane est bien définie. Dans ce cas nous allons donc lancer une exception. Nous choisissons le type invalid_argument comme type de l’exception.

a — Valeur moyenne

Avant de traiter le problème plus difficile du calcul de la médiane, nous commençons par le calcul de la valeur moyenne.

Compléter la fonction mean dans le fichier median.cpp. Cette fonction prend en paramètre (une référence constante à) un vecteur d’entiers et retourne la moyenne de ses éléments. Si le vecteur est vide, elle lance une exception de type invalid_argument.

b — Rang d’un entier dans un vecteur

Compléter la fonction rank_of dans le fichier median.cpp. Cette fonction prend en paramètre (une référence constante à) un vecteur d’entiers vec et un entier n. Elle renvoie le nombre d’éléments de vec qui sont inférieurs ou égaux à n.

c — Médiane

Compléter la fonction median dans le fichier median.cpp. Cette fonction prend en paramètre (une référence constante à) un vecteur d’entiers et retourne sa médiane. Si le vecteur est vide, elle lance une exception de type invalid_argument.

Astuce : commencer avec le cas d’un nombre impair d’éléments et utiliser la fonction rank_of pour trouver un élément dont le rang est minimal parmi les rangs strictement supérieurs à \(\frac{n-1}{2}\).

retour au site web du cours