Aller au contenu

Sujet n°7

Sujet original

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

Exercice n°1

Écrire une fonction conv_bin qui prend en paramètre un entier positif n et renvoie un couple (b, bit) où :

  • b est une liste d'entiers correspondant à la représentation binaire de n ;
  • bit correspond aux nombre de bits qui constituent b.
Commentaires

Ici, 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.

Exemple

>>> conv_bin(9) 
([1, 0, 0, 1], 4) 

Aide

  • l'opérateur // donne le quotient de la division euclidienne : 5//2 donne 2 ;
  • l'opérateur % donne le reste de la division euclidienne : 5%2 donne 1 ;
  • append est une méthode qui ajoute un élément à une liste existante :
    Soit T = [5, 2, 4], alors T.append(10) ajoute 10 à la liste T. Ainsi, T devient [5, 2, 4, 10].
  • reverse est une méthode qui renverse les éléments d'une liste.
    Soit T = [5, 2, 4, 10]. Après T.reverse(), la liste devient [10, 4, 2, 5].

On remarquera qu’on récupère la représentation binaire d’un entier n en partant de la gauche en appliquant successivement les instructions :
b = n%2
n = n//2
répétées autant que nécessaire.

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def conv_bin(n):
    """
    n - int - entier positif ou nul
    Sortie: tuple, couple constitué d'un tableau des bits formant
            l'écriture binaire de n et du nombre de bits
    """
    if n==0:
        return [0], 1
    else:
        tab = []
        while n > 0:
            tab.append(n%2)
            n = n//2
        tab.reverse()
        return tab, len(tab)


if __name__ == '__main__':
    print(conv_bin(9) == ([1, 0, 0, 1], 4))
    print(conv_bin(97) == ([1, 1, 0, 0, 0, 0, 1], 7))

Exercice n°2

La fonction tri_bulles prend en paramètre une liste T d’entiers non triés et renvoie la liste triée par ordre croissant.

Commentaires

A nouveau, 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.

Compléter le code Python ci-dessous qui implémente la fonction tri_bulles.

1
2
3
4
5
6
7
8
9
def tri_bulles(T):
    n = len(T)
    for i in range(..., ..., -1):
        for j in range(i):
            if T[j] > T[...]:
                ... = T[j]
                T[j] = T[...]
                T[j+1] = temp
    return T
Commentaires sur le code original

Pour télécharger l'original du fichier à compléter, cliquer ici.

Pas d'exemple dans ce sujet et une demande de rédaction d'un algorithme de tri « nouveau », sans préciser comment fonctionne un tri à bulles. Cela ne semble pas conforme aux préconisations de l'épreuve.

Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def tri_bulles(T):
    n = len(T)
    for i in range(n-1, 0, -1):
        for j in range(i):
            if T[j] > T[j+1]:
                temp = T[j]
                T[j] = T[j+1]
                T[j+1] = temp
    return T


if __name__ == '__main__':
    print(tri_bulles([4, 2, 5, 9, 6, 7, 8]) == [2, 4, 5, 6, 7, 8, 9] )
    print(tri_bulles([8, 5, 1, 7, 6, 9, 1, 4, 2]) == [1, 1, 2, 4, 5, 6, 7, 8, 9] )