Solution de Conversion en binaire - Sujet 42 - EP NSI 2025

Exercice 1

Écrire une fonction Python appelée nb_repetitions qui prend en paramètres un élément elt et un tableau tab (type list) d’éléments du même type et qui renvoie le nombre de fois où l’élément apparaît dans le tableau.

Exemples :

>>> nb_repetitions(5, [2, 5, 3, 5, 6, 9, 5])
3
>>> nb_repetitions('A', ['B', 'A', 'B', 'A', 'R'])
2
>>> nb_repetitions(12, [1, '!', 7, 21, 36, 44])
0

Exercice 2

Pour rappel, la conversion d’un nombre entier positif en binaire peut s’effectuer à l’aide des divisions successives comme illustré ici :

[Figure : schéma des divisions successives de 77 par 2, disposé en escalier. On divise 77 par 2 (reste 1, quotient 38), puis 38 par 2 (reste 0, quotient 19), puis 19 par 2 (reste 1, quotient 9), puis 9 par 2 (reste 1, quotient 4), puis 4 par 2 (reste 0, quotient 2), puis 2 par 2 (reste 0, quotient 1), puis 1 par 2 (reste 1, quotient 0). Une flèche rouge remontant la diagonale des restes porte la mention « Lecture du résultat ».]

Voici une fonction Python basée sur la méthode des divisions successives permettant de convertir un nombre entier positif en binaire :

Compléter la fonction binaire.

def binaire(a):
    '''convertit un nombre entier a en sa representation
    binaire sous forme de chaine de caractères.'''
    if a == 0:
        return '0'
    bin_a = ...
    while ...:
        bin_a = ... + bin_a
        a = ...
    return bin_a

Exemples :

>>> binaire(0)
'0'
>>> binaire(77)
'1001101'

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

Exercice 1

Contraintes :

• 0 <= len(tab) <= 10^4
• tab est de type list et peut être vide
• tab peut mélanger des éléments de types différents (par exemple int et str)
• elt peut être de n’importe lequel de ces types
• les éléments entiers vérifient -10^9 <= x <= 10^9 ; les éléments de type str ont une longueur inférieure ou égale à 100
• la comparaison est décidée uniquement par == : la fonction ne doit lever aucune exception, même si elt et un élément de tab n’ont pas le même type
• la valeur renvoyée est un int compris entre 0 et len(tab) ; elle vaut 0 si elt n’apparaît pas dans tab

Exercice 2

Contraintes :

• a est de type int et vérifie 0 <= a <= 10^9, la valeur 0 étant incluse
• les valeurs négatives de a sont hors du champ du sujet et ne sont pas testées
• la valeur renvoyée est une chaîne de caractères (str) composée uniquement des caractères 0 et 1
• la représentation renvoyée ne comporte pas de zéro initial superflu : binaire(0) renvoie '0' et, pour a > 0, le premier caractère est 1

Exercice 1 - compter les apparitions d’un élément

L’idée. Il n’y a pas de raccourci : pour savoir combien de fois elt apparaît, il faut regarder tout le tableau. On prépare donc un compteur à 0, on parcourt le tableau élément par élément, et chaque fois qu’un élément est égal à elt, on ajoute 1 au compteur. À la fin du parcours, le compteur contient la réponse.

Un petit exemple. Pour nb_repetitions(5, [2, 5, 3, 5, 6, 9, 5]), le compteur passe à 1 sur le deuxième élément, à 2 sur le quatrième, à 3 sur le dernier : on renvoie 3.

def nb_repetitions(elt, tab):
    compteur = 0
    for element in tab:
        # Le test == suffit : deux valeurs de types différents renvoient simplement False
        if element == elt:
            compteur = compteur + 1
    return compteur

compteur retient le nombre d’égalités déjà rencontrées. Comme il vaut 0 avant la boucle, un tableau vide ou un élément absent donnent bien 0, sans traitement particulier à écrire.

Attention au troisième exemple, nb_repetitions(12, [1, '!', 7, 21, 36, 44]) : le tableau mélange un entier et une chaîne. Ce n’est pas un problème, car en Python comparer un entier et une chaîne avec == ne provoque aucune erreur, cela vaut simplement False. La fonction renvoie donc 0.

Exercice 2 - conversion en binaire

L’idée. On applique la méthode des divisions successives du sujet. À chaque tour, le reste de la division de a par 2 donne un chiffre binaire, et on remplace a par son quotient a // 2. Le problème est que ces restes sortent dans le mauvais sens : le premier reste obtenu est le chiffre le plus à droite. C’est pour cela qu’on écrit bin_a = ... + bin_a : chaque nouveau chiffre est collé devant ceux déjà trouvés. On s’arrête quand a est tombé à 0.

Un petit exemple. Pour a = 77, les restes successifs sont 1, 0, 1, 1, 0, 0, 1 et la chaîne se construit ainsi : '1', puis '01', '101', '1101', '01101', '001101', et enfin '1001101'.

def binaire(a):
    '''convertit un nombre entier a en sa representation
    binaire sous forme de chaine de caractères.'''
    if a == 0:
        return '0'
    bin_a = ''
    while a > 0:
        # Le nouveau reste est le chiffre de gauche des chiffres déjà trouvés
        bin_a = str(a % 2) + bin_a
        a = a // 2
    return bin_a

bin_a part de la chaîne vide '' et grandit d’un caractère par tour. a % 2 vaut 0 ou 1, et str(...) le transforme en caractère pour pouvoir le concaténer. a = a // 2 est la division entière : c’est elle qui fait descendre a vers 0 et donc qui termine la boucle.

Le cas a == 0 est traité à part, avant la boucle, et c’est indispensable : avec a valant 0, la condition a > 0 est fausse dès le départ, la boucle ne tourne jamais et la fonction renverrait la chaîne vide au lieu de '0'.