Algo Parcours Suite

Identification

Infoforall

3 - 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 ?

Image d'un tableur
Un tableur ?

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) :

  1. On commence par la case d'indice 0
  2. Tant que la case ne possède pas le contenu cherché et qu'il reste des cases, on passe à la case suivante
  3. 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.
  4. 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

    i0

    TANT QUE i < longueur ET que t[i] est différent de x

      ii + 1

    Fin TANT QUE

    SI i < longueur

      reponsei

    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) :

  1. Implémentation avec un while et un seul return
  2. 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
    • 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.
  3. Implémentation avec un while et deux return
  4. 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
    • 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.
  5. Implémentation avec un for associé à un return
  6. 1 2 3 4 5
    def rechercher(t, x): for i in range(len(t)): if t[i] == x: return i return -1
    • 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èdent deux sorties, deux return.

    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.

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° Deux questions

  • Rajouter deux autres exemples d'utilisation dans la documentation (sous la ligne 13).
  • Expliquer pourquoi on peut donner des exemples de fonctionnement de la fonction avant même qu'on ai tapé les lignes d'instructions nécessaires à son fonctionnement réel.

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. 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 !

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 ?

  1. Une boucle bornée (implémentée facilement avec for en Python)
  2. 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) :

  1. On stocke -1 dans une variable reponse
  2. 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.
  3. 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

        reponsei

      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) ?

  1. for i in range(len(t)):
  2. for i in range(len(t)-1):
  3. while i in range(len(t)):
  4. while i in range(len(t)-1):

...CORRECTION...

  1. 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 ?

  1. Constant
  2. Logarithmique
  3. Linéaire
  4. Quadratique
  5. Exponentiel
Algorithme de recherche

Vous devez pouvoir :

  1. 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)
  2. 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 ne part pas 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)

  1. 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.
  2. 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.
  3. 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_temporairet[0]

    i ← 1

    TANT QUE i < longueur

      SI t[i] > max_temporaire

        max_temporairet[i]

      Fin du SI

      ii + 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)

  1. On initialise le max_temporaire avec le contenu de la première case du tableau.
  2. 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.
  3. 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_temporairet[0]

    POUR i variant de 1 à (longueur -1)

      SI t[i] > maxi

        max_temporairet[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) -> une valeur 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.

Voici l'implémentation Python utilisant cette version.

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_maximum(t): '''Fonction qui renvoie la valeur maximale lue dans le tableau :: param t(list) :: un tableau d'éléments qu'on peut comparer :: 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 ''' max_temporaire = t[0] for i in range( 1, len(t) ): if t[i] > max_temporaire: max_temporaire = t[i] return max_temporaire

11° Trois questions :

  1. Quelle va être la première valeur de la variable de boucle i du POUR ?
  2. 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 ?
  3. Quelle ligne poserait problème si l'utilisateur n'avait pas respecté la précondition et avait envoyé un tableau vide ?

...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]) ???
  1. Que vont répondre les appels 1 et 2 suivants ?
  2. 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 moyenne

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 :

  1. à coût constant (ou avec une complexité en 𝞗(1)) : temps d'exécution constant quelque soit la taille du tableau d'entrée
  2. à coût linéaire (ou avec une complexité en 𝞗(n)) : le temps d'exécution double si l'entrée double
  3. à coût quadratique (ou avec une complexité en 𝞗(n2)) : le temps d'exécution est multiplié par 4 si l'entrée double
  4. à 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
string_prenoms ='''Andy Angel Anouk Anthony'''

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 :

📁 tp_prenoms

📄 prenoms_paris.py

📄 question_finale_algo3.py

Une fois téléchargés et placés au bon endroit :

  1. 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.
  2. Ouvrir le script question_finale_algo3.py pour vérifier qu'il se compose de trois parties :
  3. 1 2 3 4 5 ... 100 101 102
    # 1 - Importation from prenoms_paris import string_prenoms # 2 - Déclaration des fonctions # 3 - PROGRAMME prenoms = string_prenoms.split('\n') del string_prenoms

    Lire les explications pour comprendre ce que fait le programme pour l'instant :

    • 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.

✎ 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
def prenoms_commencant_par(c, t): '''Affiche les prénoms commençant par la lettre c fournie et leurs nombres de lettres :: param c(str) :: la première lettre du prénom :: param t(list) :: un tableau de strings contenant des prénoms :: return (None) :: aucun retour, que de l'affichage ''' for i in range(len(t)): prenom = t[i] # prenom est donc un string qui contient donc l'un des prénoms if prenom[0] == c: # En Python, l'indice 0 veut dire le premier caractère du string print(f"{prenom} qui comporte {len(prenom)} caractères") def prenoms_finissant_par(c, t): '''Affiche les prénoms finissant par la lettre c fournie et leurs nombres de lettres :: param c(str) :: la dernière lettre du prénom :: param t(list) :: un tableau de strings contenant des prénoms :: return (None) :: aucun retour, que de l'affichage ''' for i in range(len(t)): prenom = t[i] # prenom est donc un string qui contient donc l'un des prénoms if prenom[-1] == c: # En Python, l'indice -1 veut dire le dernier caractère du string print(f"{prenom} qui comporte {len(prenom)} caractères")

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.

Dans les prochaines activités Algorithmique, nous verrons comment créer un algorithme plus performant qu'un algorithme linéaire mais nécessitant des données triées.

Si vous avez fait l'activité OpenData, vous savez ce que nous allons faire maintenant : des calculs et de l'évaluation non pas d'un tableau de valeurs mais d'un tableau d'enregistrements !

Activité publiée le 13 03 2020
Dernière modification : 08 03 2022
Auteur : ows. h.