(*But de l'algo : on passe une liste de "lignes en une dimention" exemple : [(4, 7); (0, 2); (1, 5)] et on veut "simplifier" ces lignes.*) let car (a, b) = a ;; let cdr (a, b) = b ;; let cmp_int a b = if a = b then 0 else if a > b then 1 else -1;; type line = int * int ;; let order_abscisses (a,b) (c,d) = a - c ;; let solve li = let rec each a1 b1 acc = function | [] -> (a1, b1)::acc | (a2, b2)::tl -> if a2 < b1 then each a1 b2 acc tl else each a2 b2 ((a1, b1)::acc) tl in let sorted = List.sort order_abscisses li in each (car (List.hd sorted) ) (cdr (List.hd sorted) ) [] sorted ;; solve [(4, 7); (0, 2); (1, 5); (-2, -1); (8, 9); (-6, -2)] ;; let somme li = List.fold_left (fun a b -> a + b) 0 li ;; let distance li = somme (List.map (fun (a, b) -> b - a) (solve li) );; distance [(4, 7); (0, 2); (1, 5); (-2, -1); (8, 9); (-6, -2)] ;; (*la meme mais avec des rectangles, cette fois-ci, notre but est juste de calculer l'aire*) type rectangle = line * line ;; let rect_a1 rect1 = car ( car rect1 );; let rect_a2 rect1 = car ( cdr rect1 );; let rect_o1 rect1 = cdr ( car rect1 );; let rect_o2 rect1 = cdr ( cdr rect1 );; let order_rect f rect1 rect2 = (f rect1) - (f rect2) ;; let rectangles_in a b r = (rect_a1 r) <= a && (rect_a2 r) >= b;; let solve_rect li = let rectangles_tries = List.sort (order_rect rect_a1) li in let subdivision = List.merge cmp_int (List.map rect_a1 rectangles_tries) (List.sort cmp_int (List.map rect_a2 rectangles_tries)) in let distance_subdivision a b = (* ici on peut optimiser, comme les rectangles sont tries*) let rectangles_subdivision = List.filter (rectangles_in a b) rectangles_tries in distance (List.map (fun r -> ((rect_o1 r), (rect_o2 r)) ) rectangles_subdivision) in let rec parcourt_subdivision aire = function | hd::[] -> aire | a::b::tl -> parcourt_subdivision ( (b - a) * (distance_subdivision a b) + aire) (b::tl) in parcourt_subdivision 0 subdivision;; solve_rect [ ((1, 1), (3, 3)) ; ((0,0), (2,2)) ] ;;
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.