Série 7
Tableaux
But
Cette série a pour but de vous faire pratiquer les tableaux dynamiques et de tailles fixes (vector et array).
Préliminaires :
Les fichiers de cette série devront se trouver dans le répertoire ~/myfiles/cpp/serie07. Si ce n'est pas déjà fait, créez un sous-répertoire serie07 dans le répertoire ~/myfiles/cpp.
Exercice 0 : Manipulation d'un tableau dynamique (niveau 0)
Le but de cet exercice est d'illustrer l'utilisation d'un tableau dynamique.
Cliquez ici si vous voulez faire cet exercice.
Exercice 1 : Échauffement avec les tableaux dynamiques (niveau 1)
(exercice n°18, pages 56 et 220, dans la 2e édition).
Rappel : Pour utiliser le type vector, il faut inclure la librairie définissant ce type, au moyen de la directive :
#include <vector>
En vous aidant si nécessaire d'un programme, répondez aux questions suivantes :
A : Quelles valeurs contient le tableau tab après l'exècution des lignes suivantes ? Expliquez.
int const taille(10); vector<int> tab; for (unsigned int i(0); i < taille; ++i) { tab.push_back(tab.size()); }
B : Que fait la fonction f suivante ?
void f(vector<int>& tab, vector<int>& tab2) { for (int i(0); i < tab.size(); ++i) { tab2.push_back(tab[0]); } }
Exercice 2 : Produit scalaire (tableaux dynamiques, niveau 1)
(dans la 2e édition : exercice n°17 (pages 55 et 218) : version C++98, tableau à la C
ici: vector de C++11).
Écrivez un programme scalaire.cc qui calcule le produit scalaire de deux vecteurs, implémenté au moyen de tableaux dynamiques.
Votre programme devra utiliser (entre autres) les éléments suivants :
- deux variables de type tableau dynamique de réels ;
- une fonction qui calcule le produit scalaire : double scalaire(vector<double> u, vector<double> v);
- demander à l'utilisateur d'entrer n, la taille effective des vecteurs.
- demander à l'utilisateur les composantes (v10... v1n-1 , v20 ... v2n-1) des vecteurs v1 et v2.
- appeler la fonction scalaire(...) pour calculer le produit scalaire de v1 et v2.
- afficher le résultat.
Rappel :
Le produit scalaire de a par b est: a.b =
a1*b1 + a2*b2 + ... +
an*bn
Exemple: a = (5, 3, -1) b = (2, 1, 2) a.b = 11
Exercice 3 : Multiplication de matrices (tableaux dynamiques, niveau 2)
(pages 57 et 221 dans la 2e édition).
On cherche ici à écrire un programme mulmat.cc qui calcule la multiplication de deux matrices (rappel ci-dessous).
Vous utiliserez pour représenter la matrice un vecteur de vecteurs de doubles.
Déclarations :
- dans main(), déclarez deux matrices M1 et M2.
Fonctions :
la fonction de prototype
vector<vector<double>> lire_matrice();
- la fonction de prototype
vector<vector<double>> multiplication(const vector<vector<double>>& Mat1, const vector<vector<double>>& Mat2);
- la fonction de prototype
void affiche_matrice(const vector<vector<double>> M);
Méthode :
- lire depuis le clavier les dimensions l1 (nombre de lignes) et c1 (nombre de colonnes) de la première matrice M1
- lire le contenu de M1.
- De même, lire les dimensions puis le contenu de la seconde matrice M2.
- Vérifier que le nombre de lignes de M2 est identique au
nombre de colonnes de M1.
Dans le cas contraire, afficher un message d'erreur «Multiplication de matrices impossible !». - Effectuer la mutliplication des matrices : M = M1*M2 :
- Les dimensions de M sont : l1 (nombre de lignes) et c2 (nombre de colonnes).
-
l'élément Mi,j est défini par
- afficher le résultat ligne par ligne.
Exemple d'utilisation :
Saisie d'une matrice : Nombre de lignes : 2 Nombre de colonnes : 3 M[1,1]=1 M[1,2]=2 M[1,3]=3 M[2,1]=4 M[2,2]=5 M[2,3]=6 Saisie d'une matrice : Nombre de lignes : 3 Nombre de colonnes : 4 M[1,1]=1 M[1,2]=2 M[1,3]=3 M[1,4]=4 M[2,1]=5 M[2,2]=6 M[2,3]=7 M[2,4]=8 M[3,1]=9 M[3,2]=0 M[3,3]=1 M[3,4]=2 Résultat : 38 14 20 26 83 38 53 68
Exercice 4 : Crible d'Ératosthène (niveau 2)
Un nombre est dit premier s'il admet exactement 2 diviseurs distincts (1 et lui-même). 1 n'est donc pas premier.
Le crible d'Ératosthène est une méthode de recherche des nombres premiers plus petits qu'un entier naturel n donné. Cette méthode est simple:
- On commence par supprimer tous les multiples de 2 inférieurs à n.
- L'entier 3 n'a pas été supprimé et il ne peut être multiple des entiers qui le précèdent, sinon on l'aurait supprimé; il est donc premier. Supprimons alors tous les multiples de 3 inférieurs à n.
- L'entier 5 n'a pas été supprimé, il est donc premier. Supprimons tous les multiples de 5 inférieurs à n.
- Et ainsi de suite jusque n. Les valeurs n'ayant pas été supprimées sont les nombres premiers plus petits que n.
Écrivez le code qui applique cette méthode pour trouver les nombres premiers inférieurs à 100. Vous devez trouver: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
On utilisera un tableau de booléens :
// tableau des éléments supprimés // supprimes[i] vaut true si i est supprimé (pas premier) array<bool, 100> supprimes;
Exercice 5 : Placement sans recouvrement (tableaux, niveau 2)
(pages 59 et 223 dans la 2e édition).
Le but de cet exercice est de placer sans recouvrement des objets rectilignes sur une grille carrée. Cela pourrait être par exemple une partie d'un programme de bataille navale.
Dans le fichier recouvrement.cc :
-
Définissez une constante globale entière non-signée, nommée DIM et de valeur 10. Elle représentera la taille de la grille (carrée).
-
Prototypez et écrivez une fonction :
bool remplitGrille(array<array<bool, DIM>, DIM>& grille, unsigned int ligne, unsigned int colonne, char direction, unsigned int longueur);
Si le placement est possible, la fonction devra de plus effectuer ce placement (voir ci-dessous la description de la grille).La fonction devra indiquer (par la valeur de retour) si le placement a pu être réalisé ou non.
- Dans le main()
-
Définissez une variable nommée grille,
de type array<array<bool, DIM>, DIM>.
La valeur true dans une case [i][j] de cette grille représente le fait qu'un (bout d')objet occupe la case de coordonnées (i, j). - Utilisez la fonction précédente
pour remplir interactivement la grille, en
demandant à l'utilisateur de spécifier la position, la taille et la
direction des objets à placer.
Indiquez à chaque fois à l'utilisateur si l'élément a pu ou non être placé dans la grille.
Le remplissage se termine lorsque l'utilisateur entre une position/coordonnée strictement inférieure à 0. - Terminer alors en "dessinant" la grille : afficher un '.' si la case est vide et un '#' si la case est occupée.
-
Définissez une variable nommée grille,
de type array<array<bool, DIM>, DIM>.
- Dans l'interface utilisateur, pour indiquer les positions, utilisez au choix soit les coordonnées du C++ : 0 à DIM-1 (plus facile), soit les coordonnées usuelles (1 à DIM, un peu plus difficile) , MAIS dans tous les cas utilisez les indices de 0 à DIM-1 pour votre tableau (aspect programmeur).
- Pensez à effectuer des tests de validité sur les valeurs entrées (débordement du tableau).
- pour représenter la direction, vous pouvez soit utiliser un caractère ('N' pour nord. 'S' pour sud, etc..., plus facile), soit un type enuméré (plus difficile : pensez à l'interface avec l'utilisateur).
- N'oubliez pas d'initialiser la grille en tout début de programme !
Exemple de fonctionnement (version facile : coordonées de 0 à 9 et lettres pour les directions) :
Entrez coord. x: 2 Entrez coord. y: 8 Entrez direction (N,S,E,O): E Entrez taille: 2 Placement en (2,8) direction E longueur 2 -> succès Entrez coord. x: 0 Entrez coord. y: 8 Entrez direction (N,S,E,O): S Entrez taille: 5 Placement en (0,8) direction S longueur 5 -> ECHEC Entrez coord. x: 0 Entrez coord. y: 9 Entrez direction (N,S,E,O): O Entrez taille: 5 Placement en (0,9) direction O longueur 5 -> succès Entrez coord. x: -1
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
---|---|---|---|---|---|---|---|---|---|---|
0 | ||||||||||
1 | ||||||||||
2 | ||||||||||
3 | ||||||||||
4 | ||||||||||
5 | ||||||||||
6 | ||||||||||
7 | ||||||||||
8 | ||||||||||
9 |
Exercice 6 : Devoir 4 du MOOC (continuation)
Les devoirs du MOOC, même s'il ne sont pas notés pour vous, sont un bon moyen de vous entraîner aussi. Vous pouvez les soumettre à un correcteur automatique (autant de fois que vous le souhaitez) et recevoir un feedback. Vous pouvez continuer à programmer le devoir de la semaine 4 pour vous entraîner à l'utilisation de fonctions.