DS 3 — Partie pratique (OCaml)¶
MP2I, année 2021-2022. Devoir surveillé 3 du 16 décembre 2021, partie pratique sur machine (exercices Learn OCaml « DS3 - Récursif » et « DS3 - Impératif »). La partie écrite est sur une page séparée.
Récursif¶
Attention dans toute cette partie, vous n'avez pas le droit d'utiliser de
références ni d'utiliser les modules List ou Array.
Les fonctions avec 
en indication vous garantissent, si vous les faites toutes, une note de 15.
Question 1.
Écrire une fonction fact calculant la factorielle de l'entier naturel passé
en argument.
Corrigé
Pas de difficulté pour fact mis-à-part le fait de se rappeler de la
définition...
let rec fact n =
if n = 0 then 1 else n * fact (n-1)
Question 2.
Écrire une fonction somme_liste qui renvoie la somme des éléments de la
liste d'entiers passée en paramètre.
Corrigé
Toutes les questions qui portent sur un parcours d'une liste vont être récursives et de la forme :
let rec parcours l = match l with
| [ ] -> (* Cas de la liste vide *)
| t::q -> (* On traite le cas où la liste commence par t
et on va appeler parcours q *)
let rec somme_liste l =
match l with
| [] -> 0
| t::q -> t + somme_liste q
Question 3.
Écrire une fonction renverse qui renvoie la liste passée en argument dans
l'ordre inverse. Attention vous ne pourrez pas la programmer directement
en récursif, il faut passer par une fonction auxiliaire qui prend un
accumulateur.
Attention vous aurez la moitié des points si votre fonction est en \(O(n^2)\).
Corrigé
Ici, on tire parti du fait que le parcours d'une liste va naturellement voir les éléments de gauche à droite : le premier élément vu est la tête de la liste, ce sera le dernier élément de la liste renversée, donc si on la construit progressivement, c'est le premier élément qui sera mis devant la liste vide. Pour cela, on utilise donc une fonction auxiliaire qui va avoir un accumulateur et qui va rajouter chaque tête à l'accumulateur.
Si on le faisait avec des références ça correspondrait à ça :
let renverse l =
let acc = ref [] in
let lr = ref l in
while !lr <> [] do
let t::q = !lr in (* warning car possible [] meme si exclu *)
acc := t :: !acc;
lr := q
done;
!acc
Le code récursif est équivalent mais bien plus clair et élégant.
let renverse l =
let rec aux l acc = match l with
| [] -> acc
| t::q -> aux q (t::acc)
in aux l []
Question 4.
Ici et dans les deux questions qui suivent, on va considérer des listes du
type ('a * 'b) list qui permettent de stocker des associations entre des
éléments du type 'a et des éléments du type 'b. C'est une manière de
réaliser un dictionnaire. Ainsi, la liste [ ("a", 42); ("toto", 12) ] va
associer la valeur 42 à la clé "a" et la valeur 12 à la clé "toto". On
appelle cette structure de donnée une liste d'associations.
Écrire une fonction ajoute_assoc : ('a * 'b) list -> 'a -> 'b -> ('a * 'b) list
qui prend une liste d'associations en entrée et a et b et rajoute une
association entre a et b.
Attention cette fonction est très simple.
Corrigé
Question très simple mais qui demande de bien comprendre l'énoncé !
let ajoute_assoc l a b =
(a,b) :: l
Question 5.
Écrire une fonction cherche_assoc : ('a * 'b) list -> 'a -> 'b qui prend
une liste d'associations et une valeur a en entrée et renvoie la valeur b qui
lui est associée ou produit une erreur avec l'instruction
failwith "invalide".
Corrigé
On effectue une simple recherche dans la liste mais en tirant parti du fait que les éléments sont des couples. À noter ici le fait de faire un seul filtrage en filtrant aussi la forme de la tête.
let rec cherche_assoc l a =
match l with
| [] -> failwith "invalide"
| (a',b)::q -> if a = a' then b else cherche_assoc q a
Question 6.
Écrire une fonction cherche_assoc_opt : ('a * 'b) list -> 'a -> 'b option
qui se comporte comme la fonction précédente hormis qu'elle utilise le type
option pour renvoyer None en cas d'échec plutôt que de produire une erreur.
Corrigé
Comme précédemment mais avec des options.
let rec cherche_assoc_opt l a =
match l with
| [] -> None
| (a',b)::q -> if a = a' then Some b else cherche_assoc_opt q a
Question 7.
Écrire une fonction zip : 'a list -> 'b list -> ('a * 'b) list qui prend
deux listes de même longueur et renvoie la liste des couples d'un élément
de la première liste associé avec l'élément correspondant de la seconde.
Ainsi zip [1;2;3] ['a';'b';'c'] doit renvoyer
[ (1,'a'); (2,'b'); (3,'c') ].
Corrigé
Encore une question assez simple mais qui déroute par l'énoncé. Prenez l'habitude de vous appuyer sur les exemples.
let rec zip l1 l2 =
match l1, l2 with
| t1::q1, t2::q2 -> (t1, t2)::zip q1 q2
| _ -> []
Question 8.
Écrire une fonction range : int -> int -> int list telle que l'appel à
range a b renvoie la liste d'entiers [ a;a+1;...;b ].
Corrigé
Ici, on calcule \(\range{a}{b}\) en remarquant que
\(\range{a}{b} = \emptyset\) = [ ] quand \(a > b\) et sinon,
\(\range{a}{b} = a\) :: \(\range{a+1}{b}\).
let rec range a b =
if a > b
then []
else a :: range (a+1) b
Question 9. (Difficile)
Écrire une fonction gen_tuples : 'a list -> int -> 'a list list qui prend
en entrée une liste [a1;...;an] et un entier p et renvoie tous les p-uplets
de la liste sous forme de liste et dans l'ordre lexicographique correspondant
à l'ordre de la liste. Ainsi pour ['a';'c';'b'] et 2 on va renvoyer
[ ['a';'a']; ['a';'c']; ['a';'b']; ['c';'a']; ['c';'c'];
['c';'b']; ['b';'a']; ['b';'c']; ['b';'b'] ]
Corrigé
let rec gen_tuples l n =
if n = 0
then [ [] ]
else
let tt = gen_tuples l (n-1) in
let rec ajoute t l = match l with
| [] -> []
| ll::q -> (t::ll) :: ajoute t q
in
let rec aux l' =
match l' with
| [] -> []
| t::q -> (ajoute t tt) @ aux q
in aux l
Question 10. (Difficile)
Écrire une fonction gen_plists : 'a list -> int -> 'a list list qui prend
en entrée une liste [a1;...;an] et un entier p et renvoie toutes les
p-listes de la liste sous forme de liste et dans l'ordre lexicographique
correspondant à l'ordre de la liste.
La différence entre une p-liste et un p-uplet est qu'on ne peut avoir qu'une
seule fois chacun des ai dans une p-liste. Attention, on distingue ici les
positions dans la liste d'une même valeur. Pour [1;2;1] on a une 2-liste
[1;1] mais [2;2] n'en est pas une.
Ainsi pour ['a';'c';'b'] et 2 on va renvoyer
[ ['a';'c']; ['a';'b']; ['c';'a']; ['c';'b']; ['b';'a']; ['b';'c'] ]
Corrigé
let rec gen_plists l n =
if n = 0
then [ [] ]
else
let rec retire t l =
match l with
| [] -> []
| x::q -> if x = t then q else x :: retire t q
in
let rec ajoute t l = match l with
| [] -> []
| ll::q -> (t::ll) :: ajoute t q
in
let rec aux l' =
match l' with
| [] -> []
| t::q -> (ajoute t (gen_plists (retire t l) (n-1))) @ aux q
in aux l
Impératif¶
Attention dans toute cette partie, vous n'avez pas le droit d'utiliser de
fonctions du module Array autres que length, make, make_matrix,
init.
Les fonctions avec
en indication vous garantissent, si vous les faites toutes, une note de 15.
Question 1.
Écrire une fonction somme qui prend en entrée un tableau d'entiers et
renvoie la somme de ses éléments.
Corrigé
let somme a =
let s = ref 0 in
for i = 0 to Array.length a - 1 do
s := a.(i) + !s
done;
!s
Question 2.
Écrire une fonction compte qui prend en entrée un tableau d'éléments de type
'a et une valeur x de type 'a et renvoie le nombre de fois que cette
valeur est présente dans le tableau.
Corrigé
let compte a x =
let c = ref 0 in
for i = 0 to Array.length a - 1 do
if a.(i) = x
then incr c
done;
!c
Question 3.
Écrire une fonction indice_minimum qui prend en entrée un tableau d'éléments
de type 'a et renvoie le plus petit indice du minimum du tableau.
Cette fonction ne sera jamais appelée sur un tableau vide.
Corrigé
let indice_minimum a =
let i = ref 0 in
for j = 0 to Array.length a - 1 do
if a.(j) < a.(!i)
then i := j
done;
!i
Question 4.
Écrire une fonction array_concat qui prend en entrée deux tableaux t1,
t2 et renvoie le tableau correspondant à mettre les éléments de t1 suivis
des éléments de t2.
Corrigé
Attention aux cas de base et à la valeur par défaut de Array.make.
let array_concat a1 a2 =
if a1 = [||] then a2 else
let n1 = Array.length a1 in
let n2 = Array.length a2 in
let a = Array.make (n1+n2) a1.(0) in
for i = 0 to n1-1 do
a.(i) <- a1.(i)
done;
for i = 0 to n2-1 do
a.(n1+i) <- a2.(i)
done;
a
Question 5.
Écrire une fonction compte_inversions qui prend en entrée un tableau t et
compte le nombre de paires d'indices i, j tels que i < j et
t.(i) > t.(j).
Corrigé
let compte_inversions a =
let c = ref 0 in
let n = Array.length a in
for i = 0 to n-1 do
for j = i+1 to n-1 do
if a.(i) > a.(j)
then incr c
done
done;
!c
Question 6.
Écrire une fonction cherche_motif qui étant donnés deux tableaux t et m
renvoie un booléen indiquant si m est un sous-tableau de t.
C'est la même notion que l'inclusion de motif dans une chaîne vue en TP.
Corrigé
let cherche_motif a am =
let n = Array.length a in
let m = Array.length am in
let v = ref false in
for i = 0 to n-m do
let trouve = ref true in
for k = 0 to m-1 do
trouve := !trouve && a.(i+k) = am.(k)
done;
v := !trouve || !v
done;
!v
Question 7. (Chronophage) Écrire une fonction dessine_sapin qui étant
donné un entier p > 0 dessine un sapin ainsi :
p p le motif fait 2*p+1
<------> <------>
*
* *
* *
* *<- dernier caractère
* * on ne met pas les espaces
* *
* *
* *
*****************
||| <- comme p>0 on a 2*p+1>=3 et
||| il y a toujours un tronc
Pour 5 on aura donc le sapin
*
* *
* *
* *
* *
***********
|||
|||
On utilisera les fonctions print_char : char -> unit et print_newline ().
On fera un saut de ligne après la dernière ligne.
Corrigé
let dessine_sapin p =
for i = 0 to p-1 do
for j = 1 to p-i do
print_char ' '
done;
print_char '*';
for j = 1 to 2*i-1 do
print_char ' '
done;
if i > 0 then print_char '*';
print_newline ()
done;
for i = 0 to 2*p do
print_char '*'
done;
print_newline ();
for i = 1 to 2 do
for j = 0 to p-2 do
print_char ' '
done;
for _ = 1 to 3 do print_char '|' done;
print_newline ()
done
Question 8. Écrire une fonction tri qui trie un tableau en place par la
méthode de votre choix. Cette fonction ne renvoie rien vu qu'elle modifie le
tableau passé en argument.
Corrigé
Tri par sélection :
let tri a =
let echange a i j =
let temp = a.(i) in
a.(i) <- a.(j);
a.(j) <- temp
in
for i = 0 to Array.length a - 2 do
let j = ref i in
for k = i+1 to Array.length a - 1 do
if a.(k) < a.(!j)
then j := k
done;
echange a i !j
done
Question 9. (Difficile) Écrire une fonction
carre : bool array array -> int -> int -> int telle que carre m x y
renvoie la dimension du plus grand carré de true dans la matrice carrée de
booléens m où le coin supérieur gauche du carré a pour coordonnées
(x, y).
Si on voit cette matrice comme une image en noir et blanc, il s'agit de
trouver la taille du carré noir commençant au pixel (x, y).
Cette fonction est toujours appelée avec des coordonnées pour lesquelles la
valeur est true.
Corrigé
On agrandit le carré d'une couronne (colonne \(y+r\) et ligne \(x+r\)) tant
que celle-ci ne contient que des true et ne sort pas de la matrice.
let carre m x y =
if m.(x).(y)
then begin
let r = ref 1 in
let valid = ref true in
let n = Array.length m in
while x + !r < n && y + !r < n && !valid do
for xi = x to x + !r do
valid := !valid && m.(xi).(y + !r)
done;
for yi = y to y + !r do
valid := !valid && m.(x + !r).(yi)
done;
if !valid then incr r
done;
!r
end else 0
Question 10. (Nécessite la précédente) Écrire une fonction
plus_grand_carre qui renvoie la dimension du plus grand carré dans la
matrice donnée en entrée selon la définition précédente.
Corrigé
let plus_grand_carre m =
let n = Array.length m in
let c = ref 0 in
for x = 0 to n-1 do
for y = 0 to n-1 do
let cxy = carre m x y in
if cxy > !c
then c := cxy
done
done;
!c