TP 3 : Structures persistantes

Petites questions¶

Exercice

1. Écrire une fonction fact : int -> int telle que fact n renvoie $n!$ (=$n\times (n-1)\times ... \times 2 \times 1$), en utilisant une boucle.
2. Écrire une fonction taille : 'a list -> int pour calculer le nombre d'élements d'une liste (déjà fait dans le cours mais il faut savoir le refaire).
3. Écrire une fonction somme : float list -> int pour calculer la somme des élements d'une liste (déjà fait dans le cours mais il faut savoir le refaire).
4. Écrire une fonction moyenne : float list -> float pour calculer la moyenne des élements d'une liste (on pourra utiliser les deux fonctions précédentes et float_of_int).
5. Écrire une fonction oppose : int list -> int list telle que oppose l renvoie une liste contenant l'opposé de chaque élément de l. Par exemple, oppose [1; 2; 3] renvoie [-1; -2; -3].
6. Écrire une fonction positif : int list -> bool pour déterminer si tous les éléments d'une liste sont positifs.
7. Écrire une fonction dernier pour obtenir le dernier élément d'une liste.

Solution

In [ ]:

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

(* 2 *)
let rec taille l = match l with
    | [] -> 0
    | e::q -> 1 + taille q;;

(* 3 *)
let rec somme = function
    | [] -> 0.
    | e::q -> e +. somme q;;

(* 4 *)
let moyenne l = (somme l) /. (float_of_int (taille l));;

(* 5 *)
let rec oppose = function
    | [] -> []
    | e::q -> (-e)::oppose q;;

(* 6 *)
let rec positif = function
    | [] -> true
    | e::q -> e >= 0 && positif q;;

(* 7 *)
let rec dernier = function
    | [] -> failwith "Pas de dernier élément"
    | [e] -> e
    | _::q -> dernier q

(* 1 *) let rec fact n = if n = 0 then 1 else n*fact (n - 1);; (* 2 *) let rec taille l = match l with | [] -> 0 | e::q -> 1 + taille q;; (* 3 *) let rec somme = function | [] -> 0. | e::q -> e +. somme q;; (* 4 *) let moyenne l = (somme l) /. (float_of_int (taille l));; (* 5 *) let rec oppose = function | [] -> [] | e::q -> (-e)::oppose q;; (* 6 *) let rec positif = function | [] -> true | e::q -> e >= 0 && positif q;; (* 7 *) let rec dernier = function | [] -> failwith "Pas de dernier élément" | [e] -> e | _::q -> dernier q

Nombres premiers¶

Exercice

1. Écrire une fonction premier : int -> bool déterminant si un entier est premier. On pourra utiliser une fonction récursive ou une boucle for.
2. En déduire une fonction tous_premiers : int -> int list telle que tous_premiers n renvoie la liste des nombres premiers entre $2$ et $n$.

Solution

In [1]:

(* 1. *)
let premier n =
    let rec aux d = (* teste s'il existe un d < n divisant n *)
        if d = 1 then false (* on n'a pas trouvé de diviseur *)
        else n mod d = 0 || aux (d - 1) in
    aux (n/2)
    
(* 2 *)
let tous_premiers n =
    if n = 1 then []
    else let l = tous_premiers (n - 1) in
         if premier n then n::l
         else l

(* 1. *) let premier n = let rec aux d = (* teste s'il existe un d < n divisant n *) if d = 1 then false (* on n'a pas trouvé de diviseur *) else n mod d = 0 || aux (d - 1) in aux (n/2) (* 2 *) let tous_premiers n = if n = 1 then [] else let l = tous_premiers (n - 1) in if premier n then n::l else l

Out[1]:

val premier : int -> bool = <fun>

Bezout¶

Exercice

Écrire une fonction récursive bezout : int -> int -> int*int*int telle que bezout a b renvoie un triplet (d, u, v) tel que d est le PGCD de a et b et u, v vérifient au + bv = d (coefficients de Bézout).
Pour cela, on appelera récursivement bezout b r où $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$ (on a donc $a = bq + r$). bezout b r donne un triplet $(d, u', v')$ et on essaiera d'exprimer $u, v$ en fonction de $u'$, $v'$ (on pourra sortir une feuille pour chercher une relation).
Le cas de base sera obtenu pour $b = 0$.

Solution

On a : $$a = bq + r$$ $$\Longrightarrow r = a - bq$$ Donc : $$d = u'b + v'r$$ $$\Longrightarrow d = u'b + v'(a - bq)$$ $$\Longrightarrow d = \underbrace{(u' - v'q)}_vb + \underbrace{v'}_ua$$

Solution

In [4]:

let rec bezout a b =
    if b = 0 then (a, 1, 1)  (* a = 1*a + 1*b *)
    else let d, u', v' = bezout b (a mod b) in
         d, v', u' - v'*(a/b) in
bezout 7 3

let rec bezout a b = if b = 0 then (a, 1, 1) (* a = 1*a + 1*b *) else let d, u', v' = bezout b (a mod b) in d, v', u' - v'*(a/b) in bezout 7 3

Out[4]:

- : int * int * int = (1, -2, 5)

Fusion de listes¶

Exercice

1. Écrire une fonction fusion : int list -> int list -> int list telle que, si l1 et l2 sont deux listes triées, fusion l1 l2 renvoie une liste triée composée de l'union de l1 et l2.
   Par exemple, fusion [2; 5; 8] [3; 4; 10] doit renvoyer [2; 3; 4; 5; 8; 10].
2. Écrire une fonction kfusion : int list list -> int list qui prend une liste de listes triées en argument et renvoie une liste triée contenant l'union de toutes les ces listes.
   Par exemple, kfusion [[2; 5; 8]; [3; 4; 10]; [0; 13]] doit renvoyer [0; 2; 3; 4; 5; 8; 10; 13].
3. Implémenter le tri fusion permettant de trier une liste l :
   • Décomposer l en deux listes l1 et l2 de tailles (à peu près) égales
   • Trier récursivement l1 et l2 pour obtenir l1' et l2'
   • Fusionner l1' et `l2' pour obtenir une seule liste triée

Solution

In [9]:

(* 1 *)
let rec fusion l1 l2 = match l1, l2 with
    | [], _ -> l2
    | _, [] -> l1
    | e1::q1, e2::q2 -> if e1 < e2 then e1::fusion q1 l2
                        else e2::fusion l1 q2 in
fusion [2; 5; 8] [3; 4; 10];;

(* 2 *)
let rec kfusion ll = match ll with
    | [] -> []
    | l::q -> fusion l (kfusion q) in
kfusion [[2; 5; 8]; [3; 4; 10]; [0; 13]];;

(* 3 *)
(* Voir cours complexité *)

(* 1 *) let rec fusion l1 l2 = match l1, l2 with | [], _ -> l2 | _, [] -> l1 | e1::q1, e2::q2 -> if e1 < e2 then e1::fusion q1 l2 else e2::fusion l1 q2 in fusion [2; 5; 8] [3; 4; 10];; (* 2 *) let rec kfusion ll = match ll with | [] -> [] | l::q -> fusion l (kfusion q) in kfusion [[2; 5; 8]; [3; 4; 10]; [0; 13]];; (* 3 *) (* Voir cours complexité *)

Out[9]:

- : int list = [2; 3; 4; 5; 8; 10]

Out[9]:

- : int list = [0; 2; 3; 4; 5; 8; 10; 13]