Réduction

Attendus

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)

Réduction

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

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

  2. 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]

La recherche trichotomique

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