(* ********************************************************************** *) (* Code de gray*) (* Il existe de nombreuses implémentations, certaines sont plus efficaces. Voir entre autres http://www.research.att.com/~njas/sequences/A003188 *) let apply f n = (*Applique la fonction f aux 2^n vecteurs booléens de taille n*) let rec gray array i = if i >= 0 then ( gray array (i-1); array.(i) <- not array.(i); f array; gray array (i-1); ) in let array = Array.make n false in f array; gray array (n-1);; (* exemple *) let print a = Array.iter (fun b -> print_int (if b then 1 else 0); print_string " ") a; print_newline();; apply print 3;; (* ********************************************************************** *) (* PGCD rapide *) (* L'avantage de cet algorithme est d'utiliser surtout des opérations logiques et rapides telles que lsr *) let pgcd a b = let rec valuation_en_2 a b result = (* valuation en 2 du pgcd *) if (a lor b) land 1 = 1 (* Si a ou b est impair c'est 0 *) then result else valuation_en_2 (a lsr 1) (b lsr 1) (result + 1) in (* sinon c'est [1+valuation_en_2 (a/2) (b/2)] *) let rec pgcd_impair a b = (* on suppose a ou b impair *) match a land 1 with (* [if] serait plus efficace que [match], mais moins clair *) | 0 -> if a=0 then b else pgcd_impair (a lsr 1) b (* Si a est pair c'est [pgcd (a/2) b] *) | 1 -> (* Sinon... *) (match b land 1 with | 0 -> pgcd_impair b a (* b est pair, on va le diviser par 2 au prochain appel *) | 1 -> pgcd_impair (abs(b-a)) (min a b) (* a et b sont impairs, donc b-a est pair et le min est impair *) | _ -> failwith "b land 1 <> 0 ou 1 ???") | _ -> failwith "a land 1 <> 0 ou 1 ???" in let v = valuation_en_2 a b 0 in (1 lsl v) * pgcd_impair (a lsr v) (b lsr v);; List.map2 pgcd [55; 12*11; 8*11*13; 23; 1; 0] [65; 5*11 ; 9*17*13; 12; 10; 10];; (* [5; 11; 13; 1; 1; 10] *) (* ********************************************************************** *) (* Entiers de Hamming *) (* Les entiers de Hamming sont les entiers naturels dont les seuls facteurs premiers sont 2, 3 ou 5. *) let hamming n = (* Renvoie les n premiers entiers de Hamming *) (* Si l'on connaît les n-1 premiers, il suffit de les multiplier par 2, 3 et 5 et de prendre le plus petit nouveau résultat, c'est l'entier de Hamming suivant. On se rappelle de quels nombres on a déjà multipliés par 2 grâce à pointeur2 : les entiers 2*result.(0) ... 2*result.(pointeur2-1) sont déjà dans result ; l'entier 2*result.(pointeur2) est stocké dans val2. Idem pour pointeur3 et val3.*) let result = Array.make n (-1) in result.(0) <- 1; let pointeur2 = ref 0 in let pointeur3 = ref 0 in let cinq = ref 5 in (* Contient successivement les puissance de 5. *) let val2 = ref (2* result.(!pointeur2)) in (* contient toujours 2*result.(!pointeur2) *) let val3 = ref (3* result.(!pointeur3)) in for i=1 to n-1 do if !val2 < !val3 then if !val2 < !cinq then (result.(i) <- !val2; incr pointeur2; val2:= 2* result.(!pointeur2);) else (result.(i) <- !cinq; cinq:= 5* !cinq;) else if !val2 = !val3 then if !val2 < !cinq then (result.(i) <- !val2; incr pointeur2; incr pointeur3; val2:= 2* result.(!pointeur2); val3:= 3* result.(!pointeur3);) else (result.(i) <- !cinq; cinq:= 5* !cinq;) else if !val3 < !cinq then (result.(i) <- !val3; incr pointeur3; val3:= 3* result.(!pointeur3);) else (result.(i) <- !cinq; cinq:= 5* !cinq;) done; result;; hamming 100;; (* ********************************************************************** *) (* Sous ensembles à p éléments de {1,2,...,n} *) let rec entiers n suffixe = (* Renvoie 1 :: 2 :: 3 ... n :: suffixe *) assert (n>=0); if n = 0 then suffixe else entiers (n-1) (n::suffixe);; let cnp f n p = (* Applique f aux C_n^p sous ensembles à p éléments de 1..n *) let rec cnp_rec n p suffixe = (* idem en ajoutant suffixe à chaque sous-ensemble *) assert (n>=p); if p = 0 then f suffixe else ( if n = p then f (entiers n suffixe) (* Si n=p il n'y a qu'un sous-ensemble *) else ( (* Sinon on décompse en ceux qui contiennent n et ceux qui ne le contienne pas : *) cnp_rec (n-1) p suffixe; cnp_rec (n-1) (p-1) (n::suffixe))) in if p > 0 then cnp_rec n p [];; (* le test p>0 évite d'appliquer f à la liste vide quand on appelle [cnp f n 0] *) let print l = List.iter (fun i -> Printf.printf "%i " i) l; Printf.printf "\n%!";; cnp print 6 3;; cnp print 6 4;; cnp print 6 5;; cnp print 6 6;; cnp print 6 0;;