Exercice 1

Programmer la fonction recherche, prenant en paramètre un tableau non vide tab (type list) d’entiers et un entier n, et qui renvoie l’indice de la dernière occurrence de l’élément cherché. Si l’élément n’est pas présent, la fonction renvoie None.

Exemples

>>> recherche([5, 3],1) # renvoie None
>>> recherche([2,4],2)
0
>>> recherche([2,3,5,2,4],2)
3

Exercice 2

On souhaite programmer une fonction indiquant le point le plus proche d’un point de départ dans un tableau de points non vide. Les points sont tous à coordonnées entières et sont donnés sous la forme d’un tuple de deux entiers. Le tableau des points à traiter est donc un tableau de tuples.

On rappelle que la distance $d$ entre deux points du plan de coordonnées $(x ; y)$ et $(x’ ; y’)$ vérifie la formule :

$$d^2 = (x - x’)^2 + (y - y’)^2$$

Compléter le code des fonctions distance_carre et point_le_plus_proche fournies ci-dessous pour qu’elles répondent à leurs spécifications.

def distance_carre(point1, point2):
    """ Calcule et renvoie la distance au carre entre 
    deux points."""
    return (...)**2 + (...)**2 

def point_le_plus_proche(depart, tab):
    """ Renvoie les coordonnées du premier point du tableau tab se 
    trouvant à la plus courte distance du point depart."""
    min_point = tab[0]
    min_dist = ... 
    for i in range(1, len(tab)):
        if distance_carre(tab[i], depart) < ...: 
            min_point = ... 
            min_dist = ... 
    return min_point

Exemples :

>>> distance_carre((1, 0), (5, 3))
25
>>> distance_carre((1, 0), (0, 1))
2
>>> point_le_plus_proche((0, 0), [(7, 9), (2, 5), (5, 2)])
(2, 5)
>>> point_le_plus_proche((5, 2), [(7, 9), (2, 5), (5, 2)])
(5, 2)

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• tab est une list non vide d’entiers : 1 <= len(tab) <= 10^4
• -10^4 <= tab[i] <= 10^4
• n est un entier : -10^4 <= n <= 10^4
• la fonction renvoie l’indice de la dernière occurrence de n dans tab, ou None si n n’apparaît pas dans tab

Exercice 2

Contraintes :

• depart est un tuple de deux entiers (x, y)
• tab est une liste non vide de tuples de deux entiers : 1 <= len(tab) <= 10^4
• toutes les coordonnées sont des entiers compris entre -10^4 et 10^4
• distance_carre renvoie la distance au carré (sans racine carrée) : tous les calculs sont entiers
• en cas d’égalité, point_le_plus_proche renvoie le premier point de tab réalisant la distance minimale

Solution

Exercice 1 - la dernière occurrence

L’idée. On cherche la position de la dernière fois que n apparaît dans tab. Une seule chose change par rapport à une recherche classique : au lieu de s’arrêter dès qu’on a trouvé, on continue jusqu’au bout du tableau et on garde en mémoire la position la plus récente où on a vu n. À la fin, la valeur retenue est donc bien la dernière occurrence. Si on n’a jamais rien trouvé, on renvoie None.

Un petit exemple. Pour tab = [2, 3, 5, 2, 4] et n = 2 : on voit 2 en position 0, on retient 0 ; puis on revoit 2 en position 3, on remplace par 3 ; plus rien ensuite, donc la réponse est 3.

def recherche(tab, n):
    indice = None
    for i in range(len(tab)):
        if tab[i] == n:
            # On n'arrête pas la boucle : une occurrence plus loin remplacera celle-ci
            indice = i
    return indice

Explication. La variable indice retient la dernière position trouvée. On l’initialise à None : si le if n’est jamais vrai, None est renvoyé tel quel, ce qui est exactement le comportement demandé quand n est absent. La boucle parcourt tout le tableau, sans return à l’intérieur : c’est précisément ce qui fait la différence entre la première et la dernière occurrence.

Exercice 2 - le point le plus proche

L’idée. Comparer des distances ou comparer des distances au carré revient au même : si un point est plus proche, son carré de distance est plus petit aussi. On évite donc la racine carrée, et tous les calculs restent des entiers. Ensuite, pour trouver le point le plus proche, on fait comme pour chercher un minimum : on suppose que le premier point du tableau est le meilleur, puis on parcourt les autres et on remplace le champion dès qu’on trouve strictement mieux.

Un petit exemple. Depuis (0, 0), le point (7, 9) est à 49 + 81 = 130, le point (2, 5) est à 4 + 25 = 29, et le point (5, 2) est aussi à 25 + 4 = 29. Le champion devient (2, 5), et il n’est pas remplacé par (5, 2) car 29 < 29 est faux.

def distance_carre(point1, point2):
    """ Calcule et renvoie la distance au carre entre 
    deux points."""
    return (point1[0] - point2[0])**2 + (point1[1] - point2[1])**2

def point_le_plus_proche(depart, tab):
    """ Renvoie les coordonnées du premier point du tableau tab se 
    trouvant à la plus courte distance du point depart."""
    min_point = tab[0]
    min_dist = distance_carre(tab[0], depart)
    for i in range(1, len(tab)):
        # Comparaison stricte : en cas d'égalité on garde le point déjà retenu, donc le premier
        if distance_carre(tab[i], depart) < min_dist:
            min_point = tab[i]
            min_dist = distance_carre(tab[i], depart)
    return min_point

Explication. Un point est un tuple, donc point1[0] est son abscisse et point1[1] son ordonnée : la formule du sujet se recopie directement. Dans la seconde fonction, min_point garde le meilleur point rencontré jusqu’ici et min_dist garde sa distance au carré ; les deux vont toujours ensemble, c’est pourquoi on les met à jour dans le même if. On part de tab[0], ce qui explique que la boucle commence à l’indice 1 ; le tableau étant non vide, tab[0] existe toujours. Enfin, le < strict, et non <=, est ce qui garantit qu’en cas d’égalité on renvoie bien le premier point du tableau, comme l’exige la spécification.