Vous devez rendre pour le 27/02/20 sur l'E.N.T un dossier compressé à votre nom contenant :
Les fonctions doivent être documentées, doivent contenir des tests (doctest) et doivent contenir des assert() (invariant de boucle)
On trie parfois une liste avant de résoudre un autre problème sur cette liste. Ce procédé en algorithmique qui consiste à utiliser une technique pour résoudre un autre problème s'appelle réduction
Voici quelques exemples
Combien y-a-t-il de valeurs différentes dans une liste donnée ?
En premier trier la liste avec la fonction sort() de Python, puis parcourir la liste triée en comptant les valeurs vraiment différentes
Etant données deux listes d'éléments comparables et sans doublons
Il s'agit de fusionner les deux listes et la nouvelle liste n'a pas de doublons aussi
En premier on trie les deux listes, puis on parcourt les deux listes en parallèle en ne gardant que les éléments distincts
Par exemple si liste1 = [a,c,f,u] et si liste2 = [c,d,m,t,u,w] alors la liste obtenue par fusion est [a,c,d,f,m,t,u,w]
On étend l'idée de la recherche dichotomique
Si $v \in [a,b[$ alors soit $v \in [a,\dfrac{2a+b}{3}[$ soit $v \in [\dfrac{2a+b}{3},\dfrac{a+2b}{3}[$ soit $v \in [\dfrac{a+2b}{3},b[$
Définir une fonction qui met au point cette idée