Eléments de Programmation (en Python)Recueil d’exercices

Partie 1

© Équipe enseignante 1i001 / UPMC – Licence CC-BY-SA (fr3.0)

UPMC – Licence 1 – 2015/2016

Table des matièresThème 1 : Exercices numériques simples 3

Exercice 1.1 : Moyenne de trois nombres . . . . . . . . . . . . . . . . . . . . . . . . . . 3Exercice 1.2 : Calcul d’un prix TTC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Exercice 1.3 : Calcul de fonctions polynômiales . . . . . . . . . . . . . . . . . . . . . . 4Exercice 1.4 : Calcul du n-ième nombre de Fermat . . . . . . . . . . . . . . . . . . . . 5

Thème 2 : Exercices avec fonctions simples 6Exercice 2.1 : Calcul des mentions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Exercice 2.2 : Manipulation des booléens . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Thème 3 : Exercices simples sur les boucles 10Exercice 3.1 : Somme des impairs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10Exercice 3.2 : Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11Exercice 3.3 : Suite de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Thème 4 : Exercices avancés sur les boucles 15Exercice 4.1 : Couples et intervalles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Thème 5 : Exercices sur les intervalles et chaînes de caractères 18Exercice 5.1 : Voyelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Exercice 5.2 : Palindromes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

Thème 6 : Exercices simples sur les listes 21Exercice 6.1 : Listes de répétitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Exercice 6.2 : Maximum d’une liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Exercice 6.3 : Moyenne et variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Exercice 6.4 : Listes obtenues par multiplication ou division . . . . . . . . . . . . . . . 24Exercice 6.5 : Découpages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Thème 7 : Exercices avancés sur les listes 28Exercice 7.1 : Nombres complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Exercice 7.2 : Base de données des étudiants . . . . . . . . . . . . . . . . . . . . . . . . 29

1

Thème 8 : Exercices sur les compréhensions de listes 32Exercice 8.1 : Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Thème 9 : Exercices simples sur les ensembles et dictionnaires 34Exercice 9.1 : Magasin en ligne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34Exercice 9.2 : Recettes de cuisine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Exercice 9.3 : Statistiques sur les lettres . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Thème 10 : Exercices avancés sur les ensembles et dictionnaires 42Exercice 10.1 : Gestion de bibliothèque . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Exercice 10.2 : Calcul de Trajets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2

Thème 1 : Exercices numériques simples

Exercice 1.1 : Moyenne de trois nombres

Cet exercice a pour but de trouver les paramètres d’une fonction pour résoudre un problème, etd’écrire la spécification et la définition de fonctions très simples.

Question 1

Donner une définition de la fonction moyenne_trois_nb qui effectue la moyenne arithmétiquede trois nombres.

Dans le jeu de tests, on vérifiera notamment le calcul de moyenne des nombres 3, 6 et −3 puisde −3, 0 et 3 puis de 1.5, 2.5 et 1.0 (on pourra ajouter d’autres tests en complément).

Question 2 : moyenne pondérée

Écrire une définition de la fonction moyenne_ponderee qui effectue la moyenne de trois nombresa, b, c avec des coefficients de pondération, respectivement pa (pondération en a), pb et pc.

Proposer un jeu de tests comprenant au moins trois tests.

Exercice 1.2 : Calcul d’un prix TTC

Le but de cet exercice est d’effectuer des conversions simples entre des prix hors-taxe (HT) etdes prix toutes taxes comprises (TTC). Ceci permet de s’intéresser au passage d’un problème dela vie courante à une solution informatique.

Question 1

Ecrire une définition de la fonction prix_ttc qui calcule le prix toutes taxes comprises (TTC)à partir d’un prix hors taxe (HT) et d’un taux de TVA exprimé en pourcentage, par exemple20.0 pour une TVA de 20%.

Remarque : les calculs seront effectués en flottants (type float).

Par exemple :>>> prix_ttc(100.0, 20.0)120.0

>>> prix_ttc(100, 0.0) # remarque : conversion implicite de l'entier 100# en le flottant équivalent 100.0

100.0

3

>>> prix_ttc(100, 100.0)200.0

>>> prix_ttc(0, 20)0.0

>>> prix_ttc(200, 5.5)211.0

Question 2

Donner une définition de la fonction prix_ht qui calcule le prix hors taxe à partir du prix toutestaxes comprises et du taux de TVA.

Remarque : votre jeu de tests doit correspondre à celui proposé pour la fonction prix_ttc.

Exercice 1.3 : Calcul de fonctions polynômiales

Cet exercice a pour but de définir des fonctions de calcul de polynômes. On souhaite mettrel’accent sur l’efficacité des algorithmes utilisés (minimisation du nombre de multiplications).

Question 1

Après avoir spécifié le problème, écrire un jeu de tests et donner une définition de la fonctionpolynomiale telle que polynomiale(a, b, c, d, x) rend la valeur de ax3 + bx2 + cx + d.

Par exemple :>>> polynomiale(1, 1, 1, 1, 2)15

>>> polynomiale(1, 1, 1, 1, 3)40

Quel est le nombre de multiplications effectuées par votre définition ? Peut-on faire mieux ? Sioui, proposer une version plus efficace, sinon justifiez.

Question 2

Après avoir spécifié le problème, écrire un jeu de tests et donner une définition de la fonctionpolynomiale_carre qui rend la valeur de ax4 + bx2 + c.

Par exemple :>>> polynomiale_carre(1, 1, 1, 2)21

>>> polynomiale_carre(1, 1, 1, 3)91

4

Quel est le nombre de multiplications effectuées par votre définition ? Pouvez-vous proposer uneversion plus efficace ?

Exercice 1.4 : Calcul du n-ième nombre de Fermat

Les nombres de Fermat sont, en arithmétique, des nombres qui s’écrivent sous la forme Fn =22n + 1. Fermat conjectura qu’ils étaients tous premiers (ils sont en fait, premiers jusqu’à F4, etnon-premiers de F5 à F32. On connaît peu la primalité de ces nombres à partir de F33).

Le but de cet exercice est d’écrire un programme permettant de calculer, étant donné une valeurn quelconque, le n-ième nombre de Fermat.

Question 1

Donner une définition et un jeu de tests de la fonction fermat qui calcule Fn, le n-ième nombrede Fermat dont la valeur est 22n + 1.

Rappel : La fonction exponentiation est définie dans la carte de référence.

Par exemple :>>> fermat(0)3

>>> fermat(1)5

>>> fermat(2)17

>>> fermat(5)4294967297

Question 2

En Python, proposer une expression permettant de vérifier que F5 est divisible par 641, et n’estdonc pas premier.

5

Thème 2 : Exercices avec fonctions simples

Exercice 2.1 : Calcul des mentions

Cet exercice a pour but de faire manipuler des alternatives multiples et/ou imbriquées. Il s’agitde calculer la mention correspondant à une note sur 20.

Question 1

Donner une définition en Python de la fonction mention qui calcule la mention correspondant àune note (sur 20) donnée en utilisant les intervalles de notes suivants :

— [0, 10[→ Eliminé,— [10, 12[→ Passable,— [12, 14[→ AB,— [14, 16[→ B,— [16, 20]→ TB.

Les mentions seront représentées par des chaînes de caractères encadrées par des guillemetssimples. La mention Eliminé sera par exemple représentée par la valeur 'Eliminé' de type str.

Voici quelques exemples d’applications de la fonction mention :>>> mention(0)'Eliminé'

>>> mention(8)'Eliminé'

>>> mention(10)'Passable'

>>> mention(12.5)'AB'

>>> mention(15)'B'

>>> mention(20)'TB'

Remarque : penser à utiliser le mot-clef elif pour les alternatives multiples.

Question 2

Définir à nouveau la fonction mention, cette fois-ci en imbriquant les structures conditionnelles.

L’objectif est de minimiser le nombre moyen de tests conditionnels effectués en fonction de larépartition des notes, en supposant que la majorité des notes se situent entre 10 et 12.

6

Exercice 2.2 : Manipulation des booléens

Cet exercice a pour but de définir des fonctions sur les booléens en utilisant des alternatives.

Question 1

Sans utiliser les opérateurs logiques or, and et not, écrire les trois prédicats ou, et et non dontles spécifications sont les suivantes :def ou(p, q):

"""bool * bool -> bool

retourne la disjonction de p et q."""

def et(p, q):"""bool * bool -> bool

retourne la conjonction de p et q."""

def non(p):"""bool -> bool

retourne la négation de p."""

Par exemple :>>> ou(True, False)True

>>> ou(et(True, False), False)False

>>> et(ou(False, True), non(False))True

>>> non(non(3 == 1 + 2))True

Remarque : les jeux de tests proposés devront couvrir tous les cas possibles.

Question 2

Que se passe-t-il si on évalue l’expression suivante ?ou(3 == 3, 5 // 0 == 2)

Quelle est la différence avec l’évaluation de l’expression suivante ?(3 == 3) or (5 // 0 == 2)

Même questions pour l’expression :

7

et(3 == 4, 5 // 0 == 2)

comparée à :(3 == 4) and (5 // 0 == 2)

Question 3

En utilisant les fonctions écrites à la question 1, écrire les prédicats implique et ou_exclusifdont les spécifications sont les suivantes :def implique(p, q):

"""bool * bool -> bool

retourne le résultat de 'p implique q'."""

def ou_exclusif(p, q):"""bool * bool -> bool

retourne le résultat de 'p xor q'."""

Il peut être utile de se rappeler les formules de logique suivantes :

— p implique q est équivalent à (la négation de p) ou q.— p xor q est équivalent à (p et (la négation de q)) ou ((la négation de p) et

q).

Par exemple :>>> implique(False, False)True

>>> implique(True, False)False

>>> implique(True, 3 == 3)True

>>> ou_exclusif(True, False)True

>>> ou_exclusif(3 == 2, 3 == 3)True

>>> ou_exclusif(2 == 2, 3 == 3)False

Remarque : encore une fois, on s’assurera que les jeux de tests couvrent tous les cas possibles.

Question 4

En utilisant les prédicats de la question précédente, écrire le prédicat equivalent de spécification:

8

def equivalent(p, q):"""bool * bool -> bool

retourne True si et seulement si p et q sont équivalents."""

Il peut être utile de se rappeller la formule de logique suivante :

— p équivaut à q si et seulement p implique q et q implique p.

Par exemple :>>> equivalent(True, 3 == 3)True

>>> equivalent(True, 3 == 4)False

>>> equivalent(3 == 2, 3 == 8)True

Remarque : le jeu de tests de equivalent devra encore une fois couvrir tous les cas possibles.

9

Thème 3 : Exercices simples sur les boucles

Exercice 3.1 : Somme des impairs

Question 1

Donner une définition de la fonction somme_impairs_inf telle que somme_impairs_inf(n)renvoie la somme des entiers impairs inférieurs ou égaux à n.

Par exemple :>>> somme_impairs_inf(1)1

>>> somme_impairs_inf(2)1

>>> somme_impairs_inf(5)9

Question 2

Donner une définition de la fonction somme_premiers_impairs telle que somme_premiers_impairs(n)renvoie la somme des n premiers entiers impairs.

Par exemple :>>> somme_premiers_impairs(1)1

>>> somme_premiers_impairs(2)4

>>> somme_premiers_impairs(5)25

Remarque : comme les exemples ci-dessus le suggérent, la somme des n premiers impairs vautn2 (le démontrer est un bon exercice mathématique). On exploitera cette propriété dans les jeuxde tests (rappel : l’opérateur d’élévation à la puissance est ** en Python).

Question 3

Effectuer la simulation de boucle pour l’application somme_premiers_impairs(5) donc pourn=5.

10

Exercice 3.2 : Nombres premiers

Le but de cet exercice est d’écrire une fonction qui teste si un nombre est premier ou non. Cecipermet d’étudier les alternatives dans les boucles ainsi que les sorties anticipées de fonction.

On rappelle qu’un entier naturel n est dit premier s’il n’existe aucun entier naturel autre que 1et n lui-même qui le divise.

Par convention, 1 n’est pas un nombre premier.

Question 1

Donner une définition de la fonction divise qui, étant donné un entier naturel non nul n et unentier naturel p renvoie True si n divise p, False sinon.

Par exemple :>>> divise(1, 4)True

>>> divise(2, 4)True

>>> divise(3,4)False

>>> divise(4,2)False

Question 2

On se propose de définir la fonction est_premier qui, étant donné un entier naturel n, renvoieTrue si n est premier, False sinon.

Par exemple :>>> est_premier(0)False

>>> est_premier(1)False

>>> est_premier(2)True

>>> est_premier(17)True

>>> est_premier(357)False

Donner deux définitions distinctes de la fonction est_premier :

— une première définition sans sortie anticipée de la fonction

11

— une seconde définition avec sortie anticipée

Exercice 3.3 : Suite de Fibonacci

Dans cet exercice, nous nous intéressons aux calculs répétitifs autour des nombres de la suite deFibonacci.

Les termes de la suite de Fibonacci sont définis par :

F0 = 0F1 = 1Fn = Fn−2 + Fn−1 pour tout n > 1

Question 1

Proposer une définition de la fonction fibonacci qui calcul le n-ième terme de la suite deFibonacci.

Les premiers termes de cette suite sont les suivants :

F0 F1 F2 F3 F4 F5 F6 F7 F8

0 1 1 2 3 5 8 13 21

Remarque : il sera utile de séparer les cas n == 0 et n >= 1. On pourra également avoir besoind’une variable temporaire temp pour stocker un résultat intermédiaire.

Question 2

Effectuer la simulation de la boucle du cas n >= 2 pour fibonacci(8).

Quelle est valeur de F8 ?

Question 3

La suite de Fibonacci possède de nombreuses propriétés intéressantes. L’une de ces propriétéslui donne même un côté un peu mystique.

Commençons donc à étudier cette propriété qui repose sur les divisions entre éléments consécutifsde la suite de Fibonacci, donc la suite :

Dk = Fk

Fk−1pour k ≥ 2

Donner une définition de la fonction fibo_diff qui retourne le k-ième terme de la suite D.

Donner un jeu de tests pour les trois premiers termes de la suite.

12

Question 4

Voici quelques valeurs de fibo_diff pour k ≥ 5 :>>> fibo_diff(5)1.6666666666666667

>>> fibo_diff(10)1.6176470588235294

>>> fibo_diff(41)1.618033988749895

On peut montrer en fait que la suite Dk converge et tend, lorsque k tend vers l’infini, vers lavaleur suivante :

ϕ = 1 +√

52

>>> import math>>> (1 + math.sqrt(5)) / 21.618033988749895

Au 41-ième terme de la suite nous avons déjà atteint la précision maximale pour l’approximationde la constante ϕ qui n’est autre que le célèbre nombre d’or, cher aux architectes, peintres,etc.

Cette propriété de la suite Dk de converger vers le nombre d’or ϕ nous offre un moyen alternatifpour calculer le n-ième terme de la suite de Fibonacci.

L’idée est d’exploiter la formule :

Fn ≈ϕn

√5

lorsque n est «suffisamment» grand.

En utilisant l’opérateur ** d’élévation à la puissance de Python, proposer une définition de lafonction fibo_approx qui utilise la formule précédente pour approcher les éléments de la suitede Fibonacci.

Remarque : il n’est pas évident de tester cette fonction, mais on peut donner les exemplessuivants :>>> fibo_approx(5)4.959674775249769

>>> fibonacci(5)5

>>> fibo_approx(10)55.00363612324743

>>> fibonacci(10)55

13

On peut voir sur ces exemples que l’approximation est plutôt bonne même pour des valeursassez «petites» de n.

Que proposez-vous pour tester votre fonction d’approximation ?

Indice : l’arrondi d’un flottant x à l’entier le plus proche (vers 0) se note round(x) en Python.

Complément : la page Wikipedia sur le thème Suite de Fibonacci contient de nombreusesinformations intéressantes sur ce thème.

14

Thème 4 : Exercices avancés sur les boucles

Exercice 4.1 : Couples et intervalles

Cet exercice se concentre sur l’utilisation des boucles imbriquées ainsi que sur la notion desorties de boucle et de fonction anticipées. On s’intéresse pour ce faire aux couples d’entiersappartenant à un intervalle.

Question 1

Donner une définition de la fonction nb_couples_intervalle qui, étant donné deux entiers net p tels que n ≤ p, renvoie le nombre de couples (i, j) d’entiers appartenant à l’intervalle [n, p]tels que i < j.

Par exemple :>>> nb_couples_intervalle(0, 0)0

>>> nb_couples_intervalle(2, 4)3

>>> nb_couples_intervalle(-1, 3)10

Question 2

Donner une définition de la fonction nb_couple_divise qui, étant donné deux entiers n et ptels que n ≤ p, compte le nombre de couples (i, j) d’entiers distincts appartenant à l’intervalle[n, p] tels que i divise j.

Par exemple :>>> nb_couples_divise(4,6)0

>>> nb_couples_divise(2,6)3

>>> nb_couples_divise(-1,1)2

>>> nb_couples_divise(1,10)17

15

Question 3 : tracer une exécution (TME)

Modifier la fonction précédente pour qu’elle trace l’exécution des boucles imbriquées. Il fautpour cela insérer des instructions d’affichage (print) au bon endroit.

Par exemple :>>> nb_couples_divise_trace(2,6)couple ( 2 , 3 )couple ( 2 , 4 )------------2 divise 4 !------------couple ( 2 , 5 )couple ( 2 , 6 )------------2 divise 6 !------------couple ( 3 , 4 )couple ( 3 , 5 )couple ( 3 , 6 )------------3 divise 6 !------------couple ( 4 , 5 )couple ( 4 , 6 )couple ( 5 , 6 )3

Question 4 : Sortie de boucle anticipée

On se pose maintenant le problème non pas du nombre mais de l’existence d’un tel couple (i, j)tel que i divise j.

Une solution possible pour répondre à ce problème pourrait être la définition de la fonctionsuivante :def existe_couples_divise(n, p):

""" int * int -> boolHypothèse : n <= p

renvoie True s'il existe un couple (i,j) d'entiers appartenantà l'intervalle [n,p] tels que i != j et i divise j,ou False sinon."""

return nb_couples_divise(n,p) > 0

# Jeu de testsassert existe_couples_divise(0, 0) == Falseassert existe_couples_divise(2, 6) == Trueassert existe_couples_divise(-1, 1) == True

16

assert existe_couples_divise(1, 10) == Trueassert existe_couples_divise(21, 34) == False

Le problème de cette définition est qu’elle n’est pas efficace puisqu’elle calcule tous les couplespossibles alors qu’il suffit de s’arrêter dès qu’un couple est trouvé.

Donner une définition de la fonction existe_couples_divise_rapide qui utilise une sortie deboucle anticipée pour améliorer l’efficacité de la fonction.

Question 5 : Sortie de fonction anticipée

Donner une variante de cette fonction utilisant une sortie de fonction anticipée.

Question 6 subsidiaire (TME)

Donner des variantes des fonctions existe_couple_divise, existe_couple_divise_rapideet existe_couple_divise_rapide2 qui affichent le nombre de couples testés avant de renvoyerla réponse.

Par exemple :>>> existe_couples_divise_trace_tour(3, 1000)nombre de couples testés : 497503True

>>> existe_couples_divise_rapide_trace_tour(3, 1000)nombre de couples testés : 3True

>>> existe_couples_divise_rapide2_trace_tour(3, 1000)nombre de couples testés : 3True

>>> existe_couples_divise_trace_tour(21, 35)nombre de couples testés : 105False

>>> existe_couples_divise_rapide_trace_tour(21, 35)nombre de couples testés : 105False

>>> existe_couples_divise_rapide2_trace_tour(21, 35)nombre de couples testés : 105False

17

Thème 5 : Exercices sur les intervalles et chaînes de carac-tères

Exercice 5.1 : Voyelles

Cet exercice étudie des réductions, filtrages et transformations simples de chaînes. On s’intéresseaux voyelles présentes dans une chaîne de caractère.

Pour identifier une voyelle, on utilise le prédicat suivant :def est_voyelle(c):

"""str -> boolHypothèse : len(c) == 1

retourne True si et seulement si c est une voyelleminiscule ou majuscule."""

return (c == 'a') or (c == 'A') \or (c == 'e') or (c == 'E') \or (c == 'i') or (c == 'I') \or (c == 'o') or (c == 'O') \or (c == 'u') or (c == 'U') \or (c == 'y') or (c == 'Y')

# Jeu de testsassert est_voyelle('a') == Trueassert est_voyelle('E') == Trueassert est_voyelle('b') == Falseassert est_voyelle('y') == Trueassert est_voyelle('z') == False

Question 1 : réduction

Donner une définition de la fonction nb_voyelles qui retourne le nombre de voyelles présentesdans une chaîne s passée en paramètre. Il s’agit donc d’une réduction d’une chaîne vers le typeint.

Par exemple :>>> nb_voyelles('la maman du petit enfant le console')12

>>> nb_voyelles('mr brrxcx')0

>>> nb_voyelles('ai al o ents')5

18

Question 2 : accents

Considérons l’application suivante :>>> nb_voyelles('la maman du bébé le réconforte')8

On peut remarquer que les lettres accentuées ne sont pas prises en compte dans le compte desvoyelles. Proposer une définition de la fonction nb_voyelles_accents qui corrige ce défaut.

Par exemple :>>> nb_voyelles_accents('la maman du bébé le réconforte')11

Question 3 : filtrage

Donner une définition de la fonction de filtrage sans_voyelle qui élimine les voyelles d’unechaîne de caractères.

Par exemple :>>> sans_voyelle('aeiouy')''

>>> sans_voyelle('la balle au bond rebondit')'l bll bnd rbndt'

>>> sans_voyelle('mr brrxcx')'mr brrxcx'

Question 4 : transformation

Donner une définition de la fonction mot_mystere qui remplace dans une chaîne de caractèresles voyelles par des symboles soulignés _.

Par exemple :>>> mot_mystere('aeiouy')'______'

>>> mot_mystere('la balle au bond rebondit bien')'l_ b_ll_ __ b_nd r_b_nd_t b__n'

>>> mot_mystere('mr brrxcx')'mr brrxcx'

19

Exercice 5.2 : Palindromes

Question 1

Donnez la spécification et une définition de la fonction est_palindrome telle queest_palindrome(s) retourne True si s est un palindrome, c’est-à-dire une chaîne quiest la même si on la lit de la gauche vers la droite ou de la droite vers la gauche.

Par exemple :>>> est_palindrome('')True

>>> est_palindrome('je ne suis pas un palindrome')False

>>> est_palindrome('aba')True

>>> est_palindrome('amanaplanacanalpanama')True

Question 2

On se propose maintenant de définir une fonction de création automatique de palindromes.

Cette fonction miroir prend une chaîne de caractères en paramètre et retourne un palindromeà partir de cette chaîne, correspondant simplement au miroir de la chaîne.

Par exemple :>>> miroir('abc')'abccba'

>>> miroir('amanaplanacanal')'amanaplanacanallanacanalpanama'

>>> miroir('do-re-mi-fa-sol')'do-re-mi-fa-sollos-af-im-er-od'

20

Thème 6 : Exercices simples sur les listes

Exercice 6.1 : Listes de répétitions

Dans cet exercice introductif, on s’intéresse à la construction de listes par répétition d’un élémentou d’une liste d’éléments.

Question 1

Donner une définition de la fonction repetition qui, étant donné un élément x et un entiernaturel k, renvoie la liste contenant k occurrences de x.

Par exemple :>>> repetition("thon", 4)['thon', 'thon', 'thon', 'thon']

>>> repetition(3, 8)[3, 3, 3, 3, 3, 3, 3, 3]

>>> repetition(5, 0)[]

Question 2

Donner une définition de la fonction repetition_bloc qui, étant donné une liste L et un entiernaturel k, renvoie la liste obtenue en concaténant k fois la liste L.

Par exemple :>>> repetition_bloc(["chat", "thon", "loup"], 3)['chat', 'thon', 'loup', 'chat', 'thon', 'loup', 'chat', 'thon', 'loup']

>>> repetition_bloc([1, 2, 3], 5)[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]

>>> repetition_bloc([1, 2, 3, 4, 5], 0)[]

Exercice 6.2 : Maximum d’une liste

Cet exercice propose quelques problèmes de réduction associés à la notion de maximum.

21

Question 1

Donner une définition de la fonction max_liste qui, étant donné une liste non vide de nombres,renvoie le plus grand élément de cette liste.

Par exemple :>>> max_liste([3, 7, 9, 5.4, 8.9, 9, 8.999, 5])9

Question 2

Donner une définition de la fonction nb_occurrences qui, étant donné une liste L et un élémentx, renvoie le nombre d’occurrences de x dans L.

Par exemple :>>> nb_occurrences([3, 7, 9, 5.4, 8.9, 9, 8.999, 5], 9)2

>>> nb_occurrences(["chat", "ours", "chat", "chat", "loup"], "chat")3

>>> nb_occurrences(["chat", "ours", "chat", "chat", "loup"], "ou")0

Question 3

Donner une définition de la fonction nb_max qui, étant donné une liste non vide de nombres L,renvoie le nombre d’occurrences du maximum de L dans L.

Par exemple :>>> nb_max([3, 7, 9, 5.4, 8.9, 9, 8.999, 5])2

>>> nb_max([-2, -1, -5, -3, -1, -4, -1])3

Exercice 6.3 : Moyenne et variance

Cet exercice propose des problèmes assez simples de réduction et de transformation, sur unethématique statistique.

Question 1

Donner une définition de la fonction somme qui, étant donné une liste de nombres, renvoie lasomme des éléments de cette liste, ou 0 si la liste est vide.

22

Par exemple :>>> somme([1, 2, 3, 4, 5])15

>>> somme([1, 2.5, 3.2, 4, 5])15.7

>>> somme([1, 2.5, 3.5, 4, 5])16.0

>>> somme([])0

Question 2

Donner une définition de la fonction moyenne qui, étant donné une liste non vide de nombres,renvoie la moyenne des éléments de cette liste.

Par exemple :>>> moyenne([1, 2, 3, 4, 5])3.0

>>> moyenne([1, 2.5, 3.5, 4, 5])3.2

>>> moyenne([5])5.0

Question 3

Donner une définition de la fonction carres qui, étant donné une liste L de nombres, renvoie laliste des carrés des éléments de L.

Par exemple :>>> carres([1, 2, 3, 4, 5])[1, 4, 9, 16, 25]

>>> carres([1, -2, -3, 4, 5])[1, 4, 9, 16, 25]

>>> carres([])[]

>>> carres([10, 0.5, 2.0])[100, 0.25, 4.0]

# Jeu de testsassert carres([1, 2, 3, 4, 5]) == [1, 4, 9, 16, 25]assert carres([-5, -1, 2]) == [25, 1, 4]

23

assert carres([]) == []assert carres([10, 0.5]) == [100, 0.25]

Question 4

La variance d’une liste de nombres est égale à la différence entre la moyenne des carrés deséléments de la liste et le carré de la moyenne des éléments de la liste.

Donner une définition de la fonction variance qui, étant donné une liste non vide de nombres,renvoie la variance de la liste.

Par exemple :>>> variance([10, 10, 10, 10])0.0

>>> variance([20, 0, 20, 0])100.0

Question 5

L’écart-type d’une liste de nombres est égal à la racine carrée de la variance de la liste.

Donner une définition de la fonction ecart_type qui, étant donné une liste non vide de nombres,renvoie l’écart-type de la liste.>>> ecart_type([10, 10, 10, 10])0.0

>>> ecart_type([20, 0, 20, 0])10.0

>>> ecart_type([15, 15, 5, 5])5.0

>>> ecart_type([12, 11, 10, 12, 11])0.7483314773547993

Exercice 6.4 : Listes obtenues par multiplication ou division

Dans cet exercice, on résout des problèmes de transformation et de filtrage, ainsi que decombinaison de listes.

Question 1

Donner une définition de la fonction liste_mult qui, étant donné une liste L d’entiers et unentier k, retourne la liste obtenue en multipliant par k tous les éléments de L.

Par exemple :

24

>>> list_mult([3, 5, 9, 4], 2)[6, 10, 18, 8]

>>> list_mult([], 2)[]

Question 2

Donner une définition de la fonction liste_div qui, étant donné une liste L d’entiers et unentier k non nul, retourne la liste obtenue en divisantpar k les éléments de L qui sont multiples de k et en supprimant les autres.

Par exemple :>>> list_div([2, 7, 9, 24, 6], 2)[1, 12, 3]

>>> list_div([2, 7, 9, 24, 6], 3)[3, 8, 2]

>>> list_div([2, 7, 9, 24, 6], 5)[]

>>> list_div([2, 7, 9, -24, 6], -3)[-3, 8, -2]

>>> list_div([], 3)[]

Exercice 6.5 : Découpages

Pour comprendre un mécanisme, il est utile de savoir le reconstruire. Nous appliquons ce principedans cet exercice en reconstruisant les découpages de listes.

Question 1 : découpages simples

Donner une définition de la fonction decoupage_simple qui, étant donné une liste L et deuxentiers i et j, retourne le découpage L[i:j] en faisant l’hypothèse que les indices i et j sontpositifs.

Remarque : on ne peut bien sûr pas utiliser de découpages dans la définition puisque notreobjectif consiste à les redéfinir.

Le jeu de tests pour cette fonction correspond aux exemples du cours sur les découpages :# Jeu de tests

# Comptine : list[str]Comptine = ['am', 'stram', 'gram', 'pic', 'pic', 'col', 'gram']

25

assert decoupage_simple(Comptine, 1, 3) == Comptine[1:3]assert decoupage_simple(Comptine, 3, 4) == Comptine[3:4]assert decoupage_simple(Comptine, 3, 3) == Comptine[3:3]assert decoupage_simple(Comptine, 5, 3) == Comptine[5:3]assert decoupage_simple(Comptine, 0, 7) == Comptine[0:7]

Question 2 : découpage avec pas

Donner une définition de la fonction decoupage_pas telle que decoupage_pas(L, i, j, p)retourne le même résultat que L[i:j:p] en supposant i, j positifs et p strictement positif.

Voici le jeu de tests associé :# Jeu de tests

# Comptine : list[str]Comptine = ['am', 'stram', 'gram', 'pic', 'pic', 'col', 'gram']

assert decoupage_pas(Comptine,1, 5, 2) == Comptine[1:5:2]assert decoupage_pas(Comptine,2, 6, 1) == Comptine[2:6:1]

Question 3 : pas inverse

Donner une définition de la fonction decoupage_pas_inv telle que decoupage_pas_inv(L, i,j, p) retourne le même résultat que L[i:j:p] en supposant i, j positifs et p strictementnégatif.

Voici le jeu de tests associé :# Jeu de tests

# Comptine : list[str]Comptine = ['am', 'stram', 'gram', 'pic', 'pic', 'col', 'gram']

assert decoupage_pas_inv(Comptine, 5, 2, -2) == Comptine[5:2:-2]assert decoupage_pas_inv(Comptine, 6, 0, -1) == Comptine[6:0:-1]assert decoupage_pas_inv(Comptine, 6, 0, -3) == Comptine[6:0:-3]

Question 4 : découpage généralisé

On souhaite maintenant redéfinir le découpage général decoupage tel quel découpage(L,i,j,p)retourne le même résultat que l’expression L[i:j:p]. La seule contrainte imposée est que p estdifférent de 0.

Il nous reste à traiter les indices négatifs, et pour cela nous utilisons la fonction de normalisationsuivante.

26

def normalisation(k, l):""" int * int -> intHypothèse : l >= 0retourne la normalisation de l'indice k pour

une liste de longueur l."""

if k < 0: # indice négatifif -k <= l: # dans l'intervalle [O;l]

return l + kelse: # en dehors de l'intervalle [0;l]

return 0else: # indice positif

if k > l: # en dehors de l'intervalle [0;l]return l

else:return k # déjà normalisé

# jeu de testsassert normalisation(0, 6) == 0 # positif dans [0;6]assert normalisation(4, 6) == 4 # positif dans [0;6]assert normalisation(6, 6) == 6 # positif dans [0;6]assert normalisation(7, 6) == 6 # positif hors [0;6]assert normalisation(-0, 6) == 0 # négatif (cas limite)assert normalisation(-1, 6) == 5 # négatif dans [0;6]assert normalisation(-3, 6) == 3 # négatif dans [0;6]assert normalisation(-5, 6) == 1 # négatif dans [0;6]assert normalisation(-6, 6) == 0 # négatif dans [0;6]assert normalisation(-7, 6) == 0 # négatif hors [0;6]

En utilisant cette fonction ainsi que les fonction decoupage_pas et decoupage_pas_inv, pro-poser une définition de la fonction decoupage pour le découpage généralisé.

Remarque : on reprendra tous les exemples du cours pour valider la fonction.

27

Thème 7 : Exercices avancés sur les listes

Exercice 7.1 : Nombres complexes

Le but de cet exercice est de définir quelques opérations simples sur les nombres complexes cequi amène à définir des fonctions simples manipulant des couples de flottants.

Question 1

Les nombres complexes sont décrits la plupart du temps par un couple de réels qui définitleur partie réelle et leur partie imaginaire. Définissons donc un type Complexe = tuple[floatfloat] pour une telle représentation. Ainsi le nombre complexe 2 + 3i sera représenté par lecouple (2.0, 3.0), le nombre i par (0.0, 1.0) et un réel r par (r, 0.0).

Donner la spécification et une définition en Python des fonctions partie_relle etpartie_imaginaire telles que partie_reelle(c) (resp. partie_imaginaire(c)) renvoie lapartie réelle (resp. imaginaire) d’un nombre complexe. Par exemple :>>> partie_reelle((2.0,3.0))2.0

>>> partie_imaginaire((2.0,3.0))3.0

>>> partie_reelle((0.0,1.0))0.0

>>> partie_imaginaire((0.0,1.0))1.0

>>> partie_reelle((4.0,0.0))4.0

>>> partie_imaginaire((4.0,0.0))0.0

Question 2

Donner la spécification et une définition en Python de la fonction addition_complexe telle queaddition_complexe(c1, c2) renvoie l’addition des nombres complexes c1 et c2

Par exemple :>>> addition_complexe((1.0,0.0), (0.0,1.0))(1.0, 1.0)

>>> addition_complexe((2.0,3.0), (0.0,1.0))(2.0, 4.0)

28

Question 3

On rappelle que le produit de deux nombres complexes (a + bi) et (c + di) est donné par(a + bi) ∗ (c + di) = (ac− bd) + (ad + bc)i. Donner la spécification et une définition en Pythonde la fonction produit_complexe telle que produit_complexe(c1, c2) renvoie le produit desnombres complexes c1 et c2

Par exemple :>>> produit_complexe((0.0,0.0), (1.0,1.0))(0.0, 0.0)

>>> produit_complexe((0.0,1.0), (0.0,1.0))(-1.0, 0.0)

>>> produit_complexe((2.0,3.0), (0.0,1.0))(-3.0, 2.0)

Remarque : les nombres complexes existent en fait en Python. Ils ont pour type complex.

Exercice 7.2 : Base de données des étudiants

Dans cet exercice, nous illustrons une utilisation courante des listes de n-uplets : la manipulationd’une base de données.

Nous manipulerons une base de données composée d’une liste d’enregistrements, chaque enregis-trement étant un quadruplet avec :

1. le nom de l’étudiant de type str2. le prénom de l’étudiant de type str3. son numéro d’étudiant de type int4. d’une liste de notes sur 20 obtenues aux examens, de type list[int]

On définit donc l’alias de type suivant :# type Etudiant = tuple[str, str, int, list[int]]

On fait de plus l’hypothèse implicite que toutes les notes enregistrées sont entre 0 et 20.

La base de données manipulée est donc du type list[Etudiant].

Pour l’exercice on considérera la base de données suivante :# BaseUPMC : list[Etudiant]BaseUPMC = [('GARGA', 'Amel', 20231343, [12, 8, 11, 17, 9]),

('POLO', 'Marcello', 20342241, [9, 11, 19, 3]),('AMANGEAI', 'Hildegard', 20244229, [15, 11, 7, 14, 12]),('DENT', 'Arthur', 42424242, [8, 4, 9, 4, 12, 5]),('ALEZE', 'Blaise', 30012024, [17, 15, 20, 14, 18, 16, 20]),('D2', 'R2', 10100101, [10, 10, 10, 10, 10, 10])]

29

Question 1 : moyenne des notes

Donner une définition de la fonction note_moyenne qui, à partir d’une liste de notes (entre 0 et20) retourne leur moyenne.

Par exemple :>>> note_moyenne([12, 8, 14, 6, 5, 15])10.0

>>> note_moyenne([])0.0

Question 2 : moyenne générale

Donner une définition de la fonction moyenne_generale qui, étant donné une base de donnéesd’étudiants, retourne la moyenne générale des notes des étudiants enregistrés (c’est-à-dire lamoyenne des moyennes de chaque étudiant).

Par exemple :>>> moyenne_generale(BaseUPMC)11.307142857142857

>>> moyenne_generale([])0.0

Question 3 : Nom et prénom du meilleur étudiant

On cherche maintenant dans la base le nom et le prénom de l’étudiant qui possède la meilleuremoyenne. La spécification utilisée est la suivante :def top_etudiant(BD):

""" list[Etudiant] -> tuple[str, str]Hypothèse : len(BD) > 0

retourne l'étudiant de la base BD avec la meilleuremoyenne. Si des étudiants sont ex-aequo alors onretourne le premier dans l'ordre séquentiel de la liste."""

Pour notre base UPMC on obtient :>>> top_etudiant(BaseUPMC)('ALEZE', 'Blaise')

Question 4 : Recherche d’une moyenne

Donner une définition de la fonction partielle recherche_moyenne qui étant donné un numérod’étudiant rnum ainsi qu’une base de données BD, retourne la moyenne de l’étudiant correspondou None si ce numéro d’étudiant est inconnu.

30

Par exemple :>>> recherche_moyenne(20244229, BaseUPMC)11.8

>>> recherche_moyenne(20342241, BaseUPMC)10.5

>>> recherche_moyenne(2024129111, BaseUPMC)

Remarque : dans ce dernier cas, None est retourné et donc l’interprète Python ne montre pasde réponse.

31

Thème 8 : Exercices sur les compréhensions de listes

Exercice 8.1 : Variance

Cet exercice permet de manipuler des compréhensions simples sur une thématique de statistique.

La notion de moyenne est pratique pour synthétiser une série de nombres en ce qu’elle donneune valeur caractéristique de cette série. Cependant des séries de nombres différents peuventavoir une moyenne identique. Ainsi, les listes [10,10,10] et [0,10,20] ont toutes deux unemoyenne de 10. Dans le premier cas pourtant, la valeur 10 est bien plus représentative que dansle deuxième cas puisque toutes les nombres de la liste valent 10.

La notion de variance permet justement de rendre compte de ce phénomène en calculant ladispersion des valeurs de la liste vis-à-vis de la moyenne. Plus précisément, elle calcule lamoyenne des carrés des écarts à la moyenne. Ainsi dans notre exemple, la variance de la premièreliste est :

((10− 10)2 + (10− 10)2 + (10− 10)2)/3 = 0/3 = 0

Alors que la variance de la seconde liste est :

((0− 10)2 + (10− 10)2 + (20− 10)2)/3 = 200/3 = 66.66666666

Cet exercice consiste à écrire une fonction permettant de calculer la variance d’une série denombres. Le but est bien sûr d’utiliser le plus possible les compréhensions pour répondre auxquestions. À noter que ce problème du calcul de la variance a déjà été traité lors du thème 6mais en proposant un autre algorithme que celui présenté ci-dessous.

Question 1

Donner la définition et la spécification de la fonction moyenne qui calcule la moyenne d’une listenon vide de nombres. Par exemple :>>> moyenne([10,10,10])10.0

>>> moyenne([0,10,20])10.0

>>> moyenne([1,2])1.5

32

Question 2

En utilisant une compréhension, donner la définition et la spécification de la fonctionecart_nombre qui, étant donné une liste de nombres L et un nombre x, renvoie la liste de lavaleur absolue de la différence des nombres de L avec x. Par exemple>>> ecart_nombre([10,10,10],10)[0, 0, 0]

>>> ecart_nombre([0,10,20], 10)[10, 0, 10]

>>> ecart_nombre([1,2],1.5)[0.5, 0.5]

Question 3

En utilisant une compréhension, donner la définition et la spécification de la fonctionliste_carre qui, étant donné une liste de nombres L, renvoie la liste des carrés des élémentsde L. Par exemple>>> liste_carre([0,0,0])[0, 0, 0]

>>> liste_carre([10,0,10])[100, 0, 100]

>>> liste_carre([0.5,0.5])[0.25, 0.25]

Question 4

Donner la définition et la spécification de la fonction variance qui, étant donné une liste denombres L, renvoie la variance associée à L. Par exemple>>> variance([10,10,10])0.0

>>> variance([0,10,20])66.66666666666667

>>> variance([1,2])0.25

Question 5

L’implémentation précédente est un peu inefficace car elle parcourt une première fois la listepour calculer les écarts à la moyenne, puis une seconde fois pour calculer le carré de cesécarts. Proposer une implémentation plus efficace de la fonction variance ne faisant qu’un seulparcours.

33

Thème 9 : Exercices simples sur les ensembles et diction-naires

Exercice 9.1 : Magasin en ligne

Dans cet exercice, nous nous familiarisons avec les manipulations de dictionnaires sur unethématique de magasin en ligne.

«Chez Geek and sons tout ce qui est inutile peut s’acheter, et tout ce qui peuts’acheter est un peu trop cher.»

La base de prix des produits de Geek and sons est représentée en Python par un dictionnaire detype dict[str:float] avec :

— les noms de produits, de type str, comme clés— les prix des produits, de type float, comme valeurs associées.

Question 1

Donner une expression Python pour construire la base des prix des produits correspondant à latable suivante :

Nom du produit Prix TTCSabre laser 229.0Mitendo DX 127.30Coussin Linux 74.50Slip Goldorak 29.90Station Nextpresso 184.60

Question 2

Donner une définition de la fonction disponibilite qui étant donné un nom de produit prodet une base de prix Prix, retourne True si le produit est présent dans la base, ou False sinon.

Question 3

Donner une définition de la fonction prix_moyen qui, étant donné une base de prix (contenantau moins un produit), retourne le prix moyen des produits disponibles.

Par exemple :>>> prix_moyen({'Sabre Laser': 229.0,

'Mitendo DX': 127.30,'Coussin Linux' : 74.50,

34

'Slip Goldorak' : 29.90,'Station Nextpresso' : 184.60})

129.06

Question 4

Donner une définition de la fonction fourchette_prix qui, étant donné un prix minimummini, un prix maximum maxi et une base de Prix, retourne l’ensemble des noms de produitsdisponibles dans cette fourchette de prix.

Par exemple :>>> fourchette_prix(50.0, 200.0, {'Sabre Laser': 229.0,

'Mitendo DX': 127.30,'Coussin Linux' : 74.50,'Slip Goldorak' : 29.90,'Station Nextpresso' : 184.60})

{'Coussin Linux', 'Mitendo DX', 'Station Nextpresso'}

Question 5

Le panier est un concept omniprésent dans les sites marchands, Geeks and sons n’échappepas à la règle. En Python, le panier du client sera représenté par un dictionnaire de typedict[str:int] avec :

— les noms de produits comme clés— une quantité d’achat comme valeurs associées.

Donner une expression Python correspondant à l’achat de 3 sabres lasers, de 2 coussins Linuxet de 1 slip Goldorak.

Question 6

Donner une définition de la fonction tous_disponibles qui, étant donné un panier d’achatPanier et une base de Prix, retourne True si tous les produits demandés sont disponibles, ouFalse sinon.

Question 7

Donner une définition de la fonction prix_achats qui, étant donné un panier d’achat Panieret une base de Prix, retourne le prix total correspondant.

Par exemple :>>> prix_achats({'Sabre Laser': 3, 'Coussin Linux': 2, 'Slip Goldorak': 1},

{'Sabre Laser': 229.0,'Mitendo DX' : 127.30,'Coussin Linux' : 74.50,

35

'Slip Goldorak' : 29.90,'Station Nextpresso' : 184.60})

865.9

Remarque : on supposera que tous les articles du paniers sont disponibles dans la base deproduits.

Exercice 9.2 : Recettes de cuisine

Dans cet exercice, on s’intéresse à la définition de fonctions permettant de manipuler un livrede recettes de cuisine. Comme tout bon livre de recettes qui se respecte, chaque recette décritnotamment l’ensemble des ingrédients qui la composent. À titre d’exemple, un livre de recettesde desserts pourrait contenir les informations suivantes :

Recette IngrédientsGâteau au chocolat chocolat, oeuf, farine, sucre, beurreGâteau au yaourt yaourt, oeuf, farine, sucreCrêpes oeuf, farine, laitQuatre-quarts oeuf, farine, beurre, sucreKouign amann farine, beurre, sucre

Un livre de recettes est donc représenté en Python par un dictionnaire de type dict[str :set[str]]

— les noms des recettes, de type str, comme clés— l’ensemble des ingrédients, de type set[str], comme valeurs associées.

Ainsi, l’exemple précédent donnerait le dictionnaire Dessert suivant :Dessert = {

'gateau chocolat' : {'chocolat', 'oeuf', 'farine', 'sucre', 'beurre'},'gateau yaourt' : {'yaourt', 'oeuf', 'farine', 'sucre'},'crepes' : {'oeuf', 'farine', 'lait'},'quatre-quarts' : {'oeuf', 'farine', 'beurre', 'sucre'},'kouign amann' : {'farine', 'beurre', 'sucre'}}

Dans la suite de cet exercice, on pourra utiliser l’alias de type Recette pour dict[str :set[str]]

Question 1

Donner une définition de la fonction nb_ingredients qui, étant donnés un livre de recettes Det le nom d’une recette r contenue dans D, renvoie le nombre d’ingrédients nécessaires à larecette r.

Par exemple:

36

>>> nb_ingredients(Dessert, 'crepes')3

>>> nb_ingredients(Dessert, 'gateau chocolat')5

Question 2

Donner une définition de la fonction recette_avec qui, étant donnés un livre de recettes D etle nom d’un ingrédient i, renvoie l’ensemble des recettes qui utilisent cet ingrédient.

Par exemple :>>> recette_avec(Dessert, 'beurre'){'gateau chocolat', 'kouign amann', 'quatre-quarts'}

>>> recette_avec(Dessert, 'lait'){'crepes'}

>>> recette_avec(Dessert, 'fraise')set()

Question 3

Donner une définition de la fonction tous_ingredients qui, étant donné un livre de recettes D,renvoie l’ensemble de tous les ingrédients apparaissant au moins une fois dans une recette de D.

Par exemple :>>> tous_ingredients(Dessert){'beurre', 'chocolat', 'farine', 'lait', 'oeuf', 'sucre', 'yaourt'}

Question 4

Tout livre de recettes contient une table des ingrédients permettant d’associer à chaque ingré-dient l’ensemble des recettes qui l’utilisent. Une telle table est représentée en Python par letype dict[str : set[str]] dans lequel une clé est un ingrédient dont la valeur associée estl’ensemble des recettes qui l’utilisent.

Donner une définition de la fonction table_ingredients qui, étant donné un livre de recettesD, renvoie la table des ingrédients associée.

Par exemple :>>> table_ingredients(Dessert){'chocolat': {'gateau chocolat'},'oeuf' : {'crepes', 'gateau chocolat', 'gateau yaourt', 'quatre-quarts'},'lait' : {'crepes'},'yaourt' : {'gateau yaourt'},'farine' : {'crepes',

37

'gateau chocolat' ,'gateau yaourt' ,'kouign amann' ,'quatre-quarts' },

'beurre' : {'gateau chocolat', 'kouign amann', 'quatre-quarts'},'sucre' : {'gateau chocolat','gateau yaourt' ,'kouign amann' ,'quatre-quarts' }}

Question 5

Donner une définition de la fonction ingredient_principal qui, étant donné un livre derecettes D, renvoie le nom de l’ingrédient utilisé par le plus grand nombre de recettes. Onsupposera ici que D contient au moins une recette.

Par exemple :>>> ingredient_principal(Dessert)'farine'

Question 6

Certaines personnes sont allergiques à certains ingrédients. On aimerait donc pouvoir ne conserverd’un livre de recettes que celles qui n’utilisent pas un ingrédient donné.

Donner une définition de la fonction recettes_sans qui, étant donnés un livre de recettes Det un ingrédient i, renvoie un nouveau livre de recettes ne contenant que des recettes de Dn’utilisant pas l’ingrédient i.

Par exemple :>>> recettes_sans(Dessert, 'farine'){}

>>> recettes_sans(Dessert, 'oeuf'){'kouign amann': {'beurre', 'farine', 'sucre'}}

>>> recettes_sans(Dessert, 'beurre'){'gateau yaourt': {'farine', 'oeuf', 'sucre', 'yaourt'},'crepes' : {'farine', 'lait', 'oeuf'}}

Exercice 9.3 : Statistiques sur les lettres

Dans cet exercice, on effectue quelques calculs statistiques sur les fréquences de lettres dans destextes (chaînes de caractères).

38

Les fréquences (ou nombre d’occurrences) des lettres sont représentées sous la forme d’undictionnaire de type dict[str:int] avec :

— des lettres (caractères) comme clés— des entiers naturels (fréquence du caractère) pour les valeurs associées

Pour séparer les lettres de la langue française des autres caractères possibles dans les chaînes,on utilise la fonction suivante :def est_lettre(c):

""" str -> boolHypothèse : len(c) == 1 (caractère)Retourne True si le caractère c est une lettre, ou False sinon."""

return ((c >= 'a') and (c <= 'z')) \or ((c >= 'A') and (c <= 'Z')) \or (c in {'é', 'è', 'à', 'ù', 'œ'})

Question 1

Définir la fonction frequences_lettres qui étant donnée un chaîne de caractère s retourne lesfréquences des lettres de s sous la forme d’un dictionnaire de type dict[str:int].

Par exemple :>>> frequences_lettres('alea jacta est'){'j': 1, 'e': 2, 't': 2, 'c': 1, 'a': 4, 's': 1, 'l': 1}

>>> frequences_lettres("l'élève"){'é': 1, 'e': 1, 'v': 1, 'l': 2, 'è': 1}

Question 2

Définir une fonction lettre_freq_max qui retourne la lettre de fréquence maximale dans undictionnaire Freqs de fréquences.

Par exemple :>>> lettre_freq_max(frequences_lettres('alea jacta est'))'a'

>>> lettre_freq_max(frequences_lettres("l'élève"))'l'

Remarque : s’il y a plusieurs lettres de fréquence maximale, alors on n’en retourne qu’unechoisie arbitrairement.

Question 3 (en TME)

Dans cette question, nous aimerions effectuer notre petit test statistique sur un véritable texte.

39

Pour cela, nous allons tout d’abord définir une fonction chargement_texte permettant de lireun fichier texte et de placer le résultat dans une chaîne de caractères.

Remarque : nous n’étudions pas le chargment et la sauvegarde des fichiers dans ce cours, doncon utilisera cette fonction en suivant simplement sa spécification.def chargement_texte(fichier):

""" str -> strHypothèse : le fichier est présent sur le disqueRetourne la chaîne de caractères correspondant au contenudu fichier."""

# contenu : strcontenu = '' # contenu du fichier

with open(fichier, 'r') as f:contenu = f.read()

return contenu

On récupérera alors un fichier texte (encodage UTF-8) de langue française pour en étudier lecontenu.

On peut par exemple récupérer un texte intégral via le Projet Gutemberg, à l’adresse suivante :http://www.gutenberg.org

Pour le TME, on peut choisir son propre texte mais attention à ce qu’il ne soit pas tropvolumineux. Pour les exemples on a choisi Quatrevingt treize de Victor Hugo que l’on trouveradans :

/Vrac/1I001/quatrevingt-treize.txt

Donner deux expressions Python permettant de :

1. récupérer le dictionnaire des fréquences des lettres présentes dans votre texte d’exemple.2. trouver la lettre dont la fréquence est la plus grande.

Question 4

On souhaite maintenant connaître les lettres qui ne dépassent pas une fréquence donnée dans untexte. Donner une définition de la fonction lettres_freq_inf qui étant donné un dictionnairede fréquences Freqs et une fréquence fseuil retourne l’ensemble des lettres de fréquenceinférieure ou égale à fseuil.

Par exemple :>>> lettres_freq_inf(frequences_lettres('alea jacta est'), 1){'c', 'j', 'l', 's'}

40

>>> lettres_freq_inf(frequences_lettres("l'élève"), 2){'e', 'l', 'v', 'è', 'é'}

Remarque : on fera l’hypothèse que la fréquence de seuil est strictement positive. En effet,nous n’étudions pas l’absence d’un lettre dans le texte.

Question 5 (en TME)

Donner une expression Python permettant d’obtenir l’ensemble des lettres utilisées moins de100 fois dans votre texte.

41

Thème 10 : Exercices avancés sur les ensembles et diction-naires

Exercice 10.1 : Gestion de bibliothèque

Dans cet exercice, nous illustrons les compréhensions sur les dictionnaires en travaillant sur unebase de données de livres empruntables dans une bibliothèque.

La base de données que nous allons utiliser en exemple est la suivante :# LivresBD : dict[str:tuple[str,int]]LivresBD = {'Les misérables':('Victor Hugo', 5),

'Le dernier des Mohicans' :('James F. Cooper', 0),'Un animal doué de raison' : ('Robert Merle', 6),'Le grand Meaulnes' :('Alain Fournier', 1),'Notre-dame de Paris' :('Victor Hugo', 4),'Les comtemplations' :('Victor Hugo', 0) }

La base permet de rechercher rapidement un livre à partir de son titre (clé du dictionnaire). Onobtient alors l’auteur du livre ainsi que le nombre d’exemplaire(s) empruntable(s) en stock.

Par exemple :>>> LivresBD['Notre-dame de Paris']('Victor Hugo', 4)

Question 1

Proposer une définition de la fonction auteurs qui, étant donné une base de Livres, retournel’ensemble des noms d’auteurs de cette base.

Question 2

Donner une définition de la fonction titres_empruntables qui, étant donné une base de Livres,retourne l’ensemble des livres empruntables.

Par exemple :>>> titres_empruntables(LivresBD){'Le grand Meaulnes','Les misérables' ,'Notre-dame de Paris' ,'Un animal doué de raison' }

42

Question 3

Donner une définition de la fonction titres_auteur qui, étant donné un nom d’auteur et unebase de Livres, retourne l’ensemble des titres de livres écrits par cet auteur.

Par exemple :>>> titres_auteur('Victor Hugo', LivresBD){'Les comtemplations', 'Les misérables', 'Notre-dame de Paris'}

>>> titres_auteur('Robert Merle', LivresBD){'Un animal doué de raison'}

>>> titres_auteur('Gaston Leroux', LivresBD)set()

Exercice 10.2 : Calcul de Trajets

Cet exercice utilise un dictionnaire pour représenter une carte de transport ferroviaire. Il s’agitd’un exercice avancé sur les dictionnaires et les ensembles.

On représente une carte de transport par un dictionnaire de type dict[str: set[str]]. Lesclés sont des chaînes de caractères représentant des stations. A chaque clé-station est associéecomme valeur une correspondance : l’ensemble des noms des stations accessibles directement –c’est-à-dire sans changement de train – depuis la clé-station. On suppose que toutes les stationsapparaissant comme étant accessibles sont des clefs de la base.

Dans cet exercice, nous allons travailler sur un dictionnaire correspondant à une toute petitepartie de la carte de transport du réseau ferré français :# Grandes_Lignes : dict[str:set[str]]Grandes_Lignes = {'Paris': {'Strasbourg', 'Dijon', 'Toulouse',

'Lille' , 'Lyon', 'Bordeaux'},'Strasbourg' :{'Paris', 'Dijon', 'München'},'München' : {'Strasbourg'},'Dijon' : {'Paris', 'Strasbourg', 'Lyon', 'Toulouse'},'Lyon' :{'Paris', 'Dijon', 'Toulouse'},'Toulouse' : {'Paris', 'Lyon', 'Dijon', 'Bordeaux'},'Bordeaux' : {'Nantes', 'Paris'},'Nantes' : {'Paris', 'Bordeaux','Quimper'},'Quimper' :{'Nantes'}, 'Ajaccio': {'Bastia'},'Bastia' : {'Ajaccio'}, 'Lille': {'Paris'}}

Question 1 - Trajet direct

Donner une définition du prédicat trajet_direct(carte, st1, st2) qui renvoie True quandil existe un trajet direct de la station st1 à la station st2 dans carte et False sinon.

Par exemple :

43

>>> trajet_direct(Grandes_Lignes, 'Paris', 'Bordeaux')True

>>> trajet_direct(Grandes_Lignes, 'Paris', 'Ajaccio')False

Question 2 - Ajouter une station

Donner une définition de la fonction ajout_station qui prend en paramètre une stationstation, un ensemble de stations correspondances et une carte de transport carte et quirenvoie une carte de transport correspondant à carte dans laquelle la station station estajoutée, ainsi que ses connexions directes à toutes les stations de correspondances.

Remarques :

— On supposera que la connexion est symétrique (si station1 est directement connectée àstation2, alors station2 est directement connectée à station1).

— On supposera également que toutes les stations de correspondances existent déjà dansla carte.

Par exemple :>>> # Nouvelles_Lignes : dict[str:set[str]]>>> Nouvelles_Lignes = ajout_station('Limoges', {'Paris', 'Toulouse', 'Bordeaux'},

Grandes_Lignes)

>>> trajet_direct(Nouvelles_Lignes, 'Limoges', 'Paris')True

>>> trajet_direct(Nouvelles_Lignes, 'Bordeaux', 'Limoges')True

>>> trajet_direct(Nouvelles_Lignes, 'Limoges', 'Dijon')False

Question 3 - stations atteignables en k correspondances

Dans cette question un peu plus difficile, on souhaite récuperer l’ensemble des stations qui sontatteignables depuis une station de depart en exactement k correspondances.

Par exemple :>>> stations_atteignables(Grandes_Lignes, 'Paris', 0){'Paris'}

>>> stations_atteignables(Grandes_Lignes, 'Paris', 1){'Bordeaux', 'Dijon', 'Lille', 'Lyon', 'Strasbourg', 'Toulouse'}

>>> stations_atteignables(Grandes_Lignes, 'Paris', 2){'Bordeaux','Dijon' ,'Lyon' ,

44

'München' ,'Nantes' ,'Paris' ,'Strasbourg' ,'Toulouse' }

Remarque: Paris est bien sûr atteignable depuis Paris en 2 étapes (trajet direct aller/retour)

Question 4 - Compteur de changements

Déduire de la question précédente une définition de la fonction compteur_changements quiretourne le nombre de correspondances à effectuer pour rejoindre une station arrivee depuisune station depart pour une carte donnée.

Remarque : on fera l’hypothèse qu’un trajet avec correspondance(s) existe dans la carte entreles deux stations.

Par exemple :>>> compteur_changements(Grandes_Lignes, 'Paris', 'Paris')0

>>> compteur_changements(Grandes_Lignes, 'Paris', 'Dijon')1

>>> compteur_changements(Grandes_Lignes, 'Paris', 'Quimper')3

Question 5 - Existence d’un trajet

On souhaite maintenant vérifier si dans une carte donnée il exsite un trajet entre une stationde depart et une station arrivee.

La fonction à définir se nommme existence_trajet, voici quelques exemples d’utilisation :>>> existence_trajet(Grandes_Lignes, 'Paris', 'München')True

>>> existence_trajet(Grandes_Lignes, 'Ajaccio', 'Bordeaux')False

Remarque: la fonction est proche de stations_atteignables (cf. Question 3) mais il faudrapenser à ne pas visiter deux fois la même station. Que se passe-t-il d’après vous s’il on negarantit pas cette propriété ?

45