TUTORIEL OCAML

Correction des exercices

Bon voici les corrections ^_^.

Calculs

Ici sera quelques fonctions qui permettent de faire des calculs de base.
Certaines existent déjà en Caml, mais l'objectif est de se perfectionner en récursivité :-D.

Somme Deux Entiers

Principe :
- On reconnaît le cas de sortie lorsque l'une des deux valeurs est égale à 0 (j'ai choisi de prendre pour x = 0 comme cas de sortie).
- Sinon on incrémente de 1 le tout et on décrémente de 1 la valeur de x .

Version Classique :

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

Version Terminale :

let somme x y =
  let rec add x y =
    if x = 0 then y
    else add (x-1) (y+1)
in add x y;;

Multiplication de Deux Entiers

Même principe que pour l'addition, sauf que au lieu d'incrémenter de 1 on incrémente de y . Et le cas de sorti est pour x = 1.

Version Classique :

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

Version Terminale :

let mult x y =
  let rec mu x y acc =
    if x = 1 then acc
    else mu (x-1) y (acc+y)
in mu x y y;;

PGCD

Je vous ai déjà expliquer cette fonction ici.

Version Terminale :

let pgcd x y =
  let rec pg x y =
    if (x mod y = 0) then y
    else pg y (x mod y)
in pg x y;;

print_int (pgcd 34 12);;
2

Suite de fibonacci

Version Classique :

let rec fibo n = match n with
  |0->0
  |1->1
  |_->fibo(n-1)+fibo(n-2);; print_int (fibo 6) ;;

Version Terminale :

let fibo x =
  let rec fib x acc1 acc2 =
    if x = 0 then acc2
    else fib (x-1) acc2 (acc1+acc2)
in fib x 1 0;;

Nombre de Chiffre dans un Nombre

Ici 'x ' est le nombre dont on cherche à déterminer le nombre de chiffre(s) qui le contient (exemple : 1234 contient 4 chiffres).

Principe :
- Si x / 10 = 0, cela signifie en Caml que x ne contient qu'un seul chiffre (1 ou 2 ou 3 ou ... ou 9).
- Sinon on rappelle la fonction avec ( x / 10) ce qui signifie qu'on la rappelle avec un chiffre de moins dans x , on va donc incrémenter de 1 à chaque récursion. Au final, la fonction renverra le ne nombre de chiffre que contient x .

Version Classique :

let rec nb_chiffres x =
  if x / 10 = 0 then 1
  else 1 + nb_chiffres (x/10);;

Version Terminale :

let nb_chiffres x =
  let rec nbch x acc =
    if x / 10 = 0 then acc
    else nbch (x/10) (acc+1)
in nbch x 1;;

Fonction Puissance

On va calculer x ^y .
En mathématiques, pour tout x , x ⁰ = 1. On a notre cas de sortie !
Tous les autres cas: on multiplie par x à chaque récursion (et on fait un total de y récursion(s)).

Version Classique :

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

Version Terminale :

let pow x y =
  let rec p x y acc =
    if y = 0 then acc
    else p x (y-1) (acc*x)
in p x y 1;;

Nombres de diviseurs

Je n'ai pas réussi à faire cette fonction en version non terminale, si vous y arrivez je suis preneur :-P Merci !

Principe :

- x est le nombre dont on cherche à déterminer le nombre de diviseur(s) qu'il possède.
- y est la variable qui va nous permettre de déterminer quels sont les diviseurs de x , au départ y vaut x et va décrémenter jusqu'à 1.
Quoiqu'il arrive y décrémente à chaque récursion.
- acc représente le nombre de diviseurs de x .
- A chaque récursion, on vérifie si ( x mod y = 0) c'est-à-dire si y est un diviseur de x .
Si c'est le cas, on rappelle la fonction avec acc qui est incrémenté. - Sinon on rappelle la fonction avec acc qui stagne.

Version Classique :

let rec nbdiv x div =
  if div = 1 then 1
  else if (x mod div) = 0 then 1 + (nbdiv x (div-1))
  else (nbdiv x (div-1)) ;;

Voici un exemple d'application :

nbdiv 12 12;;
- : int = 6 (* car 12 a bien 6 diviseurs *)

Cet fonction doit nous renvoyer le nombre de diviseurs d'un entier naturel (ex: le nombre de diviseurs de 12).
Mais ici notre fonction prend deux paramètres (c'est l'inconvénient de ma version classique... la version terminale fonctionne beaucoups mieux pour ça).

Voilà ce que l'on peut faire :

let nbdiviseurs x = nbdiv x x;;

On vient de créer une nouvelle fonction : nbdiviseurs qui ne prend qu'un paramètre
Et qui nous renvoie bien le nombre de diviseurs de x :

nbdiviseurs 12 ;;
- : int = 6

Version Terminale :

let nbdiv x =
  let rec nbdi x y acc =
    if y = 1 then acc
    else if (x mod y = 0) then nbdi x (y-1) (acc+1)
    else nbdi x (y-1) acc
in nbdi x x 1;;

La valeur renvoyée est le nombre de diviseur(s) de x , cela inclut 1, lui-même et ses diviseurs intermédiaires :

- Il faut modifier la valeur initiale de acc en 0 pour ne plus prendre en compte la valeur x elle-même.
- Et il faut mettre le cas d'arrêt à y = 2 pour ne plus prendre en compte 1 comme diviseur.

Vérifier q'un entier est Premier

let est_premier x =
nbdiv x = 2;;

Un nombre premier a exactement deux diviseurs :
1 et lui-même.
C'est plutôt simple, même pas de récursivité !
En fait si il y a bien un peu de récursivité puisqu'on appelle nbdiv avec 2 (et comme cette fonction est récursive...).

Décomposition d'un Entier en Facteur(s) Premier(s)

Je vous renvoie vers cette page pour plus d'explication : Définition Wikipédia.
Voici comment utiliser habilement les listes pour accumuler des valeurs, si on fait le produit de toutes ces valeurs on retrouve la valeur avec laquelle on a appelé la fonction :

Version Terminale :

let facteur_premier x =
  let rec fp x y acc =
    if est_premier x then (acc@[x])
    else if (x mod y = 0) then fp (x / y) y (acc@[y])
    else fp x (y+1) acc
in fp x 2 []
;;

facteur_premier 45 ;;
- : int list = [3; 3; 5] (* 3 * 3 * 5 = 45 On retombe sur nos pattes :-) *)

Nombre Parfait

On va vérifier qu'un entier x est parfait ou non: Définition Wikipédia

Principe :
- Comme pour la fonction qui calcule le nombre de diviseurs d'un entier, on introduit une variable y qui permettra de reconnaître le(s) diviseur(s) de x et acc qui, cette fois-ci accumulera la **somme** de tous les diviseurs de x .
- La différence de cette fonction avec celle qui détermine le nombre de diviseur d'un entier est qu'au lieu d'incrémenter acc de 1 on l'incrémente de valeur de y .

Version Terminale :

let est_parfait x = (* x est la valeur que l'on veut vérifier. *)
  let rec parfait x y acc = (* y représente les diviseurs potentiels de x. *)
    if y = x then acc (* acc accumule la somme des diviseurs, donc de y. *)
    else if (x mod y = 0) then parfait x (y+1) (acc+y)
    else parfait x (y+1) acc
in parfait x 1 0 = x;;

print_string (string_of_bool (est_parfait 6) );;
true

Astuce :

La fonction renvoie bien acc dans le cas de sortie, mais en tapant la dernière ligne de la fonction ça permet de renvoyer un booléen.
Si parfait x 1 0 est égal à x alors True sinon False .

Conversion Base b -> Base 10

Version Terminale :

let de_b_en_10 x b = (* x est la valeur a convertir; b est la base d'origine de x *)
  let rec aux x b acc i =
    if x = 0 then acc
    else if (x mod 10 >= b) then failwith "Erreur: L'entier a convertir n'est pas de la base indique !"
    else aux (x / 10) b (acc + ((pow b i) * (x mod 10))) (i+1)
in aux x b 0 0;;

La fonction convertie depuis toutes les bases (même supérieur à 16), tant que l'entier à convertir ne contient aucun chiffre supérieur à 9 (A, B, C, D, E, F, G, ....) !

Attention :

Comme dit ci-dessus, il n'y a pas d'interprétation des lettres, A, B, C, D, E, F,...
Pour cela il faudrait optimiser ce programme en ajoutant justement les valeurs respéctives à chacun de ces lettres.

Vous pouvez vous amusez à créer cette fonction plus hardue pour vous entrainer.
Je dis ça, je dis rien =p

Conversion Base 10 -> Base b

Version Terminale :

let de_10_en_b x b = (* x est la valeur a convertir, b est la base d'arrive *)
  let rec aux x b acc i =
  if x < b then (x * (pow 10 i)) + acc
  else aux (x/b) b (acc + ((pow 10 i) * (x mod b)) ) (i+1);
in aux x b 0 0;;

La fonction convertie depuis toutes les bases (même supérieur à 16), tant que l'entier à convertir ne contient aucun chiffre supérieur à 9 (A, B, C, D, E, F, G, ….) !

Attention :

Comme dit ci-dessus, il n'y a pas d'interprétation des lettres, A, B, C, D, E, F,...
Pour cela il faudrait optimiser ce programme en ajoutant justement les valeurs respéctives à chacun de ces lettres.

Vous pouvez vous amusez à créer cette fonction plus hardue pour vous entrainer.
Je dis ça, je dis rien =p

Conversion Base b -> Base b'

print_string "Saisissez base d'origine: ";;
let b = read_int();;

print_string "Saisissez base d'arrive: ";;
let b2 = read_int();;

print_string "Saisissez la valeur a convertir: ";;
let x = read_int();;

print_string ((string_of_int x) ^ " (base " ^ (string_of_int b) ^ ") = " ^ (string_of_int ( de_10_en_b ( de_b_en_10 x b ) b2 ) ) ^ " (base " ^ (string_of_int b2) ^ ")\n");;

Résultat :

Saisissez base d'origine: 2
Saisissez base d'arrive: 8
Saisissez la valeur a convertir: 1001
1001 (base 2) = 11 (base 8)

Listes

Quelques fonctions sur les listes, certaines existent déjà mais on les refait nous même pour mieux comprendre la récursivité.

Longueur d'une liste

Le cas de sortie évidant est la liste vide qui a longueur de 0.
Les cas où la liste n'est pas vide, on incrémente de 1 et on rappelle la fonction avec la queue de la liste. Une fois que cette queue est vide, on se trouve dans le cas de sortie.
J'ai choisi ici de faire la version classique avec un //match with// et la version terminale avec //if then else// mais au final les deux versions sont quasi identiques (un cas de sortie et tous les autres cas). Dans la version classique, j'identifie la tête de la liste avec head et la queue avec tail (un peu d'anglais ne fait pas de mal) mais vous êtes libre de les appeler comme vous le voulez.

Version Classique :

let rec longueur_liste liste = match liste with
  | [] -> 0
  | head::tail -> 1 + longueur_liste tail;; (* On incrémente de 1 et on rappelle la fonction avec la queue 'tail' *)

Version Terminale :

let longueur_liste liste =
  let rec longueur liste acc =
    if liste = [] then acc
    else longueur (List.tl liste) (acc+1) (* On rappelle la fonction avec la queue (List.tl liste) et on incrémente acc *)
in longueur liste 0;;

Somme des Entiers d'une Liste

Même chose que la fonction précédente :
- Le cas de sortie est le même et on repère toujours les autres cas par un liste non vide.
- Au lieu d'incrémenter de 1 on va incrémenter de la tête de la liste (List.hd dans la version classique et head dans la terminale).

Version Classique :

let rec somme_liste l =
  if l = [] then 0
    else (List.hd l) + somme_liste (Liste.tl l);;

Version Terminale :

let somme l =
  let rec sum l acc = match l with
    |[] -> acc
    |head::tail -> sum tail (acc+head)
in sum l 0;;

Cette fonction ne doit être appelé qu'avec une liste d'entier(s), c'est imposé par le '+' .
Si vous voulez faire la même fonction mais qui fonctionne avec des float, il vous suffit de changer ce '+' en '+.' !

Miroir Liste

Je décide de me simplifier la vie,' e ' représente la tête de ma liste et ' f ' sa queue.
A chaque récursion, on a qu'à concaténer la tête à la fin de la liste en utilisant l'opérateur **@**. Ne pas oublier les crochets autour de e .

Là encore, le cas de sortie se repère par la liste vide.

Version Classique :

let rec mirroir l = match l with
  |[] -> []
  |e::f -> (mirroir f)@[e];;

Version Terminale :

let mirroir l =
  let rec mir l acc = match l with
    |[] -> acc
    |e::f -> mir f acc@[e]
in mir l [];;

Cette fonction a l'avantage de pouvoir s'appliquer à tous les types de listes ( int , float , char , string , ...).

Maximum de Liste d'Entier

Une liste vide n'a pas de maximum parce qu'il n'y a aucun élément, c'est pourquoi j'utilise la fonction failwith pour gérer le cas d'une liste vide.

Principe :
- S'il n'y a qu'un élément dans notre liste, le maximum est justement cet élément.
- Sinon on prend le max entre la tête et le max de la queue. Pour déterminer le max de la queue il faut parcourir toute la queue jusqu'à ce qu'il n'y ait plus qu'un élément dedans.

Version Classique :

let max x y = if x < y then y else x;;

let rec liste_max l = match l with
  |[x] -> x
  |t::q -> max t (liste_max q)
  |[] -> failwith "Liste vide!";;

Version Terminale :

let maxli l =
  if l = [] then failwith "Empty List !"
  else let rec aux l acc = match l with
    |[e] -> max e acc
    |e::f -> aux f (max e acc)
    |[] -> failwith "Empty List !"
in aux (List.tl l) (List.hd l);;

Appartenance d'un Élément dans une Liste (non triée)

Principe :
- Si la liste est vide, l'élément recherché est absent donc on peut renvoyer False .
- Sinon on compare la tête e avec x , s'ils sont égaux on peut renvoyer True sinon on rappelle la fonction avec la queue de la liste f .

Version Classique :

let rec appartient x l = match l with
  |[] -> false
  |e::f -> if e = x then true else est_element x f;;

print_string ("2 appartient a [1;2;3;4;5;6;789] : " ^ string_of_bool (appartient 2 [1;2;3;4;5;6;789]) ^ "\n\n") ;;

Version Terminale :

let appartient x l =
  let rec recher x l acc = match l with
    |[] -> acc
    |e::f -> if e = x then true else recher x f (false || acc)
in recher x l false
;;

Ici nous avons deux cas de sortie :

- Lorsque la liste est vide.
- Lorsque que x = e .

Appartenance d'un Élément dans une Liste (triée dans l'ordre croissant)

Maintenant que notre liste est triée dans l'ordre croissant on peut améliorer la fonction appartient (notre première version fonctionne très bien, mais pour le cas particulier d'une liste triée on peut rendre notre fonction plus performante).

La première version parcourt la liste jusqu'à ce qu'on tombe sur la valeur recherchée.
Alors que la deuxième version parcourt la liste jusqu'à ce que les valeurs de la liste soient plus grandes que la valeur recherchée OU qu'on ait trouvé la valeur.

Principe :
- C'est le même cas de sortie que la première version.
- On ne va pas que vérifier si ' x ' est égal à la tête ' e ' de la liste, on va aussi regarder si ' e ' est supérieur à ' x ' , si c'est le cas on peut tout de suite sortir de la fonction en renvoyant False . Sinon on continue de parcourir la liste.

Version Classique :

let rec appartient x l = match l with
  |[] -> false
  |e::f -> if e > x then false
    else if e = x then true
    else appartient x f ;;

Version Terminale :

let appartient x l =
  let rec recher x l acc = match l with
    |[] -> acc
    |e::f -> if e > x then false
      else if e = x then true
      else recher x f (acc || false)
in recher x l false
;;

Ces deux versions fonctionnent avec des listes de type: int , float , char et string .

Enlever le Premier Élément x d'une Liste

eneleve_element 2 [1;2;3;2;4;2] ;; - : int list [1;3;2;4;2] (* seul le premier 2 a ete eneleve ! *)

Comme on cherche à n'enlever que le premier élément x on a des chances de ne pas parcourir la liste entièrement.

Principe :
- Si la liste est vide, on renvoie la même chose !
- Si la tête e est égal à x alors on peut renvoyer la queue f .
Sinon on rappelle la fonction sur la queue f en conservant e en tête de liste.

Version Classique :

let rec enleve_element x l = match l with
  |[] -> []
  |e::f -> if e = x then f
    else e::(enleve_element x f)
;;

Version Terminale :

let enleve_element x l =
  let rec aux x l acc = match l with
    |[] -> acc
    |e::f -> if e = x then (acc@f) else aux x f (acc@[e])
in aux x l []
;;

Enlever Tous les Éléments x d'une Liste

On cherche à enlever tous les éléments x d'une liste.

eneleve_element 2 [1;2;3;2;4;2] ;;
- : int list [1;3;4] (* Tous les 2 ont ete enleve ! *)

Principe :

- Si la liste est vide donc il suffit encore de renvoyer la même chose !
- Si la tête e est égal à x on rappelle la fonction avec la queue f et on peut oublier la tête e.
Sinon on rappelle la fonction avec la queue f ET en conservant la tête e .

Version Classique :

let rec enleve_tous_elements x l = match l with
  |[] -> []
  |e::f ->
    if e = x then enleve_tous_elements x f
    else e::(enleve_element x f)
;;

Version Terminale :

let enleve_tous_elements x l =
  let rec aux x l acc = match l with
    |[] -> acc
    |e::f -> if e = x then aux x f acc else aux x f (acc@[e])
in aux x l []
;;

Accès à un élément dans une Liste

Principe :

- La fonction prend en paramètre la liste l et l'indice i .
- i doit être compris entre 1 et la longueur de la liste (nous allons devoir gérer ces deux cas d'erreur).
- Si i = 1 alors on renvoie la tête de la liste, sinon on rappelle la fonction avec la queue de la liste et i qui décrémente.

Version Terminale :

let acces l i =
  if (i <= 0) || (i > List.length l) then failwith "En dehors de la liste !"
  else let rec aux l i =
    if i = 1 then List.hd l
    else aux (List.tl l) (i-1)
in aux l i
;;

Récurrence d'un élément dans une Liste

On va calculer le nombre de fois qu'apparaît un élément x dans une liste.

Principe :
- On va devoir parcourir toute la liste envoyée en paramètre pour être sûr de n'oublier aucune récurrence de x .
- Une liste vide contient évidemment 0 fois l'élément x .
- Si la tête e vaut x alors on rappelle la fonction avec la queue f et en incrémentant, sinon on ne fait que rappeler la fonction avec la queue f .

Version Classique :

let rec nb_element x l = match l with
  |[] -> 0
  |e::f -> if e = x then 1 + nb_element x f else nb_element x f;;

Version Terminale :

let recurrence x l =
  let rec recur x l acc =
    if l = [] then acc
    else if List.hd l = x then recur x (List.tl l) (acc+1)
    else recur x (List.tl l) acc
in recur x l 0;;

print_int (recurrence 2 [1;2;2;2;2;2;2;3]);;
6

List4all

On va appliquer la fonction g à tous les éléments de la liste l.

Principe :
- Si la liste est vide, on renvoie la liste vide...
- Sinon on applique la fonction g à la tête e , on conserve le résultat et on passe à la queue de la liste f .

Version Classique :

let rec list4all g l = match l with
  |[] -> []
  |e::f -> (g e)::(list4all g f)
;;

Version Terminale :

let list4all a l =
  let rec forall a l acc = match l with
    |[] -> acc
    |e::f -> forall a f (acc@[a e])
in forall a l []
;;

Somme de deux listes

(*permet d'ajouter des zeros dans une liste jusqu'à atteindre la taille voulue*)
let rec ajoutezero (liste,taille) =
  if ((List.length liste) = taille) then liste
  else ajoutezero ((0::liste),taille);;

(*permet d'afficher une liste *)
let show_int_list t = List.iter (fun v -> Printf.printf "%d" v) t;;

(*ajoute des zéros dans la liste la plus petite des deux*)
let f (l1,l2) =
  if (List.length l1 > List.length l2) then
    let l2 = ajoutezero (l2, List.length l1) in (l1,l2)
  else if (List.length l1 < List.length l2) then
    let l1 = ajoutezero ( l1, List.length l2) in (l1,l2)
  else (l1,l2);;

(*calcule la somme de la liste*)

(* sinon somme tête des listes et rappel de la fonction avec comme argument la queue des listes*)
let rec sommeliste (l1,l2) =
  if ((l1 = []) && (l2 = [])) then [](*condition d'arrêt*)
  else (List.hd l1+List.hd l2)::sommeliste(List.tl l1,List.tl l2);;(*voir dessin*)

(*definition des listes et appel des fonctions*)
let liste1 = [1;2;3;4];;
let liste2 = [1;2];;
show_int_list (sommeliste(f(liste2,liste1)));;

Minimum d'une Liste D'Entiers

Version Classique :

let min x y = if x < y then x else y;;

let rec liste_min l = match l with
  |[x] -> x
  |t::q -> min t (liste_min q)
  |[] -> failwith "Liste vide!";;

Version Terminale :

let minli l =
  if l = [] then failwith "Empty List !"
  else let rec aux l acc = match l with
    |[e] -> min e acc
    |e::f -> aux f (min e acc)
in aux l (List.hd l);;

Tri de Liste par Minimum Successif

On va trier une liste en cherchant à chaque récursion le minimum de la liste.

Principe :
- On sait chercher le minimum d'une liste d' int , de float , de char ou de string .
- On prend le premier minimum de la liste, on le concatène en tête de liste et on rappelle la fonction sans oublier de retirer ce premier minimum de la liste de départ.
- Pour retirer le minimum de la liste on a qu'à utiliser la fonction que nous avons créer plus haut (enleve_element).

Version Classique:

let min x y = if x < y then x else y;;

let rec min_liste l = match l with
  |[x] -> x
  |e::f -> min e (min_liste f)
  |[] -> failwith "Liste vide !";;

let rec tri_croissant l = match l with
  |[] -> []
  |_ -> (min_liste l)::(tri_croissant (enleve_element (min_liste l) l) );;

tri_croissant [-12; -999; 12; 0; 67]
[-999; -12; 0; 12; 67]

tri_croissant [-12.; -999.; 12.; 0.; 67.]
[-999.; -12.; 0.; 12.; 67.]

tri_croissant ['z'; 'y'; 'x'; 'w'] (* On pourra faire un dictionnaire avec ça :-) ! *)
['w'; 'x'; 'y'; 'z']

mirroir (tri_croissant [-12; -999; 12; 0; 67]) (* tri_decroissant ! *)
[67; 12; 0; -12; -999]

Version Terminale :

let min x y = if x < y then x else y;;

let min_liste l =
  let rec minli l acc = match l with
    |e::[] -> min e acc
    |e::f::g -> minli (f::g) (min e acc)
    |[] -> failwith "Liste vide !"
in minli l (List.hd l);;

let tri_croissant l =
  let rec tri l acc =
    if l = [] then acc
    else tri (enleve_element (min_liste l) l) (acc@[min_liste l])
in tri l [];;

print_list (tri_croissant [3;2;1]);;
1 2 3

print_int (min_liste [1;-1;99;-10] );;
-10

Tri à bulle

1^ère Version Classique :

(* fonction permettant échange d'éléments si 2e + petit que le 1er *)

let rec tri l = match l with
  |[] -> [] (* condition arrêt *)
  |[a] -> l (* si 1 seul element présent, renvoi liste *)
  |h1::h2::t -> if h1 > h2 then h2::(tri (h1::t)) else h1::(tri (h2::t));;

(* fonction permettant de lancer le tri à bulles plusieurs fois pr limiter erreurs *)

let triabulle l =
  let rec trifinal l nb = match nb with
  |0 -> l
  |_-> trifinal (tri l) (nb-1) in trifinal l (List.length l);;

2^ème Version Classique: la fonction utilise un booléen pour effectuer le nombre de tri minimum :

let rec triabul l =
  let rec verif l = match l with
    |[] -> true (* Si on arrive à un seul élément ou à la liste vide, c'est que la liste est triée dans l'ordre croissant *)
    |[a] -> true
    |h1::h2::t -> if h1 > h2 then false else verif ( h2::t)
     in match (verif l) with
    |true -> l
    |false -> triabul (tri l);;

Version Terminale :

let tri liste =
  let rec temp acc liste = match liste with
    |[]-> []
    |head::[] -> List.rev (head::acc)
    |head::head1::tail ->       if head > head1 then temp (head::acc) (head1::tail)
      else temp (head1::acc) (head::tail) in temp [] liste;;

let verif liste =
  let rec temp acc liste = match liste with
    |[] -> acc
    |_::[] -> acc
    |head::head1::tail ->
      if head < head1 then (false && acc)
      else temp (true && acc) (head1::tail) in temp true liste;;

let tri_a_bulle liste =
  let rec temp acc liste =
    if (acc = 0) && (tri liste) then liste
    else temp (acc-1) (test liste) in temp ((List.length liste)-1) liste;;

Eléments Communs de Deux Listes

Version Classique :

let rec enCom l1 l2 = match l1 with
  |[] -> []
  |e::f -> if appartient e l2 then partiel2 (e::(enCom f l2))
    else partiel2 (enCom f l2) ;;

Version Terminale :

let enCommuns l1 l2 =
  let rec aux l1 l2 acc = match l1 with
    |[] -> partiel2 acc
    |e::f -> if appartient e l2 then aux f l2 (acc@[e])
      else aux f l2 acc
in aux l1 l2 []
;;

Liste de Listes

Version Terminale :

let list_list l =
  let rec aux l acc acc2 = match l with
    |[] -> acc2@[acc]
    |e::f -> aux f (acc@[e]) (acc2@[acc])
in aux l [] []
;;

Mix de Deux Listes

On va créer une fonction qui prend en paramètre deux listes de couples int * string et qui va renvoyer un liste de triplets, chaque triplet sera de la forme int * string * string :

let l1 = [(1, "un"); (2, "deux"); (3, "trois")];; (* Nos deux listes doivent être de cette forme *)
let l2 = [(1, "one"); (2, "two"); (3, "three")];; (* Les deux listes sont de la même tailles *)

On devra obtenir :

- : (int * string * string) list = [(1, "un", "one"); (2, "deux", "two"); (3, "trois", "three")]

Principe :
- Nos deux listes ont la même taille, donc le cas de sortie se repère lorsque les deux liste sont vides en même temps.
- Sinon on fait un "mix" entre le premier duplet de chacune des deux listes pour créer un triplet.

Version Classique :

let rec partiel l1 l2 = match (l1,l2) with
  |([],[]) -> []
  |( (a,b)::c, (d,e)::f ) -> (a,b,e)::(partiel c f);;

Version Terminale :

let partiel l1 l2 =
  let rec aux l1 l2 acc = match (l1,l2) with
    |([],[]) -> acc
    |( (a,b)::c, (d,e)::f ) -> aux c f (acc@[(a,b,e)])
in aux l1 l2 [];;

Supprime Doublons de Liste

La liste renvoyer par cette fonction ne contient plus aucun doublon, chaque élément n'apparaît une et une seule fois dans cette liste.

Principe :
- Bien sur une liste vide n'a pas de doublon, dans ce cas on pourra renvoyer la liste vide.
- On aura besoin de la fonction //appartient//, afin de déterminer si la tête e est aussi présente dans la queue f .

(* Ma fonction "appartient" vérifie l'appartenance d'un élément dans une liste *)
let appartient x l =
  let rec aux x l acc = match l with
    |[] -> acc
    |e::f -> if e = x then aux x f (true || acc) else aux x f acc in aux x l false;;

Version Classique :

let rec doublon l = match l with
  |[] -> []
  |e::f -> if appartient e f then doublon f else e::(doublon f);;

Version Terminale :

let doublon l =
  let rec aux l acc = match l with
    |[] -> acc
    |e::f ->
      if appartient e f then aux f acc
      else aux f (acc@[e])
    in aux l [];;

Divers

Quelques exercices divers, assurez vous de maîtriser le reste avant de passer à ces exercices.

Types Quelconques

Partie A :

fonction1;; (* Calcule la somme de 0 à x *)
val fonction1 : int -> int =

fonction2;;
val fonction2 : ('a -> 'b -> bool) -> ('c -> 'd -> bool) -> 'a -> 'b -> 'c -> 'd -> bool =

fonction3;;
val fonction3 : int -> int -> int -> bool =

fonction4;;
val fonction4 : int * in

t -> int =

Partie B :

fonction5 : 1 seul argument, un triplet (float,int,bool) et renvoie un string .
fonction6 : 4 arguments, trois bool et une fonction qui prend en argument un duplet de bool et renvoie un bool , fonction6 renvoie un bool .
fonction7 : 1 seul argument qui est une fonction qui prend en argument un float et renvoie un int , fonction7 retourne un char .
fonction8 : 1 argument, un quadruplet (int, float, int, char) , et retourne une iste d'entier int list .

Un peu de logique ?

type expbool = |Cte of bool
  |And of ( expbool * expbool)
  |Or of ( expbool * expbool)
  |Not of expbool
  ;;

let rec eval x = match x with |Or (a,b) -> eval a || eval b
  |And (a,b) -> eval a && eval b
  |Not a -> not (eval a)
  |Cte a -> a
  ;;

Un Tout Petit Jeu

type t_race = |Humain |Gnome |Alien |Robot;;
type t_classe = |Etudiant |Mage |Potier |PorteurDeau;;
type t_perso = {nom : string; niveau : int; race: t_race; classe : t_classe};;

let kuk = {nom = "KuK"; niveau = 0; race = Robot; classe = PorteurDeau};;

(* fonction quete *)
let rec quete a x =
  if x = 0 then print_string "\n\nBienvenue dans la quete d'un tout petit jeu ! \n\nVous entrez dans la foret de ShareWood,\nafin de retrouver l'epe sacree qui vous a ete derobee.\nIl est tres facil de se perdre dans cette foret.\nChaque coisement vous oblige a choisir entre 2 nouveaux chemins au hasard.\n\nArriverez-vous a trouvez le bon chemin ? \n\n\n";

  if x = 5 then a.niveau <- a.niveau + 5;

  begin
  print_string "Vous arrivez à un croisement :\nVous avez le choix entre le chemin 1 et le chemin 2 (tapez 1 ou 2): ";


  let choix = read_line() and secret = string_of_int ( (Random.int 2)+1 ) in
    if choix = secret then
      begin
      a.niveau <- a.niveau + 1;
      print_string "\n\n\nBravo !\nVous avez choisie le bon chemin !\n\n\nPRESS ENTER TO CONTINUE . . .\n\n\n";
      let attente = read_line() in quete a (x+1);
      end
    else
      begin
      print_string "\n\n\nDommage vous n'avez pas choisie le bon chemin . . .\n\n\n";
      end;
    end
;;

Souvenir, souvenir,...

A une époque on avait optimiser le jeu en lui ajoutant :
  - un système de création de personnage par l'utilsateur
  - un système d'Arène entre perso ainsi créer
  (Certaines Races avait l'avantage sur d'autre, et de même pour les Classes.)

Mais ça remonte à loin déjà ^_^

A vous de jouer maintenant : )

Compte Chaque Lettre

D'abord on va créer une fonction qui nous permettra de transformer une chaîne de caractères en une liste de caractère :

(* A partir d'une chaîne de caractères, renvoie une liste de caractères *) let list_of_string s =
  let rec aux s i acc =
    if i = String.length s then acc
    else aux s (i+1) (acc@[s.[i]])
in aux s 0 []
;;

On va réutiliser les fonctions tri_croissant et récurrence (que nous avons créer plus haut) dans la fonction compte_lettre.
Cette nouvelle fonction prendra en paramètre une chaîne de caractère et renverra une liste de couple(s) char * int (un caractère avec le nombre de fois qu'apparaît ce caractère dans la chaîne):

let compte_lettre s =
  let rec aux l acc1 acc2 = match l with
    |[] -> (tri_croissant acc1)
    |e::f -> if appartient e acc2 then aux f acc1 acc2
      else aux f (acc1@[(e, recurrence e l)]) (acc2@[e])
      in aux (list_of_string s) [] []
;;

Maintenant, nous avons besoin d'une fonction qui une liste de couple char * int et qui affiche (de manière lisible le résultat final) :

let rec affiche l = match l with
  |[] -> ()
  |(a,b)::f -> begin
  print_string ("Le caractère '" ^ String.make 1 a ^ "' apparait " ^ string_of_int b ^ " fois.\n");
  affiche f;
end;;

Et pour finir, une toute petite fonction pour que ce soit plus simple à l'appel :

let compte_chaque_lettre s = affiche (compte_lettre s) ;;
let saisie () =
  print_string "Saisissez une chaine de caractere: " ;
  let chaine = read_line () in begin print_string "\n"; compte_chaque_lettre chaine;
end ;
  print_string "\n"
;;

saisie () ;; (* on oublie pas d'appeler la fonction avec () *)

Exemple :

Saisissez une chaine de caractere: abracadabra

Le caractère 'a' apparait 5 fois.
Le caractère 'b' apparait 2 fois.
Le caractère 'c' apparait 1 fois.
Le caractère 'd' apparait 1 fois.
Le caractère 'r' apparait 2 fois.


Et voilà on a terminé !

Estimation de Pi 'Π'

Nous allons apprendre à faire une estimation du nombre Π en utilisant les nombres aléatoires.
On commence par créer une fonction qui génère un float entre un Min et un Max :

Random.self_init();; (* Initialisation du générateur *)

let nbAleat min max = (* renvoie un float entre min et max *)
  min +. Random.float (max -. min);;

Maintenant on va imaginer un carré de coté 1 unité (peu importe l'unité dans tout l'exercice) dont le coin bas gauche est l'origine d'un repère orthonormé. Dans ce carré, il y a un cercle inscrit, son centre est en (0,5 ; 0,5).
On va placer un nombre x de points aléatoirement dans le carré, comme le cercle est inscrit certains points ne seront que dans le carré d'autres seront dans le cercle. Là où ça devient intéressant, c'est que le nombre de point dans le cercle divisé par le nombre total de point donne un estimation d'un quart de Π.
Fonction qui calcule la distance d'un point aléatoire au centre du cercle :

let distance xB yB =
  sqrt ( ( (xB -. 0.5) *. (xB -. 0.5) ) +. ( (yB -. 0.5) *. (yB -. 0.5) ) );;

Si cette fonction renvoie une valeur inférieur à 0,5 c'est que ce point est dans le cercle.

Calcul du nombre de points dans le cercle :

let point x =
  let rec aux x acc =
    if x = 0 then acc
    else if ( distance (nbAleat 0. 1.) (nbAleat 0. 1.) ) < 0.5 then aux (x-1) (acc+.1.)
    else aux (x-1) (acc1+.1.) acc2
in aux x 0. 0.
;;

Cette fonction renvoie le nombre de point inclut dans le cercle.

Estimation :

let pi x =
  4. *. ((point x) /. (float_of_int x));;

Et voilà, ça suffit 8-) ! On a plus qu'à appelé pi avec le nombre de point que l'on veut. Plus le nombre de point est important, plus la précision de Π sera correcte. Malheureusement, c'est aussi beaucoup plus long...

let constante_pi = 3.14159265 ;; (* Pour faire un comparaison *)
val constante_pi : float = 3.14159265

pi 10 ;;
- : float = 2.8 (* Vraiment trop peu de point *)

pi 100 ;;
- : float = 3.28

pi 1000 ;;
- : float = 3.136

pi 10000 ;;
- : float = 3.1528

pi 100000 ;;
- : float = 3.14784 (* Ça devient intéressant :-). On a un précision au centième près *)

pi 1000000 ;;
- : float = 3.140288

pi 10000000 ;;
- : float = 3.1403632

pi 100000000 ;;
- : float = 3.14156916

Résultat convenable lorsque l'on trace 10⁸ points, ça met pas mal de temps (surtout si votre machine est lente :-) ). Si vous appelez plusieurs fois la fonction avec le même nombre de points vous tomberez sur un autre résultat différent plus ou moins proche de Π. C'est dû au fait que c'est basé sur de l'aléatoire.

Seulement pour les personnes qui se débrouillent, suivez le lien : Annexes.