(* 1.3.1 Tri par arbre binaire de recherche *) type 'a bin_tree = Empty | Node of 'a bin_tree * 'a * 'a bin_tree;; (* exercice 1 *) let rec ins_abr f x t = match t with Empty -> Node (Empty, x , Empty) | Node(left, y, right) -> if (f x y) then Node(ins_abr f x left, y, right) else Node(left, y, ins_abr f x right);; (* exercice 2 *) let rec abr_of_list f l = match l with [] -> Empty | x::tail -> ins_abr f x (abr_of_list f tail);; (* exercice 3 *) let rec list_of_abr = function Empty -> [] | Node(left, x, right) -> (list_of_abr left)@[x]@(list_of_abr right);; (* exercice 4 *) let tri_liste f l = list_of_abr (abr_of_list f l);; (* 1.3.2 Fonctions polynomes *) type exp = Const of float | X | Somme of exp * exp | Produit of exp * exp | Puiss of exp * int;; (* exercice 5 *) let rec str_of_exp = function Const(x) -> (string_of_float x) | X -> "x" | Somme(left, right) -> "("^(str_of_exp left)^ "+"^(str_of_exp right)^ ")" | Produit(left, right) -> "("^(str_of_exp left)^ "*"^(str_of_exp right)^ ")" | Puiss(left, n) -> "("^(str_of_exp left)^ "^"^(string_of_int n)^ ")" ;; (* exercice 6 *) let rec image e x = match e with Const(c) -> c | X -> x | Somme(left, right) -> image left x +. image right x | Produit(left, right) -> image left x *. image right x | Puiss(left, n) -> let rec fast_exp b = function 0 -> 1. | n -> if (n mod 2 = 0) then fast_exp (b*.b) (n/2) else fast_exp (b*.b) ((n-1)/2) *. b in fast_exp (image left x) n;; (* exercice 7 *) let rec derive = function Const(_) -> Const(0.) | X -> Const(1.) | Somme(left, right) -> Somme(derive left, derive right) | Produit(left, right) -> Somme(Produit(derive left, right), Produit(left, derive right)) | Puiss(left, n) -> Produit(Produit(Const(float_of_int n), derive left), Puiss(left, n-1));; (* exercice 8 *) let rec degre = function Const(_) -> 0 | X -> 1 | Somme(left, right) -> max (degre left) (degre right) | Produit(left, right) -> degre left + (degre right) | Puiss(left, n) -> degre left * n;;