let rec quo(a,b) = if b > 0 then if a >= 0 then if a 0 then if a >= 0 then if a liste de ses chiffres en base 10 *) let liste_chiffres = function |n -> base(n,10);; (* étape 2 : produit des éléments d'une liste *) exception Liste_vide;; let produit(liste) = let rec produit_local = function |[],acc -> raise Liste_vide |tete::[],acc -> tete*acc |tete::queue,acc -> produit_local(queue,tete*acc) in produit_local(liste,1);; (* étape 3 : calcul de la persistance d'un entier *) let persistance(n) = let rec pers_local(n,acc) = if n >= 0 then if n < 10 then acc else pers_local(produit(liste_chiffres(n)),1+acc) else pers_local(-n,acc) in pers_local(n,0);; (* étape 4 : recherche du + petit entier de persistance donnée (impératif) *) let petit_pers1(p) = let k = ref 0 in while persistance(!k) < p do k := !k + 1; done; !k ;; (* étape 4-bis : recherche du + petit entier de persistance donnée (récursif) *) let petit_pers2(p) = let rec petit_local(n,debut) = if persistance(debut) == n then debut else petit_local(n,debut+1) in petit_local(p,0);; exception Date_yennapas_exister;; exception Date_avant_petit_JC;; (*----------- Exo 2-9 -------------------------*) (* prévoir aussi un vérificateur de bonne date *) let zeller(j,m,a) = if (a==1582) && (m==10) && ((j>4)&&(j<15)) then raise Date_yennapas_exister else if a <= 0 then raise Date_avant_petit_JC else let semaine = [|"Samedi";"Dimanche";"Lundi";"Mardi";"Mercredi";"Jeudi";"Vendredi"|] in let mm = if m < 3 then m+12 else m in (* décalage éventuel du no de mois *) let aa = if m < 3 then a-1 else a in (* décalage éve1ntuel du no d'année *) let na = aa mod 100 (* numéro d'année *) in let s = aa / 100 (* numéro de siècle *) in let greg = if ((a<1582)||((a==1582)&&((m<10)||((m==10)&&(j<5))))) then (5-s) else (s/4 -2*s) in (* résidu à ajouter selon gregorien/julien *) let nj = j + na + na/4 +(26*(mm+1))/10 +greg in semaine.(rem(nj,7)) ;; (* pgcd en récursif *) let rec pgcd(a,b)= if a >= b then if b == 0 then a else pgcd(b,a mod b) else pgcd(b,a);; (* pgcd en itératif *) let pgcdit(a,b)= let aa = if a >= b then ref a else ref b in let bb = if a >= b then ref b else ref a in let temp = ref 0 in while rem(!aa,!bb) > 0 do temp := !aa ; aa := !bb ; bb := rem(!temp,!bb) ; done; !bb ;; (* Euclide étendu : coeff de Bézout *) let rec euclide2(a,b) = let rec euc(u,v,r,u',v',r') = if r' == 0 then [u;v;r] else euc(u',v',r',u - quo(r,r') * u', v - quo(r,r') * v', r - quo(r,r') * r') in euc(1,0,a,0,1,b);; (* Nb de diviseurs d'un entier *) (* récursif naïf :*) let rec nb_div_naif(n) = let rec nb_div_naif_loc(nb_a_diviser,candidat) = if candidat > nb_a_diviser then 0 else if nb_a_diviser mod candidat = 0 then 1 + nb_div_naif_loc(nb_a_diviser,candidat+1) else nb_div_naif_loc(nb_a_diviser,candidat+1) in nb_div_naif_loc(n,1);; (* Impératif naïf *) let nb_div_it(n) = let k = ref 0 in for i=1 to n do if n mod i = 0 then k := !k + 1; done; !k ;; (* Récursif amélioré *) let rec nb_div(n) = let rec nb_div_loc(nb_a_diviser,candidat) = if candidat*candidat > nb_a_diviser then 0 else if candidat*candidat = nb_a_diviser then 1 else if nb_a_diviser mod candidat = 0 then 2 + nb_div_loc(nb_a_diviser,candidat+1) else nb_div_loc(nb_a_diviser,candidat+1) in nb_div_loc(n,1);; (*----- exo 2-12 --------*) (* liste des diviseurs *) let rec liste_div(n) = let rec liste_div_loc(m,candidat) = if candidat*candidat > m then [] else if (candidat*candidat = m) then (*pas besoin d'aller voir plus loin *) [candidat] else if m mod candidat = 0 then (*on rajoute candidat et m/candidat à la liste *) (m/candidat)::candidat::liste_div_loc(m,candidat+1) else (*on passe au suivant sans rien ajouter*) liste_div_loc(m,candidat+1) in liste_div_loc(n,1);; (* somme des éléments d'une liste *) (* laisse une impression de déjà-vu... *) exception Liste_vide;; let rec som_liste = function |[] -> raise Liste_vide |tete::[] -> tete |tete::queue -> tete + som_liste(queue) ;; let parfait(n) = if som_liste(liste_div(n)) = n+n then true else false ;; let cherche_parfait(max) = let rec cherche_local(candidat,borne) = if candidat > borne then [] else if parfait(candidat) then candidat::cherche_local(candidat+1,borne) else cherche_local(candidat+1,borne) in cherche_local(1,max) ;; (*----Plus efficace------*) (* Calcule directement la somme des diviseurs de n *) let rec som_div1(n) = let rec som_div_loc(nb,candidat) = if candidat*candidat > nb then 0 else if (candidat*candidat = nb) then candidat else if nb mod candidat = 0 then candidat + (nb/candidat) + som_div_loc(nb,candidat+1) else som_div_loc(nb,candidat+1) in som_div_loc(n,1);; (* Version terminale : plus efficace *) let rec som_div(n) = let rec som_div_loc(nb,candidat,acc) = if candidat*candidat > nb then acc else if (candidat*candidat = nb) then candidat+acc else if nb mod candidat = 0 then som_div_loc(nb,candidat+1,acc+candidat+(nb/candidat)) else som_div_loc(nb,candidat+1,acc) in som_div_loc(n,1,0);; (* test de perfection *) let parfait(n) = if som_div(n) = 2*n then true else false ;; (* Recherche des parfaits <= max donné en argument *) let cherche_parfait1(max) = let rec cherche_local(candidat,borne) = if candidat > borne then [] else if parfait(candidat) then candidat::cherche_local(candidat+1,borne) else cherche_local(candidat+1,borne) in cherche_local(1,max) ;; (* récursion terminale tout en 1 plus rapide *) let cherche_parfait(max) = let rec som_div(n) = let rec som_div_loc(nb,candidat,acc) = if candidat*candidat > nb then acc else if (candidat*candidat = nb) then candidat+acc else if nb mod candidat = 0 then som_div_loc(nb,candidat+1,acc+candidat+(nb/candidat)) else som_div_loc(nb,candidat+1,acc) in som_div_loc(n,1,0) in let rec cherche_local(candidat,borne,acc) = if candidat > borne then acc else if som_div(candidat)=2*candidat then cherche_local(candidat+1,borne,candidat::acc) else cherche_local(candidat+1,borne,acc) in cherche_local(1,max,[]) ;; (*------------------------PGCD & Co-------------------------------*) (*------Algo d'Euclide I / calcul du PGCD version récursive-------*) let rec pgcd(a,b) = if a >= b then if b = 0 then a else pgcd(b,a mod b) else pgcd(b,a);; (*----- Avec espion pour compter les récursions----*) let pgcd_spy(a,b) = let rec pgcd(a,b,spy) = if a >= b then if b = 0 then (a,spy) else pgcd(b,a mod b,spy+1) else pgcd(b,a,spy+1) in pgcd(a,b,0);; (*------Fonction qui teste si 2 entiers sont 1ers entre eux--------*) let premiers_entre_eux(a,b) = if pgcd(a,b) = 1 then true else false;; (*-Euclide II / calcul du PGCD + coeff de Bézout version récursive-*) let bezout(a,b) = let rec euc(u,v,r,u',v',r') = if r' = 0 then [u;v;r] else let q = r/r' in euc(u',v',r',u-q*u',v-q*v',r-q*r') in euc(1,0,a,0,1,b);; (* ---------------------------------------------------------------------- FIN DE LA PREMIÈRE PARTIE VOICI MAINTENANT LES CODES UTILES POUR LA DEUXIÈME PARTIE *) (*Utilisation des big zentiers*) #load "nums.cma";; open Big_int;; let badd(a,b) = Big_int.add_big_int a b;; (* la même en infixe on fera a &+ b *) let (&+) a b = Big_int.add_big_int a b;; let bmul(a,b) = Big_int.mult_big_int a b;; (* la même en infixe *) let (&*) a b = Big_int.mult_big_int a b;; let bmod(a,n) = Big_int.mod_big_int a n;; (* la même en infixe *) let (&%) a n = Big_int.mod_big_int a n;; let bquo(a,b) = Big_int.div_big_int a b;; (* la même en infixe *) let (&/) a b = Big_int.div_big_int a b;; let bsub(a,b) = Big_int.sub_big_int a b;; (* la même en infixe *) let (&-) a b = Big_int.sub_big_int a b;; let begal(a,b) = Big_int.eq_big_int a b ;; (* la même en infixe *) let (&=) a b = Big_int.eq_big_int a b ;; (* transforme un petit entier en grand entier *) let big(n) = Big_int.big_int_of_int n;; (* les petits entiers basiques *) let zero = zero_big_int;; let un = unit_big_int ;; let deux = big(2) ;; (* pour afficher un grand entier sous forme de chaîne *) let montre(b) = Big_int.string_of_big_int b;; (* Le pgcd pour plus tard *) let bgcd a b = Big_int.gcd_big_int a b ;; (* fonction polymorphe définissant une opération op modulo p*) let modop(a,b,p,op) = ((op) (a &% p) (b &% p)) &% p;; (* Version infixe de la multiplication modulaire a*b mod p est obtenu par a &&* (b,p) *) let (&&*) a (b,p) = modop(a,b,p,(&*));; (*Rabin Miller *) (*Grand entier aléatoire*) exception Taille_negative;; (* nombres aléatoires (d'après le module numerix de Michel Quercia) *) (* land est le ET logique bit à bit : plus rapide que mod 1 lsl p effectue un décalage de 1 bit : plus rapide que 2^p 0xn est l'entier écrit n en base 16 On travaille donc par paquet de 16^4 renvoie un nombre < 2^n*) let nrandom n = if n < 0 then raise Taille_negative else if n = 0 then big(0) else begin let p = if n land 15 = 0 then 16 else n land 15 in let mask = (1 lsl p) - 1 in let r = ref(big(((Random.int(0xfffe)) land (mask-2))+2)) in for i=1 to (n-p)/16 do r := add_int_big_int (Random.int(0x10000)) (mult_int_big_int 0x10000 !r) done; !r end ;; let fonction_1(n) = let rec loop(s,t) = if (s &% deux) &= zero then loop( s &/ deux , t &+ un ) else [|s;t|] in loop(n &- un,zero);; let fonction_2(v,n,t) = if v &= un then true else let rec loop(v,u) = if v &= (n &- un) then true else if u &= (t &- un) then false else loop( v &&^ (deux,n) , u &+ un ) in loop(v,zero);; let fonction_3(n) = int_of_float(log(float_of_big_int(n))/.log(2.));; let nrandom1 n = if n < 0 then raise Taille_negative else if n = 0 then zero else begin let p = if n land 15 = 0 then 16 else n land 15 in let mask = 1 lsl (p-1) in let r = ref(big_int_of_int((Random.int(0x10000) land (mask-1)) lor mask)) in for i=1 to (n-p)/16 do r := add_int_big_int (Random.int(0x10000)) (mult_int_big_int 0x10000 !r) done; !r end ;;