Exercice 3 - Questions 2.b, 2.c, 2.d · Bac Numérique et Sciences Informatiques Polynésie 2023 (jour 1)

EXERCICE 3 (5 points)

Cet exercice porte sur l'algorithmique, la programmation orientée objet et la méthode diviser-pour-régner.

L'objectif de cet exercice est de trouver les deux points les plus proches dans un nuage de points pour lesquels on connaît les coordonnées dans un repère orthogonal.

On rappelle que la distance entre deux points A et B de coordonnées $(x_A; y_A)$ et $(x_B; y_B)$ est donnée par la formule: $AB = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$.

Les coordonnées d'un point seront stockées dans un tuple de deux nombres réels.

Le nuage de points sera représenté en Python par une liste de tuples de taille $n$, $n$ étant le nombre total de points. On suppose qu'il n'y a pas de points confondus (mêmes abscisses et mêmes ordonnées) et qu'il y a au moins deux points dans le nuage.

Pour calculer la racine carrée, on utilisera la fonction sqrt du module math, pour rappel:

1 >>> from math import sqrt

2 >>> sqrt(16)

3 4.0

La fonction liste_segments donnée ci-dessous prend en paramètre une liste de points et renvoie une liste contenant les objets Segment qu'il est possible de construire à partir de ces points. On considère les segments [AB] et [BA] comme étant confondus et on ajoutera un seul objet dans la liste.

def liste_segments(liste_points):

n = len(liste_points)

segments = []

for i in range(......):

for j in range(......, n):

# On construit le segment à partir des points i et j.

seg =..........................

segments.append(seg) # On l'ajoute à la liste.

return segments

b)

Recopier la fonction sans les commentaires et compléter le code manquant.

c)

Donner en fonction de $n$ la longueur de la liste segments. Le résultat peut être laissé sous la forme d'une somme.

d)

Donner, en fonction de $n$, la complexité en temps de la fonction liste_segments.