Sujet n°40
Sujet original
Pour télécharger l'énoncé original, cliquer ici.
Exercice n°1
Pour cet exercice :
-
On appelle « mot » une chaîne de caractères composée de caractères choisis
parmi les 26 lettres minuscules ou majuscules de l'alphabet,
-
On appelle « phrase » une chaîne de caractères :
- composée d’un ou de 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 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('Cet exercice est simple.')
4
>>> nombre_de_mots('Le point d exclamation est separe !')
6
>>> nombre_de_mots('Combien de mots y a t il dans cette phrase ?')
10
>>> nombre_de_mots('Fin.')
1
Une solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | 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__':
# Exemples de l'énoncé
print(nombre_de_mots('Cet exercice est simple.') == 4)
print(nombre_de_mots('Le point d exclamation est separe !') == 6)
print(nombre_de_mots('Combien de mots y a t il dans cette phrase ?') == 10)
print(nombre_de_mots('Fin.') == 1)
# Exemples supplémentaires
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 Noeud ci-dessous permet d'implémenter une structure d'arbre binaire de
recherche (ABR). On considère que la clé d’un nœud est un entier et qu’elle est
unique dans l’ABR.
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 | class Noeud:
def __init__(self, valeur):
'''Méthode constructeur pour la classe Noeud.
Paramètre d'entrée : valeur (int)'''
self.valeur = valeur
self.gauche = None
self.droit = None
def getValeur(self):
'''Méthode accesseur pour obtenir la valeur du noeud
Aucun paramètre en entrée'''
return self.valeur
def droitExiste(self):
'''Méthode renvoyant True si le sous-arbre droit est non vide
Aucun paramètre en entrée'''
return (self.droit is not None)
def gaucheExiste(self):
'''Méthode renvoyant True si le sous-arbre gauche est non vide
Aucun paramètre en entrée'''
return (self.gauche is not None)
def inserer(self, cle):
'''Méthode d'insertion de clé dans un arbre binaire de recherche
Paramètre d'entrée : cle (int)'''
if cle < ... :
# on insère à gauche
if self.gaucheExiste():
# on descend à gauche et on recommence le test initial
...
else:
# on crée un fils gauche
self.gauche = ...
elif cle > ... :
# on insère à droite
if ... :
# on descend à droite et on recommence le test initial
...
else:
# on crée un fils droit
... = Noeud(cle)
|
Commentaire sur le code original
Pour télécharger l'original du fichier à compléter,
cliquer ici.
Compléter la fonction récursive inserer afin qu'elle permette d’insérer un nœud
dans l’arbre binaire de recherche proposé, à l’aide de sa clé.
Exemple
Voici un exemple d'utilisation :
>>> arbre = Noeud(7)
>>> for cle in (3, 9, 1, 6):
... arbre.inserer(cle)
>>> arbre.gauche.getValeur()
3
>>> arbre.droit.getValeur()
9
>>> arbre.gauche.gauche.getValeur()
1
>>> arbre.gauche.droit.getValeur()
6
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 | class Noeud:
def __init__(self, valeur):
'''Méthode constructeur pour la classe Noeud.
Paramètre d'entrée : valeur (int)'''
self.valeur = valeur
self.gauche = None
self.droit = None
def getValeur(self):
'''Méthode accesseur pour obtenir la valeur du noeud
Aucun paramètre en entrée'''
return self.valeur
def droitExiste(self):
'''Méthode renvoyant True si le sous-arbre droit est non vide
Aucun paramètre en entrée'''
return (self.droit is not None)
def gaucheExiste(self):
'''Méthode renvoyant True si le sous-arbre gauche est non vide
Aucun paramètre en entrée'''
return (self.gauche is not None)
def inserer(self, cle):
'''Méthode d'insertion de clé dans un arbre binaire de recherche
Paramètre d'entrée : cle (int)'''
if cle < self.valeur :
# on insère à gauche
if self.gaucheExiste():
# on descend à gauche et on recommence le test initial
self.gauche.inserer(cle)
else:
# on crée un fils gauche
self.gauche = Noeud(cle)
elif cle > self.valeur :
# on insère à droite
if self.droitExiste() :
# on descend à droite et on recommence le test initial
self.droit.inserer(cle)
else:
# on crée un fils droit
self.droit = Noeud(cle)
if __name__ == '__main__':
# Exemple de l'énoncé
arbre = Noeud(7)
for cle in (3, 9, 1, 6):
arbre.inserer(cle)
print(arbre.gauche.getValeur() == 3)
print(arbre.gauche.gauche.getValeur() == 1)
print(arbre.gauche.droit.getValeur() == 6)
# Exemple supplémentaire
arbre = Noeud(3)
for cle in (1, 2, 4, 5):
arbre.inserer(cle)
print(arbre.gauche.droit.getValeur() == 2)
print(arbre.droit.getValeur() == 4)
print(arbre.droit.droit.getValeur() == 5)
|