Adloun

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.