Solution de Occurrences des caractères d'une chaîne - Sujet 07 - EP NSI 2025

Résoudre ce problème
Moyen Officiel
Python (3.14.0)

Énoncé du problème

Exercice 1

EXERCICE 1 (10 points)

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 les occurrences des caractères dans une phrase. On souhaite stocker ces occurrences dans un dictionnaire dont les clefs seraient les caractères de la phrase et les valeurs l’occurrence de ces caractères.

Par 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’a 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.

Exercice 2

EXERCICE 2 (10 points)

La fonction fusion prend deux tableaux tab1, tab2 (type list) d’entiers triés par ordre croissant et les fusionne en un tableau trié tab12 qu’elle renvoie.

Compléter le code de la fonction fusion ci-dessous.

def fusion(tab1,tab2):
    '''Fusionne deux tableaux triés et renvoie
    le nouveau tableau trié.'''
    n1 = len(tab1)
    n2 = len(tab2)
    tab12 = [0] * (n1 + n2)
    i1 = 0
    i2 = 0
    i = 0
    while i1 < n1 and ...:
        if tab1[i1] < tab2[i2]:
            tab12[i] = ...
            i1 = ...
        else:
            tab12[i] = tab2[i2]
            i2 = ...
        i += 1
    while i1 < n1:
        tab12[i] = ...
        i1 = i1 + 1
        i = ...
    while i2 < n2:
        tab12[i] = ...
        i2 = i2 + 1
        i = ...
    return tab12

Exemple :

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

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

Exercice 1

Contraintes :

  • chaine est une chaîne de caractères (type str)
  • 0 <= len(chaine) <= 10^4
  • chaine peut contenir des lettres (accentuées comprises), des chiffres, des espaces et des signes de ponctuation
  • la casse est significative : 'B' et 'b' sont deux clefs distinctes
  • si chaine est vide, la fonction renvoie le dictionnaire vide {}
  • l’ordre des clefs du dictionnaire renvoyé n’a pas d’importance

Exercice 2

Contraintes :

  • tab1 et tab2 sont des tableaux (type list) d’entiers
  • 0 <= len(tab1) <= 10^4 et 0 <= len(tab2) <= 10^4
  • -10^9 <= tab1[i], tab2[i] <= 10^9
  • tab1 et tab2 sont triés par ordre croissant
  • les valeurs peuvent être répétées, au sein d’un même tableau comme entre les deux tableaux
  • le tableau renvoyé est trié par ordre croissant et de longueur len(tab1) + len(tab2)

Solution

Corrigé - Sujet 07 - EP NSI 2025

Exercice 1 - nombre d’occurrences des caractères

L’idée. On veut compter, pour chaque caractère de la chaîne, combien de fois il apparaît. On part d’un dictionnaire vide et on parcourt la chaîne caractère par caractère. À chaque caractère, deux cas seulement : soit il est déjà une clef du dictionnaire, et on ajoute 1 à sa valeur ; soit c’est la première fois qu’on le voit, et on crée la clef avec la valeur 1. À la fin du parcours, le dictionnaire contient tous les comptages.

Un petit exemple. Pour 'bob' : on voit 'b' (nouveau, on écrit {'b': 1}), puis 'o' (nouveau, {'b': 1, 'o': 1}), puis 'b' (déjà là, sa valeur passe à 2). On obtient {'b': 2, 'o': 1}.

def nbr_occurrences(chaine):
    occurrences = {}
    for caractere in chaine:
        # Déjà rencontré : on incrémente. Jamais vu : on crée la clef à 1
        if caractere in occurrences:
            occurrences[caractere] = occurrences[caractere] + 1
        else:
            occurrences[caractere] = 1
    return occurrences

occurrences est le dictionnaire que l’on construit petit à petit : ses clefs sont les caractères déjà rencontrés, ses valeurs le nombre de fois qu’on les a vus jusqu’ici. Le test caractere in occurrences regarde si le caractère est déjà une clef du dictionnaire.

On parcourt directement la chaîne avec for caractere in chaine, ce qui donne les caractères un par un, sans avoir besoin d’indices. Remarquez qu’il n’y a rien de spécial à faire pour la chaîne vide : la boucle ne tourne alors aucune fois et on renvoie le dictionnaire vide {}, ce qui est bien le résultat attendu. Attention enfin, la casse compte : 'B' et 'b' sont deux clefs différentes, et l’espace ' ' est un caractère comme un autre, qui a donc aussi sa clef.

Exercice 2 - 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 comparer la première valeur restante de tab1 et la première valeur restante de tab2, d’écrire la plus petite des deux dans le tableau résultat, et de recommencer. Quand l’un des deux tableaux est épuisé, on recopie tout ce qui reste de l’autre : ces valeurs sont déjà dans le bon ordre et sont toutes plus grandes que ce qu’on a écrit avant.

Un petit exemple. Pour tab1 = [1, 6, 10] et tab2 = [0, 7] : on compare 1 et 0, on écrit 0 ; on compare 1 et 7, on écrit 1 ; on compare 6 et 7, on écrit 6 ; on compare 10 et 7, on écrit 7. tab2 est alors fini, il ne reste qu’à recopier le 10. On obtient [0, 1, 6, 7, 10].

def fusion(tab1,tab2):
    '''Fusionne deux tableaux triés et renvoie
    le nouveau tableau trié.'''
    n1 = len(tab1)
    n2 = len(tab2)
    tab12 = [0] * (n1 + n2)
    i1 = 0
    i2 = 0
    i = 0
    # Tant que les deux tableaux ont encore des valeurs, on écrit la plus petite des deux têtes
    while i1 < n1 and i2 < n2:
        if tab1[i1] < tab2[i2]:
            tab12[i] = tab1[i1]
            i1 = i1 + 1
        else:
            tab12[i] = tab2[i2]
            i2 = i2 + 1
        i += 1
    # Un seul des deux tableaux peut encore contenir des valeurs : on recopie ce qui reste
    while i1 < n1:
        tab12[i] = tab1[i1]
        i1 = i1 + 1
        i = i + 1
    while i2 < n2:
        tab12[i] = tab2[i2]
        i2 = i2 + 1
        i = i + 1
    return tab12

Il y a trois compteurs, et c’est le point à bien comprendre : i1 dit où on en est dans tab1, i2 où on en est dans tab2, et i où on en est dans tab12, le tableau que l’on remplit. Chaque tour de boucle écrit exactement une valeur, donc i avance à chaque tour, alors que i1 et i2 n’avancent que quand c’est leur valeur qui a été choisie.

La première boucle s’arrête dès que l’un des deux tableaux est épuisé, d’où le and : il faut qu’il reste des valeurs des deux côtés pour pouvoir comparer. Ensuite, une seule des deux boucles suivantes tourne réellement, celle du tableau qui n’était pas fini ; l’autre s’arrête tout de suite. C’est aussi pour cela qu’il n’y a rien à traiter à part pour les tableaux vides : si tab1 et tab2 sont vides, tab12 vaut [0] * 0, c’est-à-dire [], aucune boucle ne tourne, et on renvoie bien [].

On note enfin que tab12 a été créé d’avance à la bonne taille, n1 + n2 cases. On n’ajoute donc rien à la fin du tableau : on écrit dans la case i avec tab12[i] = ....