Problème: carré magique#
Un carré magique est une grille carrée contenant des entiers telle que la somme de chaque ligne, de chaque colonne et de chaque diagonale ait la même valeur. Un carré magique de \(n\) lignes est dit normal s’il contient chaque entier compris entre \(1\) et \(n^2\) exactement une fois. Par exemple, le tableau suivant est un carré magique normal:
Dans la suite de l’exercice, il s’agit d’écrire étape par étape les
fonctions utiles pour tester si un tableau bidimensionnel est un carré
magique normal. Vous pouvez utiliser les fonctions des étapes
précédentes, même si vous ne les avez pas implantées. Pour alléger les
notations, on définit un raccourci Grille pour les tableaux
bidimensionnels d’entiers:
using Grille = vector<vector<int>>;
Dans les tests, on pourra supposer que l’on a à disposition la variable suivante:
Grille carreMagique = { { 6, 7, 2}, {1, 5, 9}, {8, 3, 4} };
Définissez deux autres variables appelées carre et rectangle contenant des tableaux d’entiers à
deux dimensions tels que :
carresoit une grille carrée 3x3 qui n’est pas un carré magiquerectanglesoit un tableau deux dimensions qui n’est pas un carré (le nombre de colonne est différent du nombre de lignes)
/// BEGIN SOLUTION
Grille carre = { { 6, 7, 2}, {1, 6, 9}, {8, 3, 4} };
Grille rectangle = { { 6, 7}, {1, 6}, {8, 3} };
/// END SOLUTION
On considère la fonction estCarre documentée ci-dessous.
/** renvoie si un tableau à 2 dimensions est un carré
* @param g de type Grille
* @return true si toutes les lignes ont le même nombre de colonnes qui
* est égal au nombre de ligne, false sinon
**/
Proposez quatre tests pour cette fonction (en utilisant CHECK) sur
les trois variables carreMagique, carre, rectangle ainsi que sur
la variable triangle définie ci-dessous :
Grille triangle = {{1,2,4},{3,5},{2}};
/// BEGIN SOLUTION
CHECK( estCarre(carreMagique) );
CHECK( estCarre(carre) );
CHECK( not estCarre(rectangle) );
CHECK( not estCarre(triangle) );
/// END SOLUTION
La définition ci-dessous de estCarre est erronée. Annotez les tests
ci-dessus pour indiquer lesquels ne passent pas, puis annotez la
définition ci-dessous pour indiquer comment la corriger.
bool estCarre(Grille g) {
for ( int i = 0 ; i < g.size() ; i++ ) {
if ( g[i].size() != g.size() ) {
return false;
} else {
return true;
}
}
}
Définissez une fonction sommeColonne qui prend en paramètres un entier
\(c\) et une grille et qui renvoie la somme des éléments de la \(c\)-ième
colonne de la grille. Par exemple, l’appel sur l’exemple
sommeColonne(carreMagique, 1) renvoie \(7+5+3=15\). On supposera que le numéro de colonne est un indice valide.
Dans la suite, on supposera que l’on dispose aussi d’une fonction
sommeLigne analogue.
/// BEGIN SOLUTION
int sommeColonne(Grille g, int c) {
int somme = 0;
for (int i = 0 ; i < g.size() ; i++)
somme = somme + g[i][c];
return somme;
}
/// END SOLUTION
Spécifiez et définissez une fonction sommeDiagonaleMajeure qui prend
en paramètre une grille carrée et renvoie la somme des éléments de la
diagonale majeure de la grille (la diagonale majeure est celle qui
commence en haut à gauche et termine en bas à droite; dans l’exemple
ci-dessus, elle contient 6, 5 et 4).
/// BEGIN SOLUTION
/** renvoie la somme des éléments de la diagonale majeure d'une grille
* @param g de type Grille
* @return la somme des éléments de la diagonale majeure de g
**/
int sommeDiagonaleMajeure(Grille g) {
int somme = 0;
for (int i = 0 ; i < g.size() ; i++)
somme = somme + g[i][i];
return somme;
}
/// END SOLUTION
On suppose que l’on dispose d’une fonction sommeDiagonaleMineure qui
prend en paramètre une grille carrée et renvoie la somme des éléments
de la diagonale mineure de la grille (la diagonale mineure est celle
qui commence en bas à gauche et termine en haut à droite; dans
l’exemple ci-dessus, elle contient 8, 5 et 2). Écrivez un test pour la
fonction sommeDiagonaleMineure (ne pas écrire la fonction, seulement
le test).
/// BEGIN SOLUTION
CHECK( sommeDiagonaleMineure(carreMagique) == 15 );
/// END SOLUTION
Définissez une fonction estCarreMagique qui prend en paramètre une
grille, et renvoie true s’il s’agit d’un carré magique (pas
forcément normal), false sinon comme dans les tests proposés.
bool estCarreMagique(Grille g) {
/// BEGIN SOLUTION
int somme = sommeLigne(g, 0);
if ( not estCarre(g) )
return false;
for ( int i = 0 ; i < g.size() ; i++ )
if ( somme != sommeLigne(g, i) or somme != sommeColonne(g, i) )
return false;
if ( somme != sommeDiagonaleMajeure(g) or somme != sommeDiagonaleMineure(g) )
return false;
return true;
/// END SOLUTION
}
CHECK( estCarreMagique(carreMagique) );
CHECK( not estCarreMagique(carre) );
CHECK( not estCarreMagique(rectangle) );
CHECK( not estCarreMagique(triangle) );
\(\clubsuit\) On a défini la fonction histogramme suivante :
using Tableau = vector<int>;
Tableau histogramme(Grille g) {
int n = g.size();
vector<int> H = vector<int>(n*n);
for ( int i = 0 ; i < n*n ; i++ )
H[i] = 0;
for ( int i = 0 ; i < n ; i++ )
for ( int j = 0 ; j < g[i].size() ; j++ )
if ( g[i][j] > 0 and g[i][j] <= n*n )
H[g[i][j]-1] += 1;
return H;
}
Donnez le résultat de la fonction sur l’exemple suivant ainsi que sur
la grille carreMagique :
Grille exemple = {{3, 0, 3}, {2, 2, 2}, {1, 4, 1}};
/// BEGIN SOLUTION
CHECK( histogramme(exemple) == vector<int>({2, 3, 2, 1, 0, 0, 0, 0, 0});
CHECK( histogramme(carreMagique) == vector<int>({1, 1, 1, 1, 1, 1, 1, 1, 1});
/// END SOLUTION
\(\clubsuit\) Définissez une fonction estCarreMagiqueNormal qui prend
en paramètre une grille et renvoie true s’il s’agit d’un carré
magique normal, false sinon.
Indication : on pourra utiliser la fonction précédente.
/// BEGIN SOLUTION
bool estCarreMagiqueNormal(Grille g) {
vector <int> H;
if (!estCarreMagique(g))
return false;
H = histogramme(g);
for (int i = 0 ; i < H.size() ; i++)
if (H[i]!=1)
return false;
return true;
}
/// END SOLUTION