Aller au contenu

Sujet n°33

Sujet original

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

Exercice n°1

On modélise la représentation binaire d'un entier non signé par un tableau d'entiers dont les éléments sont 0 ou 1. Par exemple, le tableau [1, 0, 1, 0, 0, 1, 1] représente l'écriture binaire de l'entier dont l'écriture décimale est

2**6 + 2**4 + 2**1 + 2**0 = 83

À l'aide d'un parcours séquentiel, écrire la fonction convertir répondant aux spécifications suivantes :

1
2
3
4
5
6
7
def convertir(T):
    """
    T est un tableau d'entiers, dont les éléments sont 0 ou 1 et
    représentant un entier écrit en binaire. Renvoie l'écriture
    décimale de l'entier positif dont la représentation binaire
    est donnée par le tableau T
    """

Exemple

>>> convertir([1, 0, 1, 0, 0, 1, 1])
83
>>> convertir([1, 0, 0, 0, 0, 0, 1, 0])
130
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def convertir(T):
    """
    T est un tableau d'entiers, dont les éléments sont 0 ou 1 et
    représentant un entier écrit en binaire. Renvoie l'écriture
    décimale de l'entier positif dont la représentation binaire
    est donnée par le tableau T
    """
    resultat = 0
    puis = 1
    for i in range(len(T)-1, -1, -1):
        resultat = resultat + T[i]*puis
        puis = puis*2
    return resultat


if __name__ == '__main__':
    print(convertir([1, 0, 1, 0, 0, 1, 1]) == 83)
    print(convertir([1, 0, 0, 0, 0, 0, 1, 0]) == 130)

Exercice n°2

La fonction tri_insertion suivante prend en argument une liste L et trie cette liste en utilisant la méthode du tri par insertion.

Compléter cette fonction pour qu'elle réponde à la spécification demandée.

 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 tri_insertion(L):
    n = len(L)

    # cas du tableau vide
    if ...:
        return L

    for j in range(1,n):
        e = L[j]
        i = j

        # A l'étape j, le sous-tableau L[0,j-1] est trié
        # et on insère L[j] dans ce sous-tableau en déterminant
        # le plus petit i tel que 0 <= i <= j et L[i-1] > L[j].
        while  i > 0 and L[i-1] > ...:
            i = ...

        # si i != j, on décale le sous tableau L[i,j-1] d’un cran
        # vers la droite et on place L[j] en position i
        if i != j:
            for k in range(j,i,...):
                L[k] = L[...]
            L[i] = ...
    return L
Commentaires sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. Dans ce code, le mot « liste » est à comprendre dans le sens « liste Python » (c'est-à-dire tableau) plutôt que dans le sens du type abstrait de données liste étudié en Terminale.

  3. Dans cet exercice, il faut reprogrammer un algorithme usuel, à avoir travaillé de nombreuses fois ! Ici, le code comporte d'inutiles complications alors qu'il pourrait comporter moitié moins de lignes et être plus clair dans la dénomination des variables.

Exemple

>>> tri_insertion([2, 5, -1, 7, 0, 28])
[-1, 0, 2, 5, 7, 28]
>>> tri_insertion([10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
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
def tri_insertion(L):
    n = len(L)

    # cas du tableau vide
    if L==[]:
        return L

    for j in range(1, n):
        e = L[j]
        i = j

        # A l'étape j, le sous-tableau L[0, j-1] est trié
        # et on insère L[j] dans ce sous-tableau en déterminant
        # le plus petit i tel que 0 <= i <= j et L[i-1] > L[j].
        while  i > 0 and L[i-1] > L[j]:
            i = i-1

        # si i != j, on décale le sous tableau L[i, j-1] d’un cran
        # vers la droite et on place L[j] en position i
        if i != j:
            for k in range(j, i, -1):
                L[k] = L[k-1]
            L[i] = e
    return L


if __name__ == '__main__':
    print(tri_insertion([2, 5, -1, 7, 0, 28]) == [-1, 0, 2, 5, 7, 28])
    print(tri_insertion([10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]) == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])