Aller au contenu

Fractions

On va écrire ici un type et des fonctions pour manipuler des éléments de \(\Q\). Pour pouvoir tester directement l'égalité, on va adopter une représentation irréductible des rationnels : pour tout \(r \in \Q\), il existe un unique couple \((a,b) \in \Z \times \N^*\) tel que \(r = \frac{a}{b}\) et \(\text{pgcd}(a,b) = 1\).

Question 1. Écrire une fonction pgcd : int -> int -> int qui prend en entrée deux entiers relatifs \(a,b\) tels que \((a,b) \neq (0,0)\) et renvoie leur pgcd (qui est positif).

On pourra utiliser les relations suivantes : \(\text{pgcd}(a,0) = |a|\) et si \(b \neq 0\) et \(a = b q + r\), on a \(\text{pgcd}(a,b) = \text{pgcd}(b,r)\).

Tests 
let test a b v =
    Printf.printf "Test %d ^ %d : " a b;
    let v' = pgcd a b in
    if v <> v'
    then Printf.printf "Erreur %d <> %d\n" v' v
    else Printf.printf "OK\n" in
test 1 10 1;
test 10 1 1;
test (-3) 0 3;
test 12 16 4;;
Corrigé 
let rec pgcd a b =
    if b = 0
    then if a < 0 then -a else a
    else pgcd b (a mod b)

En OCaml, a mod b peut être négatif quand a l'est, mais on a toujours a = b * (a / b) + a mod b, ce qui suffit pour appliquer la relation précédente.

On va définir le type OCaml suivant :

type fraction = {
    num : int;
    den : int
}

Pour définir une fraction, il suffit donc d'écrire { num = 3; den = 2 } et si \(f\) est une fraction, on peut utiliser f.num ou f.den.

Question 2. Écrire une fonction est_irreductible : fraction -> bool qui renvoie un booléen indiquant si une fraction est bien irréductible, c'est-à-dire \(\frac{a}{b}\) avec \(\text{pgcd}(a,b)=1\) et \(b > 0\).

Tests 
assert(est_irreductible { num = 8; den = 27 });
assert(not (est_irreductible { num = 1; den = -1 }));
assert(not (est_irreductible { num = 12; den = 16 }));
Printf.printf "est_irreductible : OK\n";;
Corrigé 
let est_irreductible f =
    pgcd f.num f.den = 1 && f.den > 0

Question 3. Écrire une fonction simplifie : fraction -> fraction qui, étant donnée une fraction \(\frac{a}{b}\) (avec \(b \neq 0\)), renvoie une fraction irréductible \(\frac{a'}{b'}\) telle que \(\frac{a}{b} = \frac{a'}{b'}\).

Tests 
let test f v =
    Printf.printf "Test %d/%d : " f.num f.den;
    let v' = simplifie f in
    if v <> v'
    then Printf.printf "Erreur %d/%d <> %d/%d\n" 
        v'.num v'.den v.num v.den
    else Printf.printf "OK\n" in
test { num = 12; den = 4 } { num = 3; den = 1 };
test { num = 12; den = -4 } { num = -3; den = 1 };
test { num = 0; den = 3 } { num = 0; den = 1 };
test { num = -3; den = -2 } { num = 3; den = 2 };
test { num = 3; den = -2 } { num = -3; den = 2 };;
Corrigé 
let simplifie f =
    let k = pgcd f.num f.den in
    let s = if f.den / k < 0 then -1 else 1 in
    {
        num = s * f.num / k;
        den = s * f.den / k
    }

Question 4. Écrire les fonctions suivantes en supposant que les fractions en entrée sont irréductibles et qui renvoient des fractions irréductibles :

  • frac_som : fraction -> fraction -> fraction qui renvoie la somme de deux fractions
  • frac_mult : fraction -> fraction -> fraction qui renvoie le produit de deux fractions
  • frac_neg : fraction -> fraction qui renvoie l'opposée d'une fraction
  • frac_sub : fraction -> fraction -> fraction qui renvoie la différence de deux fractions
  • frac_inv : fraction -> fraction qui renvoie l'inverse d'une fraction non nulle
  • frac_div : fraction -> fraction -> fraction qui renvoie le quotient de deux fractions
Tests 
let f1 = { num = 1; den = 3 } in
let f2 = { num = 1; den = 2 } in
Printf.printf "Test frac_som\n";
assert(frac_som f1 f2 = { num = 5; den = 6 });
assert(frac_som f2 f2 = { num = 1; den = 1 });
Printf.printf "Test frac_mult\n";
assert(frac_mult f1 f2 = { num = 1; den = 6 });
Printf.printf "Test frac_neg\n";
assert(frac_neg f1 = { num = -1; den = 3 });
Printf.printf "Test frac_sub\n";
assert(frac_sub f1 f2 = { num = -1; den = 6 });
Printf.printf "Test frac_inv\n";
assert(frac_inv f1 = { num = 3; den = 1 });
Printf.printf "Test frac_div\n";
assert(frac_div f1 f2 = { num = 2; den = 3 });
Printf.printf "OK";;
Corrigé 
let frac_som f1 f2 =
    simplifie { 
        num = f1.num * f2.den + f1.den * f2.num;
        den = f1.den * f2.den
    }

let frac_mult f1 f2 =
    simplifie {
        num = f1.num * f2.num;
        den = f1.den * f2.den
    }

let frac_neg f =
    { num = -f.num; den = f.den }

let frac_sub f1 f2 =
    frac_som f1 (frac_neg f2)

let frac_inv f =
    if f.num = 0 then failwith "Division par zéro";
    if f.num > 0
    then { num = f.den; den = f.num }
    else { num = - f.den; den = - f.num }

let frac_div f1 f2 =
    frac_mult f1 (frac_inv f2)

Pour frac_inv, il faut faire attention au signe : l'inverse de \(\frac{-2}{3}\) doit être représenté par \(\frac{-3}{2}\) et non par \(\frac{3}{-2}\), qui n'est pas irréductible au sens précédent.

Retour sur les listes

Remarque

On va ici reprendre le type récursif essentiel en OCaml : les listes.

Il s'agit de questions de révision qui reprennent parfois des fonctions déjà traitées dans les TP précédents.

On rappelle que les listes peuvent être vues comme définies par le type :

type 'a list = [] | (::) of 'a * 'a list

Ainsi, si t est une valeur de type 'a et q une valeur de type 'a list, alors t::q est une valeur de type 'a list qu'on peut voir comme étant la liste qui commence par t et se poursuit par q.

Attention :: n'est vraiment pas symétrique ! Comme pour \(\in\) en mathématiques, il y a un déséquilibre : element :: liste.

Question 5. Écrire une fonction ajoute_ind_pair : int list -> int qui prend en entrée une liste d'entiers et renvoie la somme de ses éléments d'indices pairs.

Ainsi, si on passe la liste \([a_0;a_1;\dots;a_{n-1}]\) cela va renvoyer \(a_0 + a_2 + a_4 + \dots\).

Tests 
let test l v =
    Printf.printf "Test [%s] : " (l |> List.map string_of_int |> String.concat ";");
    let v' = ajoute_ind_pair l in
    if v <> v'
    then Printf.printf "Erreur %d <> %d\n" v' v
    else Printf.printf "OK\n" in
test [] 0;
test [1] 1;
test [1;2] 1;
test [1;2;3] 4;
test [1;2;3;4] 4;;
Corrigé 
let rec ajoute_ind_pair l =
    match l with
    | [] -> 0
    | [x] -> x
    | a::b::q -> a + ajoute_ind_pair q

Question 6. Écrire une fonction mex : int list -> int qui prend en entrée une liste d'entiers relatifs et renvoie le plus petit entier naturel, donc \(\ge 0\), qui n'est pas présent dans cette liste.

Il est facile de faire une fonction de complexité quadratique, mais essayez d'en faire une ensuite de complexité linéaire.

Tests 
assert(mex [1;2;3] = 0);
assert(mex [0;1;3] = 2);
assert(mex [0;1;2] = 3);
assert(mex [-1;-4;2] = 0);
assert(mex [-1;-4;0] = 1);
Printf.printf "OK\n";;
Corrigé 
(* Version quadratique *)
let mex l =
    let rec aux n =
        if List.mem n l
        then aux (n+1)
        else n
    in aux 0

(* Version linéaire *)
let mex l =
    let n = List.length l in 
    let a = Array.make (n+1) false in
    List.iter (fun i -> 
        if 0 <= i && i <= n 
        then a.(i) <- true) l;
    let m = ref 0 in
    while a.(!m) do
        incr m
    done;
    !m

La version linéaire repose sur le fait que, si la liste est de longueur \(n\), l'un des entiers \(0, 1, \dots, n\) est absent : le mex est donc au plus \(n\) et on peut ignorer les valeurs hors de \(\range{0}{n}\).

Question 7. Écrire une fonction coupures : 'a list -> ('a list * 'a list) list qui, étant donné une liste l, renvoie, sous forme d'une liste, la liste de tous les couples (l1,l2) tels que l = l1 @ l2.

Exemple : coupures [1;2;3] renvoie [ ([], [1;2;3]); ([1], [2;3]); ([1;2], [3]); ([1;2;3], []) ].

Corrigé 
let rec coupures l =
    ([], l) :: match l with
               | [] -> []
               | t::q -> 
                   List.map (fun (l1,l2) -> (t::l1, l2)) 
                     (coupures q)

Ici, le List.map sert à rajouter t en tête de toutes les listes l1.

Installer OCaml et son écosystème sur votre ordinateur

On a vu comment avoir un environnement complet avec la machine virtuelle, mais c'est peu efficace. Le mieux est d'avoir directement OCaml (et ça va impliquer d'avoir un compilateur C en fait, donc on fait d'une pierre deux coups).

Installer opam

Le plus simple, de très loin, est d'être sur Linux. Il suffit alors d'installer opam avec votre gestionnaire de paquets.

Sur macOS, il faut d'abord installer un gestionnaire de paquets et ensuite, c'est comme si on était sur Linux. Le meilleur est brew.

Sur Windows, la meilleure option, de très loin, est d'installer WSL qui va, en fait, superposer une installation de Linux dans Windows. C'est un peu comme si vous aviez un calque Linux qui se rajoute au-dessus. Ensuite, on procède exactement comme sur Linux. Pour installer WSL, vous pouvez suivre ces instructions.

Installer un switch

Une fois opam installé, on peut installer sa propre mini-distribution de OCaml.

Pour cela, dans un terminal, commencez par lancer opam init pour initialiser la configuration d'opam, puis on va choisir une version de OCaml 5 avec, par exemple, opam switch create 5.2.0 (la commande opam switch list-available donne la liste des versions disponibles).

Répondez y à tout. Quand vous relancez un terminal, normalement, vous avez la version de OCaml choisie.