Solution de Conversion binaire grand-boutiste - Sujet 37 - EP NSI 2025

EXERCICE 1 (10 points)

On considère dans cet exercice une représentation binaire d’un entier non signé en tant que tableau de booléens.

Si

tab = [True, False, True, False, False, True, True]

est un tel tableau, alors l’entier qu’il représente est 2^6 + 2^4 + 2^1 + 2^0 = 83. Cette représentation consistant à placer en premier le booléen indiquant la puissance la plus élevée de 2 est dite big-endian ou grand-boutiste.

Écrire une fonction gb_vers_entier qui prend en paramètre un tel tableau et renvoie l’entier qu’il représente.

Exemple :

>>> gb_vers_entier([])
0
>>> gb_vers_entier([True])
1
>>> gb_vers_entier([True, False, True,
      False, False, True, True])
83
>>> gb_vers_entier([True, False, False, False,
      False, False, True, False])
130

EXERCICE 2 (10 points)

La fonction tri_insertion suivante prend en argument un tableau tab (type list) et trie ce tableau en utilisant la méthode du tri par insertion. Compléter cette fonction pour qu’elle réponde à la spécification demandée.

On rappelle le principe du tri par insertion : on considère les éléments à trier un par un, le premier élément constituant, à lui tout seul, un tableau trié de longueur 1. On range ensuite le second élément pour constituer un tableau trié de longueur 2, puis on range le troisième élément pour avoir un tableau trié de longueur 3 et ainsi de suite…

A chaque étape, le premier élément du sous-tableau non trié est placé dans le sous-tableau des éléments déjà triés de sorte que ce sous-tableau demeure trié.

Le principe du tri par insertion est donc d’insérer à la n-ième itération, le n-ième élément à la bonne place.

def tri_insertion(tab):
    '''Trie le tableau tab par ordre croissant
    en appliquant l'algorithme de tri par insertion'''
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = ...
        # la variable j sert à déterminer
        # où placer la valeur à ranger
        j = ...
        # tant qu'on n'a pas trouvé la place de l'élément à
        # insérer on décale les valeurs du tableau vers la droite
        while j > ... and valeur_insertion < tab[...]:
            tab[j] = tab[j-1]
            j = ...
        tab[j] = ...

Exemple :

>>> tab = [98, 12, 104, 23, 131, 9]
>>> tri_insertion(tab)
>>> tab
[9, 12, 23, 98, 104, 131]

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

Exercice 1

Contraintes :

• 0 <= len(tab) <= 10^3
• chaque élément de tab est un booléen : True ou False
• tab[0] est le booléen de poids fort (représentation grand-boutiste)
• le tableau vide est autorisé : gb_vers_entier([]) vaut 0
• la valeur renvoyée est un entier positif ou nul de type int

Exercice 2

Contraintes :

• 0 <= len(tab) <= 10^3
• tab est de type list et chaque élément de tab est un entier avec -10^9 <= tab[i] <= 10^9
• les valeurs de tab peuvent être répétées
• tri_insertion trie tab en place, par ordre croissant, et ne renvoie rien (None)

Exercice 1 - gb_vers_entier

L’idée. Le tableau est donné en grand-boutiste : la case 0 porte la plus grande puissance de 2. On peut donc le lire simplement de gauche à droite en construisant l’entier au fur et à mesure. On garde dans une variable la valeur formée par les booléens déjà lus ; chaque fois qu’on avance d’une case, tout ce qui a été lu jusque-là est décalé d’un rang, c’est-à-dire multiplié par 2, et on ajoute 1 si le booléen courant vaut True. Comme on part de 0, le tableau vide renvoie bien 0.

Un petit exemple. Pour [True, False, True] : on part de 0, puis 0 * 2 + 1 = 1, puis 1 * 2 + 0 = 2, puis 2 * 2 + 1 = 5. On retrouve bien 4 + 1 = 5.

def gb_vers_entier(tab):
    entier = 0
    for bit in tab:
        # passer à la case suivante décale d'un rang ce qui est déjà lu
        entier = entier * 2
        if bit:
            entier = entier + 1
    return entier

entier contient à tout moment la valeur du début du tableau déjà parcouru. Il n’y a besoin ni de calculer des puissances de 2, ni de connaître la longueur du tableau : c’est la multiplication par 2 à chaque tour qui donne automatiquement le bon poids à chaque booléen. Le if bit: suffit, car les éléments sont des booléens.

Exercice 2 - tri_insertion

L’idée. À l’étape i, la partie tab[0] à tab[i-1] est déjà triée et il faut y ranger tab[i]. On met d’abord cette valeur de côté dans valeur_insertion, car sa case va être écrasée. Ensuite on remonte vers la gauche : tant qu’on n’est pas au début du tableau et que la valeur de gauche est plus grande que celle qu’on range, on la décale d’une case vers la droite. Quand on s’arrête, le trou qui reste est exactement la bonne place : on y écrit valeur_insertion. Le tri se fait sur place, la fonction ne renvoie rien.

Un petit exemple. Avec [12, 98, 23] et i = 2 : on retient 23, on décale 98 vers la droite, on s’arrête devant 12 qui est plus petit, et on écrit 23 dans le trou. On obtient [12, 23, 98].

def tri_insertion(tab):
    '''Trie le tableau tab par ordre croissant
    en appliquant l'algorithme de tri par insertion'''
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = tab[i]
        # la variable j sert à déterminer
        # où placer la valeur à ranger
        j = i
        # tant qu'on n'a pas trouvé la place de l'élément à
        # insérer on décale les valeurs du tableau vers la droite
        while j > 0 and valeur_insertion < tab[j-1]:
            tab[j] = tab[j-1]
            j = j - 1
        tab[j] = valeur_insertion

j est la position du trou : au départ le trou est en i, et il recule d’une case à chaque décalage. La condition j > 0 empêche de sortir du tableau quand la valeur rangée est la plus petite de toutes. Le test valeur_insertion < tab[j-1] est un < strict : on s’arrête dès qu’on rencontre une valeur égale, ce qui évite des décalages inutiles. Enfin, la boucle for commence à 1 parce qu’un tableau réduit à sa première case est déjà trié ; les tableaux de longueur 0 ou 1 ne sont donc pas modifiés.