5 - Différents algorithmes de parcours
Nous avons vu que parcourir un tableau élément par élément nécessite un algorithme dont le coût est linéaire et sa complexité est 𝓞(n).
Nous allons voir aujourd'hui d'autres algorithmes ayant le même coût mais permettant de faire d'autres choses.
Et aujourd'hui, nous allons voir comment fonctonne un tableur. Quelqu'un l'a bien programmé non ?
Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ...
Prérequis ✎ : Savoir utiliser while, for, if et les tableaux
Evaluation ✎ : questions 02-03-07-13-14-15-20-21.
Documents de cours : open document ou pdf
Le cours : open document ou pdf
1 - Recherche d'un élément
Nous avions déjà vu un algorithme permettant de rechercher un élément dans un tableau dans l'activité précédente :
Algorithme de recherche séquentielle (de la première occurrence)
BUT : trouver la position de la première occurrence de l'élément recherché dans un tableau.
PRINCIPE (en 4 étapes) :
- On commence par la case d'indice 0
- Tant que la case ne possède pas le contenu cherché et qu'il reste des cases, on passe à la case suivante
- Si la valeur finale de l'indice est valide : la réponse est bien l'indice. Sinon, la réponse est -1 ou VIDE car on a atteint la fin du tableau sans trouver.
- On renvoie la réponse
Description des entrées / sortie
- ENTREES :
- t : un tableau contenant n éléments.
- x : l' élément qu'on recherche dans le tableau
- (optionnelle selon les langages d'implémentation) longueur, le nombre d'éléments dans le tableau t
- SORTIE : un entier valant
- soit l'indice où se trouve la première occurrence de l'élément x cherché.
- soit -1 si l'élément x n'est pas présent dans le tableau
Description de l'algorithme
i ← 0
TANT QUE i < longueur ET que t[i] est différent de x
i ← i + 1
Fin TANT QUE
SI i < longueur
reponse ← i
SINON
reponse ← -1
Fin Si
Renvoyer reponse
Implémentation TANT QUE ou POUR d'un même algorithme
Un algorithme doit être implémenté en machine si on veut l'utiliser autrement qu'à la main. Implémenter veut donc dire "programmer cet algorithme dans un langage de programmation".
D'un point de vue extérieur, deux implémentations différentes d'un même algoritmhe doivent donner le même résultat :
- si on fournit les mêmes ENTREES aux deux fonctions (les mêmes paramètres),
- elles vont répondre avec la même SORTIE.
Voici 3 fonctions qui implémentent de trois façons différentes l'algorithme (mais qui donnent bien pourtant le même résultat) :
- Implémentation avec un while et un seul return
- Propre car la boucle TANT QUE est bien implémentée via un while.
- Propre car la fonction ne possède qu'une seule sortie, un seul return : cela le rendra plus facilement vérifiable et démontrable.
- Implémentation avec un while et deux return
- Propre car la boucle TANT QUE est bien implémentée via un while.
- Moins propre car la fonction possèdent deux sorties, deux return.
- Implémentation avec un for associé à un return
- Avantage : facile à lire car l'initialisation et la variation progressive de la variable de boucle sont cachées dans le for
- Désavantage :
- Moins propre : on utilise for associé à return pour recréer un while. On casse donc une boucle bornée pour créer une boucle non bornée.
- Moins propre car la fonction possède deux sorties, deux return.
1
2
3
4
5
6
7
8
9
10 | def rechercher(t, x):
i = 0
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
if i < longueur:
reponse = i
else:
reponse = -1
return reponse
|
1
2
3
4
5
6
7
8
9 | def rechercher(t, x):
i = 0
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
if i < longueur:
return i
else:
return -1
|
1
2
3
4
5 | def rechercher(t, x):
for i in range(len(t)):
if t[i] == x:
return i
return -1
|
On fera donc bien la différence entre
- l'algorithme qui décrit le principe de façon abstraite et
- la fonction Python qui l'implémente et permet de le faire fonctionner concrétement. Un même algorithme peut s'implémenter de différentes manières.
01 ✔° Placer en mémoire la fonction proposée ci-dessous qui implémente l'algorithme de recherche. Il s'agit de la version "propre".
Utiliser (via la console Python) les exemples proposés sur les lignes 9 à 12 pour vérifier qu'il répond bien comme la documentation l'indique.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | def rechercher(t, x):
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent
:: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x
:: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau
:: return (int) :: l'indice de la case ou -1
:: exemples ::
>>> test = [10, 20, 30, 40, 50]
>>> rechercher(test, 20)
1
>>> rechercher(test, 60)
-1
"""
i = 0
longueur = len(t)
while i < longueur and t[i] != x:
i = i + 1
if i < longueur:
reponse = i
else:
reponse = -1
return reponse
|
02° Rajouter deux autres exemples d'utilisation dans la documentation (sous la ligne 13).
Notez bien mentalement qu'on peut rajouter des exemples d'utilisations et les réponses attendues avant même que la fonction ne soit vraiment réalisée.
On peut néanmoins faire plus "simple" mais plus "sale" en profitant des boucles for et du fait qu'on sorte immédiatement des fonctions dès qu'on rencontre un return.
03° Lancer le programme en mémoire et tester pour vérifier que cette nouvelle implémentation répond exactement comme la précédente.
Question :
Expliquer pourquoi la fonction ne renvoie pas systématiquement -1 alors que la dernière instruction de la fonction (L19) est return -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | def rechercher(t, x):
"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent
:: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x
:: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau
:: return (int) :: l'indice de la case ou -1
:: exemples ::
>>> test = [10,20,30,40,50]
>>> rechercher(test, 20)
1
>>> rechercher(test, 60)
-1
"""
for i in range(len(t)):
if t[i] == x:
return i
return -1 # Si on arrive ici, c'est qu'on a jamais rencontré la ligne précédente !
|
...CORRECTION...
Tout simplement car on sort définitivement de la fonction lorsqu'on rencontre un return. Si on rencontre celui de la ligne 18, on ne peut donc pas rencontrer celui de la ligne 19.
Passons à un algorithme légérement différent : on voudrait obtenir la dernière position de l'élément s'il apparaît plusieurs fois dans le tableau. Nous allons donc être obligé de faire notre recherche dans toutes les cases du tableau avant de répondre.
04° Quelle est le type de boucle associé à ce problème ?
- Une boucle bornée (implémentée facilement avec for en Python)
- Une boucle non bornée (implémentée facilement avec while en Python)
...CORRECTION...
Il faut lire toutes les cases, on peut donc prévoir à l'avance le nombre d'étapes : c'est la longueur du tableau.
Le problème est donc plutôt lié à une boucle bornée.
Voici la description de cette recherche de la dernière occurrence.
Algorithme de recherche séquentielle (de la dernière occurrence)
BUT : trouver la position de la dernière occurrence de l'élément recherché dans un tableau.
PRINCIPE (en 3 étapes) :
- On stocke -1 dans une variable reponse
- En utilisant un par un les indices du tableau, on lit chaque case du tableau et si la case contient la valeur cherchée, on stocke dans reponse le numéro de la case.
- On renvoie la reponse
Description des entrées / sortie
- ENTREES :
- t : un tableau contenant n éléments.
- x : l' élément qu'on recherche dans le tableau
- (optionnelle selon les langages d'implémentation) longueur, le nombre d'éléments dans le tableau t
- SORTIE : un entier valant
- soit l'indice où se trouve la dernière occurrence de l'élément cherché.
- soit -1 si l'élément x n'est pas présent dans le tableau
Description de l'algorithme
reponse ← -1
POUR i variant de 0 (inclus) à longueur-1 (inclus)
SI t[i] est égal à x
reponse ← i
Fin Si
Fin POUR
Renvoyer reponse
05° Que doit-on taper en Python pour obtenir une boucle bornée variant de 0 (inclus) à longueur -1 (inclus) ?
- for i in range(len(t)):
- for i in range(len(t)-1):
- while i in range(len(t)):
- while i in range(len(t)-1):
...CORRECTION...
- for i in range(len(t)):
On notera que cela revient à taper ceci :
for i in range(0, len(t), 1):
POINT CHAUD A SURVEILLER
Notez bien que
- dans les algorithmes, les boucles FOR sont données avec valeur finale incluse.
- en Python, la valeur finale d'un range est exclue.
Je n'y peux rien. C'est à surveiller lors de l'implémentation.
06° Compléter la fonction rechercher() ci-dessous pour qu'elle implémente avec un FOR la recherche de la position de la dernière occurrence.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | def rechercher(t, x):
"""Renvoie l'indice de la dernière occurrence de x dans t, -1 si non présent
:: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x
:: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau
:: return (int) :: l'indice de la case ou -1
:: exemples ::
>>> test = [10,20,30,40,20]
>>> rechercher(test, 20)
4
>>> rechercher(test, 60)
-1
"""
return -1
|
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | def rechercher(t, x):
"""Renvoie l'indice de la dernière occurrence de x dans t, -1 si non présent
:: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x
:: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau
:: return (int) :: l'indice de la case ou -1
:: exemples ::
>>> test = [10,20,30,40,20]
>>> rechercher(test, 20)
4
>>> rechercher(test, 60)
-1
"""
reponse = -1
for i in range(len(t)):
if t[i] == x:
reponse = i
return reponse
|
07° Quel est le coût de cet algorithme ?
- Constant
- Logarithmique
- Linéaire
- Quadratique
- Exponentiel
...CORRECTION...
Si on prend comme opération élémentaire la comparaison avec le if, on voit qu'on va devoir en faire autant que de cases dans le tableau. Le coût est donc linéaire.
Algorithme de recherche
Vous devez pouvoir :
- Dire que l'algorithme de recherche de la première occurrence utilise une boucle non bornée
- Fournir l'algorithme et l'implémenter en Python avec un while
- Justifier que le coût est linéaire (mais qu'on ne part pas systématiquement au bout du tableau)
- Dire que l'algorithme de recherche de la dernière occurrence utilise une boucle bornée
- Fournir l'algorithme et l'implémenter en Python avec un for
- Justifier que le coût est linéaire (et qu'on part systématiquement au bout du tableau)
2 - Recherche de valeur maximale ou minimale
Nous n'avons pas le choix : il va falloir lire les éléments un par un, jusqu'au bout.
Il s'agit donc bien d'un algorithme linéaire mais puisqu'on va nécessairement au bout à chaque fois, on pourra écrire Θ(n).
08° Utiliser l'animation ci-dessous pour visualiser le déroulement de la recherche du maximum.
Quel est le premier maximum détecté lors de la recherche ?
Reste-il le maximum tout au long de la recherche ?
Quel est le dernier maximum détecté ? Reste-il le maximum jusqu'au bout cette fois ?
| Indice i | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Case t[i] | 60 | 89 | 15 | 56 | 82 | 1 | 86 | 97 | 24 | 86 | 75 | 6 | 14 | 69 | 98 | 31 | 37 | 89 | 91 | 56 |
Comme vous le voyez, le principe est de lire les éléments un par un et d'écraser les valeurs anciennes du maximum si on en découvre une plus grande.
Seule la valeur finale après avoir parcouru tout le tableau a donc un sens.
Algorithme de recherche de maximum ("version TANT QUE")
Principe (3 étapes)
- On initialise le max_temporaire avec le contenu de la première case du tableau et l'indice i pointe sur la prochaine case, la numéro 1.
- TANT QUE l'indice i est bien un indice valide pour le tableau reçu
- Si la case actuelle contient une valeur plus grande que le max_temporaire, on stocke cette valeur dans max_temporaire.
- On passe à la case suivante en incrémentant i.
- On renvoie la valeur stockée dans max_temporaire.
Description des entrées / sortie
- ENTREES :
- PRECONDITION sur t : il doit être tableau non vide (au moins s un élément.
- (optionnelle selon les langages d'implémentation) longueur, le nombre d'éléments dans le tableau
- SORTIE : la valeur maximale dans le tableau.
Exemple
| t = [13, 18, 89, 1024, 45, -12, 18] | ⇒ | RECHERCHER_MAXIMUM | ⇒ | |
| et | 1024 | |||
| longueur = 7 |
Description de l'algorithme
max_temporaire ← t[0]
i ← 1
TANT QUE i < longueur
SI t[i] > max_temporaire
max_temporaire ← t[i]
Fin du SI
i ← i + 1
Fin du TANT QUE
Renvoyer max_temporaire
09° Cette version de l'algorithme présente une boucle non bornée : est-il vraiment judicieux d'utiliser une boucle non bornée pour la recherche du maximum ?
...CORRECTION...
Puisqu'on sait qu'on va devoir lire tous les éléments pour trouver le maximum, il serait plus judicieux d'utiliser une boucle bornée.
Algorithme de recherche de maximum ("version POUR")
Principe (3 étapes)
- On initialise le max_temporaire avec le contenu de la première case du tableau.
- POUR CHAQUE autre indice de case possible dans le tableau
- Si la case actuelle contient une valeur plus grande que le max_temporaire, on stocke cette valeur dans max_temporaire.
- On renvoie la valeur stockée dans max_temporaire.
Description des entrées / sortie
- ENTREES :
- PRECONDITION sur t : il doit être tableau non vide qui possède au moins un élément.
- (optionnelle selon les langages d'implémentation) longueur, le nombre d'éléments dans le tableau
- SORTIE : la valeur maximale dans le tableau.
Exemple
| t = [13, 18, 89, 1024, 45, -12, 18] | ⇒ | RECHERCHER_MAXIMUM | ⇒ | |
| et | 1024 | |||
| longueur = 7 |
Description de l'algorithme
max_temporaire ← t[0]
POUR i variant de 1 à (longueur -1)
SI t[i] > maxi
max_temporaire ← t[i]
Fin du SI
Fin du POUR
Renvoyer max_temporaire
Encore une fois, pas de tableau vide à gérer puisque la PRECONDITION demande d'envoyer un tableau possédant au moins un élément. Le cas d'un tableau d'un seul élément ne pose pas problème : la boucle POUR devrait aller de 1 à 0 en augmentant. Elle ne démarrera donc pas, et le maximum reste l'élément d'indice 0.
10° Réaliser l'implémentation de cet algortihme via une fonction Python rechercher_maximum() dont voici le prototype :
rechercher_maximum(t:tableau NON VIDE) -> un élément du tableau
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | def rechercher_maximum(t):
"""Fonction qui renvoie la valeur maximale lue dans le tableau non vide
:: param t(list) :: un tableau non vide d'éléments comparables entre eux
:: return (type des valeurs du tableau) :: la valeur maximale
:: exemples ::
>>> test = [10,20,60,40,50]
>>> rechercher_maximum(test)
60
>>> test = [10,20,60,40,50,100]
>>> rechercher_maximum(test)
100
>>> test = [100,20,60,40,50]
>>> rechercher_maximum(test)
100
"""
pass
|
La correction est fournie ci-dessous si vraiment vous bloquez.
11° Trois questions :
- Quelle va être la première valeur de la variable de boucle i du POUR ?
- Pourquoi noter len(t) en ligne 20 dans le programme Python alors qu'on a POUR i variant de 1 à (longueur -1) dans l'algorithme ?
- Quelle ligne poserait problème si l'utilisateur n'avait pas respecté la précondition et avait envoyé un tableau vide ?
1
2
3
4
5 | def rechercher_maximum(t:'Tableau NON VIDE') -> 'Elt':
"""Fonction qui renvoie la valeur maximale lue dans le tableau NON VIDE"""
max_temporaire = t[0]
for i in range( 1, len(t) ):
if t[i] > max_temporaire:
max_temporaire = t[i]
return max_temporaire
|
...CORRECTION...
La variable de boucle i commence à 1. Par défaut, si on ne précise pas la valeur de départ, l'interpréteur Python place 0. Mais, ici, on a placé la valeur 1.
La différence entre l'algorithme et Python sur la valeur finale vient du fait qu'en Python, on fournit une valeur finale exclue, une valeur qu'on n'atteint pas.
C'est max_temporaire = t[0] qui posera problème avec un tableau vide, puisque l'élément 0 n'existe pas dans ce cas. On va se retrouver avec un IndexError.
range
Taper range(6) revient à fournir le tableau de valeurs suivant : [0, 1, 2, 3, 4, 5].
La valeur initiale par défaut est 0 et la valeur initiale de l'incrémentation est +1.
Taper range(6) revient à avoir tapé range(0, 6, 1)
Quelques exemples :
>>> for x in range(0,6,1): print(x, end='-')
0-1-2-3-4-5-
>>> for x in range(2,6,1): print(x, end='-')
2-3-4-5-
>>> for x in range(1,6,2): print(x, end='-')
1-3-5-
>>> for x in range(6,1,-1): print(x, end='-')
6-5-4-3-2-
On remarquera ici qu'on peut transmettre à la fonction native print() un paramètre nommé end qui contient le caractère séparant les différents affichage. Sa valeur par défaut correspond au passage à la ligne (\n) mais ici, on demande d'afficher un simple tiret.
12° Réaliser la fonction rechercher_position_max() pour qu'elle renvoie la position du maximum dans le tableau (à savoir son indice) et pas sa valeur.
rechercher_position_max(t:tableau) -> int
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | def rechercher_position_max(t):
"""Fonction qui renvoie l'indice de la valeur maximale lue dans le tableau NON VIDE
:: param t(list) :: un tableau NON VIDE d'éléments comparables entre eux
:: return (int) :: l'indice de la valeur maximale
:: exemples ::
>>> test = [10,20,60,40,50]
>>> rechercher_position_max(test)
2
>>> test = [10,20,60,40,50,100]
>>> rechercher_position_max(test)
5
>>> test = [100,20,60,40,50]
>>> rechercher_position_max(test)
0
"""
pass
|
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | def rechercher_position_max(t):
"""Fonction qui renvoie l'indice de la valeur maximale lue dans le tableau NON VIDE
:: param t(list) :: un tableau NON VIDE d'éléments comparables entre eux
:: return (int) :: l'indice de la valeur maximale
:: exemples ::
>>> test = [10,20,60,40,50]
>>> rechercher_position_max(test)
2
>>> test = [10,20,60,40,50,100]
>>> rechercher_position_max(test)
5
>>> test = [100,20,60,40,50]
>>> rechercher_position_max(test)
0
"""
indice_du_maximum = 0
for i in range( 1, len(t) ):
if t[i] > t[indice_du_maximum]:
indice_du_maximum = i
return indice_du_maximum
|
✎ 13° Répondre aux questions liées à ces deux appels :
>>> rechercher_position_max([20, 500, 10, 40])
???
>>> rechercher_position_max([20, 50, 100, 50, 100])
???
- Que vont répondre les appels 1 et 2 suivants ?
- Quelle est la légère modification à faire dans le programme pour renvoyer la dernière occurrence du maximum rencontré dans le cas où la valeur maximale apparaît plusieurs fois ?
✎ 14° Fournir une fonction rechercher_position_min() qui renvoie la position du minimum des valeurs (en cas d'égalité, on prendra le cas du premier indice rencontré).
rechercher_position_min(t:tableau) -> int
✎ 15° En respectant le principe "Une tâche, une fonction", fournir une fonction rechercher_minimum() qui renvoie la valeur du minimum des valeurs en utilisant simplement la fonction rechercher_position_min().
rechercher_minimum(t:tableau) -> valeur d'un élément
3 - Somme et valeur moyenne
Dernière fonction typique à savoir réaliser : la moyenne des valeurs contenues dans un tableau.
On doit cette fois créer une variable-mémoire, disons somme, dans laquelle on place la somme progressive des éléments du tableau.
Connaissant la longueur du tableau, on va alors renvoyer somme / longueur.
On voit donc que la fonction calculer_moyenne() va avoir besoin de faire un appel à la fonction calculer_sommme().
16° Ecrire la fonction calculer_sommme() qui renvoie la somme des éléments présents dans un tableau d'entiers. Fournir également la documentation de la fonction.
calculer_somme(t:tableau) -> int|float
PRECONDITON : on envoie un tableau contenant des nombres. On peut envoyer un tableau VIDE, dans ce cas la somme doit valoir 0.
Remarque : la barre verticale signifie OU : la fonction va donc renvoyer un entier ou un flottant.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | def calculer_somme(t):
"""Renvoie la somme des éléments présents dans le tableau
:: param t(list) :: un tableau de nombres
:: return (int) :: la somme des nombres
:: exemples ::
>>> test = [10,20,60]
>>> calculer_somme(test)
90
>>> test = []
>>> rechercher_position_max(test)
0
"""
somme = 0
for i in range(len(t)):
somme = somme + t[i]
return somme
|
17° Ecrire la fonction calculer_moyenne() qui renvoie la moyenne des éléments présents dans un tableau d'entiers NON VIDE. Fournir également la documentation de la fonction.
calculer_moyenne(t:tableau) -> float
PRECONDITON : on envoie un tableau NON VIDE contenant des nombres.
Une fois la fonction réalisée, dire pourquoi on a dû rajouter la précondition "TABLEAU NON VIDE" sur le paramètre t ?
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | def calculer_moyenne(t):
"""Renvoie la moyenne des éléments présents dans le tableau
:: param t(list) :: un tableau de nombres
.... PRECONDITION .. tableau t NON VIDE
:: return (float) :: la moyenne des nombres
:: exemples ::
>>> test = [10,20,60]
>>> calculer_somme(test)
30.0
"""
return calculer_somme(t) / len(t)
|
18° QCM. Ces algorithmes (maximum, minimum, somme et moyenne) ont donc besoin de lire les éléments un par un jusqu'au bout. Sont-ils :
- à coût constant (ou avec une complexité en 𝞗(1)) : temps d'exécution constant quelque soit la taille du tableau d'entrée
- à coût linéaire (ou avec une complexité en 𝞗(n)) : le temps d'exécution double si l'entrée double
- à coût quadratique (ou avec une complexité en 𝞗(n2)) : le temps d'exécution est multiplié par 4 si l'entrée double
- à coût cubique (ou avec une complexité en 𝞗(n3)) : le temps d'exécution est multiplié par 8 si l'entrée double
...CORRECTION...
Comme on parcourt le tableau séquentiellement et une seule fois, la réponse est la réponse B.
4 - Mini-projet : application concrète
Nous allons travailler sur la liste des prénoms déclarés à l'état-civil de 2004 à 2021 sur la ville de Paris. La liste elle-même est présente à cette adresse si vous voulez aller vérifier : LISTE en OPEN DATA
Nous allons travailler plus tard sur l'OPEN DATA et la possibilité de récupérer facilement ces données dans Python à partir d'un fichier texte.
Pour l'instant, vous allez simplement travailler à partir d'un script Python ne contenant qu'un très loooooooooooooong string multiligne contenant un prénom par ligne. Voici le début :
1
2
3
4 | |
Comme on peut le voir : un prénom par ligne, le caractère séparateur est donc le passage à la ligne ('\n' en Python).
Comment obtenir un tableau à partir de ce string ? En utilisant la méthode des strings split().
Voici un rappel de son fonctionnement en pratique :
>>> string_prenoms = '''Andy
Angel
Anouk
Anthony'''
>>> string_prenoms
'Andy\nAngel\nAnouk\nAnthony'
>>> prenoms = string_prenoms.split('\n')
>>> prenoms
['Andy', 'Angel', 'Anouk', 'Anthony']
ATTENTION : chaque prénom peut apparaître plusieurs fois puisqu'il s'agit d'une liste des déclarations de naissance. Plusieurs personnes ont donné le prénom.
19° Réaliser cette structure sur votre ordinateur en créant un dossier tp_prenoms dans lequel vous allez placer les deux fichiers qu'il faudra télécharger avec un clic-droit à l'aide des liens ci-dessous :
Une fois téléchargés et placés au bon endroit :
- Vérifier en l'ouvrant avec Thonny que prenoms_paris.py ne contient bien qu'une variable nommée string_prenoms qui est un très long string contenant les prénoms donnés, un prénom par ligne.
- Ouvrir le script question_finale_algo3.py pour vérifier qu'il se compose de trois parties :
- Ligne 3 : on importe la variable string_prenoms depuis le module Python nommé prenoms_paris
- Ligne 101 : on crée un tableau nommé prenoms en séparant les différents prénoms du string string_prenoms en utilisant le passage à la ligne comme élément séparateur.
- Ligne 102 : nouveauté, on demande de supprimer de la mémoire le string (qui occupe pas mal de place) maintenant que les données sur les prénoms sont dans le tableau prenoms.
1
2
3
4
5
...
100
101
102 | |
Lire les explications pour comprendre ce que fait le programme pour l'instant :
✎ 20 (mini-projet)° Utiliser les deux fonctions proposées prenoms_commencant_par() et prenoms_finissant_par() pour vérifier qu'elles fonctionnent ET que vous comprenniez vraiment comment elles fonctionnent.
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | |
Vous devriez obtenir des résultats de ce type :
>>> prenoms_commencant_par('X', prenoms)
Xavier qui comporte 6 caractères
Xavier qui comporte 6 caractères
...
>>> prenoms_finissant_par('X', prenoms)
>>>prenoms_finissant_par('x', prenoms)
Alix qui comporte 4 caractères
Max qui comporte 3 caractères
Felix qui comporte 5 caractères
Félix qui comporte 5 caractères
...
Réaliser ENSUITE une à une et progressivement les autres fonctions demandées :
- nombre()
- nombre_prenom()
- nombre_prenoms_commencant_par()
- nombre_prenoms_finissant_par()
- nombre_prenoms_longs()
- nombre_prenoms_courts()
- prenoms_de_x_caracteres()
- longueur_maximale()
- prenoms_les_plus_longs()
✎ 21 (mini-projet)° Créer maintenant une seconde version du projet. On ne veut pas que les fonctions affichant une liste de réponses renvoient plutôt un tableau contenant les réponses. Le plus simple est de travailler en utilisant des déclarations par compréhension.
5 - FAQ
On peut avoir de plus gros fichiers de prénoms ?
Sans problème avec l'OpenData : Les prénoms en France de 1900 à 2019
Le fichier est au format CSV que vous avez peut-être découvert en seconde et qui sera étudié en 1er de toutes manières.
Activité publiée le 13 03 2020
Dernière modification : 08 03 2022
Auteur : ows. h.