Soit {E} une partie finie de {\mathbb{R}^{2}.} On veut déterminer deux points de {E} minimisant la distance entre points distincts de {E.}
L’ensemble {E} sera représenté par un tableau {t} de taille {n\ge 2} formé de couples distincts de flottants.
La fonction dist calcule la distance entre deux points de {\mathbb{R}^{2}.}
|
1 2 |
let dist (x, y) (x', y') = sqrt ((x -. x') ** 2. +. (y -. y') ** 2.);; val dist : float * float -> float * float -> float = <fun> |
8.4.1 Algorithme naïf
Une méthode très na ̈ive consiste à considérer toutes les paires de points distincts de {E.}
C’est ce que fait la fonction plus_proches_naif, qui renvoie un couple de points distincts réalisant la distance minimum :
|
1 2 3 4 5 6 7 8 9 10 |
let plus_proches_naif t = let n = Array.length t and d = ref (dist t.(0) t.(1)) and i0 = ref 0 and j0 = ref 1 in for j = 1 to n - 1 do for i = 0 to j - 1 do if dist t.(i) t.(j) < !d then (d := dist t.(i) t.(j); i0 := i; j0 := j) done; done; (t.(!i0), t.(!j0));; val plus_proches_naif : (float * float) array -> (float * float) * (float * float) = <fun> |
La complexité de cette fonction est de l’ordre du nombre de paires de {E,} donc de l’ordre de {n^{2}.}
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres