Exercice 1

Dans cet exercice, on considère des phrases composées de mots.

• On appelle mot une chaîne de caractères composée avec des caractères choisis parmi les 26 lettres minuscules ou majuscules de l’alphabet.
• On appelle phrase une chaîne de caractères :
  • composée avec un ou plusieurs mots séparés entre eux par un seul caractère espace ' ',
  • se finissant :
    • soit par un point '.' qui est alors collé au dernier mot,
    • soit par un point d’exclamation '!' ou d’interrogation '?' qui est alors séparé du dernier mot par un seul caractère espace ' '.

Voici deux exemples de phrases :

'Cet exercice est simple.'
'Le point d exclamation est separe !'

Après avoir remarqué le lien entre le nombre de mots et le nombre de caractères espace dans une phrase, programmer une fonction nombre_de_mots qui prend en paramètre une phrase et renvoie le nombre de mots présents dans cette phrase.

>>> nombre_de_mots('Cet exercice est simple.')
4
>>> nombre_de_mots('Le point d exclamation est séparé !')
6
>>> nombre_de_mots('Combien de mots y a t il dans cette phrase ?')
10
>>> nombre_de_mots('Fin.')
1

Exercice 2

Un arbre binaire de recherche est soit vide, représenté en Python par la valeur None, soit un nœud, contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance de la classe Noeud donnée ci-dessous.

On considère ici que les étiquettes des nœuds sont des entiers et que les arbres binaires de recherche considérés ne contiennent pas de doublons.

class Noeud:
    def __init__(self, etiquette):
        '''Méthode constructeur pour la classe Noeud.
        Crée une feuille d'étiquette donnée.'''
        self.etiquette = etiquette
        self.gauche = None
        self.droit = None

    def inserer(self, cle):
        '''Insère la clé dans l'arbre binaire de recherche
        en préservant sa structure.'''
        if cle < self.etiquette:
            if self.gauche != None:
                ...
            else:
                self.gauche = ...
        else:
            ...
                ...
            else:
                ... = Noeud(cle)

Compléter la méthode récursive inserer afin qu’elle permette d’insérer une clé dans l’arbre binaire de recherche non vide sur lequel on l’appelle.

Voici un exemple d’utilisation :

>>> arbre = Noeud(7)
>>> for cle in (3, 9, 1, 6):
        arbre.inserer(cle)
>>> arbre.gauche.etiquette
3
>>> arbre.droit.etiquette
9
>>> arbre.gauche.gauche.etiquette
1
>>> arbre.gauche.droit.etiquette
6

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

Exercice 1

Contraintes :

• phrase est une chaîne de caractères (str) toujours bien formée au sens de la définition de phrase donnée ci-dessus
• 1 <= nombre de mots de phrase <= 60
• 1 <= longueur de chaque mot <= 20
• len(phrase) <= 1000
• les mots sont séparés entre eux par un seul caractère espace ' ', et il n’y a ni espace en début de phrase ni espace multiple
• phrase se termine soit par '.' collé au dernier mot, soit par ' !' ou ' ?' (un seul espace avant le signe)
• la fonction renvoie un entier (int)

Exercice 2

Contraintes :

• les étiquettes et les clés sont des entiers (int) avec -10^4 <= etiquette, cle <= 10^4
• l’arbre ne contient pas de doublons et cle n’est pas déjà présente dans l’arbre
• inserer est toujours appelée sur un arbre non vide, c’est-à-dire sur une instance existante de Noeud
• au plus 10^3 appels à inserer sont effectués sur un même arbre
• inserer ne renvoie rien : elle modifie l’arbre en place en préservant sa structure d’arbre binaire de recherche

Corrigé

Exercice 1 - nombre de mots dans une phrase

L’idée. Il n’est pas nécessaire de découper la phrase : il suffit de compter les espaces. Entre deux mots voisins il y a exactement un espace, donc une phrase de n mots contient n - 1 espaces. Mais quand la phrase se termine par ! ou ?, un espace de plus sépare ce signe du dernier mot ; cet espace-là ne sépare pas deux mots, et le compte tombe alors exactement sur n. On compte donc les espaces, puis on regarde le dernier caractère pour savoir s’il faut ajouter 1 ou non.

Un petit exemple. 'Fin.' ne contient aucun espace et se termine par un point : 0 + 1 = 1 mot. 'Quoi ?' contient un espace et se termine par ? : cela fait 1 mot aussi.

def nombre_de_mots(phrase):
    nombre_espaces = 0
    for caractere in phrase:
        if caractere == ' ':
            nombre_espaces = nombre_espaces + 1
    # Un point est collé au dernier mot : il y a alors un espace de moins que de mots.
    # Avec '!' ou '?', l'espace qui les précède ne sépare pas deux mots : les nombres coïncident.
    if phrase[-1] == '.':
        return nombre_espaces + 1
    else:
        return nombre_espaces

Quelques explications. nombre_espaces est un simple compteur : la boucle parcourt la phrase caractère par caractère et l’augmente de 1 à chaque espace rencontré. phrase[-1] est le dernier caractère de la chaîne, celui qui décide du cas dans lequel on se trouve. On ne regarde jamais quelles lettres composent les mots : seuls les espaces et la ponctuation finale servent au calcul, donc les lettres accentuées ne posent aucun problème.

Exercice 2 - insertion dans un arbre binaire de recherche

L’idée. Insérer une clé, c’est descendre jusqu’à la place que lui impose la règle de rangement de l’arbre : plus petite que l’étiquette, elle va à gauche ; sinon, elle va à droite. À chaque nœud rencontré il n’y a donc que deux situations possibles. Soit le sous-arbre où l’on veut aller existe déjà, et on relance la même méthode sur lui : c’est la récursivité. Soit il est vide (None), et c’est justement la place cherchée : on y accroche une nouvelle feuille Noeud(cle). Le squelette donné dans le sujet dessine exactement ces quatre cas.

Un petit exemple. Dans l’arbre de racine 7 qui a déjà 3 comme fils gauche, insérons 6. Comme 6 < 7, on part à gauche ; le sous-arbre gauche existe (c’est le nœud 3), donc on rappelle inserer(6) sur lui. Là, 6 n’est pas plus petit que 3, on part à droite ; le fils droit de 3 vaut None, donc 6 devient ce fils droit.

class Noeud:
    def __init__(self, etiquette):
        '''Méthode constructeur pour la classe Noeud.
        Crée une feuille d'étiquette donnée.'''
        self.etiquette = etiquette
        self.gauche = None
        self.droit = None

    def inserer(self, cle):
        '''Insère la clé dans l'arbre binaire de recherche
        en préservant sa structure.'''
        if cle < self.etiquette:
            if self.gauche != None:
                # Le sous-arbre gauche existe : on relance la recherche dedans
                self.gauche.inserer(cle)
            else:
                self.gauche = Noeud(cle)
        else:
            if self.droit != None:
                self.droit.inserer(cle)
            else:
                # Place libre à droite : on accroche la nouvelle feuille ici
                self.droit = Noeud(cle)

Quelques explications. La méthode ne renvoie rien : elle modifie l’arbre en place, en changeant un attribut gauche ou droit. Les deux branches sont symétriques, seul le côté change. Chaque appel récursif descend d’un niveau dans l’arbre, et la descente finit toujours par tomber sur un sous-arbre vide : c’est ce qui garantit que la récursion s’arrête. Enfin, comme le sujet précise que l’arbre ne contient pas de doublons, le cas où cle serait égale à self.etiquette ne se présente pas : la branche else signifie donc simplement « la clé est plus grande ».