TD 7 : Tableaux à deux dimensions (tableaux 2D)#

Exercice 1 : Échauffement

On considère le tableau d’entiers à deux dimensions suivant :

vector<vector<int>> t={{7, -1, 4, 3}, {15, 11, 17, 12}, {20, 34, 42, 25}};

  1. Quelles sont les valeurs t[0][0], t[0][1], t[2][3] ?

  2. Donnez le nombre de lignes et de colonnes du tableau t.

Exercice 2 : Déclaration, allocation et initialisation de tableau 2D

Écrire un fragment de programme qui construit un tableau 2D résultat de L lignes et C colonnes et qui l’initialise avec un entier v dans chaque case (on supposera L, C et v prédéfinis).

Exercice 3 : Opérations sur tableaux à deux dimensions

Dans cet exercice on considère des tableaux de caractères à deux dimensions. Par exemple l’un des tableaux respectivement carré tc, rectangulaire tr ou quelconque tq définis comme suit :

vector<vector<char>> tc = { {'P','o','u','r'}, {'b','i','e','n'}, {'r','i','r','e'}, {'l','i','s','!'} };   
vector<vector<char>> tr = { {'B','r','a','v','o'}, {'b','o','n','n','e'}, {'A','N','N','E','E'}        };
vector<vector<char>> tq = { {'T','o','u','t'}, {'v','a'}, {'m','i','e','u','x'}                        };

Pour chaque opération ci-dessous, spécifiez et implantez une fonction qui la réalise (ces fonctions prendront en paramètre un tableau à deux dimensions t, et éventuellement d’autres paramètres) :

  1. renvoyer le nombre de lignes de t.

  2. renvoyer le nombre de colonnes de t (supposé rectangulaire).

  3. afficher les éléments de la ligne d’indice \(\ell\) de t.

  4. afficher les éléments de la colonne d’indice \(c\) de t (supposé rectangulaire).

  5. afficher les éléments de la diagonale de t (supposé carré).

  6. afficher les éléments de t; pour t=tc, tr et tq, les affichages seraient respectivement :

    Pour          Bravo          Tout
bien          bonne          va
rire          ANNEE          mieux 
lis!

  7. indiquer si oui ou non, t contient le caractère c.

Exercice 4 : Matrices

Pour être plus spécifique et éviter d’avoir à écrire vector<vector<int>> à tout bout de champ, on peut définir un raccourci. Dans les questions suivantes, qui traitent de matrices, on utilisera par exemple le raccourci suivant :

using Matrice = vector<vector<int>>;

Les deux constructions suivantes sont alors totalement équivalentes :

vector<vector<int>> tab = { {1,2,3}, {4,5,6}, {7,8,9} };
Matrice tab = { {1,2,3}, {4,5,6}, {7,8,9} };

Spécifiez et implantez une fonction pour chacune des questions suivantes :

  1. teste si un tableau carré est symétrique, i.e. si \(T_{i, j} = T_{j, i}\) pour tous \(i\) et \(j\).

  2. \(\clubsuit\) teste si une matrice est carrée et symétrique.

  3. calcule la somme de deux matrices (supposées de mêmes dimensions). On vous rappelle que la somme de deux matrices \(T\) et \(T'\) est une matrice \(C\), où \(C_{i,j}=T_{i,j}+T'_{i,j}\) pour tous \(i\) et \(j\).

  4. \(\clubsuit\) calcule le produit de deux matrices. On vous rappelle que le produit de deux matrices \(T\) et \(T'\) est une matrice \(C\), où \(C_{i,j}=T_{i,1}T'_{1,j}+ T_{i,2}T'_{2,j} + \cdots\).

Exercice 5 : Réservation de salle

Une salle de réunion peut être utilisée par les employés d’une entreprise. La réservation se fait par plages d’une heure, de 8h00 à 19h00, chaque plage horaire commençant à l’heure pile; par exemple, il y a une plage 9h00-10h00 mais il n’y a pas de plage 9h15-10h15. Le planning hebdomadaire de la salle est modélisé par un tableau de booléens à deux dimensions: cinq lignes correspondant aux cinq jours de la semaine, onze colonnes correspondant aux onze plages horaires de la journée. La valeur pour un jour et une plage horaire donnée est true si la salle est réservée sur cette plage horaire, et false si elle est libre. On suppose pour la suite de l’exercice avoir accès au tableau suivant :

vector<string> jours = {"lundi", "mardi", "mercredi", "jeudi", "vendredi"};

  1. Écrivez une fonction qui construit un planning vide.

  2. Écrivez une fonction qui prend en paramètre le planning de réservation d’une salle et qui l’affiche de façon intelligible :

    1. avec des phrases (par exemple : salle réservée le mardi de 9h00 à 10h00).

    2. \(\clubsuit\) sous la forme d’une grille jour / plage horaire, où le mot «Réservée» figure dans les cases concernées.

  3. Écrivez une fonction, avec son test, qui calcule le taux d’occupation d’une salle, c’est à dire le nombre de plages réservées divisé par le nombre total de plages.

Exercice 6 : \(\clubsuit\) Le jeu du démineur

L’objectif de cet exercice est de réaliser une version simple du jeu du «démineur». Le but est de localiser des mines cachées dans un champ virtuel avec pour seule indication le nombre de mines dans les zones adjacentes.

Plus précisément, le champ consiste en une grille rectangulaire dont chaque case contient ou non une mine. Au départ, le contenu de chaque case est masqué. À chaque étape, l’utilisateur peut :

  • Démasquer le contenu d’une case; s’il y a une mine, « BOUM! », il a perdu. Sinon, le nombre de cases adjacentes (y compris en diagonale) contenant une mine est affiché.

  • Marquer une case, s’il pense qu’elle contient une mine.

L’utilisateur a gagné lorsqu’il a démasqué toutes les cases ne contenant pas de mine.

Pour représenter en mémoire l’état interne de la grille, on utilisera un tableau à deux dimensions de caractères (type vector<vector<char>>). On utilisera les conventions suivantes pour représenter l’état d’une case :

  • “m”: présence d’une mine, “M”: présence d’une mine, case marquée;

  • “o”: absence de mine, “O”: absence de mine, case marquée;

  • “ “: absence de mine, case démasquée.

Afin d’éviter d’avoir à écrire vector<vector<char>> à tout bout de champ on utilise un raccourci :

using GrilleDemineur = vector<vector<char>>; // tableau 2D de caractères

  1. Implantez une fonction permettant de compter le nombre total de mines (marquées ou pas) dans une grille.

  2. Implantez une fonction permettant de tirer au hasard une grille initiale. On supposera fournie une fonction bool boolAleatoire() renvoyant un booléen tiré au hasard.

  3. Implantez une fonction permettant de tester si une grille est gagnante.

  4. Implantez une fonction permettant de compter le nombre de mines dans les cases adjacentes à une case donnée d’une grille.

  5. Implantez une fonction permettant de renvoyer une chaîne de caractères représentant la grille telle que doit la voir le joueur.