(* Question 1.2 *) let rec fusionne_listes l1 l2 = match (l1,l2) with | ([],_) -> l2 | (_,[]) -> l1 | (t1::q1, t2::_) when (t1 <= t2) -> t1 :: (fusionne_listes q1 l2) | (t1::_, t2::q2) (* t1 > t2 *) -> t2 :: (fusionne_listes l1 q2);; fusionne_listes [1;2;8;11] [1;5;6;7];; let rec decoupe = function | [] -> ([],[]) | [x] -> ([x],[]) | t1::(t2::q) -> let l,r = decoupe q in (t1::l, t2::r);; let rec tri_fusion = function | [] -> [] | [x] -> [x] | l -> let g, d = decoupe l in fusionne_listes (tri_fusion g) (tri_fusion d);; tri_fusion [4;5;1;8;10;4;11;14;20;25;14;13];; (* Question 1.3 *) type point = { x : float; y : float; };; let dist p1 p2 = let x = p1.x -. p2.x and y = p1.y -. p2.y in sqrt (x*.x +. y*.y);; (* Je sépare car je réutilise dans la question suivante *) let naif_tab pts imin imax = let min_val = ref (10000000., (-1,-1)) in let n = imax-imin+1 in for i = imin to imax do for j = imin to imax do if (i <> j) then ( let newdist = dist pts.(i) pts.(j) in if (newdist < (fst !min_val)) then min_val := (newdist, (i,j)); ); done; done; !min_val;; let naif pts = naif_tab pts 0 (vect_length pts - 1);; let test_pts = [|{x=2.;y=2.;} ; {x=5.;y=3.;} ; {x=1.;y=1.;} ; {x=6.;y=7.;}|];; naif test_pts;; (* Question 1.4 *) let rec closest_pair_sous_tab pts imin imax = let n = imax-imin+1 in if n = 1 then failwith "pas assez de points" else if n = 2 then (dist pts.(imin) pts.(imin+1), (imin,imin+1)) else if n = 3 then ( (* Fait tous les tests *) let v1 = dist pts.(imin+0) pts.(imin+1) and v2 = dist pts.(imin+1) pts.(imin+2) and v3 = dist pts.(imin+0) pts.(imin+2) in let m = min (min v1 v2) v3 in if v1 = m then (v1, (imin+0,imin+1)) else if v2 = m then (v2, (imin+1,imin+2)) else (v3, (imin+0,imin+2)) ) else ( let cut = n/2-1 in let xl = pts.(imin+cut).x in let p1 = closest_pair_sous_tab pts imin cut and p2 = closest_pair_sous_tab pts (cut+1) imax in let delta = min (fst p1) (fst p2) in let minpair = if delta = (fst p1) then p1 else p2 in let ibandemin = ref (-1) and ibandemax = ref (-1) in for i = imin to imax do if (!ibandemin = (-1) && pts.(i).x >= xl -. delta) then ibandemin := i; if (!ibandemax = (-1) && pts.(i).x > xl +. delta) then ibandemax := i-1; done; if !ibandemax = -1 then ibandemax := imax; (* C'est ici qu'on pourrait faire l'astuce des 7 points *) (* Ici on fait l'algo naïf *) let newmin = naif_tab pts !ibandemin !ibandemax in if (fst newmin) < delta then newmin else minpair );; let closest_pair pts = closest_pair_sous_tab pts 0 ((vect_length pts) - 1);; let test_pts2 = [|{x=(-1.);y=2.;} ; {x=1.;y=3.;} ; {x=2.;y=1.;} ; {x=6.;y=7.;}|];; closest_pair test_pts2;; naif test_pts2;; (* Question 2.1 *) let plssc x y = let m = vect_length x and n = vect_length y in let c = make_matrix (m+1) (n+1) 0 in let plssc_exhib = make_matrix (m+1) (n+1) 0 in for i = 1 to m do for j = 1 to n do if (x.(i-1) = y.(j-1)) then c.(i).(j) <- c.(i-1).(j-1) + 1 else c.(i).(j) <- max c.(i).(j-1) c.(i-1).(j); done; done; c.(m).(n);; plssc [|1;2;3;4;7;9;10;3;1;4|] [|2;4;6;5;9;6;7;10;1;4|];; (* Question 2.6 *) (* la distance recherchée est en (i,j) car un plus court chemin passe évidemment par des noeuds d'étiquette inférieure à |V| *) (* Question 2.7 *) let floyd g = let n = vect_length g in let dist = make_matrix n n 0 in for i = 0 to n-1 do for j = 0 to n-1 do dist.(i).(j) <- g.(i).(j); done; done; for i = 0 to n-1 do for s = 0 to n-1 do for t = 0 to n-1 do if s <> t then ( let newdist = dist.(s).(i) + dist.(i).(t) in if dist.(s).(t) > newdist then dist.(s).(t) <- dist.(s).(i) + dist.(i).(t); ); done; done; done; dist;;