Des compteurs☘
Objectifs de cette page d'exercices☘
Dans cette page, les exercices portent essentiellement sur des compteurs (on compte des éléments d'une liste vérifiant une certaine propriété).
Vous essayerez de définir ces compteurs par les deux stratégies suivantes:
Stratégie 1.☘
Le compteur est obtenu par "accumulation".
- Une variable compteur est initialisée à 0.
- On parcourt ensuite les éléments de la liste et à chaque élément de la liste satisfaisant la condition imposée, on incrémente le compteur.
Stratégie 2.☘
- On essaie de définir la liste des mots satisfaisant la contrainte (liste générée par compréhension avec filtrage).
- Puis on renvoie la longueur de cette liste.
Exemple☘
Nous voulons définir une fonction prenant en paramètre une liste contenant des entiers relatifs. La fonction doit renvoyer le nombre d'entiers strictement négatifs de la liste.
Avec un compteur par accumulation
def test_compte_negatifs():
assert compte_negatifs([1,2,0]) == 0
assert compte_negatifs([1,2,0,-1, 9, -2]) == 2
def compte_negatifs(tab):
"""
tab: liste d'entiers
renvoie le nombre d'entiers <0 de tab.
"""
compteur = 0
for k in tab:
if k < 0:
compteur += 1
return compteur
Avec la longueur d'une liste
def compte_negatifs(tab):
"""
tab: liste d'entiers
renvoie le nombre d'entiers <0 de tab.
"""
return len([x for x in tab if x < 0])
Exercices☘
Au moins une☘
- Écrire une fonction python spécifiée comme suit:
def au_moins_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant au moins une fois
le caractère lettre
>>> au_moins_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
>>> au_moins_un('g', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
"""
Un code
def au_moins_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant au moins une fois
le caractère lettre
>>> au_moins_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
>>> au_moins_un('g', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
"""
compteur = 0
for mot in liste_mots:
if lettre in mot:
compteur += 1
return compteur
- Essayez de proposer une version s'appuyant sur la définition d'une liste en compréhension.
Solution
On pourrait utiliser les listes en compréhension comme suit:
def au_moins_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant au moins une fois
le caractère lettre
>>> au_moins_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
>>> au_moins_un('g', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
"""
return len([mot for mot in liste_mots if lettre in mot])
Le code est plus concis. Un inconvénient éventuel: on crée une seconde liste. Si la liste initiale et la liste ainsi créée sont toutes deux conséquentes, on "consomme" de la mémoire vive... alors que la version avec compteur ne crée qu'une variable supplémentaire (la variable compteur).
Exactement une☘
- Écrire une fonction python spécifiée comme suit:
def liste_exactement_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant exactement une fois
le caractère lettre
>>> liste_exactement_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
>>> liste_exactement_un('c', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
"""
Un code
Comme d'habitude, on doit découper en fonctions...
def chaine_exactement_un(caractere, mot):
"""
mot -- chaîne de caractères
caractère -- un caractère
renvoie True si mot présente exactement un caractère égal à caractere
et renvoie False sinon.
>>> chaine_exactement_un('a', 'arbre')
True
>>> chaine_exactement_un('a', 'abracadabra')
False
"""
compteur = 0
for carac in mot:
if carac == caractere:
compteur += 1
return compteur == 1
def liste_exactement_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant exactement une fois
le caractère lettre
>>> liste_exactement_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
>>> liste_exactement_un('c', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
"""
compteur = 0
for mot in liste_mots:
if chaine_exactement_un(lettre, mot):
compteur += 1
return compteur
- Proposer une version utilisant des listes définies en compréhension.
Solution
Avec la "pénalité" éventuelle signalée précédemment (consommation de mémoire):
def chaine_exactement_un(caractere, mot):
"""
mot -- chaîne de caractères
caractère -- un caractère
renvoie True si mot présente exactement un caractère égal à caractere
et renvoie False sinon.
>>> chaine_exactement_un('a', 'arbre')
True
>>> chaine_exactement_un('a', 'abracadabra')
False
"""
return 1 == len([carac for carac in mot if carac == caractere])
def liste_exactement_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant exactement une fois
le caractère lettre
>>> liste_exactement_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
>>> liste_exactement_un('c', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
"""
return len([mot for mot in liste_mots if chaine_exactement_un(lettre, mot)])
Au plus une☘
- Écrire une fonction python spécifiée comme suit:
def liste_au_plus_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant au plus une fois
le caractère lettre
>>> liste_au_plus_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
2
>>> liste_au_plus_un('z', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
5
>>> liste_au_plus_un('a', ['zaz', 'zut'])
2
"""
Note
On rappelle que "au plus une" signifie "0 ou 1".
Un code
Comme d'habitude, on doit découper en fonctions...
def chaine_au_plus_un(caractere, mot):
"""
mot -- chaîne de caractères
caractère -- un caractère
renvoie True si mot présente au plus une occurrence
de caractere
et renvoie False sinon.
>>> chaine_au_plus_un('a', 'arbre')
True
>>> chaine_au_plus_un('a', 'abracadabra')
False
>>> chaine_au_plus_un('a', 'biniou')
True
"""
compteur = 0
for carac in mot:
if carac == caractere:
compteur += 1
return compteur <= 1
def liste_au_plus_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant au plus une fois
le caractère lettre
>>> liste_au_plus_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
2
>>> liste_au_plus_un('z', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
5
"""
compteur = 0
for mot in liste_mots:
if chaine_au_plus_un(lettre, mot):
compteur += 1
return compteur
- Proposer une version utilisant des listes définies en compréhension.
Solution
Avec la "pénalité" éventuelle signalée précédemment (consommation de mémoire):
def chaine_au_plus_un(caractere, mot):
"""
mot -- chaîne de caractères
caractère -- un caractère
renvoie True si mot présente au plus une occurrence
de caractere
et renvoie False sinon.
>>> chaine_au_plus_un('a', 'arbre')
True
>>> chaine_au_plus_un('a', 'abracadabra')
False
>>> chaine_au_plus_un('a', 'biniou')
True
"""
return len([c for c in mot if c == caractere]) <= 1
def liste_au_plus_un(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre d'éléments de la liste contenant au plus une fois
le caractère lettre
>>> liste_au_plus_un('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
2
>>> liste_au_plus_un('z', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
5
"""
return len([mot for mot in liste_mots if chaine_au_plus_un(lettre, mot)])
Cumul des occurrences☘
Écrire une fonction python spécifiée comme suit:
def liste_nombre_total(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre cumulé des occurrences
de lettre dans les mots de liste_mots.
>>> liste_nombre_total('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
9
>>> liste_nombre_total('z', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
"""
Un code
def chaine_nombre_total(lettre, chaine):
"""
chaine -- chaîne de caractères
lettre -- caractère
renvoie le nombre d'occurrences de lettre dans chaine.
>>> chaine_nombre_total('e', 'chaînette')
2
>>> chaine_nombre_total('a', 'Barbapapa')
4
"""
compteur = 0
for carac in chaine:
if carac == lettre:
compteur += 1
return compteur
def liste_nombre_total(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre cumulé des occurrences de lettre dans les mots de liste_mots.
>>> liste_nombre_total('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
9
>>> liste_nombre_total('z', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
"""
compteur = 0
for mot in liste_mots:
compteur += chaine_nombre_total(lettre, mot)
return compteur
Un autre découpage
def chaine_nombre_total(lettre, chaine):
"""
chaine -- chaîne de caractères
lettre -- caractère
renvoie le nombre d'occurrences de lettre dans chaine.
>>> chaine_nombre_total('e', 'chaînette')
2
>>> chaine_nombre_total('a', 'Barbapapa')
4
"""
return len([c for c in chaine if c == lettre])
def somme(tab):
"""
tab: liste d'entiers
renvoie la somme des éléments de tab
"""
s = 0
for k in tab:
s += k
return s
def liste_nombre_total(lettre, liste_mots):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
renvoie le nombre cumulé des occurrences de lettre dans les mots de liste_mots.
>>> liste_nombre_total('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
9
>>> liste_nombre_total('z', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
"""
return somme([chaine_nombre_total(lettre, mot) for mot in liste_mots])
Seconde série d'exercices☘
Un nombre exact de répétition d'une lettre☘
Écrire une fonction python spécifiée comme suit:
def liste_exactement(lettre, liste_mots, n):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
n -- entier naturel
renvoie le nombre de chaînes de liste_mots
qui compte exactement n occurrences de lettre.
>>> liste_exactement('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'], 2)
2
>>> liste_exactement('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'], 5)
1
"""
Un code
def chaine_exactement(lettre, chaine, n):
"""
chaine -- chaîne de caractères
lettre -- caractère
n -- entier naturel
renvoie True si chaine présente exactement n occurrences de lettre.
>>> chaine_exactement('e', 'chaînette', 2)
True
>>> chaine_exactement('a', 'Barbapapa', 5)
False
"""
compteur = 0
for carac in chaine:
if carac == lettre:
compteur += 1
return compteur == n
def liste_exactement(lettre, liste_mots, n):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
n -- entier naturel
renvoie le nombre de chaînes de liste_mots
qui compte exactement n occurrences de lettre.
>>> liste_exactement('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'], 2)
2
>>> liste_exactement('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'], 5)
1
"""
compteur = 0
for mot in liste_mots:
if chaine_exactement(lettre, mot, n):
compteur += 1
return compteur
Code avec len...
def chaine_exactement(lettre, chaine, n):
"""
chaine -- chaîne de caractères
lettre -- caractère
n -- entier naturel
renvoie True si chaine présente exactement n occurrences de lettre.
>>> chaine_exactement('e', 'chaînette', 2)
True
>>> chaine_exactement('a', 'Barbapapa', 5)
False
"""
return len([x for x in chaine if x == lettre]) == n
def liste_exactement(lettre, liste_mots, n):
"""
lettre -- un caractère
liste_mots -- liste de chaînes de caractères
n -- entier naturel
renvoie le nombre de chaînes de liste_mots
qui compte exactement n occurrences de lettre.
>>> liste_exactement('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'], 2)
2
>>> liste_exactement('a', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'], 5)
1
"""
return len([mot for mot in liste_mots if chaine_exactement(lettre, mot, n)])
Terminaison☘
- Écrire un corps possible pour la fonction suivante:
def fin_en(syllabe, liste_mots):
"""
liste_mots -- liste de chaîne de caractères
syllabe -- chaîne de caractères
renvoie le nombre de chaînes dans liste_mots terminant par syllabe
>>> fin_en('e', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
>>> fin_en('er', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
>>> fin_en('er', ['permettre', 'autoriser', 'légitimer', 'accepter', 'tolérer'])
4
"""
Solution
Un code possible ci-dessous. On a décomposé la demande en deux fonctions. Rappelons qu'il faut réfléchir ainsi: décomposer les tâches complexes en petites tâches, veiller à toujours présenter des fonctions aussi simples que possible, ne réalisant qu'une seule taĉhe.
def fin_chaine_en(chaine, syllabe):
"""
chaine -- chaine de caractères
syllabe -- chaine de caractères
renvoie True si chaine finit par syllabe, False sinon.
>>> fin_chaine_en("barycentre", "re")
True
>>> fin_chaine_en("intégrale", "la")
False
"""
lgs, lgc = len(syllabe), len(chaine)
# si syllabe est plus longue que chaine, échec assuré:
if lgs > lgc: return False
# on compare les lettres de fin de chaine avec les lettres de syllabe
# en commençant par la fin des deux chaînes :
for k in range(0, lgs):
if chaine[lgc-1-k] != syllabe[lgs-1-k]:
return False
return True
def fin_en(syllabe, liste_mots):
"""
liste_mots -- liste de chaînes de caractères
syllabe -- chaîne de caractères
renvoie le nombre de chaînes dans liste_mots terminant par syllabe
>>> fin_en('e', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
>>> fin_en('er', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
>>> fin_en('er', ['permettre', 'autoriser', 'légitimer', 'accepter', 'tolérer'])
4
"""
compteur = 0
for mot in liste_mots:
if fin_chaine_en(mot, syllabe):
compteur += 1
return compteur
- Modifier la fonction
fin_ende la solution précédente de façon à ce que le compteur soit obtenu comme longueur d'une liste définie en compréhension.
Solution
def fin_chaine_en(chaine, syllabe):
"""
chaine -- chaine de caractères
syllabe -- chaine de caractères
renvoie True si chaine finit par syllabe, False sinon.
>>> fin_chaine_en("barycentre", "re")
True
>>> fin_chaine_en("intégrale", "la")
False
"""
lgs, lgc = len(syllabe), len(chaine)
# si syllabe est plus longue que chaine, échec assuré:
if lgs > lgc: return False
# on compare les lettres de fin de chaine avec les lettres de syllabe
# en commençant par la fin des deux chaînes :
for k in range(0, lgs):
if chaine[lgc-1-k] != syllabe[lgs-1-k]:
return False
return True
def fin_en(syllabe, liste_mots):
"""
liste_mots -- liste de chaînes de caractères
syllabe -- chaîne de caractères
renvoie le nombre de chaînes dans liste_mots terminant par syllabe
>>> fin_en('e', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
3
>>> fin_en('er', ['abracadabra', 'entourloupe', 'machination', 'escroquerie', 'passe-passe'])
0
>>> fin_en('er', ['permettre', 'autoriser', 'légitimer', 'accepter', 'tolérer'])
4
"""
return len([mot for mot in liste_mots if fin_chaine_en(mot, syllabe)])
Plusieurs parcours de la liste... ou un seul☘
Répétition du maximum☘
Écrire une fonction python prenant en paramètres une liste de chaînes de
caractères tab et un caractère lettre et renvoyant un entier naturel.
L'entier naturel renvoyé est le nombre de mots dans la liste tab qui contiennent
le plus grand nombre d'occurrences de lettre.
Exemple:
>>> nb_occ_maxi_lettres(['aha', 'abraca', 'ah?', 'amanda'], 'a')
2
Dans cet exemple:
- la chaîne "aha" contient 2 'a',
- la chaîne "abraca" contient 3 'a',
- la chaîne "ah?" contient 1 'a',
- la chaîne "amanda" contient 3 'a'.
Le plus grand nombre de 'a' présents dans une chaîne est donc 3. Et il y a 2 chaînes contenant 3 'a': c'est ce nombre 2 qui est obtenu.
def nb_occ_maxi_lettres(tab, lettre):
"""
tab -- liste de chaînes de caractères
lettre -- caractère
renvoie le nombre de chaînes de la liste tab contenant
un nombre d'occurrences de lettre égal au maximum des nombres
d'occurrence de lettre dans les chaînes de tab.
>>> nb_occ_maxi_lettres(['aha', 'abraca', 'ah?', 'amanda'], 'a')
2
>>> nb_occ_maxi_lettres(['aha', 'abraca', 'ah?', 'amanda'], 'z')
4
"""
Solution
Une solution possible:
def nb_lettres(mot, lettre):
"""
mot -- chaîne de caractères
lettre -- caractère
renvoie le nombre d'occurrences de lettre dans mot
"""
return len([x for x in mot if x == lettre])
def nb_occ_maxi_lettres(tab, lettre):
"""
tab -- liste de chaînes de caractères
lettre -- caractère
renvoie le nombre de chaînes de la liste tab contenant
un nombre d'occurrences de lettre égal au maximum des nombres
d'occurrence de lettre dans les chaînes de tab.
>>> nb_occ_maxi_lettres(['aha', 'abraca', 'ah?', 'amanda'], 'a')
2
>>> nb_occ_maxi_lettres(['aha', 'abraca', 'ah?', 'amanda'], 'z')
4
"""
compteur = 0
maxi = nb_lettres(tab[0], lettre)
for mot in tab:
nv = nb_lettres(mot, lettre)
if nv > maxi:
compteur = 1
maxi = nv
elif nv == maxi:
compteur += 1
else:
pass
return compteur
Un autre code
def nb_lettres(mot, lettre):
"""
mot -- chaîne de caractères
lettre -- caractère
renvoie le nombre d'occurrences de lettre dans mot
"""
return len([x for x in mot if x == lettre])
def maxi(tab):
"""
tab: liste d'entiers
renvoie la valeur max de tab
"""
m = tab[0] # contiendra le max
for k in tab:
if k > m:
m = k
return m
def maxi_lettres(tab, lettre):
"""
tab -- liste de chaînes de caractères
lettre -- caractère
renvoie le nombre maximal d'occurrences de lettre
pour les chaînes de la liste tab.
>>> maxi_lettres(['aha', 'abraca', 'ah?'], 'a') # renvoie 3 car abraca présente 3 'a'
3
"""
return maxi([nb_lettres(mot, lettre) for mot in tab])
def nb_occ_maxi_lettres(tab, lettre):
"""
tab -- liste de chaînes de caractères
lettre -- caractère
renvoie le nombre de chaînes de la liste tab contenant
un nombre d'occurrences de lettre égal au maximum des nombres
d'occurrence de lettre dans les chaînes de tab.
>>> nb_occ_maxi_lettres(['aha', 'abraca', 'ah?', 'amanda'], 'a')
2
>>> nb_occ_maxi_lettres(['aha', 'abraca', 'ah?', 'amanda'], 'z')
4
"""
return len([mot for mot in tab if nb_lettres(mot, lettre) == maxi_lettres(tab, lettre)])
Compter les répétitions de chaque valeur☘
Écrire une fonction python spécifiée comme suit:
def compte_occ_entiers(liste, n):
"""
n -- entier naturel
liste -- liste d'entiers entre 0 et n
renvoie une liste compteurs telle que compteurs[i] est le nombre
d'occurrences de i dans liste (pour i entre 0 et n).
>>> compte_occ_entiers([4, 3, 4, 2], 9)
[0, 0, 1, 1, 2, 0, 0, 0, 0, 0]
>>> compte_occ_entiers([0, 1, 2, 3, 7, 8, 9], 9)
[1, 1, 1, 1, 0, 0, 0, 1, 1, 1]
"""
compteurs par accumulation
def compte_occ_entiers(liste, n):
"""
n -- entier naturel
liste -- liste d'entiers entre 0 et n
renvoie une liste compteurs telle que compteurs[i] est le nombre
d'occurrences de i dans liste (pour i entre 0 et n).
>>> compte_occ_entiers([4, 3, 4, 2], 9)
[0, 0, 1, 1, 2, 0, 0, 0, 0, 0]
>>> compte_occ_entiers([0, 1, 2, 3, 7, 8, 9], 9)
[1, 1, 1, 1, 0, 0, 0, 1, 1, 1]
"""
compteurs = [0 for i in range(0,n+1)]
for entier in liste:
compteurs[entier] += 1
return compteurs
compteurs avec len
Cette seconde solution basée sur l'utilisation de len sur des listes est peu pertinente: elle oblige à parcourir n fois la liste où n est la longueur de la liste. Elle transforme donc un algorithme de complexité linéaire en un algorithme quadratique.
def compte_occ_entiers(liste, n):
"""
n -- entier naturel
liste -- liste d'entiers entre 0 et n
renvoie une liste compteurs telle que compteurs[i] est le nombre
d'occurrences de i dans liste (pour i entre 0 et n).
>>> compte_occ_entiers([4, 3, 4, 2], 9)
[0, 0, 1, 1, 2, 0, 0, 0, 0, 0]
>>> compte_occ_entiers([0, 1, 2, 3, 7, 8, 9], 9)
[1, 1, 1, 1, 0, 0, 0, 1, 1, 1]
"""
return [len([k for k in liste if k == i]) for i in range(0,n+1)]