Correction 8
Tableaux dynamiques
Par ailleurs, les solutions proposées correspondent à l'état de vos connaissances au moment où la série est abordée. D'autres solutions pourront être envisagées une fois de nouveaux concepts acquis.
| Exercice 1 | Exercice 2 | Exercice 3 | Exercice 4 | Exercice 5 |
Exercice 1 : échauffement avec les tableaux dynamiques
A)
Le code fourni remplit le vecteur tab (de taille 10) d'éléments allant de
0 à 9.
En effet, push_back ajoute un élément à la fin
du tableau. Au moment de l'ajout tab.size() vaut
la taille du vecteur avant l'ajout (puisque l'élément
n'est pas encore ajouté).
Vérification : Le code suivant :
for (int i(0); i < tab.size(); ++i) cout << tab[i] << endl;
ou comme ceci (depuis C++11) :
for (auto x : tab) cout << x << endl;
affiche(nt) :
0 1 2 3 4 5 6 7 8 9
B)
Ajoute à la fin de tab2 un vecteur de même taille que le
vecteur tab et contenant que des éléments de même
valeur : la valeur du premier élément de tab.
Dans le cas où tab2 est un tableau vide
(et dans ce cas seulement), on pourrait aussi faire :
vector<int> tab2(tab.size(), tab[0]);
Exercice 2 : produit scalaire
Nous savons depuis la semaine passée qu'il ne faut jamais faire de copier-coller dans du code, mais faire des fonctions ! C'est par exemple le cas ici pour la saisie des vecteurs (cet aspect est optionnel, mais c'est bien d'y penser !).
#include <iostream>
#include <vector>
#include <string>
using namespace std;
double scalaire(vector<double> u, vector<double> v);
void saisie(const string& titre, vector<double>& vecteur);
constexpr size_t N_MAX(100);
int main()
{
size_t n;
do {
cout << "Quelle taille pour les vecteurs ? ";
cin >> n;
} while(n < 1 or n > N_MAX);
vector<double> v1(n);
vector<double> v2(n);
saisie("premier", v1);
saisie("second", v2);
cout << "Le produit scalaire de v1 par v2 vaut "
<< scalaire(v1, v2) << endl;
return 0;
}
// --------------------------------------------------------
double scalaire(vector<double> u, vector<double> v)
{
double somme(0.0);
for (size_t i(0); i < u.size(); ++i) {
somme += u[i] * v[i];
}
return somme;
}
// --------------------------------------------------------
void saisie(const string& titre, vector<double>& vecteur)
{
cout << "Saisie du " << titre << " vecteur :" << endl;
for (size_t i(0); i < vecteur.size(); ++i) {
cout << " coordonnée " << i+1 << " = ";
cin >> vecteur[i];
}
}
Exercice 3 : multiplication de matrices
Le code fourni ici est en C++11. Pour une version compilant avec l'ancien standard (C++98) voir ci-dessous. Voici une version possible du corrigé (voir aussi les commentaires en fin de corrigé pour des aspects plus avancés.)
#include <iostream>
#include <vector>
using namespace std;
// Définition d'un type synonyme (alias)
/* remarquez que par rapport à la version C++98 *
* on a le droit d'écrire: vector < vector<double>> *
* au lieu de vector < vector<double> > (plus besoin de *
* séparer les deux symboles > par un espace ) */
typedef vector < vector<double>> Matrice;
Matrice lire_matrice();
void affiche_matrice(const Matrice& M);
Matrice multiplication(const Matrice& M1, const Matrice& M2);
// ----------------------------------------------------------------------
int main()
{
Matrice M1(lire_matrice()), M2(lire_matrice());
if (M1[0].size() != M2.size())
cout << "Multiplication de matrices impossible !" << endl;
else {
cout << "Résultat :" << endl;
affiche_matrice(multiplication(M1, M2));
}
return 0;
}
// ----------------------------------------------------------------------
Matrice lire_matrice()
{
cout << "Saisie d'une matrice :" << endl;
size_t lignes;
do {
cout << " Nombre de lignes : " << flush;
cin >> lignes;
} while (lignes < 1);
size_t colonnes;
do {
cout << " Nombre de colonnes : " << flush;
cin >> colonnes;
} while (colonnes < 1);
Matrice M(lignes, vector<double>(colonnes));
for (size_t i(0); i < lignes; ++i)
for (size_t j(0); j < colonnes; ++j) {
cout << " M[" << i+1 << "," << j+1 << "]=" << flush;
cin >> M[i][j];
}
return M;
}
// ----------------------------------------------------------------------
Matrice multiplication(const Matrice& M1,
const Matrice& M2)
{
Matrice prod(M1.size(), vector<double>(M2[0].size()));
for (size_t i(0); i < M1.size(); ++i)
for (size_t j(0); j < M2[0].size(); ++j) {
prod[i][j] = 0.0;
for (size_t k(0); k < M2.size(); k++)
prod[i][j] += M1[i][k] * M2[k][j];
}
return prod;
}
/* Amélioration possible : stocker le résultats des appels à la fonction *
* size dans des variables locales (pour éviter de ré-invoquer la fonction *
* plusieurs fois)*/
// ----------------------------------------------------------------------
void affiche_matrice(const Matrice& M)
{
// On aurait aussi pu utiliser auto dans les boucles
// des autres fonctions
for (auto ligne : M) {
for (auto element : ligne) {
cout << element << " ";
}
cout << endl;
}
}
Version C++98
#include <iostream>
#include <vector>
using namespace std;
// Définition d'un type synonyme (alias)
typedef vector < vector<double> > Matrice;
Matrice lire_matrice();
void affiche_matrice(const Matrice& M);
Matrice multiplication(const Matrice& M1,
const Matrice& M2);
// ----------------------------------------------------------------------
int main()
{
Matrice M1(lire_matrice()), M2(lire_matrice());
if (M1[0].size() != M2.size())
cout << "Multiplication de matrices impossible !" << endl;
else {
cout << "Résultat :" << endl;
affiche_matrice(multiplication(M1, M2));
}
return 0;
}
// ----------------------------------------------------------------------
Matrice lire_matrice()
{
cout << "Saisie d'une matrice :" << endl;
size_t lignes;
do {
cout << " Nombre de lignes : " << flush;
cin >> lignes;
} while (lignes < 1);
size_t colonnes;
do {
cout << " Nombre de colonnes : " << flush;
cin >> colonnes;
} while (colonnes < 1);
Matrice M(lignes, vector<double>(colonnes));
for (size_t i(0); i < lignes; ++i)
for (size_t j(0); j < colonnes; ++j) {
cout << " M[" << i+1 << "," << j+1 << "]=" << flush;
cin >> M[i][j];
}
return M;
}
// ----------------------------------------------------------------------
Matrice multiplication(const Matrice& M1,
const Matrice& M2)
{
Matrice prod(M1.size(), vector<double>(M2[0].size()));
for (size_t i(0); i < M1.size(); ++i)
for (size_t j(0); j < M2[0].size(); ++j) {
prod[i][j] = 0.0;
for (size_t k(0); k < M2.size(); k++)
prod[i][j] += M1[i][k] * M2[k][j];
}
return prod;
}
/* Amélioration possible : stocker le résultats des appels à la fonction *
* size dans des variables locales (pour éviter de ré-invoquer la fonction *
* plusieurs fois)*/
// ----------------------------------------------------------------------
void affiche_matrice(const Matrice& M)
{
for (size_t i(0); i < M.size(); ++i) {
for (size_t j(0); j < M[i].size(); ++j)
cout << M[i][j] << " ";
cout << endl;
}
}
Commentaires
Nous avons avec cet exercice une belle illustration des progrès introduits dans C++11. En C++98, le code fourni produit en effet plusieurs copies inutiles : les fonctions lire_matrice et multiplication créent leur propre Matrice, laquelle est recopiée en sortie (échange de l'information entre le return de la fonction et son appel). Il y a donc à chaque fois deux Matrices : celle de l'instruction qui fait l'appel et celle de la valeur de retour de la fonction appellé. Cela est inutile et coûteux (surtout si les matrices sont de grande taille).
Une solution pour éviter cette duplication des Matrices est, en C++98, d'utiliser les pointeurs.
Tout ceci n'est plus nécessaire en C++11. Cette nouvelle version du langage introduit en effet la notion de «sémantique de déplacement» (move semantics), laquelle permet entre autres au compilateur, avec le MÊME code d'éviter ces copies (techniquement c'est parce que les vector ont maintenant un «constructeur de déplacement» (move constructor)). Cela permet aux programmeurs d'écrire des codes plus efficaces, sans avoir rien de particulier à faire !
Vous pouvez même expliciter cette optimisation (mais ce n'est pas nécessaire, le compilateur devrait pouvoir le faire pour vous), en transformant M1 et M2 en des «références vers des transitoires» (r-value refences).
const Matrice&& M1(lire_matrice()), M2(lire_matrice()); // Notez le symbole && (et c'est tout !!) Cela impose que les seules matrices existant dans tout le programme soient
celles crées dans les deux appels de lire_matrice et celle résultant de la multiplication. Plus aucune copie inutile supplémentaire...
Vive la move semantics !
![[avancé !]](../pict/3gears.gif)
Arcanes de la move semantics
Profitons-en pour pousser encore un peu plus loin pour
ceux que cela intéresse (mais cela est vraiment avancé, hors des
objectifs du cours) : peut on encore faire mieux et ne pas
introduire la 3e matrice (le résultat de la multiplication)
?
La réponse serait «oui» avec un autre algorithme pour le calcul de la multiplication permettant le calcul «sur place». Dans le cas de la multiplication matricielle, ce calcul est inutilement complexe pour illustrer notre propos. Nous allons simplifier en prenant le cas de l'addition matricielle : l'idée de faire l'addition «sur place» est de calculer le résultat de A+B dans A lui-même (ou dans B), sans utiliser une troisième matrice pour stocker le résultat.
Peut-on coder cela en C++ ? i.e. éviter de créer une 3e Matrice ? La réponse est «oui» en C++11.
Il faut pour cela tout d'abord se rendre compte qu'on ne peut le faire que si A ou B sont des «transitoires» (r-value reference). En effet si A et B sont des «vraies données» (= des variables, l-values en termes techniques) alors on est obligé de créer une 3e Matrice car on ne peut (souhaite) pas toucher à A ni à B. Il faut donc expliciter le cas où A ou B, ou les deux, sont des r-value references. Cela nous conduit aux quatres prototypes suivants :
// deux données stockées, à préserver Matrice addition(const Matrice& M1 , const Matrice& M2); // M1 "transitoire", M2 "à préserver" Matrice&& addition(Matrice&& M1 , const Matrice& M2); // M2 "transitoire", M1 "à préserver" Matrice&& addition(const Matrice& M1, Matrice&& M2 ); // deux "transitoires" Matrice&& addition(Matrice&& M1 , Matrice&& M2 );
Cependant, il est clair qu'on ne vas pas écrire quatre fois l'addition !! (jamais de copier-coller !) Comment faire ?
Commençons par choisir un cas de référence, par exemple lorsque M1 est transitoire. Que faut-il faire alors ?
Simplement faire l'addition dans M1 et retransmettre M1 plus loin, toujours en tant que transitoire.
Il y a ici encore une subtilité : il faut savoir qu'une r-value
reference nommée (par exemple en argument de fonction) devient
une
Cela nous donne donc :
/* -------------------------------------------------------------------- *
* Cas ou M1 est un temporaire. *
* On code ici la "vraie" addition et on utilisera cette version dans *
* les autres cas. *
* Note : on suppose ici que M1 et M2 sont de même taille. Dans un *
* programme plus complet, il faudrait bien sûr s'en assurer ! */
Matrice&& addition(Matrice&& M1, const Matrice& M2)
{
for (size_t i(0); i < M1.size(); ++i)
for (size_t j(0); j < M1[i].size(); ++j)
M1[i][j] += M2[i][j];
return move(M1);
}
Reste maintenant à utiliser cette addition de référence pour écrire les autres (sans duplication de code).
Le plus simple est sûrement lorsque B est transitoire et A non : il suffit d'inverser ! Attention cependant à ne pas oublier la conversion automatique d'une r-value reference nommée en l-value reference !!
Pour le cas où les deux sont des transitoires : il suffit d'en déplacer une...
Le cas le plus compliqué pour réutiliser l'addition déjà écrite sans la réécrire est peut être le cas où A et B sont des l-values. Dans ce cas, il est nécessaire d'introduire une 3e Matrice pour ne pas les écraser. L'idée est alors simplement d'introduire cette 3e Matrice, d'y recopier l'une des deux autres (e.g. A) puis de la «déplacer» dans l'appel de notre addition de référence.
Tout ceci conduit au code suivant :
// --------------------------------------------------------------------
Matrice&& addition(const Matrice& M1, Matrice&& M2)
{
return addition(move(M2), M1);
}
// --------------------------------------------------------------------
Matrice&& addition(Matrice&& M1, Matrice&& M2)
{
return addition(move(M1), M2);
}
// --------------------------------------------------------------------
Matrice addition(const Matrice& M1, const Matrice& M2)
{
Matrice resultat(M1); // copie M1 dans resultat pour...
return addition(move(resultat), M2); // ...utiliser la version r-value
}
Voilà ! ceci termine le commentaire avancé sur les arcanes de la «move semantic».
En conclusion, ce qu'il faut peut être retenir de tout ceci est que l'utilisation de ce concept et des r-value references n'est vraiment que pour de l'optimisation et qu'il vaut peut être mieux dans un premier temps ne pas y toucher explicitement mais se contenter d'utiliser ce qu'elle apporte déjà dans le langage de base (cf commentaires précédents).
Exercice 4 : Crible d'Ératosthène
La meilleure technique pour résoudre cet exercice consiste à
se servir d'un tableau de bool, initialisé à
false. On parcourt ensuite le tableau en enlevant (c'est-à-dire en
mettant à true) les multiples des nombres premiers.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<bool> supprimes(100,false); // array<bool,100> serait une bonne option
supprimes[0] = true; // 0 n'est pas premier
supprimes[1] = true; // 1 n'est pas premier
for(size_t i(2); i < supprimes.size(); ++i) {
if (not supprimes[i]) {
size_t multiple(2 * i);
while (multiple < supprimes.size()) {
supprimes[multiple] = true;
multiple = multiple + i;
}
}
}
for(size_t i(0); i < supprimes.size(); ++i) {
if (not supprimes[i]) {
cout << i << " ";
}
}
cout << endl;
return 0;
}
Exercice 5 : Comparaison de tris
Tri bulles
#include <iostream>
#include <vector>
#include <utility> // pour swap
using namespace std;
typedef int type_el;
typedef vector<type_el> Tableau;
void affiche(const Tableau& tab)
{
for (auto el : tab) cout << el << " ";
}
void tri_bulle(Tableau& tab)
{
const size_t k(tab.size()-1);
for (size_t i(0); i < k; ++i) {
for (size_t j(k); j > i; --j) {
if (tab[j-1] > tab[j]) {
swap(tab[j-1], tab[j]);
// affiche(tab);
}
}
}
}
int main()
{
Tableau tab = { 3, 5, 12, -1, 215, -2, 17, 8, 3,
5, 13, 18, 23, 5, 4, 3, 2, 1
};
cout << "A trier : ";
affiche(tab);
cout << endl;
tri_bulle(tab);
cout << "Résultat : ";
affiche(tab);
cout << endl;
return 0;
}
Tri de Shell
#include <iostream>
#include <vector>
#include <utility> // pour swap
using namespace std;
typedef int type_el;
typedef vector<type_el> Tableau;
void affiche(const Tableau& tab)
{
for (auto el : tab) cout << el << " ";
}
void tri_Shell(Tableau& tab)
{
for (size_t k(tab.size()/2); k >= 1; k /= 2)
for (size_t i(k+1); i <= tab.size(); ++i) {
int j(i-k);
while (j > 0) {
if (tab[j-1] > tab[j+k-1]) {
swap(tab[j-1], tab[j+k-1]);
affiche(tab);
cout << endl;
j -= k;
} else {
j = 0;
}
}
}
}
int main()
{
Tableau tab = { 3, 5, 12, -1, 215, -2, 17, 8, 3,
5, 13, 18, 23, 5, 4, 3, 2, 1
};
tab = { 5, 4, 1, 2, 3 };
cout << "A trier : ";
affiche(tab);
cout << endl;
tri_Shell(tab);
cout << "Résultat : ";
affiche(tab);
cout << endl;
return 0;
}
Dernière mise à jour : $Date: 2025/10/29 11:50 $