(** Exercice 1 *) let rec randlist maxval n = match n with | 0 -> [] | _ -> random__int maxval :: randlist maxval (n-1) ;; let mesurer_temps f x = let n = 20 in (* nombre d'iterations *) let start = sys__time () in for i = 1 to n do let _ = f x in (* ignorer le résultat *) () done; let stop = sys__time () in (stop -. start) /. (float_of_int n);; let rec insert x l = match l with | [] -> [x] | y::l' -> if x <= y then x :: l else y :: insert x l';; let rec insert_sort l = match l with | [] -> [] | x :: l' -> insert x (insert_sort l');; (** Exercice 3 *) (** Polynomes *) let degre p = vect_length p - 1 ;; (* opposé *) let opp_poly p = init_vect (vect_length p) (fun i -> - p.(i));; (* quotient de la division euclidienne de p par X^m *) let quotient_poly p m = let n = degre p in if n p.(i+m)) ;; (* reste de la division euclidienne de p par X^m *) let reste_poly p m = let degre_resultat = ref (min (degre p) (m-1)) in while !degre_resultat >= 0 && p.(!degre_resultat) = 0 do decr degre_resultat; done; let r = init_vect (!degre_resultat + 1) (fun i -> p.(i)) in r ;; (* produit de p par X^m *) let shift_poly p m = let r = make_vect (m + vect_length p) 0 in for i = 0 to degre p do r.(i+m) <- p.(i); done; r;; (* créer une string représentant le polynome *) let affiche_poly v = let s = ref "[|" in let first = ref true in for i = 0 to vect_length v - 1 do (if !first then first := false else s := !s ^ "; "); s := !s ^ string_of_int v.(i) done; !s ^ "|]" ;; (* vérifier si p=q, en ignorant les 0 du début si l'un est plus long * que l'autre. *) let egal_poly p q = let res = ref true in let m = degre p in let n = degre q in for i = 0 to min m n do if p.(i) <> q.(i) then res := false done; let bigger = if m > n then p else q in for i = min m n + 1 to max m n do if bigger.(i) <> 0 then res := false done; !res ;; (* polynome aleatoire dont les coeffs sont entre -20 et 20 *) let random_poly () = let degre = random__int 30 + 1 in let p = init_vect degre (fun _ -> random__int 41 - 20) in (* il faut etre sur que le dernier coefficient n'est pas 0 *) p.(vect_length p - 1) <- random__int 12 + 1; p;; (* liste de n paires de polynomes aleatoires *) let rec random_paires n = match n with | 0 -> [] | _ -> (random_poly (), random_poly()) :: random_paires (n-1);; (* tester que f1 et f2 se comportent pareillement sur des polynomes aleatoires *) let tester_similaire f1 f2 = let l = random_paires 100 in (* vérifier, sur chaque paire de l, que f1 et f2 renvoient * le meme résultat *) list__for_all (fun (p1,p2) -> let ok = egal_poly (f1 p1 p2) (f2 p1 p2) in if not ok then print_endline ("probleme pour: " ^ affiche_poly p1 ^ " et " ^ affiche_poly p2); ok ) l;; (* on peut tester son programme avec tester_similaire prod_poly karatsuba_poly;; init_vect 15 puissance_poly ;; (* pour (X+1)^n *) *)