Algorithmes et Programmation 2, année 2022
Programmation fonctionnelle.
Exercice 1: Les
fonctions enumerate et zip
La fonction enumerate prend en entrée une liste et
retourne un itérateur des paires (indices, valeurs) de la
liste.
L = ["choucroute", "garnie", "au sel"]
print(list(enumerate(L))) [(0, 'choucroute'), (1, 'garnie'), (2, 'au sel')]- Proposez une fonction impérative
mon_enumeratequi réalise (presque) la même chose: au lieu de retourner un itérateur elle retournera une liste.
La fonction zip prend en entrée deux listes et retourne
un itérateurs des paires jusqu’a avoir consommer la plus courte des
listes.
print(list(zip(["a", "b", "c"], range(2))))[('a', 0), ('b', 1)]Proposez une fonction impérative
mon_zipqui réalise (presque) la même chose: au lieu de retourner un itérateur elle retournera une liste.Proposez une implémentation de
mon_enumerateen une ligne, uniquement aveczipet la fonction count du moduleitertools.
Exercice 2: Distance euclidienne de vecteurs
On modélise les vecteurs de \(\mathbb{R}^n\) par des listes de \(n\)-float.
On rappelle que pour \(v_1,v_2\in \mathbb{R}^n\), on a la distance euclidienne de \(v_1\) a \(v_2\) qui est définit par
\[d_2(v_1,v_2) = \sqrt(\sum_{i=0}^{n-1} (v_1[i] - v_2[i])^2)\]
- Écrire une fonction impérative qui prends deux vecteurs et retourne leur distance
- Écrire une version fonctionnelle en une ligne
Exercice 3: argmax
La fonction argmax prends en entrée une liste d’entiers
et retourne l’indice du plus grand élément de la liste.
- Proposez une implémentation impérative de
argmax - Proposez une implémentation recursive de
argmax - Écrire une version fonctionnelle en une seule ligne
Exercice 4: any, all
La fonction any prends en argument une liste et retourne
True si l’un des élements de la liste est évalué à
True par la fonction bool.
L = [0, [], (), {}, ""]
print(any(L))FalsePar contre
L = [0, [], (), {}, "", "a"]
print(any(L))True- Proposez une implémentation impérative de
any - Proposez une implémentation recursive de
any - Proposez une implémentation fonctionnelle en une ligne de
any
La fonction all retourne True si tous les
arguments sont évaluées à True.
- Implémenter
allde manière fonctionnelle en une ligne à l’aide debool,anyet desmapbien choisis.
Vous pouvez utiliser le fait que logiquement: \(\forall xx \textrm{bool}(x)\) est équivalent à \(\lnot \exists x. \lnot \textrm{bool}(x)\) avec \(\lnot\) la négation logique.
Exercice 5: Counter
La fonction Counter du module collections
prends en argument un itérable et retourne un dictionnaires de
l’occurrence de chaque élément dans l’itérable.
import collections
L = [0, 1, 2, 0, 1, 0]
print(collections.Counter(L))Counter({0: 3, 1: 2, 2: 1})- Écrire une implémentation impérative de
Counter - Écrire une version récursive de
Counter - En utilisant la fonction
reduce, écrire une implémentation fonctionnelle deCounter
Pour cette fonction, il est fortement déconseiller d’utiliser une fonction lambda.
Exercice 6: Nombre premiers
Écrire une fonction impérative qui retourne les nombres premiers plus petit que \(n\).
Écrire une version récursive.
Écrire une version fonctionnelle en une ligne. (difficile)
Compiled the: mer. 04 sept. 2024 12:49:48 CEST