On travaille ici sur les entiers (type int). Le but de cet exercice est de redéfinir les opérations connues sur les entiers. On suppose que les opérations déjà existantes sont seulement l'addition et la soustraction.
1) Redéfinissez une fonction mult a b qui rend a*b (on suppose a et b positifs).
Voyons deux moyens de faire cela. La première fonction sera impérative. On crée une référence valant 0 et on lui ajoute b fois la valeur a.
let mult a b =
let n = ref 0 in
for i = 1 to b do n:= !n + a done;
!n;;
Et une version récursive : on fait une fonction auxiliaire qui prend en arguments un résultat intermédiaire nommé resu et un indice i indiquant le nombre de fois qu'il reste à ajouter a. On commence avec resu = 0 et i = b. A chaque étape, on ajoute a à resu et on enlève 1 à i. On continue jusqu'à ce que i soit nul. Dans ce cas, on rend resu :
let mult a b =
let rec aux i resu =
if i = 0 then resu else aux (i-1) (a+resu)
in aux b 0;;
Remarque : l'hypothèse que b est positif est importante car sinon le programme ne se terminerait pas (par exemple dans la version impérative, on aurait une boucle pour i variant de 1 à une valeur négative, donc la boucle ne se terminera pas). L'hypothèse pour a n'est pas importante ici, mais était là pour la symétrie des deux arguments...
2) Ecrivez une fonction puissance telle que puissance a i rende ai (on suppose a et i positifs).
On fait exactement comme pour définir la fonction mult, sauf qu'au lieu d'additionner, on se sert de mult. Version impérative :
let puissance a i =
let n = ref 1 in
for j = 1 to i do n:= mult !n a done;
!n;;
Version récursive :
let puissance a i =
let rec aux indice resu =
if indice = 0 then resu else aux (indice-1) (mult resu a)
in aux i 1;;
3) Maintenant, on s'intéresse à la division euclidienne. Pour simplifier, on ne travaille qu'avec des nombres positifs. Définissez d'abord la fonction modu (modu a b doit rendre le reste dans la division euclidienne de a par b : modu 15 4 rend 3). Définissez ensuite la fonction quot : quot a b doit rendre le quotient de la même division.
Pour modu, on fait une fonction récursive : quand on demande modu a b, si a est entre 0 et (b-1) alors le résultat est a. Sinon, on enlève b à a et on recommence.
let rec modu a b = if a < b then a else modu (a-b) b;;
Pour quot, on procède ainsi : on enlève à a le résultat de modu a b pour avoir un multiple de b. Puis on enlève b autant de fois qu'il le faut pour arriver à 0 et on compte le nombre de fois qu'on a enlevé b. Version impérative :
let quot a b =
let a2 = ref (a - (modu a b)) and compteur = ref 0 in
while !a2 > 0 do
a2 := !a2 - b; incr compteur
done;
!compteur;;
Version récursive :
let quot a b =
let rec aux a2 compteur = if a2 = 0 then compteur else aux (a2 - b) (compteur + 1)
in aux (a - (modu a b)) 0;;
4) Les deux fonctions précédentes peuvent être optimisées. En effet, quot utilise modu alors qu'on pourrait faire les deux calculs en même temps (ce qui réduit donc de moitié le temps de calcul). Voyez-vous comment ?
Solution
> Haut de la page
