Solution de Carré semimagique - Sujet 41 - EP NSI 2025

EXERCICE 1 (10 points)

L’opérateur « ou exclusif » entre deux bits renvoie 0 si les deux bits sont égaux et 1 s’ils sont différents. Il est symbolisé par le symbole ⊕. Ainsi :

• 0 ⊕ 0 = 0
• 0 ⊕ 1 = 1
• 1 ⊕ 0 = 1
• 1 ⊕ 1 = 0

Écrire une fonction ou_exclusif qui prend en paramètres deux tableaux de 0 ou de 1 de même longueur et qui renvoie un tableau où l’élément situé à position i est le résultat, par l’opérateur « ou exclusif », des éléments à la position i des tableaux passés en paramètres.

Exemples :

>>> ou_exclusif([1, 0, 1, 0, 1, 1, 0, 1], [0, 1, 1, 1, 0, 1, 0, 0])
[1, 1, 0, 1, 1, 0, 0, 1]
>>> ou_exclusif([1, 1, 0, 1], [0, 0, 1, 1])
[1, 1, 1, 0]

EXERCICE 2 (10 points)

Dans cet exercice, on appelle carré d’ordre 𝑛 un tableau de 𝑛 lignes et 𝑛 colonnes dont chaque case contient un entier naturel.

Exemples :

[Figure : trois carrés dessinés sous forme de grilles. Le premier, nommé c2, est un carré d’ordre 2 dont les lignes sont (1, 7) et (7, 1) ; légende « Un carré d’ordre 2 ». Le deuxième, nommé c3, est un carré d’ordre 3 dont les lignes sont (3, 4, 5), (4, 4, 4) et (5, 4, 3) ; légende « Un carré d’ordre 3 ». Le troisième, nommé c3bis, est un carré d’ordre 3 dont les lignes sont (2, 9, 4), (7, 0, 3) et (6, 1, 8) ; légende « Un autre carré d’ordre 3 ».]

Un carré est dit semimagique lorsque les sommes des éléments situés sur chaque ligne, chaque colonne sont égales.

• Ainsi c2 et c3 sont semimagiques car la somme de chaque ligne et chaque colonne est égale à 8 pour c2 et 12 pour c3.
• Le carre c3bis n’est pas semimagique car la somme de la première ligne est égale à 15 alors que celle de la deuxième ligne est égale à 10.

La classe Carre ci-après contient des méthodes qui permettent de manipuler des carrés.

• La méthode constructeur crée un carré sous forme d’un tableau à deux dimensions à partir d’une liste d’entiers, et d’un ordre.
• La méthode affiche permet d’afficher le carré créé.

Exemple :

>>> lst_c3 = [3, 4, 5, 4, 4, 4, 5, 4, 3]
>>> c3 = Carre(lst_c3, 3)
>>> c3.affiche()
[3, 4, 5]
[4, 4, 4]
[5, 4, 3]

Compléter la méthode est_semimagique qui renvoie True si le carré est semimagique, False sinon.

class Carre:
    def __init__(self, liste, n):
        self.ordre = n
        self.tableau = [[liste[i + j * n] for i in range(n)]
                        for j in range(n)]

    def affiche(self):
        '''Affiche un carré'''
        for i in range(self.ordre):
            print(self.tableau[i])

    def somme_ligne(self, i):
        '''Calcule la somme des valeurs de la ligne i'''
        somme = 0

        for j in range(self.ordre):
            somme = somme + self.tableau[i][j]
        return somme

    def somme_col(self, j):
        '''Calcule la somme des valeurs de la colonne j'''
        somme = 0

        for i in range(self.ordre):
            somme = somme + self.tableau[i][j]
        return somme


    def est_semimagique(self):
        s = self.somme_ligne(0)
        #test de la somme de chaque ligne
        for i in range(...):
            if ... != s:
                return ...

        #test de la somme de chaque colonne
        for j in range(...):
            if ... != s:
                return ...

        return ...

Tester la méthode est_semimagique sur les carrés c2, c3 et c3bis.

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• ou_exclusif prend en paramètres deux tableaux (listes Python) tab1 et tab2 de même longueur
• 0 <= len(tab1) <= 10^4 et len(tab2) == len(tab1)
• tab1[i] et tab2[i] valent 0 ou 1
• le tableau renvoyé a la même longueur que les tableaux passés en paramètres et ne contient que des 0 et des 1
• si les deux tableaux sont vides, le tableau renvoyé est []

Exercice 2

Contraintes :

• Carre(liste, n) reçoit un entier n qui est l’ordre du carré, avec 1 <= n <= 100
• liste est un tableau (liste Python) de longueur exactement n * n
• les éléments de liste sont des entiers naturels, avec 0 <= liste[k] <= 10^4
• est_semimagique ne prend aucun paramètre autre que self et renvoie un booléen True ou False
• un carré d’ordre 1 est semimagique

Exercice 1 - ou exclusif entre deux tableaux de bits

L’idée. Les deux tableaux ont la même longueur, et on doit comparer leurs cases deux à deux. Il n’y a donc rien à inventer : on parcourt les positions une par une, et à chaque position on regarde si les deux bits sont égaux. S’ils sont égaux on ajoute 0 au résultat, sinon on ajoute 1. On construit ainsi un nouveau tableau, case par case, et on le renvoie à la fin.

Un petit exemple. Pour [1, 1, 0, 1] et [0, 0, 1, 1] : en position 0 les bits sont 1 et 0, ils diffèrent donc on ajoute 1 ; en position 3 les bits valent 1 et 1, ils sont égaux donc on ajoute 0. On obtient [1, 1, 1, 0].

def ou_exclusif(tab1, tab2):
    resultat = []
    for i in range(len(tab1)):
        # deux bits egaux donnent 0, deux bits differents donnent 1
        if tab1[i] == tab2[i]:
            resultat.append(0)
        else:
            resultat.append(1)
    return resultat

resultat est le tableau que l’on remplit au fur et à mesure : il est vide au départ, et on lui ajoute exactement un bit par tour de boucle. La boucle va de 0 à len(tab1) - 1, donc le tableau renvoyé a bien la même longueur que ceux reçus. Comme les deux tableaux ont la même longueur, l’indice i est valide dans les deux, et tab2[i] ne sort jamais du tableau. Si les tableaux sont vides, la boucle ne s’exécute pas une seule fois et on renvoie [], ce qui est bien la réponse attendue : aucun cas particulier n’est à ajouter.

Exercice 2 - carré semimagique

L’idée. Un carré est semimagique quand toutes les lignes et toutes les colonnes ont la même somme. On n’a pas besoin de comparer toutes les sommes entre elles : il suffit de choisir une somme de référence, par exemple celle de la première ligne, et de vérifier que toutes les autres sommes lui sont égales. Les méthodes somme_ligne et somme_col sont déjà écrites, on s’en sert. Dès qu’une somme diffère de la référence, on peut arrêter et renvoyer False ; si on arrive au bout des deux boucles sans avoir rien trouvé d’anormal, c’est que tout est égal et on renvoie True.

Un petit exemple. Pour c3, la première ligne (3, 4, 5) a pour somme 12. On vérifie ensuite que les lignes (4, 4, 4) et (5, 4, 3) font aussi 12, puis que les trois colonnes font 12 : c’est le cas, donc True. Pour c3bis, la première ligne fait 15 mais la deuxième fait 10 : la boucle sur les lignes s’arrête tout de suite et renvoie False.

    def est_semimagique(self):
        s = self.somme_ligne(0)
        #test de la somme de chaque ligne
        for i in range(self.ordre):
            if self.somme_ligne(i) != s:
                return False

        #test de la somme de chaque colonne
        for j in range(self.ordre):
            if self.somme_col(j) != s:
                return False

        return True

s retient la somme de référence, celle de la ligne 0. Les deux boucles parcourent les indices de 0 à self.ordre - 1, c’est-à-dire toutes les lignes puis toutes les colonnes du carré. La première boucle repasse par la ligne 0, ce qui ne coûte rien : sa somme vaut s par construction, donc elle ne déclenche jamais le return False. Le return True est placé après les deux boucles, et non à l’intérieur : on ne peut conclure que le carré est semimagique qu’après avoir vérifié toutes les lignes et toutes les colonnes. Un carré d’ordre 1 traverse les deux boucles sans problème et renvoie donc True.

Pour tester, on crée les trois carrés et on appelle la méthode :

>>> c2 = Carre([1, 7, 7, 1], 2)
>>> c3 = Carre([3, 4, 5, 4, 4, 4, 5, 4, 3], 3)
>>> c3bis = Carre([2, 9, 4, 7, 0, 3, 6, 1, 8], 3)
>>> c2.est_semimagique()
True
>>> c3.est_semimagique()
True
>>> c3bis.est_semimagique()
False