(* 1.1.1 factorielle *) (* exercice 1 *) let rec factorielle = function 0 -> 1 | n -> n * (factorielle (n-1));; (* exercice 2 *) let rec factorielle_acc n k = if n = 0 then k else factorielle_acc (n-1) (n*k);; (* exercice 3 *) let factorielle_bis n = factorielle_acc n 1;; (* 1.1.2 exponentiation lente *) (* exercice 4 *) let rec slow_exp b = function 0 -> 1 | n -> slow_exp b (n - 1) * b;; (* exercice 5 *) let rec slow_exp_acc b n acc = if (n = 0) then acc else slow_exp_acc b (n - 1) (acc * b);; (* exercice 6 *) let slow_exp_bis b n = slow_exp_acc b n 1;; (* 1.1.3 exponentiation rapide *) (* exercice 7 *) let rec even_rec = function 0 -> true | 1 -> false | n -> even_rec (n - 2);; let even n = n mod 2 = 0;; (* exercice 8 *) let rec fast_exp b n = if (n = 0) then 1 else if (even n) then fast_exp (b*b) (n/2) else fast_exp (b) (n-1) * b;; (* exercice 9 *) (* Le parametre n de la fonction decrit une suite d'entiers strictement decroissante au fil des appels recursifs. Donc la fonction se termine. Notez bien que ca ne serait pas le cas si l'on avait place fast_exp fast_exp (b) (n/2) 2 dans le premier appel recursif. *) (* exercice 10 *) let rec fast_exp_acc b n acc = if (n = 0) then acc else if (even n) then fast_exp_acc (b*b) (n/2) acc else fast_exp_acc (b) (n-1) (acc * b);; let fast_exp_bis b n = fast_exp_acc b n 1;; (* 1.1.4 pgcd *) (* exercice 11 *) (* Lors de chaque appel recursif Le deuxieme parametre de la fonction (m) devient (n mod m). Or |n mod m| < |m|, ce qui s'obtient aisement avec la definition de la division dans z : on divise n par m en determinant q et r tels que n = mq + r, |r| < |m| Ici on a r = n mod m. Comme le deuxieme parametre est toujours strictement decroissant, et que l'algorithme s'arrete lorsqu'il atteint 0, la fonction se termine. *) (* exercice 12 *) let rec gcd n m = if (m = 0) then n else gcd m (n mod m);; (* 1.1.5 alphabet *) (* exercice 13 *) let lettre_suivante a = char_of_int (int_of_char a + 1);; (* exercice 14 *) let figure_of_int n = char_of_int (n - 1 + (int_of_char '1'));; (* exercice 15 *) let compare_lettres a b = int_of_char a <= int_of_char b;; (* exercice 16 *) let rec alphabet lettre_depart lettre_arrivee = if (compare_lettres lettre_depart lettre_arrivee) then ( print_char lettre_depart; alphabet (lettre_suivante lettre_depart) lettre_arrivee ) else ();; (* 1.1.6 mise sous forme recursive *) (* exercice 17 *) let rec mult x y = if (y = 0) then y else mult x (y - 1) + x;; (* exercice 18 *) let rec mult_acc x y acc = if (y = 0) then acc else mult_acc x (y - 1) (acc + x);; let mult_bis x y = mult_acc x y 0;; (* 1.1.7 indicatrice d'Euler *) (* exercice 19 *) let rec nb_prem a n = if (a >= n) then 0 else ( if (gcd a n = 1) then 1 else 0 ) + nb_prem (a + 1) n;; let ind_euler n = nb_prem 0 n;;