USTHB

Faculté Informatique
TP Caml
Section 3 – Groupes 2 & 4

TP CaML Ligh

TP2 : Les Fonctions

Ecrire en langage CAML les fonctions suivantes
1. Succ qui calcule le successeur d’un entier.

let Succ x = x+1;;

2. Pred qui calcule le prédécesseur d’un entier.

let Pred x = x-1;;

3. Sum qui calcule la somme de 2 entiers.

let Sum x y = x+y;;

4. Max qui calcule le maximum de 2 réels.

let Max x y = if x>y then x else y;;

5. Max3 qui calcule le maximum de 3 réels de 2 façons différentes (Sans utiliser Max,
puis en utilisant Max).

let Max3 x y z = if x>y then (if x>z then x else z) else (if y>z then y else z);;
let Max3 x y z = Max(Max x y) z;;

6. MinMax qui donne le min et le max en même temps de 2 entiers.

let MinMax x y = if(x>y) then (x,y) else (y,x);;

 7. Carre qui calcule le carre d’un entier.

let carre x = x*x;;

8. SCarre qui calcule la somme des carrés de 2 entiers (en utilisant la fonction Carre).

let SCarre x y = carre(x)+carre(y);;

9. ValAbs qui calcule la valeur absolue d’un entier. - Abs qui calcule la fonction :
Abs (x, y ) = | x – y | .

let ValAbs x = if(x<0) then x*(-1) else x;;

10. Surf qui calcule la suface d’un cercle de rayon r (∏ = 3.14).

let surf r = float_of_int(carre r) *. 3.14;;

11. Pair qui retourne vrai si son argument est un entier pair, faux sinon.

let pair x = if (x mod 2 =0) then true else false;;

12. Prem qui retourne vrai si son argument est un entier premier, faux sinon

let rec ndiv_se x i = if i>x then 0

else if i<1 then ndiv_se x 1
else if i=x then 1
else if x mod i =0 then 1+ndiv_se x (i+1)
else ndiv_se x (i+1);;
TP3 : Les Fonctions Récursives
Ecrire en langage CAML les fonctions récursives suivantes :
1. Fact : factoriel d’un entier n.

let rec fact n = if n = 0 then 1 else n * fact (n-1) ;;

2. Exp qui calcule la fonction : Exp (x , y ) = xy.

let rec Exp x y = if y=0 then 1 else x*(Exp x (y-1));;

3. Sigma : la somme des entiers de 0 à x.

let rec sigma x = if x=0 then 0 else x+sigma(x-1);;

4. Sigma2 : la somme des entiers compris entre 2 entiers a et b.

let rec sigma2 a b = if a=b then a else a+(sigma2(a+1) b);;

5. Fib : la fonction Fibbonacci définie par :

𝟎 𝒔𝒊 𝒏 = 𝟎
𝑭𝒊𝒃(𝒏) = { 𝟏 𝒔𝒊 𝒏 = 𝟏
𝑭𝒊𝒃(𝒏 − 𝟏) + 𝑭𝒊𝒏(𝒏 − 𝟐) 𝒔𝒊𝒏𝒐𝒏

let rec Fib n = if n=0 then 0 else if n=1 then 1 else Fib (n-1)+Fib (n-2) ;;

6. PGCD : la fonction qui calcule le PGCD de 2 entiers, en utilisant l'algorithme

d'Euclide : PGCD(a,b) = PGCD(b,r), où r est le reste de la division de a par b

let rec PGCD a b = if b=0 then a else PGCD b (a mod b);;

7. PGCD2 : la fonction qui calcule le PGCD de 2 entiers, en utilisant l'algorithme

suivant :
𝒂 𝒔𝒊 𝒂 = 𝒃
𝑷𝑮𝑪𝑫𝟐(𝒂, 𝒃) = {𝑷𝑮𝑪𝑫𝟐(𝒂 − 𝒃, 𝒃) 𝒔𝒊 𝒂 > 𝒃
𝑷𝑮𝑪𝑫𝟐(𝒂, 𝒃 − 𝒂) 𝒔𝒊 𝒂 < 𝒃

let rec PGCD2 a b= if a=b then a else if a>b then PGCD (a-b) b else PGCD a (b-a);;
 8. SumSerie : la fonction qui calcule la somme des n premiers termes de la série
harmonique de la forme :

let rec SumSerie n = if n=0 then 0. else 1.0 /. float_of_int n +. SumSerie (n-1);;
TP4 : Les Listes
Ecrire en langage CAML les fonctions récursives suivantes :
1. Calcule le nombre d’éléments d’une liste (nbElm).

let rec nbElm x = if x=[] then 0 else 1+nbElm (tl x);;

2. Calcule la somme des éléments d’une liste (somElm).

let rec nbElm x = if x=[] then 0 else 1+nbElm (tl x);;

3. Calcule la moyenne des éléments d’une liste en utilisant les fonctions nbElm et
somElm.

let rec moyenne x = float_of_int(somElm x) /. float_of_int(nbElm x);;

4. Insère un élément au début d’une liste.

let ins x y = x::y;;

5. Insère un élément à la fin d’une liste.

let ins_fin x y = y@(x::[]);;

6. Supprime un élément au début d’une liste non vide.

let supp_deb x = tl x;;

7. Supprime un élément à la fin d’une liste non vide (utiliser la fonction nbElm).

let rec supp_fin x = if nbElm x=1 then [] else hd x :: supp_fin (tl x);;

8. Inverse une liste

let rec inv x = if x=[] then [] else inv(tl x)@(hd x::[]);;

9. Inverse une liste. 9. Projette l’élément n°I (I >0) d’une une liste non vide.

let rec inv x = if x=[] then [] else inv(tl x)@(hd x::[]);;

 10. Détermine si un élément donné appartient ou non à une liste.

let rec appartient x liste = if liste=[] then false else if x=hd liste then true else appartient
x (tl liste);;

11. Prend un nombre entier et une liste d'entier et compte les occurrences de ce
nombre dans cette liste.

let rec occ x liste = if liste=[] then 0

else if x=hd liste then 1+(occ x (tl liste))
else occ x (tl liste);;

12. Calcule la fonction Map définie par : Map f [a1 ; a2 ; … ; an] -> [(f a1) ; (f a2) ; … ; (f
an)] (Distribue la fonction f sur les éléments de la liste).
• Appliquer la fonction Map pour élever au carrée les éléments d’une liste
d’entiers.
• Appliquer la fonction Map pour inverser les mots dans une liste de mots

let f x = x+1;;
let rec map f liste = if liste=[] then [] else f (hd liste)::map f (tl liste);;

let carre x = x*x;;

map carre [1;2;3;4];; [1; 4; 9; 16]

On connait déja inv:

let rec inv s = if string_length s=1 then s
else (sub_string s ((string_length s)-1) 1) ^
inv(sub_string s 0 ((string_length s)-1));;

map inv ["chat"; "lait"; "chien"] ;;

13. Trie une liste d’entiers par ordre croissant.

let rec supp_occ x liste = if hd liste = x then tl liste else hd liste::supp_occ x (tl liste);;
let rec min liste = if tl liste=[] then hd liste +0
else if hd liste>=hd(tl liste) then min(tl liste)
else min(hd liste :: tl(tl liste));;
let rec tri liste = if liste=[] then [] else min liste :: tri(supp_occ(min liste) liste);;
tri [5;1;8;3;0;10];;
TP5 : EXERCICES GENERAUX
Exercice 1
Ecrire une fonction calculant le produit de deux nombres suivant la méthode de la
multiplication dite égyptienne :

• 0 si x=0
• Mult_egypt (x,y) = Mult_egypt(x/2, 2*y) si x est pair
• y + Mult_egypt(x-1, y) sinon

let rec Mult_egypt x y= if x=0 then 0

else if x mod 2=0 then Mult_egypt (x/2) (2*y)
else y+Mult_egypt (x-1) y;;

Exercice 2
Ecrire une fonction calculant le ppcm (plus petit commun multiple). On pourra s'aider du
pgcd (plus grand commun diviseur).

On utilise la formule suivante : a*b=pgcd a b*ppcm a b

Donc:
let ppcm a b=a*b/pgcd a b ;

Exercice 3
1. Ecrire une fonction inv qui inverse un mot. Exemple "CAML" sera transformé en "LMAC"

let rec inv s = if string_length s=1 then s

else (sub_string s ((string_length s)-1) 1) ^
inv(sub_string s 0 ((string_length s)-1));;

2. Ecrire une fonction palind qui reconnaît les palindromes, comme "RADAR" ou
"eluparcettecrapule"

let rec palind s = if string_length s=1 then true

else if s.[0] <> s.[(string_length s) -1] then false
else palind(sub_string s 1 ((string_length s) -2));;
Exercice 4
Ecrire et tester la fonction de détermination des années bissextiles utilisant la définition
suivante :

« Toutes les années divisibles par 4 sont bissextiles sauf celles qui sont divisibles par 100 et
qui ne sont pas divisibles par 400. »

let bissextile annee = if annee mod 4 <> 0

then false
else if annee mod 100 = 0 && annee mod 400 <> 0
then false
else true;;

Exercice 5
1. Ecrire la fonction prod qui fait le produit de x par y, sans utliser l’opérateur *.

let rec prod x y = if y=0 then 0 else x+prod x (y-1);;

2. Ecrire la fonction puiss qui calcule la puissance xy en utilisant la fonction prod.

let rec puiss x y = if y=0 then 1 else prod x (puiss x (y-1));;

Exercice 6
1. Ecrire une fonction récursive rest qui calcule le reste de la division entière de x par y.

let rec rest x y = if x<y then x else rest (x-y) y;;

2. Ecrire une fonction récursive quot qui calcule le quotient de la division entière de x par y.
Remarque : On ne pourra pas utiliser les opérations / et mod

let rec quot x y = if x<y then 0 else 1+(quot (x-y) y);;