====== Recherche des deux valeurs les plus proches ======

//Exercice 2 du TP2//

Pour une séquence de longueur au moins égale à deux d'éléments comparables deux à deux, on voudrait déterminer les deux valeurs les plus proches.

À titre d'exemple, nous travaillerons sur un tableau d'entiers et la distance de ''a'' à ''b'' sera la valeur absolue |a − b|, c'est à dire ''abs(a - b)'' en Python.

===== Implémentation =====

On peut implémenter cela dans une fonction qui prend en argument une liste conforme à ce qui précède et qui retourne le couple des indices de deux valeurs parmi les plus proches.

On vous propose l'algorithme suivant.

<code lang-none linenums>
FONCTION plus_proche
ENTRÉE: tableau L d'au moins 2 nombres
SORTIE: paire d'indices des items les plus proches dans L
DÉBUT
    soit n le nombre d'éléments de L,
    la meilleure paire trouvée (pour l'instant) est faite des deux items en 0 et 1
    POUR CHAQUE indice i de 0 à n-2,
        POUR CHAQUE indice j de i+1 à n-1,
             SI la paire (i, j) est meilleure que celle trouvée ALORS
                 enregistrer cette nouvelle paire comme la meilleure trouvée
             FIN
        FIN
    FIN
    RENVOYER la meilleure paire d'indices trouvée
FIN
</code>

Traduisez le sous forme d'algorithme et testez.

===== Complexité =====

  * Si la liste est de longueur n, combien y a-t-il de comparaisons ?
  * La complexité est-elle linéaire ?

<WRAP tip>On parle de complexité quadratique pour une complexité en $n^2$.</WRAP>

===== Valeurs distinctes =====

Proposer une fonction ''ppd'' -- pour //plus proches distinctes// -- qui renvoie les indices des valeurs les plus **proches mais distinctes** ainsi que la distance trouvée.

En l'absence de valeurs distinctes, la fonction renverra ''False'' et ''0''.

Si la liste contient au moins deux valeurs distinctes, modifier la fonction précédente en ''ppd''

Exemples :
  * ''ppd([4, 25, 17, 89, 45])'' renvoie ''(1,2), 8'' car ce sont 25 et 17 les plus proches, avec une distance de 8.
  * ''ppd([3, 3, 3, 3, 3, 3, 3])'' renvoie ''False, 0''