Aller au contenu

Sujet n°20

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

L'opérateur « ou exclusif » entre deux bits renvoie 0 si les deux bits sont égaux et 1 s'ils sont différents :
0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, 1 ⊕ 1 = 0

On représente ici une suite de bits par un tableau contenant des 0 et des 1.

Exemples

a = [1, 0, 1, 0, 1, 1, 0, 1]
b = [0, 1, 1, 1, 0, 1, 0, 0]
c = [1, 1, 0, 1]
d = [0, 0, 1, 1]

Écrire la fonction xor qui prend en paramètres deux tableaux 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.

En considérant les quatre exemples ci-dessus, cette fonction doit passer les tests suivants :

Exemples

>>> xor(a, b)
[1, 1, 0, 1, 1, 0, 0, 1]

>>> xor(c, d)
[1, 1, 1, 0]
Commentaires
  1. La table de vérité aurait pu être présentée dans un tableau pour plus de lisibilité
  2. Dans l'énoncé original, les exemples sont proposés avec des assertions, ce qui diffère des énoncés précédents et devrait être évité par soucis d'harmonisation :
    assert(xor(a, b) == [1, 1, 0, 1, 1, 0, 0, 1])
    assert(xor(c, d) == [1, 1, 1, 0])
    
Une solution

Dans cette solution, on ajoute une assertion pour vérifier que les deux tableaux ont la même longueur.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def xor(bits_a, bits_b):
    """
    bits_a, bits_b - list, tableaux de bits de même longueur
    Sortie: list - tableau de bits construit bit à bit en appliquant
            l'opérateur xor entre les bits correspondants de bits_a et bits_b
    """
    assert len(bits_a) == len(bits_b), "Les tableaux n'ont pas le même nombre de bits"
    result = []
    for i in range(len(bits_a)):
        if bits_a[i] == bits_b[i]:
            result.append(0)
        else:
            result.append(1)
    return result


if __name__ == '__main__':
    a = [1, 0, 1, 0, 1, 1, 0, 1]
    b = [0, 1, 1, 1, 0, 1, 0, 0]
    c = [1, 1, 0, 1]
    d = [0, 0, 1, 1]

    print(xor(a, b) == [1, 1, 0, 1, 1, 0, 0, 1])    
    print(xor(c, d) == [1, 1, 1, 0])

Exercice n°2

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

Exemples

carrés

Un carré est dit magique lorsque les sommes des éléments situés sur chaque ligne, chaque colonne et chaque diagonale sont égales. Ainsi c2 et c3 sont magiques car la somme de chaque ligne, chaque colonne et chaque diagonale est égale à 2 pour c2 et 15 pour c3. c4 n’est pas magique car la somme de la première ligne est égale à 34 alors que celle de la dernière colonne est égale à 27.

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

Compléter la fonction est_magique qui prend en paramètre un carré et qui renvoie la valeur de la somme si ce carré est magique, False sinon.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Carre:
    def __init__(self, tableau = [[]]):
        self.ordre = len(tableau)
        self.valeurs = tableau

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

    def somme_ligne(self, i):
        '''Calcule la somme des valeurs de la ligne i'''
        return sum(self.valeurs[i])

    def somme_col(self, j):
        '''Calcule la somme des valeurs de la colonne j'''
        return sum([self.valeurs[i][j] for i in range(self.ordre)])

def est_magique(carre):
    n = carre.ordre
    s = carre.somme_ligne(0)

    #test de la somme de chaque ligne
    for i in range(..., ...):
        if carre.somme_ligne(i) != s:
            return ...

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

    #test de la somme de chaque diagonale
    if sum([carre.valeurs[...][...] for k in range(n)]) != s:
        return False
    if sum([carre.valeurs[k][n-1-k] for k in range(n)]) != s:
        return False
    return ...

Tester la fonction est_magique sur les carrés c2, c3 et c4.

Commentaires sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. 😱 Le paramètre tableau est mutable et il n'est pas initialisé à None par défaut. Ce code va donc générer des effets de bords inattendus si des objets de classe Carre sont initialisés sans argument...

  3. La fonction est_magique renvoie soit un entier, soit un booléen... Renvoyer des éléments de type différent selon les cas n'est pas recommandé.

  4. Des exemples plus complets pourraient être proposés. Par exemple :

    >>> c2 = Carre( [[1, 1], [1, 1]] )
    >>> c3 = Carre( [[2, 9, 4], [7, 5, 3], [6, 1, 8]] )
    >>> c4 = Carre( [[4, 5, 16, 9], [14, 7, 2, 11], [3, 10, 15, 6], [13, 12, 8, 1]] )
    

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Carre:
    def __init__(self, tableau = [[]]):
        self.ordre = len(tableau)
        self.valeurs = tableau

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

    def somme_ligne(self, i):
        '''Calcule la somme des valeurs de la ligne i'''
        return sum(self.valeurs[i])

    def somme_col(self, j):
        '''calcule la somme des valeurs de la colonne j'''
        return sum([self.valeurs[i][j] for i in range(self.ordre)])


def est_magique(carre):
    n = carre.ordre
    s = carre.somme_ligne(0)

    #test de la somme de chaque ligne
    for i in range(1, n):
        if carre.somme_ligne(i) != s:
            return False

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

    #test de la somme de chaque diagonale
    if sum([carre.valeurs[k][k] for k in range(n)]) != s:
            return False
    if sum([carre.valeurs[k][n-1-k] for k in range(n)]) != s:
            return False

    return s


if __name__ == '__main__':
    c2 = Carre( [[1, 1], [1, 1]] )
    c3 = Carre( [[2, 9, 4], [7, 5, 3], [6, 1, 8]] )
    c4 = Carre( [[4, 5, 16, 9], [14, 7, 2, 11], [3, 10, 15, 6], [13, 12, 8, 1]] )

    print(est_magique(c2) == 2)
    print(est_magique(c3) == 15)
    print(est_magique(c4) == False)