119 lines
2.9 KiB
OCaml
119 lines
2.9 KiB
OCaml
(*** Question 1 ***)
|
|
|
|
let card l =
|
|
let rec aux a n=
|
|
match a with
|
|
| [] -> n
|
|
| e::s -> aux s (n+1)
|
|
in aux l 0;;
|
|
|
|
(* Cette fonction est de complexite O(n) *)
|
|
(* En effet, la longueur de la liste parametre l de aux decroit *)
|
|
(* de un a chaque appel recursif *)
|
|
|
|
(*** Question 2 ***)
|
|
let nPetits p l =
|
|
let rec aux p l o =
|
|
match l with
|
|
| [] -> o
|
|
| e::s -> aux p s (o + (if e<p then 1 else 0))
|
|
in aux p l 0;;
|
|
|
|
(* Cette fonction est aussi de complexite O(n) *)
|
|
(* En effet, la longueur du parametre l de aux decroit *)
|
|
(* de un a chaque appel recursif *)
|
|
|
|
(*** Question 3 ***)
|
|
let partitionP p l =
|
|
let rec aux p l o =
|
|
match l with
|
|
| [] -> o
|
|
| e::s -> aux p s (if e<p then e::o else o)
|
|
in aux p l [];;
|
|
let partitionG p l =
|
|
let rec aux p l o =
|
|
match l with
|
|
| [] -> o
|
|
| e::s -> aux p s (if e>p then e::o else o)
|
|
in aux p l [];;
|
|
|
|
(* La complexite est toujours en O(n) *)
|
|
(* En effet, en counsiderant toujours la longueur de la liste *)
|
|
(* l, elle est decremente de un a chaque appel, soit *)
|
|
(* n decrementations, donc n appels en tout *)
|
|
|
|
|
|
(*** Question 4 ***)
|
|
exception NotFoundException;;
|
|
|
|
let rec elementDeRang k l = match l with
|
|
| [] -> raise NotFoundException
|
|
| e::s ->
|
|
let pets = nPetits e l in
|
|
if pets=k-1 then e
|
|
else begin
|
|
if pets>k-1
|
|
then (elementDeRang k (partitionP e s))
|
|
else (elementDeRang (k-pets-1) (partitionG e s))
|
|
end;;
|
|
|
|
(*** Question 5 ***)
|
|
(* Imaginons le pire des cas: notre pivot choisi au hazard est
|
|
à chaque fois le plus petit des éléments, et nous recherchons
|
|
le plus grand (rang=n, taille de la liste).
|
|
Alors, chaque appel à elementDeRang k l appelera successivement
|
|
nPetits l, puis partitionP ou partitionG, puis enfin elementDeRang.
|
|
Puisque nos sommes dans le pire cas, l'ensemble renvoyé par
|
|
partitionP ou partition G sera de cardinal (card(l)-1). Donc, si
|
|
on note u_n la complexité de l'appel à elementDeRang sur un
|
|
ensemble de cardinal n, on a u_n <= n+n+u_(n-1).
|
|
Ce qui donne u_n <= n*n, donc M(n) est de l'ordre de n*n *)
|
|
|
|
(*** Question 6 ***)
|
|
(*
|
|
*)
|
|
|
|
(*** Question 7 ***)
|
|
|
|
let lst = [5;4;3;2;6;8;9;7];;
|
|
card lst;;
|
|
nPetits 5 lst;;
|
|
partitionP 5 lst;;
|
|
partitionG 5 lst;;
|
|
elementDeRang 9 lst;;
|
|
|
|
|
|
(*** Question 11 ***)
|
|
type point = {x:int;y:int};;
|
|
|
|
let vect p1 p2 = {x=(p2.x) - (p1.x);y=(p2.y) - (p1.y)};;
|
|
let sgn x = if x>0 then +1 else (if x<0 then -1 else 0);;
|
|
|
|
let orientation p q r =
|
|
let pq = vect p q and pr = vect p r in
|
|
sgn ((pq.x*pr.y)-(pq.y*pr.x));;
|
|
|
|
let o={x=0;y=0} and b={x=1;y=1} and a={x=1;y=0} and c={x=0;y=1} and m={x=(-1);y=(-1)};;
|
|
orientation o a b;;
|
|
orientation o b a;;
|
|
orientation o b m;;
|
|
orientation o m a;;
|
|
orientation o m c;;
|
|
|
|
|
|
(*** Question 12 ***)
|
|
let adroite q1 q2 r1 r2 t =
|
|
((orientation r2 r1 t)>= 0) || (((orientation q1 q2 t) >= 0) && ((orientation r2 q2 t) >= 0));;
|
|
|
|
|
|
(*** Question 13 ***)
|
|
type listePoints = point list;;
|
|
type arbre =
|
|
Racine of arbre*arbre
|
|
| Noeud of point*point*point*point*arbre*arbre
|
|
| Feuille of point*point*point;;
|
|
|
|
|
|
let construire points =
|
|
|
|
|