(* Types des coefficients *) type 'a dico = {zero: 'a ; un : 'a ; is_zero : 'a -> bool ; plus : 'a -> 'a -> 'a ; n_plus : int -> 'a -> 'a ; mult : 'a -> 'a -> 'a ; print : 'a -> unit} (* Qui sont ici des flottants *) let dico_float = {zero=0.0 ; un=1.0 ; is_zero=(fun x -> x = 0.0) ; plus=(fun x y -> x +. y) ; n_plus=(fun n x -> float_of_int n *. x) ; mult=(fun x y -> x *. y) ; print=print_float} (* Types des polynômes *) type 'a monome = {coeff: 'a; degre: int} type 'a polynome = 'a monome list (* Insérerez vos cinq fonctions ici, puis généralisez les *) open Printf (* Pour écrire « printf » directement *) (* Pas très beau, mais bon *) let afficher_monome dico {coeff=c ; degre=d} = printf "+<" ; dico.print c ; printf "X^%d>" d let afficher d p = match p with | [] -> printf "0" (* un cas particulier, quand même *) | _ -> List.iter (afficher_monome d) p let rec somme dico p1 p2 = match p1,p2 with | [],_ -> p2 | _,[] -> p1 | ({degre=d1} as m1)::r1, ({degre=d2} as m2)::r2 -> if d1 > d2 then m1::somme dico r1 p2 else if d1 < d2 then m2::somme dico p1 r2 else (* d1 = d2 *) let c = dico. plus m1.coeff m2.coeff in if dico.is_zero c then somme dico r1 r2 else {coeff=c ; degre=d1}::somme dico r1 r2 let deriver_monome dico {coeff=c ; degre=d} = if d = 0 then {coeff=dico.zero ; degre=0} else {coeff=dico.n_plus d c ; degre=d-1} let deriver dico p = let rec d_rec p = match p with | [] -> [] | m::rem -> let m' = deriver_monome dico m in if dico.is_zero m'.coeff then d_rec rem else m'::d_rec rem in d_rec p let produit_monomes dico {coeff=c1 ; degre=d1} {coeff=c2 ; degre=d2} = {coeff=dico.mult c1 c2 ; degre=d1+d2} let produit_monome dico m p = List.map (produit_monomes dico m) p let produit dico p1 p2 = List.fold_left (fun r m1 -> somme dico (produit_monome dico m1 p2) r) [] p1 (* Puissance efficace, suppose n >= 0 *) let rec puissance dico x n = match n with | 0 -> dico.un | _ -> let y = puissance dico x (n/2) in if n mod 2 = 0 then dico.mult y y else dico.mult x (dico.mult y y) let evaluer dico p x = List.fold_left (fun r m -> dico.plus r (dico.mult m.coeff (puissance dico x m.degre))) dico.zero p (* Méthode de newton *) let newton p eps x0 = let p' = deriver dico_float p in let eval_p = evaluer dico_float p and eval_p' = evaluer dico_float p' in let rec do_rec x = let delta = eval_p x /. eval_p' x in if abs_float delta < eps then x -. delta else do_rec (x -. delta) in do_rec x0 (* Calcul de racine de deux *) let p = [{coeff=1.0 ; degre=2} ; {coeff=(-2.0) ; degre=0}] let r = newton p (1e-8) 2.0 let _ = Printf.printf "racine de deux: %g\n" r ; Printf.printf "(c'est une racine de " ; afficher dico_float p ; Printf.printf ")\n" (* C'est fini *) let _ = exit 0