Carré magique — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 5)

Carré magique

Tableaux · niveau 3 (difficile)

Énoncé

Un carré $n \times n$ est magique si les sommes de chaque ligne, de chaque colonne et des deux diagonales sont toutes égales. Écrire static boolean estMagique(int[][] c) et la tester sur

$294753618 et 147258369 .$

Combien de cases la méthode lit-elle, au plus, pour un carré $n \times n$ ?

Corrigé


static boolean estMagique(int[][] c) {
    int n = c.length;
    int cible = 0;
    for (int j = 0; j < n; j++) cible += c[0][j];   // somme de la première ligne
    int d1 = 0, d2 = 0;
    for (int i = 0; i < n; i++) {
        int sl = 0, sc = 0;                         // ligne i, colonne i
        for (int j = 0; j < n; j++) {
            sl += c[i][j];
            sc += c[j][i];
        }
        if (sl != cible || sc != cible) return false;
        d1 += c[i][i];
        d2 += c[i][n - 1 - i];
    }
    return d1 == cible && d2 == cible;
}

Le premier carré (le carré de Lo Shu) est magique, de somme $15$ ; le second ne l'est pas (ses lignes valent $6$ , $15$ et $24$ ). La méthode lit au plus $n$ cases pour la cible, puis $2 n$ cases par valeur de $i$ et deux cases diagonales : environ $2 n^{2} + 3 n$ lectures, soit un travail proportionnel au nombre $n^{2}$ de cases.