Aller au contenu

Sujet n°17

Sujet original

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

Exercice n°1

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 ' '. Une « phrase » se fini 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 quatre exemples de phrases :

  • 'Le point d exclamation est separe !'
  • 'Il y a un seul espace entre les mots !'
  • 'Le point final est colle au dernier mot.'
  • 'Gilbouze macarbi acra cor ed filbuzine ?'

Après avoir remarqué le lien entre le nombre de mots et le nombres 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.

Exemples

>>> nombre_de_mots('Le point d exclamation est separe !')
6
>>> nombre_de_mots('Il y a un seul espace entre les mots.')
9
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def nombre_de_mots(phrase):
    nb_mots = 0
    for carac in phrase:
        if carac == ' ':
            nb_mots += 1
    if phrase[len(phrase)-1] == '.':
        nb_mots += 1
    return nb_mots



if __name__ == '__main__':
    print(nombre_de_mots('Le point d exclamation est separe !') == 6)

    print(nombre_de_mots('Il y a un seul espace entre les mots.') == 9)

    print(nombre_de_mots('Bravo vous avez bien codé la fonction !') == 7)

    print(nombre_de_mots('Quelle est la meilleur manière de coder ?') == 7)

Exercice n°2

La classe ABR permet d'implémenter une structure d'arbre binaire de recherche :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Noeud:
    ''' Classe implémentant un noeud d'arbre binaire
    disposant de 3 attributs :
    - valeur : la valeur de l'étiquette,
    - gauche : le sous-arbre gauche.
    - droit : le sous-arbre droit. '''

    def __init__(self, v, g, d):
        self.valeur = v
        self.gauche = g
        self.droite = d

class ABR:
    '''Classe implémentant une structure
    d'arbre binaire de recherche. '''

    def __init__(self):
        '''Crée un arbre binaire de recherche vide'''
        self.racine = None

    def est_vide(self):
        '''Renvoie True si l'ABR est vide et False sinon.'''
        return self.racine is None

    def parcours(self, tab = []):
        '''Renvoie la liste tab complétée avec tous les
        éléments de l'ABR triés par ordre croissant. '''
        if self.est_vide():
            return tab
        else:
            self.racine.gauche.parcours(tab)
            tab.append(...)
            ...
            return tab

    def insere(self, element):
        '''Insère un élément dans l'arbre binaire de recherche.'''
        if self.est_vide():
            self.racine = Noeud(element, ABR(), ABR())
        else:
            if element < self.racine.valeur:
                self.racine.gauche.insere(element)
            else :
                self.racine.droite.insere(element)

    def recherche(self, element):
        '''
        Renvoie True si element est présent dans l'arbre
        binaire et False sinon.
        '''
        if self.est_vide():
            return ...
        else:
            if element < self.racine.valeur:
                return ...
            elif element > self.racine.valeur:
                return ...
            else:
                return ...
Commentaire sur le code original
  1. Pour télécharger l'original du fichier à compléter, cliquer ici.

  2. Le code original fait référence à des « listes », ce qui signifie des « listes Python », des tableaux plutôt que la notion de liste étudiée en Terminale.

Compléter les méthodes récursives .parcours() et .recherche() afin qu'elles respectent leurs spécifications.

Exemple

>>> a = ABR()
>>> a.insere(7)
>>> a.insere(3)
>>> a.insere(9)
>>> a.insere(1)
>>> a.insere(9)
>>> a.parcours()
[1, 3, 7, 9, 9]

>>> a.recherche(4)
False

>>> a.recherche(3)
True
Une solution
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Noeud:
    ''' Classe implémentant un noeud d'arbre binaire
    disposant de 3 attributs :
    - valeur : la valeur de l'étiquette,
    - gauche : le sous-arbre gauche.
    - droit : le sous-arbre droit. '''

    def __init__(self, v, g, d):
        self.valeur = v
        self.gauche = g
        self.droite = d

class ABR:
    '''Classe implémentant une structure
    d'arbre binaire de recherche. '''

    def __init__(self):
        '''Crée un arbre binaire de recherche vide'''
        self.racine = None

    def est_vide(self):
        '''Renvoie True si l'ABR est vide et False sinon.'''
        return self.racine is None

    def parcours(self, tab = []):
        '''Renvoie la liste tab complétée avec tous les
        éléments de l'ABR triés par ordre croissant. '''
        if self.est_vide():
            return tab
        else:
            self.racine.gauche.parcours(tab)
            tab.append(self.racine.valeur)
            self.racine.droite.parcours(tab)
            return tab

    def insere(self, element):
        '''Insère un élément dans l'arbre binaire de recherche.'''
        if self.est_vide():
            self.racine = Noeud(element, ABR(), ABR())
        else:
            if element < self.racine.valeur:
                self.racine.gauche.insere(element)
            else :
                self.racine.droite.insere(element)

    def recherche(self, element):
        '''
        Renvoie True si element est présent dans l'arbre
        binaire et False sinon.
        '''
        if self.est_vide():
            return False
        else:
            if element < self.racine.valeur:
                return self.racine.gauche.recherche(element)
            elif element > self.racine.valeur:
                return self.racine.droite.recherche(element)
            else:
                return True


if __name__ == '__main__':
    from random import randint
    a = ABR()
    a.insere(7)
    a.insere(3)
    a.insere(9)
    a.insere(1)
    a.insere(9)
    print(a.parcours() == [1, 3, 7, 9, 9])
    print(a.recherche(4) == False)
    print(a.recherche(3) == True)

    t = [randint(0, 20) for _ in range(8)]
    a = ABR()
    for elt in t:
        a.insere(elt)
    print(t)
    print(a.parcours())
    print("Y a-t-il 4 ?", a.recherche(4))
    print("Y a-t-il 12 ?", a.recherche(12))