É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)

Énoncé du problème