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.

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.

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

Traduisez le sous forme d'algorithme et testez.

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

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