EXERCICE 1 (10 points)

On veut trier par ordre croissant les notes d’une évaluation qui sont des nombres entiers compris entre 0 et 10 (inclus).

Ces notes sont contenues dans un tableau notes_eval (type list).

Écrire une fonction effectif_notes prenant en paramètre le tableau notes_eval et renvoyant un tableau de longueur 11 tel que la valeur d’indice i soit le nombre de notes valant i dans le tableau notes_eval.

Écrire ensuite une fonction notes_triees prenant en paramètre le tableau des effectifs des notes et renvoyant un tableau contenant les mêmes valeurs que notes_eval mais triées dans l’ordre croissant.

Exemple :

>>> notes_eval = [2, 0, 5, 9, 6, 9, 10, 5, 7,
                  9, 9, 5, 0, 9, 6, 5, 4]
>>> eff = effectif_notes(notes_eval)
>>> eff
[2, 0, 1, 0, 1, 4, 2, 1, 0, 5, 1]

>>> notes_triees(eff)
[0, 0, 2, 4, 5, 5, 5, 5, 6, 6, 7, 9, 9, 9, 9, 9, 10]

EXERCICE 2 (10 points)

L’objectif de cet exercice est d’écrire deux fonctions récursives dec_to_bin et bin_to_dec assurant respectivement la conversion de l’écriture décimale d’un nombre entier vers son écriture en binaire et, réciproquement, la conversion de l’écriture en binaire d’un nombre vers son écriture décimale.

Dans cet exercice, on s’interdit l’usage des fonctions Python bin et int.

L’exemple suivant montre comment obtenir l’écriture en binaire du nombre 25 :

[Figure : suite d’égalités alignées présentant la décomposition de 25 : 25 = 2 × 12 + 1 = 2 × (2 × 6 + 0) + 1 = 2 × (2 × (2 × 3 + 0) + 0) + 1 = 2 × (2 × (2 × (2 × 1 + 1) + 0) + 0) + 1 = 2 × (2 × (2 × (2 × (2 × 0 + 1) + 1) + 0) + 0) + 1 = 1 × 2⁴ + 1 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰ = 11001₂]

L’écriture binaire de 25 est donc 11001.

On rappelle également que

• l’expression a // 2 calcule le quotient de la division euclidienne de a par 2 ;
• l’expression a % 2 calcule le reste dans la division euclidienne de a par 2.

On indique enfin qu’en Python si mot = "informatique", alors

• l’expression mot[-1] vaut 'e', c’est-à-dire le dernier caractère de la chaîne de caractères mot ;
• l’expression mot[:-1] vaut 'informatiqu', c’est-à-dire l’ensemble de la chaîne de caractères mot privée de son dernier caractère.

Compléter, puis tester, le code des deux fonctions situées à la page suivante.

On précise que la fonction récursive dec_to_bin prend en paramètre un nombre entier et renvoie une chaîne de caractères contenant l’écriture en binaire du nombre passé en paramètre.

Exemple :

>>> dec_to_bin(25)
'11001'

La fonction récursive bin_to_dec prend en paramètre une chaîne de caractères représentant l’écriture d’un nombre en binaire et renvoie l’écriture décimale de ce nombre.

>>> bin_to_dec('101010')
42

def dec_to_bin(nb_dec):
    q, r = nb_dec // 2, nb_dec % 2
    if q == ...:
        return ...
    else:
        return dec_to_bin(...) + ...

def bin_to_dec(nb_bin):
    if len(nb_bin) == 1:
        if ... == '0':
            return 0
        else:
            return ...
    else:
        if nb_bin[-1] == '0':
            bit_droit = 0
        else:
            ...
        return ... * bin_to_dec(nb_bin[:-1]) + ...

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

Exercice 1

Contraintes :

• 0 <= len(notes_eval) <= 10^4 (le tableau peut être vide)
• notes_eval[i] est un entier et 0 <= notes_eval[i] <= 10
• effectif_notes renvoie un tableau (type list) de longueur exactement 11
• notes_triees prend en paramètre un tableau d’effectifs de longueur 11 composé d’entiers positifs ou nuls, tel que celui renvoyé par effectif_notes
• si tous les effectifs sont nuls, notes_triees renvoie le tableau vide

Exercice 2

Contraintes :

• nb_dec est un entier et 0 <= nb_dec <= 10^9
• dec_to_bin renvoie une chaîne de caractères composée uniquement des caractères '0' et '1' ; dec_to_bin(0) vaut '0'
• nb_bin est une chaîne de caractères composée uniquement des caractères '0' et '1', avec 1 <= len(nb_bin) <= 64
• les zéros de tête sont autorisés dans nb_bin : '00101' représente la même valeur que '101'
• bin_to_dec renvoie un entier
• les fonctions bin et int ne doivent pas être utilisées

Corrigé - Sujet 23

Exercice 1 - tri par comptage des notes

L’idée. Les notes sont des entiers entre 0 et 10, il n’y a donc que 11 valeurs possibles. Plutôt que de comparer les notes entre elles, on compte combien de fois chaque valeur apparaît : c’est le rôle de effectif_notes. Une fois ce comptage fait, trier ne demande plus aucune comparaison : on parcourt les notes de 0 à 10 dans l’ordre et on réécrit chaque note autant de fois qu’elle a été comptée. C’est notes_triees.

Un petit exemple. Pour [2, 0, 5, 0], le comptage donne [2, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0] : deux fois la note 0, une fois la note 2, une fois la note 5. En relisant ce tableau de gauche à droite, on écrit 0, 0, puis 2, puis 5, soit [0, 0, 2, 5].

def effectif_notes(notes_eval):
    effectifs = [0] * 11
    for note in notes_eval:
        # la note elle-même sert d'indice dans le tableau des effectifs
        effectifs[note] = effectifs[note] + 1
    return effectifs


def notes_triees(effectifs):
    resultat = []
    for note in range(11):
        for compteur in range(effectifs[note]):
            resultat.append(note)
    return resultat

Explications. Dans effectif_notes, effectifs est un tableau de 11 cases, toutes à zéro au départ (les indices vont de 0 à 10, ce qui correspond exactement aux notes possibles). L’astuce est d’utiliser la note comme indice : voir la note 5 revient à ajouter 1 dans la case numéro 5.

Dans notes_triees, la boucle extérieure parcourt les notes dans l’ordre croissant, de 0 à 10 : c’est elle qui garantit que le résultat est trié. La boucle intérieure recopie la note effectifs[note] fois ; si l’effectif vaut 0, range(0) est vide et la boucle ne fait rien, donc la note absente n’apparaît pas. Si le tableau de départ est vide, tous les effectifs sont nuls et notes_triees renvoie bien le tableau vide.

Exercice 2 - conversions décimal / binaire récursives

L’idée. Pour écrire nb_dec en binaire, on le divise par 2 : le reste r est le dernier chiffre binaire, et le quotient q est le nombre qu’il reste à convertir. On recommence donc sur q, et on colle r à la fin de ce qu’on obtient. On s’arrête quand q vaut 0 : il ne reste plus qu’un seul chiffre, r.

Dans l’autre sens, une écriture binaire se lit comme un nombre en base 2 : le dernier caractère vaut 0 ou 1, et tout ce qui est devant représente un nombre qu’il suffit de multiplier par 2 pour le décaler d’un rang. D’où 2 * bin_to_dec(nb_bin[:-1]) + bit_droit. On s’arrête quand la chaîne n’a plus qu’un seul caractère.

Un petit exemple. 25 = 2 * 12 + 1, donc le dernier chiffre est 1 et il reste à convertir 12. Puis 12 = 2 * 6 + 0, 6 = 2 * 3 + 0, 3 = 2 * 1 + 1, et enfin 1 = 2 * 0 + 1 où le quotient est nul : on renvoie '1'. En recollant les restes dans le sens du retour : '11001'.

def dec_to_bin(nb_dec):
    q, r = nb_dec // 2, nb_dec % 2
    if q == 0:
        return str(r)
    else:
        # le reste r est le dernier chiffre : on convertit q puis on colle r à la fin
        return dec_to_bin(q) + str(r)

def bin_to_dec(nb_bin):
    if len(nb_bin) == 1:
        if nb_bin == '0':
            return 0
        else:
            return 1
    else:
        if nb_bin[-1] == '0':
            bit_droit = 0
        else:
            bit_droit = 1
        # tout ce qui précède le dernier bit est décalé d'un rang, donc multiplié par 2
        return 2 * bin_to_dec(nb_bin[:-1]) + bit_droit

Explications. Dans dec_to_bin, q et r sont le quotient et le reste de la division par 2. Le cas d’arrêt est q == 0 : le nombre tient alors sur un seul chiffre binaire, et on renvoie str(r), c’est-à-dire '0' ou '1'. Attention à l’ordre dans le cas récursif : c’est dec_to_bin(q) + str(r) et pas l’inverse, car les chiffres de poids fort sont à gauche. On utilise str pour transformer le chiffre en caractère, ce qui est autorisé : seules bin et int sont interdites.

Dans bin_to_dec, bit_droit vaut la valeur du dernier caractère, 0 ou 1. Comme on ne peut pas utiliser int, on la retrouve avec un simple test. Chaque appel retire un caractère à droite, donc la chaîne raccourcit à chaque fois et la récursion s’arrête forcément sur le cas len(nb_bin) == 1. Les zéros de tête ne gênent pas : bin_to_dec('00101') fait 2 * 2 = 4 puis + 1, soit 5, la même valeur que bin_to_dec('101').