Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
---
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
::::