TD.md

exports:
- format: pdf
  output: TD.pdf
  template: ../../template/TD
- format: tex
  output: TDmd.tex
  template: ../../template/TD
jupytext:
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
kernelspec:
  display_name: C++17
  language: C++17
  name: xcpp17

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

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "6314e4b395620d753e384ea7d2402db6", "grade": true, "grade_id": "10", "locked": false, "points": 0, "schema_version": 3, "solution": true}}

% {raw:latex}\enlargethispage{6ex}

::::{admonition} Exercice 1 : Échauffement

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

% {raw:latex}\small :::{literalinclude} tableaux2D.cpp :start-after: BEGIN initialisationTD :end-before: END initialisationTD ::: % {raw:latex}\normalsize % {raw:latex}\vspace{-.1ex}

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

::::

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "e4d5e1c3e449191eea037306bc2f9d69", "grade": true, "grade_id": "20", "locked": false, "points": 0, "schema_version": 3, "solution": true}}

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

Écrivez 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).

% REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

::::

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "83b0cf141a64fbfd9f9926792f38c7c7", "grade": true, "grade_id": "30", "locked": false, "points": 0, "schema_version": 3, "solution": true}}

::::{admonition} 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 suivants, respectivement carré tc, rectangulaire tr ou quelconque tq :

% {raw:latex}\tiny :::{literalinclude} tableaux2Dchar-correction.cpp :start-after: BEGIN init :end-before: END init ::: % {raw:latex}\normalsize % {raw:latex}\vspace{-.1ex}

Pour chaque opération ci-dessous, spécifiez et définissez une fonction qui la réalise (elle prendra en paramètre un tableau t à deux dimensions, et éventuellement d'autres paramètres) :

1. renvoyer le nombre de lignes de t.

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

3. afficher les éléments de la ligne d'indice

   $\ell$
   de t.

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

4. afficher les éléments de la colonne d'indice

   $c$
   de t (supposé rectangulaire).

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % {raw:latex}\small

   Pour          Bravo          Tout
   bien          bonne          va
   rire          ANNEE          mieux 
   lis!

   % {raw:latex}\normalsize % {raw:latex}\vspace{-.1ex}

   % {raw:latex}\footnotesize % % ::::{grid} % % :::{grid-item-card} % | | | | | % |---|---|---|---| % | P | o | u | r | % | b | i | e | n | % | r | i | r | e | % | l | i | s | ! | % ::: % :::{grid-item-card} % | | | | | | % |---|---|---|---|---| % | B | r | a | v | o | % | b | o | n | n | e | % | A | N | N | E | E | % ::: % :::{grid-item-card} % | | | | | | % |---|---|---|---|---| % | T | o | u | t | | % | v | a | | | | % | m | i | e | u | x | % ::: % :::: % % {raw:latex}\normalsize % % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

::::

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "5bea6ec76349fa3c36fdabe0124d7a22", "grade": true, "grade_id": "40", "locked": false, "points": 0, "schema_version": 3, "solution": true}}

::::{admonition} 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 définissez 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$
   .

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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$
   .

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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$
   .

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

::::

% {raw:latex}\clearpage

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "cf9527b044feae83c529ff3762240b0f", "grade": true, "grade_id": "50", "locked": false, "points": 0, "schema_version": 3, "solution": true}}

::::{admonition} 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 :

% {raw:latex}\small :::{literalinclude} occupation-salle.cpp :start-after: BEGIN jours :end-before: END jours ::: % {raw:latex}\normalsize

1. Définissez une fonction qui construit un planning vide.

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

2. Définissez 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).

      % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

      % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

3. Définissez 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.

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

::::

+++ {"deletable": false, "nbgrader": {"cell_type": "markdown", "checksum": "4f1ea1eecfe02e89a8ca3f2bb3a61467", "grade": true, "grade_id": "60", "locked": false, "points": 0, "schema_version": 3, "solution": true}}

::::{admonition} 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. Dans ce jeu, le joueur doit localiser des mines cachées dans un champ virtuel avec pour seule indication le nombre de mines dans les zones adjacentes. 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, le joueur 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.

Le joueur 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 :

:::{literalinclude} demineur.cpp :start-after: BEGIN GrilleDemineur :end-before: END GrilleDemineur :::

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

3. Définissez une fonction permettant de tester si une grille est gagnante.

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE

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

   % REMPLACEZ CETTE LIGNE PAR VOTRE RÉPONSE ::::