Solution de Écriture binaire d'un entier - Sujet 04 - EP NSI 2025

EXERCICE 1 (10 points)

Écrire une fonction ecriture_binaire_entier_positif qui prend en paramètre un entier positif n et renvoie une chaine de caractère correspondant à l’écriture binaire de n.

On rappelle que :

• l’écriture binaire de 25 est 11001 car 25 = 1 × 2⁴ + 1 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰ ;
• n % 2 vaut 0 ou 1 selon que n est pair ou impair ;
• n // 2 donne le quotient de la division euclidienne de n par 2.

Il est interdit dans cet exercice d’utiliser la fonction bin de Python.

Exemples :

>>> 5 % 2
1
>>> 5 // 2
2
>>> ecriture_binaire_entier_positif(0)
'0'
>>> ecriture_binaire_entier_positif(2)
'10'
>>> ecriture_binaire_entier_positif(105)
'1101001'

EXERCICE 2 (10 points)

La fonction tri_bulles prend en paramètre un tableau tab d’entiers (type list) et le modifie pour le trier par ordre croissant.

Le tri à bulles est un tri en place qui commence par placer le plus grand élément en dernière position en parcourant le tableau de gauche à droite et en échangeant au passage les éléments voisins mal ordonnés (si la valeur de l’élément d’indice i a une valeur strictement supérieure à celle de l’indice i + 1, ils sont échangés). Le tri place ensuite en avant-dernière position le plus grand élément du tableau privé de son dernier élément en procédant encore à des échanges d’éléments voisins. Ce principe est répété jusqu’à placer le minimum en première position.

Exemple : pour trier le tableau [7, 9, 4, 3] :

• première étape : 7 et 9 ne sont pas échangés, puis 9 et 4 sont échangés, puis 9 et 3 sont échangés, le tableau est alors [7, 4, 3, 9]
• deuxième étape : 7 et 4 sont échangés, puis 7 et 3 sont échangés, le tableau est alors [4, 3, 7, 9]
• troisième étape : 4 et 3 sont échangés, le tableau est alors [3, 4, 7, 9]

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

def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = ...
    tab[i] = ...
    tab[j] = ...

def tri_bulles(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri à bulles.'''
    n = len(tab)
    for i in range(...):
        for j in range(...):
            if ... > ...:
                echange(tab, j, ...)

Exemples :

>>> tab = []
>>> tri_bulles(tab)
>>> tab
[]
>>> tab2 = [9, 3, 7, 2, 3, 1, 6]
>>> tri_bulles(tab2)
>>> tab2
[1, 2, 3, 3, 6, 7, 9]
>>> tab3 = [9, 7, 4, 3]
>>> tri_bulles(tab3)
>>> tab3
[3, 4, 7, 9]

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

Exercice 1

Contraintes :

• n est un entier positif ou nul : 0 <= n <= 10^9
• les entiers strictement négatifs ne sont pas testés
• la valeur renvoyée est une chaîne de caractères (type str) composée uniquement des caractères 0 et 1
• la chaîne renvoyée ne comporte pas de zéro initial, sauf pour n = 0 où elle vaut '0'

Exercice 2

Contraintes :

• tab est un tableau d’entiers (type list) avec 0 <= len(tab) <= 10^3
• -10^9 <= tab[i] <= 10^9
• tab peut être vide et peut contenir plusieurs fois la même valeur
• tri_bulles trie tab en place et ne renvoie rien (None)
• echange(tab, i, j) reçoit des indices valides : 0 <= i < len(tab) et 0 <= j < len(tab)

Exercice 1 - l’écriture binaire d’un entier positif

L’idée. Le sujet donne les deux outils dont on a besoin : n % 2 est le dernier chiffre de l’écriture binaire de n (0 si n est pair, 1 s’il est impair), et n // 2 efface ce dernier chiffre. On répète donc toujours la même chose : on prend le reste, on le colle devant ce qu’on a déjà écrit, puis on remplace n par n // 2. On s’arrête quand n vaut 0, car il n’y a plus rien à convertir. Un seul piège : si n vaut 0 dès le départ, la boucle ne tourne pas une seule fois et on renverrait la chaîne vide ; on traite donc ce cas à part.

Un petit exemple. Pour n = 6 : 6 % 2 vaut 0, on a '0' et n devient 3 ; 3 % 2 vaut 1, on a '10' et n devient 1 ; 1 % 2 vaut 1, on a '110' et n devient 0, on s’arrête. Réponse : '110'.

def ecriture_binaire_entier_positif(n):
    if n == 0:
        return '0'
    resultat = ''
    while n > 0:
        # Le reste sort le chiffre le plus à droite : on l'ajoute devant resultat
        resultat = str(n % 2) + resultat
        n = n // 2
    return resultat

Explications. resultat contient les chiffres déjà trouvés, dans le bon ordre de lecture. Comme les restes apparaissent à l’envers (le chiffre des unités sort en premier), on écrit str(n % 2) + resultat et surtout pas resultat + str(n % 2) : chaque nouveau chiffre doit se placer devant les précédents. La boucle s’arrête dès que n vaut 0. La fonction bin est interdite dans cet exercice - et c’est justement ce calcul-là qu’elle ferait à votre place.

Exercice 2 - le tri à bulles

L’idée. Une étape du tri, c’est un parcours du tableau de gauche à droite pendant lequel on compare chaque élément avec son voisin de droite, et on les échange s’ils sont mal ordonnés. À la fin de ce parcours, la plus grande valeur a été poussée jusqu’à la dernière case : elle est à sa place définitive. Le parcours suivant peut donc s’arrêter une case plus tôt, et ainsi de suite jusqu’à ce qu’il ne reste plus qu’une case.

Un petit exemple. Pour [7, 9, 4, 3] : le premier parcours compare (7, 9) - rien -, (9, 4) - échange -, (9, 3) - échange - et donne [7, 4, 3, 9] ; le 9 est placé. Le deuxième parcours ne va plus que jusqu’à l’avant-dernière case et donne [4, 3, 7, 9]. Le troisième donne [3, 4, 7, 9].

def echange(tab, i, j):
    '''Echange les éléments d'indice i et j dans le tableau tab.'''
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

def tri_bulles(tab):
    '''Trie le tableau tab dans l'ordre croissant
    par la méthode du tri à bulles.'''
    n = len(tab)
    for i in range(n - 1, 0, -1):
        for j in range(i):
            if tab[j] > tab[j + 1]:
                echange(tab, j, j + 1)

Explications. Dans echange, la variable temp met de côté tab[i] avant qu’il ne soit écrasé : sans elle, on perdrait une des deux valeurs.

Dans tri_bulles, i est l’indice de la dernière case pas encore remplie définitivement : il part de n - 1 et descend jusqu’à 1, d’où le range(n - 1, 0, -1). Inutile d’aller jusqu’à 0 : quand il ne reste qu’une case, elle contient forcément le minimum. Le parcours intérieur for j in range(i) compare tab[j] et tab[j + 1] en s’arrêtant juste avant la zone déjà triée.

Le test est > et non >= : deux valeurs égales ne sont pas échangées, ce qui évite un travail inutile et donne bien [1, 2, 3, 3, 6, 7, 9] pour [9, 3, 7, 2, 3, 1, 6]. Enfin, si le tableau est vide, n vaut 0 et range(-1, 0, -1) est vide : aucune boucle ne tourne et le tableau reste [], comme demandé. La fonction ne renvoie rien : elle modifie tab en place.