Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
(** TP1 Correction *) (** https://www.lri.fr/~conchon/PFA/ **) (* Arithmétique d'intervalles *) type interval = {inf: int; sup: int};; let make_interval inf sup = if inf <= sup then {inf = inf; sup = sup} else {inf = sup; sup = inf} ;; let inter1 = make_interval 2 4;; let inter2 = make_interval 5 3;; (*Fonctions auxiliaires intéressantes*) let min4 a b c d = min a (min b (min c d));; let max4 a b c d = max a (max b (max c d));; min4 5 6 9 4 ;; max4 5 6 9 4 ;; (*Version 1 : add*) let add int1 int2 = let a = int1.inf + int2.sup in let b = int1.sup + int2.sup in let c = int1.sup + int2.inf in let d = int1.inf + int2.inf in {inf = min4 a b c d; sup = max4 a b c d};; (*Version 2 : add*) let add2 int1 int2 = let int1_inf, int1_sup = if int1.inf <= int1.sup then (int1.inf,int1.sup) else (int1.sup,int1.inf) in let int2_inf, int2_sup = if int2.inf <= int2.sup then (int2.inf,int2.sup) else (int2.sup,int2.inf) in {inf = int1_inf + int2_inf; sup = int1_sup + int2_sup};; add inter1 inter2;; (*Version 1 : sub*) let sub int1 int2 = let a = int1.inf - int2.sup in let b = int1.sup - int2.sup in let c = int1.sup - int2.inf in let d = int1.inf - int2.inf in {inf = min a b; sup = max c d};; (*Version 2 : sub*) let sub2 int1 int2 = let int1_inf, int1_sup = if int1.inf <= int1.sup then (int1.inf,int1.sup) else (int1.sup,int1.inf) in let int2_inf, int2_sup = if int2.inf <= int2.sup then (int2.inf,int2.sup) else (int2.sup,int2.inf) in {inf = int1_inf - int2_sup; sup = int1_sup - int2_inf};; sub inter1 inter2;; (*Version 1 : mul*) let mul int1 int2 = let a = min (int1.inf * int2.sup) (int1.sup * int2.inf) in let b = min (int1.sup * int2.sup) (int1.inf * int2.inf) in let c = max (int1.inf * int2.sup) (int1.sup * int2.inf) in let d = max (int1.sup * int2.sup) (int1.inf * int2.inf) in {inf = min a b; sup = max c d};; (*Version 2 : mul*) let mul2 int1 int2 = let int1_inf, int1_sup = if int1.inf <= int1.sup then (int1.inf,int1.sup) else (int1.sup,int1.inf) in let int2_inf, int2_sup = if int2.inf <= int2.sup then (int2.inf,int2.sup) else (int2.sup,int2.inf) in {inf = int1_inf * int2_inf; sup = int1_sup * int2_sup};; mul inter1 inter2;; (* Echauffement sur les listes *) type t = B | N | R;; (*Version 1 : permute recursive*) let rec permute l = match l with | [] -> [] | B :: tl -> N :: (permute tl) | N :: tl -> R :: (permute tl) | R :: tl -> B :: (permute tl) ;; (*Version 2 : permute CPS*) let permute2 l = let rec perm_aux l k = match l with | [] -> k [] | B :: tl -> perm_aux tl (fun r -> k (N :: r)) | N :: tl -> perm_aux tl (fun r -> k (R :: r)) | R :: tl -> perm_aux tl (fun r -> k (B :: r)) in perm_aux l (fun x -> x) ;; (*Version 3 : permute avec itérateur*) let permute3 = List.map (function B->N|N->R|R->B);; permute3 [B;B;R;N];; (*Version 1 : compteB récursive*) let rec compteB l = match l with |[] -> 0 |B::tl -> 1 + compteB tl |hd::tl -> compteB tl ;; (*Version 2 : compteB recursive terminale*) let compteB2 l = let rec aux l acc = match l with |[] -> acc |B::tl -> aux tl (1 + acc) |hd::tl -> aux tl acc in aux l 0 ;; (*Version 3 : compteB CPS*) let compteB3 l = let rec aux l k = match l with |[] -> k 0 |B::tl -> aux tl (fun r -> k (1 + r)) |hd::tl -> aux tl k in aux l (fun x -> x) ;; (*Version 4 : compteB avec itérateur*) let compteB4 = List.fold_left (fun acc x -> match x with B -> acc + 1 | _ -> acc) 0;; compteB4 [B;B;R;N];; (*Version 1 : plus_grande_sequence_de_B recursive*) let plus_grande_sequence_de_B l = let rec aux l acc m = match l with |[] -> max acc m |B::tl -> aux tl (acc + 1) m |hd::tl -> aux tl 0 (max acc m) in aux l 0 0 ;; plus_grande_sequence_de_B [N;R;N;R];; (*Version 2 : plus_grande_sequence_de_B CPS*) let plus_grande_sequence_de_B2 l = let rec aux l k = match l with |[] -> k (0,0) |B::tl -> aux tl (fun (r1,r2) -> k (r1 + 1, r2)) |hd::tl -> aux tl (fun (r1,r2) -> k (0, (max r1 r2))) in aux l (fun (r1,r2) -> max r1 r2) ;; plus_grande_sequence_de_B2 [B;N;R;B;B;B;N;R;B;B];; let remplace l = let rec aux l k = match l with |[] -> k (B, []) |[x] -> k (x,[x]) |B::tl -> aux tl (fun (r1,r2) -> k (r1, r1::r2)) |hd::tl -> aux tl (fun (r1,r2) -> k (r1, hd::r2)) in aux l (fun (_,r) -> r) ;; remplace [B;N;N;B;B;B;R;N;N;B;B;R];; (*Echauffement sur les itérateurs*) let affiche_liste_entiers l = Printf.printf "["; List.iter (Printf.printf "%d;") l; Printf.printf "]" ;; affiche_liste_entiers [];; let count a = List.fold_left (fun acc x -> if x == a then acc + 1 else acc) 0 ;; count 1 [1;5;8;6;1;5;2];; let flatten l = List.fold_right (fun x y -> List.append x y) l [];; flatten [[2] ;[] ;[3 ;4 ;5]] ;; let fst_list = List.map (fun (x,y) -> x);; fst_list [(1,3);(2,6)];; (* Le tri fusion *) (* Couper *) let rec couper l = match l with |[] -> [],[] |[x] -> [x],[] |hd1::hd2::tl -> let l1,l2 = couper tl in hd1::l1,hd2::l2 ;; couper [1;2;3;4;5;6;7];; let rec couper2 l = match l with |[] -> [],[] |hd::tl -> let l1,l2 = couper2 tl in (l2,hd::l1) ;; couper2 [1;2;3;4;5;6;7];; let rec couper3 = List.fold_left (fun (x,y) z -> (y,z::x)) ([],[]);; couper3 [1;2;3;4;5;6;7];; (* Fusion *) let fusion comp l1 l2 = let rec aux l = function |[],l3|l3,[] -> List.rev_append l l3 |hd1::tl1,hd2::tl2 -> if comp hd1 hd2 <= 0 then aux (hd1::l) (tl1, (hd2::tl2)) else aux (hd2::l) ((hd1::tl1), tl2) in aux [] (l1, l2) ;; fusion compare [1;3;4;6;7] [2;5];; (*Tri fusion*) let rec trier comp = function |[]-> [] |[x] -> [x] |l -> let l1,l2 = couper l in fusion comp (trier comp l1) (trier comp l2) ;; trier compare [5;6;2;5;3;1;8];; (* Création d'une liste quelconque *) let make_list n = List.init n (fun _-> Random.int (n-1));; make_list 5;;