Sujet n°24

Sujet original

Pour télécharger l'énoncé original, cliquer ici.

Exercice n°1

Le nombre d’occurrences d’un caractère dans une chaîne de caractère est le nombre d’apparitions de ce caractère dans la chaîne.

Exemples

• le nombre d’occurrences du caractère 'o' dans 'bonjour' est 2 ;
• le nombre d’occurrences du caractère 'b' dans 'Bébé' est 1 ;
• le nombre d’occurrences du caractère 'B' dans 'Bébé' est 1 ;
• le nombre d’occurrences du caractère ' ' dans 'Hello world !' est 2.

On cherche le nombre d’occurrences des caractères dans une chaîne de caractères. On souhaite stocker ces nombres d’occurrences dans un dictionnaire dont les clefs seraient les caractères de la chaîne et les valeurs le nombre d’occurrences de ces caractères.

Exemple

Avec la phrase 'Hello world !' le dictionnaire est le suivant :

{'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 2, 'w': 1, 'r': 1, 'd': 1, '!': 1}

L’ordre des clefs n’ayant pas d’importance.

Écrire une fonction nbr_occurrences prenant comme paramètre une chaîne de caractères chaine et renvoyant le dictionnaire des nombres d’occurrences des caractères de cette chaîne.

Une solution

def nbr_occurrences(chaine):
    """
    chaine - str
    Sortie: dict, dictionnaire tel que :
            - les clefs sont les caractères présents dans chaine
            - les valeurs associées sont le nombre d'occurrences de ces caractères dans chaine.
    """
    dico = dict()
    for carac in chaine:
        if carac in dico.keys():
            dico[carac] += 1
        else:
            dico[carac] = 1
    return dico


if __name__ == '__main__':
    # Exemple de l'énoncé
    print(nbr_occurrences('Hello world !') == {'H': 1,'e': 1,'l': 3,'o': 2,' ': 2,'w': 1,'r': 1,'d': 1,'!': 1})

    # Exemples supplémentaires
    print(nbr_occurrences('Je teste un exemple.') == {'J': 1, 'e': 6, ' ': 3, 't': 2, 's': 1, 'u': 1, 'n': 1, 'x': 1, 'm': 1, 'p': 1, 'l': 1, '.': 1})
    print(nbr_occurrences('Un dernier exemple') == {'U': 1, 'n': 2, ' ': 2, 'd': 1, 'e': 5, 'r': 2, 'i': 1, 'x': 1, 'm': 1, 'p': 1, 'l': 1})

Exercice n°2

La fonction fusion prend deux listes lst1, lst2 d’entiers triées par ordre croissant et les fusionne en une liste triée lst12 qu’elle renvoie.

Commentaires

1. Ici, le mot « liste » est à comprendre dans le sens « liste Python » (c'est-à-dire tableau) plutôt que dans le sens du type abstrait de données liste étudié en Terminale.
2. Le sujet est adapté d'une version de 2022, mais la mise à jour des noms L1, L2 et L12 vers lst1, lst2 et lst12 est incomplète...

Le code Python de la fonction fusion est :

def fusion(lst1, lst2):
    n1 = len(lst1)
    n2 = len(lst2)
    lst12 = [0] * (n1 + n2)
    i1 = 0
    i2 = 0
    i = 0
    while i1 < n1 and ... :
        if lst1[i1] < lst2[i2]:
            lst12[i] = ...
            i1 = ...
        else:
            lst12[i] = lst2[i2]
            i2 = ...
        i += 1
    while i1 < n1:
        lst12[i] = ...
        i1 = i1 + 1
        i = ...
    while i2 < n2:
        lst12[i] = ...
        i2 = i2 + 1
        i = ...
    return lst12

Commentaire sur le code original

1. Pour télécharger l'original du fichier à compléter, cliquer ici.

2. C'est une application « classique » de l'algorithme de tri fusion.

Compléter le code.

Exemple

>>> fusion([1, 6, 10], [0, 7, 8, 9])
[0, 1, 6, 7, 8, 9, 10]

Une solution

def fusion(lst1, lst2):
    n1 = len(lst1)
    n2 = len(lst2)
    lst12 = [0]*(n1+n2)
    i1 = 0
    i2 = 0
    i = 0
    while i1 < n1 and i2 < n2 :
        if lst1[i1] < lst2[i2]:
            lst12[i] = lst1[i1]
            i1 = i1+1
        else:
            lst12[i] = lst2[i2]
            i2 = i2+1
        i += 1
    while i1 < n1:
        lst12[i] = lst1[i1]
        i1 = i1 + 1
        i = i+1
    while i2 < n2:
        lst12[i] = lst2[i2]
        i2 = i2 + 1
        i = i+1
    return lst12



if __name__ == '__main__':
    # Exemple de l'énoncé
    print(fusion([1, 6, 10], [0, 7, 8, 9]) == [0, 1, 6, 7, 8, 9, 10])

    # Exemples supplémentaires
    print(fusion([1, 6, 10, 11], [0, 7, 8]) == [0, 1, 6, 7, 8, 10, 11])
    print(fusion([1, 6, 6, 6, 10], [0, 6, 7, 7, 8, 9, 9]) == [0, 1, 6, 6, 6, 6, 7, 7, 8, 9, 9, 10])