Un carré magique est une matrice carrée dont toutes les lignes, toutes…
Exercice d'entraînement · niveau 3 (difficile) · NSI (première), chapitre 4 — Les types construits · Matrices
Énoncé
Un carré magique est une matrice carrée dont toutes les lignes, toutes les colonnes et les deux diagonales ont la même somme. Écrire est_magique(m). Tester sur le carré de Lo Shu [[2, 7, 6], [9, 5, 1], [4, 3, 8]], et trouver une matrice qui passe le test des lignes et des colonnes mais échoue sur la diagonale.
Corrigé
def est_magique(m):
"""Vrai si m est un carre magique.
Precondition : m est une matrice carree non vide.
"""
assert len(m) > 0 and all(len(l) == len(m) for l in m), "matrice non carree"
n = len(m)
cible = somme_ligne(m, 0) # la somme de reference
for i in range(n):
if somme_ligne(m, i) != cible:
return False
for j in range(n):
if somme_colonne(m, j) != cible:
return False
d1 = 0
d2 = 0
for i in range(n):
d1 = d1 + m[i][i] # diagonale principale
d2 = d2 + m[i][n - 1 - i] # anti-diagonale
return d1 == cible and d2 == cible
Les deux diagonales, et leurs indices. m[i][i] parcourt la diagonale principale, du coin haut gauche au coin bas droit. m[i][n - 1 - i] parcourt l'autre : quand augmente, la colonne diminue. Une seule boucle suffit pour les deux — c'est le genre de détail où l'on se trompe d'un cran, et que le carré de Lo Shu détecte immédiatement.
Vérification.
lo_shu = [[2, 7, 6], [9, 5, 1], [4, 3, 8]]
assert est_magique(lo_shu) is True # toutes les sommes valent 15
assert est_magique([[1, 2], [3, 4]]) is False
assert est_magique([[5]]) is True # 1 x 1 : trivialement magique
Dans le carré de Lo Shu, la somme commune est : , , pour les lignes ; , , pour les colonnes ; et pour les diagonales.
La matrice qui passe lignes et colonnes mais pas la diagonale :
m = [[1, 2, 3],
[3, 1, 2],
[2, 3, 1]]
# lignes : 6, 6, 6 colonnes : 6, 6, 6 diagonale : 1 + 1 + 1 = 3
print(est_magique(m)) # False
C'est un carré latin : chaque valeur apparaît une fois par ligne et une fois par colonne, ce qui garantit les sommes de lignes et de colonnes — et ne dit rien des diagonales.
Ce que cet exemple enseigne sur les tests : un jeu de tests qui ne contiendrait que des matrices aléatoires ne trouverait jamais ce cas, car une matrice quelconque échoue dès la deuxième ligne. **Les cas intéressants sont ceux qui satisfont presque la spécification** — et ceux-là, il faut les construire exprès.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.