Exercice 1

EXERCICE 1 (10 points)

Programmer la fonction fusion prenant en paramètres deux tableaux non vides tab1 et tab2 (type list) d’entiers, chacun dans l’ordre croissant, et renvoyant un tableau trié dans l’ordre croissant et contenant l’ensemble des valeurs de tab1 et tab2.

Exemples :

>>> fusion([3, 5], [2, 5])
[2, 3, 5, 5]
>>> fusion([-2, 4], [-3, 5, 10])
[-3, -2, 4, 5, 10]
>>> fusion([4], [2, 6])
[2, 4, 6]
>>> fusion([], [])
[]
>>> fusion([1, 2, 3], [])
[1, 2, 3]

Exercice 2

EXERCICE 2 (10 points)

Le but de cet exercice est d’écrire une fonction récursive traduire_romain qui prend en paramètre une chaîne de caractères, non vide, représentant un nombre écrit en chiffres romains et qui renvoie son écriture décimale.

Les chiffres romains considérés sont : I, V, X, L, C, D et M. Ils représentent respectivement les nombres 1, 5, 10, 50, 100, 500, et 1000 en base dix.

On dispose d’un dictionnaire romains dont les clés sont les caractères apparaissant dans l’écriture en chiffres romains et les valeurs sont les nombres entiers associés en écriture décimale :

romains = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}

Le code de la fonction traduire_romain fournie repose sur le principe suivant :

• la valeur d’un caractère est ajoutée à la valeur du reste de la chaîne si ce caractère a une valeur supérieure (ou égale) à celle du caractère qui le suit ;
• la valeur d’un caractère est retranchée à la valeur du reste de la chaîne si ce caractère a une valeur strictement inférieure à celle du caractère qui le suit.

Ainsi, XIV correspond au nombre 10 + 5 - 1 puisque :

• la valeur de X (10) est supérieure à celle de I (1), on ajoute donc 10 à la valeur du reste de la chaîne, c’est-à-dire IV ;
• la valeur de I (1) est strictement inférieure à celle de V (5), on soustrait donc 1 à la valeur du reste de la chaîne, c’est-à-dire V.

On rappelle que pour priver une chaîne de caractères de son premier caractère, on utilisera l’instruction :

nom_de_variable[1:]

Par exemple, si la variable mot contient la chaîne "CDI", mot[1:] renvoie "DI".

Compléter le code de la fonction traduire_romain et le tester.

def traduire_romain(nombre):
    """ Renvoie l'écriture décimale du nombre donné en chiffres
    romains """
    if len(nombre) == 1:
        return ...
    elif romains[nombre[0]] >= ...:
        return romains[nombre[0]] + ...
    else:
        return ...

Exemples :

>>> traduire_romain("XIV")
14
>>> traduire_romain("CXLII")
142
>>> traduire_romain("MMXXIV")
2024

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

Exercice 1

Contraintes :

• 0 <= len(tab1) <= 10^4 et 0 <= len(tab2) <= 10^4
• tab1 et tab2 sont de type list et ne contiennent que des entiers
• -10^9 <= tab1[i], tab2[i] <= 10^9
• tab1 et tab2 sont triés dans l’ordre croissant
• les doublons sont possibles, à l’intérieur d’un tableau comme entre les deux tableaux ; le tableau renvoyé les conserve tous
• le tableau renvoyé est de type list et contient exactement len(tab1) + len(tab2) valeurs

Exercice 2

Contraintes :

• nombre est une chaîne de caractères avec 1 <= len(nombre) <= 15
• nombre ne contient que des caractères parmi I, V, X, L, C, D et M
• nombre est une écriture romaine valide au sens de la règle décrite dans l’énoncé
• la valeur renvoyée est un entier strictement positif

Corrigé

Exercice 1 - fusion de deux tableaux triés

L’idée. Les deux tableaux sont déjà triés. On n’a donc pas besoin de tout re-trier : il suffit de regarder la première valeur restante de chaque tableau, de prendre la plus petite des deux, et de recommencer. Quand un des deux tableaux est épuisé, on recopie ce qui reste de l’autre, qui est déjà dans le bon ordre.

Un petit exemple. Avec tab1 = [3, 5] et tab2 = [2, 5] : on compare 3 et 2, on prend 2 ; puis 3 et 5, on prend 3 ; puis 5 et 5, on prend le 5 de tab1 ; tab1 est fini, on recopie le 5 restant de tab2. On obtient [2, 3, 5, 5].

def fusion(tab1, tab2):
    resultat = []
    i = 0
    j = 0
    # On avance dans les deux tableaux en prenant a chaque tour la plus petite tete
    while i < len(tab1) and j < len(tab2):
        if tab1[i] <= tab2[j]:
            resultat.append(tab1[i])
            i = i + 1
        else:
            resultat.append(tab2[j])
            j = j + 1
    # Un seul des deux tableaux peut encore contenir des valeurs : on le recopie
    while i < len(tab1):
        resultat.append(tab1[i])
        i = i + 1
    while j < len(tab2):
        resultat.append(tab2[j])
        j = j + 1
    return resultat

i et j retiennent où on en est dans tab1 et dans tab2, et resultat accumule les valeurs déjà placées. La première boucle s’arrête dès qu’un des deux tableaux est fini ; les deux boucles suivantes vident celui qui restait, et une seule des deux tourne réellement. Le <= plutôt que < garde les doublons : si la même valeur est dans les deux tableaux, elle apparaît bien deux fois. Enfin, si un tableau est vide, la première boucle ne fait aucun tour et le code recopie simplement l’autre : les cas fusion([], []) et fusion([1, 2, 3], []) marchent sans écrire de cas particulier.

Exercice 2 - traduire un nombre romain

L’idée. On traite la chaîne caractère par caractère, en s’appuyant sur la traduction du reste de la chaîne. On regarde le premier caractère et celui qui le suit :

• si le premier vaut au moins autant que le suivant, on ajoute sa valeur à la traduction du reste ;
• s’il vaut strictement moins, c’est un cas soustractif (comme IV ou XL) et on retranche sa valeur à la traduction du reste.

Le cas d’arrêt est une chaîne d’un seul caractère : il n’y a plus de suivant, on renvoie directement sa valeur lue dans romains.

Un petit exemple. Pour "XIV" : X (10) vaut plus que I (1), donc le résultat est 10 + traduire_romain("IV"). Pour "IV" : I (1) vaut moins que V (5), donc le résultat est traduire_romain("V") - 1, c’est-à-dire 5 - 1 = 4. Au total 10 + 4 = 14.

romains = {"I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000}


def traduire_romain(nombre):
    """ Renvoie l'écriture décimale du nombre donné en chiffres
    romains """
    if len(nombre) == 1:
        return romains[nombre[0]]
    elif romains[nombre[0]] >= romains[nombre[1]]:
        # Le caractere vaut au moins son suivant : sa valeur s'ajoute au reste
        return romains[nombre[0]] + traduire_romain(nombre[1:])
    else:
        # Cas soustractif (IV, IX, XL...) : on retranche au reste de la chaine
        return traduire_romain(nombre[1:]) - romains[nombre[0]]

nombre[0] est le premier caractère et nombre[1] celui qui le suit ; romains[nombre[0]] est donc la valeur du premier chiffre romain. nombre[1:] est la chaîne privée de son premier caractère : c’est sur elle qu’on rappelle la fonction, et comme elle est à chaque fois plus courte d’un caractère, on finit toujours par tomber sur le cas d’arrêt len(nombre) == 1.

Attention à l’ordre dans la dernière ligne : on écrit bien traduire_romain(nombre[1:]) - romains[nombre[0]], car c’est la valeur du premier caractère qui est retranchée à celle du reste, et non l’inverse. Le test de la branche elif utilise >= et non > : deux chiffres identiques qui se suivent, comme dans "II", s’additionnent bien.