SHARE
TWEET

TD4 - Distance entre des points

csmine Mar 26th, 2019 (edited) 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (* Exercice 1
  2.  
  3. 1. Algorithme na√Įf : on va regarder la distance entre chaque point.
  4. La distance entre deux points [x,y] et [a,b] est :
  5. sqrt( (x-a)² + (y-b)² )
  6. Si on veut juste comparer des distances, autant ne pas appliquer la racine carrée, étant bijective sur les positifs.
  7.  
  8. Donc on crée une première fonction qui regarde la distance entre 1 point donné et tous les autres, et une seconde fonction qui va appliquer celle-ci en tout point.
  9.  
  10. 2. *)
  11.  
  12. let algo_naif l =
  13.     let rec aux1 l x_fixe y_fixe best_distance = match l with
  14.     |[] -> best_distance
  15.     |(x,y)::t when ( (x-.x_fixe)**2. +. (y-.y_fixe)**2. ) < best_distance -> aux1 t x_fixe y_fixe ((x-.x_fixe)**2. +. (y-.y_fixe)**2.)
  16.     |(x,y)::t -> aux1 t x_fixe y_fixe best_distance
  17.     in
  18.    
  19.     let rec aux2 l best_distance = match l with
  20.     |[] -> best_distance
  21.     |(x,y)::t -> let bd = (aux1 t x y best_distance) in aux2 t bd
  22.     in
  23. match l with
  24. |[] -> -1.
  25. |(x,y)::[] -> -1.
  26. |(x,y)::(a,b)::t -> let premiere_distance = ( (x-.a)**2. +. (y-.b)**2. ) in sqrt(aux2 l premiere_distance);;
  27.  
  28. (* Exercice 2 :
  29. Dans le cas o√Ļ il n'y a qu'une seule coordonn√©e, on pourrait simplement trier la liste des coordonn√©es par un tri par fusion (en n*lg(n)), et v√©rifier la distance entre 2 √©l√©ments cons√©cutifs (n comparaisons).
  30. La complexité est en n + n*lg(n) soit O(n*lg(n)) *)
  31.  
  32.  
  33. (* Exercice 3 :
  34.  
  35. 1ère étape : trier par ordre lexicographique. Trier les abscisses prend n*lg(n), et trier les ordonnées après donne 2*n*lg(n) (soit O(n lg(n)))
  36.  
  37. 2ème étape : on coupe à la moitié, et on applique notre fonction de l'exo 2 aux deux sous-listes O(n * lg(n)) + O(1)
  38. On obtient d1,d2 donc delta = min(d1,d2)
  39.  
  40. 3ème étape : le meilleur des cas est en O(1), le pire est en O(n²)
  41.  
  42. Total meilleur des cas:
  43. c(n) = O(n*lg(n)) + O(n*lg(n)) + O(1) = O(n*lg(n))
  44.  
  45. Total pire des cas :
  46. c(n) = O(n*lg(n)) + O(n*lg(n)) + O(n²) = O(n²) *)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top