DS 1 — Récursivité en OCaml

MP2I, année scolaire 2022-2023. Durée totale 2h.

Tout document interdit. Tout dispositif électronique interdit (calculatrice, cafetière, R2D2...)

On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles.

Bon courage et Don't panic! 😃

Fonctions proches du TP

Attention

On utilise ici les types par défaut de OCaml. C'est particulièrement important pour les listes.

Quand on vous dit que \(n \ge 0\), c'est acquis que \(n\) ne sera jamais négatif donc ne vous en préoccupez pas dans les questions et ne faites jamais de if n < 0 then failwith....

Question 1. Écrire une fonction récursive fact : int -> int telle que fact n renvoie \(n!\) où \(n \ge 0\).

Corrigé

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

Question 2. Écrire une fonction pow2 : int -> int telle que pow2 n renvoie \(2^n\) où \(n \ge 0\) de manière naïve.

Corrigé

let rec pow2 n =
  if n = 0
  then 1
  else 2 * pow2 (n-1)

Question 3. Écrire une fonction pow2_rap : int -> int telle que pow2_rap n renvoie \(2^n\) où \(n \ge 0\) en remarquant que :

\[2^{2p} = (2^p)^2\qquad 2^{2p+1} = 2 \times 2^{2p}\]

Corrigé

let rec pow2_rap n =
  if n = 0
  then 1
  else if n mod 2 = 1
  then 2 * pow2_rap (n-1)
  else let a = pow2_rap (n/2) in a * a

Attention ici, si on écrit pow2_rap (n/2) * pow2_rap (n/2) cela va faire deux appels bêtement et la complexité sera exponentielle en \(n\).

Question 4. Écrire une fonction récursive suplog2 : int -> int telle que suplog2 n renvoie le plus petit \(d \in \N\) tel que \(0 \le n < 2^d\) avec la contrainte suivante :

1. en utilisant pow2
2. sans utiliser pow2

Corrigé

1. En utilisant pow2 :

   let rec suplog2_aux n k =
     if pow2 k > n
     then k
     else suplog2_aux n (k+1)
   
   let suplog2 n = suplog2_aux n 0
   

2. Sans utiliser pow2 :

   let rec suplog2 n =
     if n = 0
     then 0
     else 1 + suplog2 (n/2)
   

Question 5. Écrire une fonction applique : ('a -> 'b) -> 'a list -> 'b list telle que l'appel à applique f l renvoie la liste obtenue en appliquant à chaque élément de l la fonction f.

Corrigé

let rec applique f l =
  match l with
  | [] -> []
  | t::q -> f t :: applique f q

Question 6. Écrire une fonction nieme : 'a list -> int -> 'a telle que l'appel à nieme l n renvoie x où x est le n-ième élément de l et déclenche une erreur s'il n'y en a pas.

Corrigé

let rec nieme l n =
  match l, n with
  | [], _ -> failwith "Liste vide"
  | t::_, 0 -> t
  | _::q, _ -> nieme q (n-1)

Fonctions et typage

Question 7. Écrire une fonction evalue telle que evalue f x renvoie la valeur de la fonction f évaluée en x.

Attention la fonction est vraiment très simple.

Corrigé

let evalue f x = f x

Question 8. Quel est le type de la fonction précédente ?

Corrigé

('a -> 'b) -> 'a -> 'b

Question 9. Écrire une fonction compose telle que compose f g x calcule la valeur de \((f \circ g)(x)\) si on utilisait la notation mathématique (utiliser la notation OCaml revient ici à répondre à la question).

Corrigé

let compose f g x = f (g x)

Question 10. Quel est le type de la fonction précédente ?

Corrigé

('a -> 'b) -> ('c -> 'a) -> 'c -> 'b

Animal de compagnie

On considère ici le type suivant :

type pet = Cat | Dog

Question 11. Écrire une fonction ennemy qui renvoie l'animal opposé. Par exemple, ennemy Cat renvoie Dog.

Corrigé

let ennemy p = match p with
  | Dog -> Cat
  | Cat -> Dog

On dit que l'age, converti en années humaines, d'un chien est de 7 fois son age réel.

Question 12. Écrire une fonction dog_years qui prend en entrée l'age réel d'un chien et renvoie son age converti.

Corrigé

let dog_years n = n * 7

On dit que l'age, converti en années humaines, d'un chat est :

• de 12 ans si le chat a 1 an
• de 24 ans si le chat a 2 ans
• et chaque année supplémentaire à partir de la troisième compte comme 5 années humaines

Ainsi, un chat de 4 ans a \(24 + 2 \times 5 = 34\) années humaines.

Question 13. Écrire une fonction cat_years qui prend en entrée l'age réel d'un chat et renvoie son age converti.

Corrigé

let cat_years n =
  match n with
  | 1 -> 12
  | _ -> 24 + 5 * (n-2)

Question 14. En déduire une fonction pet_years : pet -> int -> int qui calcule l'age converti d'un animal selon sa race.

Corrigé

let pet_years p n =
  match p with
  | Cat -> cat_years n
  | Dog -> dog_years n

Notons qu'ici on peut omettre n :

let pet_years p =
  match p with
  | Cat -> cat_years
  | Dog -> dog_years

Cela revient à imaginer qu'on calcule une fonction qui pourra être utilisée dans tous les cas avec un entier.

Couvertures

On considère une ligne de \(n\) cases carrées :

que l'on souhaite recouvrir complètement avec des tuiles de différentes longueurs.

Par exemple, si on dispose de tuiles de longueur \(1\) ou \(2\), voici une couverture valide avec deux tuiles de longueur \(1\) et deux de longueur \(2\).

Question 15. Écrire une fonction OCaml couvertures12 : int -> int telle que couvertures12 n calcule le nombre de couvertures de \(n\) cases avec des tuiles de longueurs \(1\) ou \(2\).

Indication : on pourra raisonner sur la tuile la plus à gauche d'une telle couverture.

Corrigé

Dans le cas dégénéré \(n = 0\) il n'y a qu'une couverture : c'est l'ensemble vide. Dans le cas \(n=1\) on ne peut placer qu'une tuile de taille 1.

Sinon on place une tuile de taille 1 et on couvre les \(n-1\) restants ou on place une tuile de taille 2 et on couvre les \(n-2\) restants.

let rec couvertures12 n =
  if n = 0 || n = 1
  then 1
  else couvertures12 (n-1) + couvertures12 (n-2)

Question 16. En relisant la fonction précédente, reliez ce nombre de couvertures à une suite classique.

Corrigé

Il s'agit de la suite de Fibonacci !

Question 17. Montrer qu'il est équivalent de couvrir \(n\) cases ainsi et de couvrir un échiquier de \(2 \times n\) cases avec des dominos.

Rappel : un domino est un rectangle de deux cases de long, on peut donc le placer verticalement ou horizontalement pour couvrir deux cases de l'échiquier.

Corrigé

Pour couvrir un échiquier \(2 \times n\) on a le choix sur la position du premier domino : vertical ou horizontal. Si on le place verticalement, il ne reste comme espace libre que de quoi placer un domino parallèle exactement à côté. Le choix que l'on fait est donc entre un domino horizontal ou deux dominos verticaux. C'est exactement le même choix qu'avec les tuiles précédentes. D'ailleurs on passe de l'un à l'autre en coupant l'échiquier en deux.

Question 18. Déterminer une condition sur \(n\) et \(m\) pour qu'un échiquier de \(n \times m\) cases puisse être recouvert par des dominos.

Corrigé

Si on colorie l'échiquier comme aux échecs, chaque domino est à cheval sur une case blanche et une case noire. Il faut donc que le nombre de cases blanches de l'échiquier soit égal au nombre de cases noires.

Si \(n = 2p+1\), les lignes sont tantôt à \(p\) cases noires et \(p+1\) cases blanches, tantôt l'inverse. Pour que cela s'équilibre, il faut que le nombre de lignes soit pair.

Si \(n\) est pair, l'équilibre est automatique.

La condition est donc d'avoir \(n\) ou \(m\) pair. Dans ce cas on peut découper l'échiquier en bandes de tailles \(2 \times m\) ou \(n \times 2\) et on sait que l'échiquier restant est couvrable (par exemple uniquement avec des dominos parallèles).

On a donc : \(n\times m\) admet une couverture \(\iff\) \(nm\) pair (car \(n\) ou \(m\) pair \(\iff nm\) pair).

Question 19. (difficile) Écrire une fonction OCaml couvertures : int list -> int -> int telle que couvertures l n calcule le nombre de couvertures de \(n\) cases avec des tuiles de longueur données par la liste \(l\).

Par exemple, la fonction précédente correspondra à couvertures [1;2].

On ne suppose rien sur \(l\). Si un nombre est présent plusieurs fois, c'est comme si on considérait des tuiles de même longueur mais de couleurs différentes, ce qui augmente le nombre de couvertures.

Corrigé

let rec couvertures tl n =
  let rec aux l = match l with
    | [] -> 0
    | t::q -> (if n >= t then couvertures tl (n-t) else 0) + aux q
  in if n = 0 then 1 else aux tl

Question 20. Calculer le nombre de couvertures pour la liste [1;1;1;1] qui contient donc quatre fois une tuile de longueur 1 pour quatre couleurs différentes.

Corrigé

Ici on a quatre tuiles identiques de longueur 1, donc on a quatre choix par case. Ainsi, s'il y a \(n\) cases alors on a \(4^n\) couvertures distinctes.